Il corso, di carattere teorico, ha come obiettivo principale l'acquisizione delle nozioni basilari su automi e linguaggi, e lo sviluppo delle capacità di formalizzazione, astrazione, modellazione
di sistemi e analisi di problemi complessi. Conoscenza e capacità di comprensione Il corso si propone di fornire le conoscenze di base di Teoria degli Automi e dei Linguaggi , con particolare attenzione agli Automi a stati finiti visti come descrizione matematica del controllo finito di un programma o, più in generale, di un sistema discreto sequenziale, e alle Macchine di Turing, viste come modello generale di computazione. Lo studio di questi formalismi, pietre angolari di tutta l’informatica moderna, è indispensabile per la comprensione di nozioni, risultati e concetti fondamentali per un informatico, tra i quali: le nozioni di algoritmo o procedura sequenziali e la possibilità di una loro descrizione astratta attraverso sequenze, scelte e cicli, risultato alla base della programmazione sequenziale; l’esistenza di problemi non risolubili o di problemi “difficilmente” risolubili, in termini di risorse di calcolo, e quindi la necessità di una loro classificazione in classi di complessità; la chiara distinzione tra aspetti sintattici e semantici e la nozione di simulazione e riduzione, come strumento di confronto semantico tra formalismi o problemi sintatticamente diversi. Conoscenza e capacità di comprensione applicate Il corso, anche se di carattere fondamentalmente teorico, ha una notevole valenza applicativa. In particolare, le basi teoriche apprese permettono di affrontare in modo matematicamente chiaro e rigoroso numerosi problemi di carattere applicativo: le applicazioni della Teoria degli Automi e dei Linguaggi ,spaziano infatti dal riconoscimento di linguaggi artificiali e naturali, attraverso la teoria della compilazione, al pattern matching di stringhe , alla
descrizione e verifica di sistemi complessi software e hardware (Model Checking), alla teoria dei giochi. Autonomia di giudizio e abilità comunicative I risultati di apprendimento attesi sono legati alla capacità di utilizzare gli strumenti formali più opportuni in diversi contesti applicativi, motivandone adeguatamente la scelta. Capacità di apprendere I concetti e gli strumenti formali presentati nel corso favoriscono l'approfondimento individuale delle proprie conoscenze e la comprensione di argomenti trattati in altri corsi, come ad esempio le problematiche legate alla specifica, implementazione e verifica di sistemi, si
Obiettivi specifici:
1)conoscenze e comprensione delle basi logiche e formali della teoria della calcolabilità
2)capacità di applicare le conoscenze di base sui modelli di calcolo :automi ,linguaggi.
3)competenze relative al confronto tra i differenti modelli e la loro applicabilità alla programmazione
4)capacità di comunicare e trasmettere i contenuti dell’informatica teorica inserendoli nella fondazione di una teoria dell’informatica .
5)capacità critiche che consentano di confrontare in forma laboratoriale le varie applicazioni della classificazione dei problemi rispetto alla loro complessità(classi P/np/np-HARD)