SSD

Crediti

INF/01

6

Obiettivi Formativi

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

Competenze acquisite

Si imparerà a padroneggiare i concetti teorici alla base del corso ed a svolgere esercizi che ne dimostrino la comprensione. Inoltre, lo studente imparerà le relazioni fra diversi modelli computazionali e la loro forza espressiva nella risoluzione di calcoli complessi. Lo studente inoltre imparerà ad identificare il modello computazionale più appropriato per la risoluzione di un determinato problema.

Programma

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

Testi Consigliati

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

Modalità di Verifica

–         Prova scritta con domande aperte e scelta multipla

–         La durata della prova e di massimo 1,5 ore

–         La valutazione viene espressa in trentesimi