Lezione 1: Concetti Fondamentali e Algoritmi

Introduzione alla lezione

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 (Flowchart): rappresentare visivamente la logica
• Pseudocodice: scrivere la logica prima del codice vero

Il computer: lo strumento del programmatore

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.

Programmazione su carta

Prima dell'era dei computer personali, i programmatori scrivevano algoritmi su carta, creavano flowchart alla lavagna e pensavano alla logica usando solo la mente. Anche oggi, i migliori programmatori progettano prima con carta e penna!

Il pensiero computazionale

La capacità di scomporre problemi complessi in passi semplici, di trovare pattern e di astrarre concetti è chiamata "pensiero computazionale". Questa abilità è utile in qualsiasi ambito della vita, non solo nella programmazione!

Breve storia della programmazione

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

La Macchina di Turing

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

• Nastro infinito: un nastro diviso in celle, ciascuna contenente un simbolo (come 0, 1, o vuoto). Il nastro rappresenta la memoria, potenzialmente infinita.
• Testina di lettura/scrittura: una testina che può leggere e scrivere simboli sul nastro, e muoversi a sinistra o a destra di una cella alla volta.
• Insieme di stati: un insieme finito di "stati" in cui la macchina può trovarsi (come "stato iniziale", "stato finale", "stato di calcolo", ecc.).
• Tabella di transizione: un insieme di regole che dicono "se sei nello stato X e leggi il simbolo Y, scrivi Z, muoviti a sinistra/destra e passa allo stato W".

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

Compito: scrivere XXX su un nastro vuoto.

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

Compito: incrementare 1011 (11 in decimale) di 1.

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

Compito: cercare il primo simbolo X sul 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

Compito: trasformare tutti gli 0 in 1 e tutti gli 1 in 0.

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)

Terminologia informatica di base

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

• Programma: un insieme di istruzioni scritte in un linguaggio di programmazione che il computer può eseguire per svolgere un compito specifico.
• Algoritmo: una sequenza finita e ordinata di passi precisi e non ambigui che risolve un problema o completa un'operazione in un tempo finito.
• Variabile: un "contenitore" che memorizza un valore in memoria. Ha un nome (identificatore) e può cambiare valore durante l'esecuzione del programma.
• Tipo di dato: definisce il tipo di valore che una variabile può contenere: numeri interi, decimali, testo (stringhe), valori booleani (vero/falso), ecc.
• Ciclo (Loop): una struttura che ripete un blocco di istruzioni più volte finché una condizione rimane vera o per un numero specifico di iterazioni.
• Condizione: un'espressione che può essere vera o falsa. Usata per prendere decisioni nel codice (if/else) e controllare i cicli.
• Funzione: un blocco di codice riutilizzabile che esegue un compito specifico. Può ricevere input (parametri) e restituire un output (valore di ritorno).
• Debug: il processo di identificazione e correzione degli errori (bug) nel codice. Fondamentale per creare programmi che funzionano correttamente.

Cos'è un algoritmo?

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

Schemi di flusso (Flowchart)

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 flowchart

Esistono simboli universali che ogni programmatore deve conoscere:

• Ovale: INIZIO / FINE. Indica l'inizio o la fine di un algoritmo.
• Rettangolo: PROCESSO. Rappresenta un'operazione o un'istruzione (es: calcoli, assegnazioni).
• Rombo: DECISIONE. Indica un punto in cui si prende una decisione (SI/NO, VERO/FALSO).
• Parallelogramma: INPUT / OUTPUT. Rappresenta l'inserimento di dati o la visualizzazione di risultati.
• Freccia: FLUSSO. Indica la direzione del flusso di esecuzione da un passo all'altro.
• Cerchio: CONNETTORE. Collega parti diverse del flowchart (utile quando il diagramma è grande).

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)
         └─────────┘

Pseudocodice

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

Esercizi pratici guidati

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

Altri esercizi da provare

• 5. Calcolatrice semplice: disegna un flowchart per una calcolatrice che chiede due numeri e un'operazione (+, -, *, /) e stampa il risultato. Gestisci il caso della divisione per zero!
• 6. Tavola pitagorica: crea un algoritmo che stampa l'intera tavola pitagorica (da 1×1 a 10×10). Usa due cicli annidati!
• 7. Numero primo: scrivi un algoritmo che determina se un numero è primo (divisibile solo per 1 e per se stesso). Usa un ciclo e una variabile booleana.
• 8. Simulazione Macchina di Turing: simula su carta una Macchina di Turing che inverte una sequenza binaria (tutti gli 0 diventano 1 e viceversa). Disegna il nastro ad ogni passo.

Test autovalutativo di fine unità

Sezione A: domande a risposta multipla (15 punti, 1 punto ciascuna)

1. Chi è considerata la prima programmatrice della storia?
   a) Grace Hopper   b) Ada Lovelace   c) Margaret Hamilton   d) Katherine Johnson
2. Cosa rappresenta il nastro in una Macchina di Turing?
   a) Il processore   b) La memoria   c) Il disco rigido   d) La rete internet
3. Quale simbolo di flowchart rappresenta una decisione?
   a) Rettangolo   b) Ovale   c) Rombo   d) Parallelogramma
4. Un algoritmo deve essere necessariamente:
   a) Infinito   b) Ambiguo   c) Finito   d) Casuale
5. Il computer per un programmatore è come:
   a) Un cervello alternativo   b) Il telescopio per un astronomo   c) Uno strumento indispensabile per programmare   d) La meta finale dell'apprendimento
6. In che anno Alan Turing introdusse il concetto di Macchina di Turing?
   a) 1843   b) 1936   c) 1945   d) 1991
7. Quale struttura di controllo permette di ripetere un blocco di codice?
   a) IF/ELSE   b) WHILE/FOR   c) INPUT/OUTPUT   d) INIZIO/FINE
8. Cosa rappresenta il parallelogramma in un flowchart?
   a) Un processo   b) Una decisione   c) Input/Output   d) Inizio/Fine
9. Lo pseudocodice è:
   a) Un linguaggio di programmazione reale   b) Una descrizione testuale informale di un algoritmo   c) Un diagramma grafico   d) Un tipo di variabile
10. Quale linguaggio è stato creato nel 1991 da Guido van Rossum?
    a) Java   b) C++   c) Python   d) JavaScript
11. Il "pensiero computazionale" è:
    a) Usare solo il computer per pensare   b) La capacità di scomporre problemi in passi semplici   c) Pensare velocemente come un computer   d) Memorizzare molte informazioni
12. Una variabile in programmazione è:
    a) Un valore che non cambia mai   b) Un contenitore che memorizza un valore   c) Un tipo di ciclo   d) Un simbolo di flowchart
13. Il debug è:
    a) Scrivere codice velocemente   b) Trovare e correggere errori   c) Testare il computer   d) Installare programmi
14. ENIAC (1945) era:
    a) Un linguaggio di programmazione   b) Il primo computer elettronico programmabile   c) Un algoritmo famoso   d) Un tipo di variabile
15. Si può programmare senza usare un computer?
    a) No, è impossibile   b) Sì, con carta e penna progettando algoritmi   c) Solo se sei un genio   d) Solo in teoria, mai in pratica

Sezione B: domande a risposta aperta (15 punti)

16. (5 punti) Spiega con parole tue cos'è un algoritmo e fai un esempio dalla vita quotidiana.
17. (5 punti) Scrivi un semplice algoritmo in pseudocodice per determinare se un numero è pari o dispari.
18. (5 punti) Perché la Macchina di Turing è importante per l'informatica moderna? Cosa ci ha insegnato?

INIZIO
    Leggi numero
    SE numero % 2 == 0 ALLORA
        Stampa "Il numero è pari"
    ALTRIMENTI
        Stampa "Il numero è dispari"
    FINE SE
FINE

Riepilogo della lezione

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