CALCOLABILITA' E LINGUAGGI FORMALI

Il corso si propone di studiare i rudimenti della teoria dei linguaggi formali e della calcolabilità. I linguaggi formali sono alla base di importanti applicazioni nel mondo dei compilatori e del processing automatico di testo, mentre la calcolabilità studia le limitazioni inerenti dei calcolatori e degli algoritmi.

Lo studente imparerà a padroneggiare i concetti teorici alla base del corso ed a svolgere esercizi che ne dimostrino la comprensione. In particolare, lo studente imparerà la teoria del linguaggi formali, le relazioni fra diversi modelli computazionali ed il loro potere espressivo. Lo studente inoltre imparerà ad identificare il modello computazionale più appropriato per la risoluzione di un determinato problema.

Nello specifico, gli studenti raggiungeranno i seguenti risultati di apprendimento:

i) Conoscenza e comprensione: comprensione dei concetti base della teoria dei linguaggi formali e della calcolabilità.

ii) Capacità di applicare conoscenza e comprensione: capacità di risolvere esercizi relativi agli argomenti teorici trattati nel corso.

iii) Capacità di giudizio: capacità di scegliere la tecnica di dimostrazione più adeguata per uno specifico obiettivo.

iv) Abilità comunicative: saper esporre in maniera chiara e corretta i ragionamenti effettuati in una dimostrazione matematica.

v) Capacità di apprendimento: saper studiare in autonomia nuovi concetti teorici del mondo dei linguaggi formali e della calcolabilità.

Rudimenti di Matematica Discreta

- Linguaggi regolari
- Linguaggi context-free
- Macchine di Turing
- Decidibilità
- Riduzioni
- Cenni di argomenti avanzati

Michael Sipser - Introduction to the theory of computation, terza edizione

Prova scritta con esercizi, domande teoriche e dimostrazioni relativi ai principali argomenti del corso. Durante la prova scritta non è permesso l'uso di appunti, libri e strumenti elettronici.

La prova scritta valuta il raggiungimento dei risultati di apprendimento da i) a v). In particolare, lo studente verrà valutato rispetto a questi criteri:

i) Conoscenza e comprensione: lo studente dovrà dimostrare di avere familiarità con la notazione formale introdotta nel corso, le definizioni principali e la terminologia specifica.

ii) Capacità di applicare conoscenza e comprensione: lo studente dovrà dimostrare di saper risolvere esercizi sugli argomenti introdotti all'interno del corso.

iii) Capacità di giudizio: lo studente dovrà dimostrare di saper applicare le principali tecniche di dimostrazione e di adattare dimostrazioni esistenti.

iv) Abilità comunicative: lo studente dovrà dimostrare familiarità con il linguaggio specifico e buona padronanza del ragionamento logico.

v) Capacità di apprendimento: lo studente dovrà dimostrare di essere in grado di comprendere concetti e definizioni presentati all'interno della prova di esame.

Relativamente ai criteri indicati, punteggi nella fascia 18-22 indicano competenze sufficienti ma limitate, punteggi nella fascia 23-26 indicano competenze discrete o più che discrete, punteggi nella fascia 27-30 indicano competenze da buone a ottime.

scritto

Lezione frontale alla lavagna. Assegnazione di esercizi per casa.

La lista degli argomenti trattati sarà aggiornata regolarmente sulla piattaforma Moodle.