Il corso, di carattere teorico, ha come obiettivo l'acquisizione da parte dello studente delle nozioni basilari relative alla teoria degli automi e dei linguaggi formali compresi i principali risultati limitativi nell'ambito della teoria della calcolabilità. Tali conoscenze sono rivolte a formare e ad aumentare le capacità di astrazione attraverso la rappresentazione simbolica e di comprensione di un linguaggio scientifico astratto e simbolico, capacità che hanno un ruolo fondamentale in vari ambiti dell'informatica come, ad esempio, nello sviluppo dei compilatori, nella modellazione di sistemi complessi e nell'ingegneria del software.
Al termine del corso lo studente sarà in grado di. (1) descrivere i principali modelli computazionali (automi a stati finiti, automi a pila, macchine di Turing), le loro caratteristiche e la loro potenza computazionale in termini di linguaggi riconosciuti; (2) definire formalmente la nozione di computazione nei vari modelli studiati; (3) identificare il ruolo dei vari linguaggi (in particolare per i linguaggi regolari e context-free) nel processo di compilazione dei linguaggi di programmazione e in altre applicazioni di base dei linguaggi; (4) identificare e utilizzare le notazioni (generatori) per la descrizione dei linguaggi regolari e i linguaggi context-free; (5) applicare in modo appropriato riconoscitori e generatori allo studio di semplici linguaggi; (6) dimostrare un’appropriata comprensione dei limiti dei vari modelli computazionali; (7) riconoscere e utilizzare la terminologia propria della teoria degli automi, dei linguaggi formali e della teoria della computabilità.
Prerequisiti
Per un proficuo apprendimento di questo insegnamento lo studente deve padroneggiare le nozioni matematiche e le tecniche dimostrative impartite nell’insegnamento fondamentale di Algebra e Geometria del primo anno, che dunque costituisce propedeuticità obbligatoria. Inoltre, è consigliabile che lo studente abbia frequentato e sostenuto gli insegnamenti fondamentali di Programmazione e Algoritmi e Strutture Dati del primo anno di corso.
Metodi didattici
Il corso si articola in lezioni frontali (40 ore) ed esercitazioni (12 ore). Gli argomenti presentati a lezione sono applicati nelle esercitazioni in aula che prevedono la partecipazione attiva degli studenti. Gli esercizi presentati costituiscono una fondamentale linea guida per la preparazione dell’esame.
Verifica Apprendimento
La valutazione avviene tramite un esame scritto seguito da una prova orale. Tutti gli argomenti presentati durante il corso sono oggetto di valutazione. Verrà richiesto di svolgere esercizi e dimostrazioni analoghi a quelli discussi durante lezioni ed esercitazioni.
Contenuti
• Introduzione all'informatica teorica: motivazioni, obiettivi, metodi. (2h) • Prerequisiti matematici. (4h) • Automi a stati finiti (12h, obiettivi 1,2,3,5,6,7) • Espressioni regolari. (6h, obiettivi 1,4,5) • Grammatiche libere dal contesto, automi a pila, parser, traduttori. (8h, obiettivi 1,3,4,5,7) • Macchine di Turing, funzioni primitive ricorsive, tesi di Church. (6h, obiettivi 1,2,3,7) • Aritmetizzazione e macchine di Turing universali, indecidibilità del problema dell'arresto. (4h, obiettivo 1, 6, 7) • Linguaggi ricorsivamente enumerabili e problemi indecidibili. Teoremi di ricorsione e di Rice (6h, obiettivo 1, 6, 7) • Cenni ad argomenti avanzati (complessità, lambda-calcolo). (4h, obiettivo 1, 6, 7)
