Concetti Fondamentali e Algoritmi

Benvenuto alla prima lezione del corso di Introduzione alla Programmazione! Questa lezione rappresenta il punto di partenza del tuo viaggio nel mondo del coding. Prima di imparare a scrivere codice, è fondamentale comprendere i concetti base che stanno alla base della programmazione.

In questa lezione esploreremo:

• Termini informatici fondamentali - Il vocabolario essenziale di un programmatore
• Algoritmi - Come risolvere problemi in modo sistematico
• Schemi di flusso (Flowcharts) - Rappresentare visivamente la logica
• Pseudocodice - Scrivere la logica prima del codice vero

Il computer per un programmatore è come il telescopio per un astronomo.

Un astronomo studia le stelle, le galassie e l'universo. Il telescopio è uno strumento potente che amplifica le sue capacità, permettendogli di vedere più lontano. Ma l'astronomo deve prima conoscere la fisica, l'astronomia e la matematica. Può fare calcoli, previsioni e teorie anche senza guardare nel telescopio!

Allo stesso modo, un programmatore può programmare anche senza computer! La programmazione è prima di tutto un modo di pensare, una capacità di risolvere problemi in modo logico e strutturato.

La programmazione non è nata con i computer moderni. Ha radici profonde nella storia dell'umanità, nell'esigenza di automatizzare calcoli e risolvere problemi complessi.

Tappe Fondamentali

Nel 1936, il matematico britannico Alan Turing propose un modello teorico di macchina che potesse eseguire qualsiasi calcolo possibile. Questo modello, chiamato Macchina di Turing, è alla base teorica di tutti i computer moderni.

Cos'è una Macchina di Turing?

Una Macchina di Turing è un modello matematico astratto composto da:

Componenti della Macchina di Turing

Esempi Pratici di Macchine di Turing

Vediamo alcuni esempi concreti per capire come funziona una Macchina di Turing nella pratica:

Esempio 1: Scrivere Tre X

Metafora della Persona:
La persona inizia davanti a un foglio bianco e deve scrivere tre X.

Stati mentali:
- S0: "Devo scrivere la prima X"
- S1: "Devo scrivere la seconda X"
- S2: "Devo scrivere la terza X"
- FINE: "Ho finito"

Istruzioni del manuale:
SE sono in S0:
  - Scrivo "X" nel quadretto corrente
  - Mi sposto a DESTRA
  - Passo allo stato S1

SE sono in S1:
  - Scrivo "X" nel quadretto corrente
  - Mi sposto a DESTRA
  - Passo allo stato S2

SE sono in S2:
  - Scrivo "X" nel quadretto corrente
  - Passo allo stato FINE

Esecuzione passo-passo:
Nastro iniziale:  [ ][ ][ ][ ][ ]...
                   ↑ (persona qui, stato S0)

Passo 1: Scrivo X, vado a destra, stato S1
Nastro:           [X][ ][ ][ ][ ]...
                      ↑ (persona qui, stato S1)

Passo 2: Scrivo X, vado a destra, stato S2
Nastro:           [X][X][ ][ ][ ]...
                         ↑ (persona qui, stato S2)

Passo 3: Scrivo X, stato FINE
Nastro finale:    [X][X][X][ ][ ]...
                         ↑ (persona qui, stato FINE - FERMATA)

Esempio 2: Sommare 1 a un Numero Binario

Metafora della Persona:
Immagina di sommare 1 a un numero binario su carta, partendo dalla cifra più a destra.

Istruzioni del manuale:
1. Vai all'ultima cifra (più a destra)
2. SE leggi "1": scrivi "0", vai a sinistra (c'è riporto!)
3. SE leggi "0": scrivi "1" e FERMATI (somma completata)
4. SE leggi "vuoto": scrivi "1" e FERMATI

Esecuzione passo-passo:
Nastro iniziale:  [1][0][1][1][ ][ ]...  (1011₂ = 11₁₀)
                               ↑ Parto da qui

Passo 1: Leggo [1] → Scrivo [0], vado a sinistra (riporto!)
Nastro:           [1][0][1][0][ ][ ]...
                         ↑

Passo 2: Leggo [1] → Scrivo [0], vado a sinistra (ancora riporto!)
Nastro:           [1][0][0][0][ ][ ]...
                      ↑

Passo 3: Leggo [0] → Scrivo [1], FERMATI (somma completa!)
Nastro finale:    [1][1][0][0][ ][ ]...  (1100₂ = 12₁₀)
                      ↑ FINE

Verifica: 1011₂ + 1 = 1100₂  ✓  (11 + 1 = 12)

Esempio 3: Trovare una X su un Nastro

Metafora della Persona:
Scorri il foglio da sinistra a destra finché non trovi una X.

Stati mentali:
- CERCA: "Sto cercando una X"
- TROVATO: "Ho trovato la X!"

Istruzioni del manuale:
SE sono in CERCA e leggo qualsiasi simbolo diverso da X:
  - Non scrivo niente
  - Mi sposto a DESTRA
  - Resto in stato CERCA

SE sono in CERCA e leggo "X":
  - Passo allo stato TROVATO
  - FERMATI

Esecuzione passo-passo:
Nastro:           [A][B][C][X][Y][Z]...
                   ↑ (inizio, stato CERCA)

Passo 1: Leggo [A] (non è X), vado a destra
Nastro:           [A][B][C][X][Y][Z]...
                      ↑ (stato CERCA)

Passo 2: Leggo [B] (non è X), vado a destra
Nastro:           [A][B][C][X][Y][Z]...
                         ↑ (stato CERCA)

Passo 3: Leggo [C] (non è X), vado a destra
Nastro:           [A][B][C][X][Y][Z]...
                            ↑ (stato CERCA)

Passo 4: Leggo [X] (trovata!), passo a stato TROVATO, FERMATI
Nastro:           [A][B][C][X][Y][Z]...
                            ↑ (stato TROVATO - FINE)

Esempio 4: Invertire 0 e 1

Metafora della Persona:
Scorri il foglio, quando vedi 0 cambialo in 1, quando vedi 1 cambialo in 0.

Istruzioni del manuale:
SE leggo "0":
  - Scrivo "1"
  - Vado a DESTRA
  
SE leggo "1":
  - Scrivo "0"
  - Vado a DESTRA
  
SE leggo "vuoto":
  - FERMATI (ho finito la sequenza)

Esecuzione passo-passo:
Nastro iniziale:  [1][0][1][1][0][ ]...
                   ↑

Passo 1: Leggo [1] → Scrivo [0], vado a destra
Nastro:           [0][0][1][1][0][ ]...
                      ↑

Passo 2: Leggo [0] → Scrivo [1], vado a destra
Nastro:           [0][1][1][1][0][ ]...
                         ↑

Passo 3: Leggo [1] → Scrivo [0], vado a destra
Nastro:           [0][1][0][1][0][ ]...
                            ↑

Passo 4: Leggo [1] → Scrivo [0], vado a destra
Nastro:           [0][1][0][0][0][ ]...
                               ↑

Passo 5: Leggo [0] → Scrivo [1], vado a destra
Nastro:           [0][1][0][0][1][ ]...
                                  ↑

Passo 6: Leggo [ ] (vuoto) → FERMATI
Nastro finale:    [0][1][0][0][1][ ]...

Risultato: Tutti i bit sono stati invertiti! ✓

Importanza della Macchina di Turing

• Definizione di Computabilità - Ha definito formalmente cosa significa che un problema può essere risolto da un computer
• Tesi di Church-Turing - Qualsiasi cosa calcolabile può essere calcolata da una Macchina di Turing
• Base dei Computer Moderni - Tutti i computer odierni sono essenzialmente Macchine di Turing (con memoria finita)
• Limiti della Computazione - Ha dimostrato che esistono problemi che nessun computer potrà mai risolvere (problema della fermata)

Prima di iniziare a programmare, è essenziale familiarizzare con alcuni termini fondamentali che userai quotidianamente nel mondo dello sviluppo software.

Un algoritmo è una sequenza finita di istruzioni ben definite e non ambigue che, se seguite correttamente, risolvono un problema o completano un'operazione specifica.

Caratteristiche di un Buon Algoritmo

Esempio Pratico: Preparare il Caffè

Vediamo un esempio di algoritmo nella vita quotidiana:

ALGORITMO: PreparaCaffè

INIZIO
    1. Riempi la moka con acqua fino alla valvola
    2. Inserisci il filtro nella moka
    3. Aggiungi caffè macinato nel filtro
    4. Avvita la parte superiore della moka
    5. Posiziona la moka sul fornello
    6. Accendi il fornello a fuoco medio
    7. MENTRE il caffè non è salito
        - Attendi
    8. Spegni il fornello
    9. Versa il caffè nella tazza
FINE

Algoritmo Informatico: Trovare il Massimo

Vediamo ora un esempio più tecnico: trovare il numero più grande in una lista di numeri.

ALGORITMO: TrovaNumeroMassimo

INPUT: Una lista di numeri [n1, n2, n3, ..., nk]
OUTPUT: Il numero più grande nella lista

INIZIO
    1. Imposta max = primo numero della lista
    2. PER OGNI numero nella lista:
        a. SE numero > max ALLORA
            - max = numero
    3. RESTITUISCI max
FINE

Un flowchart (o diagramma di flusso) è una rappresentazione grafica di un algoritmo. Utilizza forme geometriche standardizzate per rappresentare diversi tipi di operazioni, collegate da frecce che mostrano il flusso di esecuzione.

Simboli Standard dei Flowcharts

Esistono simboli universali che ogni programmatore deve conoscere:

Esempio: Flowchart per Controllare se un Numero è Pari

Rappresentiamo graficamente un semplice algoritmo:

┌──────────────┐
│   INIZIO     │ ← Ovale (Start)
└──────┬───────┘
       │
       ▼
┌──────────────────────┐
│ Inserisci un numero  │ ← Parallelogramma (Input)
└──────┬───────────────┘
       │
       ▼
┌─────────────────────────────┐
│ numero % 2 == 0 ?           │ ← Rombo (Decisione)
└────┬──────────────────┬─────┘
     │ SI               │ NO
     ▼                  ▼
┌─────────────┐    ┌──────────────┐
│ Stampa      │    │ Stampa       │ ← Rettangoli (Output)
│ "È pari"    │    │ "È dispari"  │
└──────┬──────┘    └──────┬───────┘
       │                  │
       └────────┬─────────┘
                ▼
         ┌─────────┐
         │  FINE   │ ← Ovale (End)
         └─────────┘

Lo pseudocodice è una descrizione testuale di un algoritmo che usa un linguaggio simile a quello di programmazione ma senza vincoli di sintassi rigida. È il ponte tra il linguaggio umano e il codice vero e proprio.

Vantaggi dello Pseudocodice

• Facile da scrivere e leggere per chiunque
• Non richiede conoscenza di un linguaggio specifico
• Aiuta a concentrarsi sulla logica senza preoccuparsi della sintassi
• Facilita la comunicazione tra programmatori
• Utile per pianificare prima di scrivere codice reale

Strutture Comuni in Pseudocodice

1. Sequenza (Istruzioni in Ordine)

INIZIO
    Istruzione 1
    Istruzione 2
    Istruzione 3
FINE

2. Selezione (IF/ELSE - Condizioni)

SE condizione ALLORA
    Istruzioni se vero
ALTRIMENTI
    Istruzioni se falso
FINE SE

// Esempio pratico:
SE età >= 18 ALLORA
    Stampa "Puoi votare"
ALTRIMENTI
    Stampa "Non puoi ancora votare"
FINE SE

3. Iterazione (Cicli - WHILE)

MENTRE condizione è vera FAI
    Istruzioni da ripetere
FINE MENTRE

// Esempio pratico:
contatore = 1
MENTRE contatore <= 10 FAI
    Stampa contatore
    contatore = contatore + 1
FINE MENTRE

4. Iterazione (Cicli - FOR)

PER i DA 1 A 10 FAI
    Istruzioni da ripetere
FINE PER

// Esempio pratico:
PER i DA 1 A 5 FAI
    Stampa "Iterazione numero: " + i
FINE PER

Esempio Completo: Calcolo del Fattoriale

Il fattoriale di un numero n (scritto n!) è il prodotto di tutti i numeri da 1 a n. Ad esempio: 5! = 5 × 4 × 3 × 2 × 1 = 120

ALGORITMO: CalcolaFattoriale

INPUT: numero intero positivo n
OUTPUT: il fattoriale di n

INIZIO
    // Controllo input
    SE n < 0 ALLORA
        Stampa "Errore: il numero deve essere positivo"
        TERMINA
    FINE SE
    
    // Caso base
    SE n == 0 O n == 1 ALLORA
        risultato = 1
    ALTRIMENTI
        // Calcolo fattoriale
        risultato = 1
        PER i DA 2 A n FAI
            risultato = risultato * i
        FINE PER
    FINE SE
    
    // Output
    Stampa "Il fattoriale di " + n + " è: " + risultato
FINE

Conversione in Codice Reale (Python)

Ecco come lo stesso algoritmo appare in Python:

def calcola_fattoriale(n):
    # Controllo input
    if n < 0:
        print("Errore: il numero deve essere positivo")
        return None
    
    # Caso base
    if n == 0 or n == 1:
        risultato = 1
    else:
        # Calcolo fattoriale
        risultato = 1
        for i in range(2, n + 1):
            risultato = risultato * i
    
    # Output
    print(f"Il fattoriale di {n} è: {risultato}")
    return risultato

# Test
calcola_fattoriale(5)  # Output: 120

Metti in pratica quello che hai imparato con questi esercizi. Per ciascuno, prova prima a risolverlo da solo su carta, poi confronta con la soluzione proposta.

Esercizio 1: Algoritmo della Colazione

Compito: Scrivi un algoritmo dettagliato per preparare la colazione (caffè + toast). Usa la notazione che preferisci (lista numerata, pseudocodice, flowchart).

ALGORITMO: PreparaColazione

INIZIO
    // Preparazione caffè
    1. Riempi moka con acqua
    2. Aggiungi caffè nel filtro
    3. Metti moka sul fornello acceso
    
    // Preparazione toast (in parallelo)
    4. Inserisci pane nel tostapane
    5. Imposta livello di tostatura
    6. Avvia tostapane
    
    // Attesa
    7. MENTRE caffè non è pronto O toast non è pronto FAI
        - Controlla caffè
        - Controlla toast
    8. FINE MENTRE
    
    // Servizio
    9. Versa caffè nella tazza
    10. Spalma burro/marmellata sul toast
    11. Servi colazione
FINE

Esercizio 2: Trovare il Numero Maggiore tra Tre

Compito: Scrivi un algoritmo in pseudocodice che prende tre numeri (A, B, C) e determina quale è il più grande.

ALGORITMO: TrovaNumeroMaggiore

INPUT: tre numeri A, B, C
OUTPUT: il numero più grande

INIZIO
    Leggi A, B, C
    
    SE A >= B E A >= C ALLORA
        max = A
        Stampa "Il numero maggiore è A: " + A
    ALTRIMENTI SE B >= A E B >= C ALLORA
        max = B
        Stampa "Il numero maggiore è B: " + B
    ALTRIMENTI
        max = C
        Stampa "Il numero maggiore è C: " + C
    FINE SE
    
    RESTITUISCI max
FINE

Esercizio 3: Conta alla Rovescia

Compito: Crea un algoritmo che conta da 10 a 0 e stampa "BOOM!" alla fine.

ALGORITMO: ContaRovescia

INIZIO
    contatore = 10
    
    MENTRE contatore >= 0 FAI
        Stampa contatore
        contatore = contatore - 1
    FINE MENTRE
    
    Stampa "BOOM!"
FINE

ALGORITMO: ContaRovescia

INIZIO
    PER i DA 10 A 0 PASSO -1 FAI
        Stampa i
    FINE PER
    
    Stampa "BOOM!"
FINE

Esercizio 4: Password Validator

Compito: Crea un algoritmo che chiede all'utente di inserire una password. Continua a chiedere finché non inserisce la password corretta "Turing1936".

ALGORITMO: ValidaPassword

INIZIO
    passwordCorretta = "Turing1936"
    accesso = FALSO
    tentativi = 0
    
    MENTRE accesso == FALSO E tentativi < 3 FAI
        Stampa "Inserisci la password: "
        Leggi passwordInserita
        
        SE passwordInserita == passwordCorretta ALLORA
            accesso = VERO
            Stampa "Accesso consentito!"
        ALTRIMENTI
            tentativi = tentativi + 1
            Stampa "Password errata. Tentativi rimasti: " + (3 - tentativi)
        FINE SE
    FINE MENTRE
    
    SE accesso == FALSO ALLORA
        Stampa "Accesso bloccato. Troppi tentativi."
    FINE SE
FINE

Sezione A: Domande a Risposta Multipla (15 punti - 1 punto ciascuna)

Sezione B: Domande a Risposta Aperta (15 punti)

Ottimo lavoro! Hai completato la prima lezione del corso. Ecco cosa hai imparato:

• Terminologia informatica - Programma, algoritmo, variabile, ciclo, condizione, funzione, debug
• Cos'è un algoritmo - Una sequenza finita di istruzioni per risolvere un problema
• Caratteristiche di un buon algoritmo - Finito, definito, con input/output, efficace e generale
• Flowcharts - Rappresentazione grafica degli algoritmi con simboli standard
• Simboli dei flowcharts - Ovale (inizio/fine), rettangolo (processo), rombo (decisione), parallelogramma (I/O)
• Pseudocodice - Descrizione testuale dell'algoritmo in linguaggio semi-formale
• Strutture di controllo - Sequenza, selezione (IF/ELSE), iterazione (WHILE/FOR)