Obiettivi della Lezione
- Comprendere la relazione tra algoritmi e automi: Apprendere come gli automi possono eseguire algoritmi.
- Definire gli automi: Imparare cosa sono gli automi e come vengono utilizzati.
- Esercitazioni pratiche sugli automi: Applicare le conoscenze acquisite per creare semplici automi.
Introduzione agli Automi
- Cos’è un Automa:
- Definizione: Un automa è una macchina con un numero finito di stati. Può cambiare stato in risposta a input esterni.
- Esempio di uso: Un distributore automatico che cambia stato in base a monete inserite e selezioni di prodotti.
Relazione tra Algoritmi e Automi
- Come si Collegano:
- Descrizione: Gli algoritmi sono passi logici per risolvere un problema, e gli automi possono eseguire questi passi in sequenza.
- Esempio: Un algoritmo che verifica se una parola è un palindromo può essere eseguito da un automa.
Tipi di Automi
- Automi a Stati Finiti (Finite State Machines):
- Definizione: Hanno un insieme finito di stati e transizioni tra stati basati su input.
- Esempio: Un semaforo con stati Verde, Giallo, Rosso.
- Automi Cellulari:
- Definizione: Una griglia di celle, ognuna delle quali può essere in diversi stati. Cambiano stato in base a regole e stati delle celle vicine.
- Esempio: Il gioco della vita di Conway.
- Macchine di Turing:
- Definizione: Modello teorico con un nastro infinito usato per rappresentare calcoli.
- Esempio: Usato per dimostrare la potenza computazionale degli algoritmi.
Progettazione di un Automa
- Passi per Progettare un Automa:
- Definire gli stati: Stati iniziale, intermedi e finale.
- Definire gli input: Simboli o segnali che l’automa può ricevere.
- Definire le transizioni: Come l’automa passa da uno stato all’altro in risposta agli input.
- Esempio: Automa che riconosce se una sequenza binaria termina con ‘0’.
Esempio di Automa a Stati Finiti
- Riconoscere Stringhe di Numeri Pari:
- Stati: Iniziale, Pari, Dispari.
- Input: 0-9.
- Transizioni:
- Se lo stato è Iniziale e il numero è 0, vai a Pari.
- Se lo stato è Pari e il numero è dispari, vai a Dispari.
- Se lo stato è Dispari e il numero è pari, vai a Pari.
Esercitazioni Pratiche
- Creare un Automa a Stati Finiti:
- Attività: Progettare un automa che riconosce le stringhe di numeri che terminano con una cifra specifica.
- Esempio: Automa che verifica se una stringa di numeri termina con 5.
- Simulare un Automa:
- Attività: Simulare l’automa su una sequenza di input.
- Esempio: Usare un automa per riconoscere numeri binari pari.