CALCOLABILITA' E LINGUAGGI FORMALI

Anno accademico
2020/2021 Programmi anni precedenti
Titolo corso in inglese
FORMAL LANGUAGES AND COMPUTABILITY
Codice insegnamento
CT0374 (AF:274957 AR:172513)
Modalità
In presenza
Crediti formativi universitari
6
Livello laurea
Laurea
Settore scientifico disciplinare
INF/01
Periodo
I Semestre
Anno corso
3
Sede
VENEZIA
Spazio Moodle
Link allo spazio del corso
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, 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à 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.
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 e domande teoriche. L'esame durerà 120 minuti e prevederà 5 quesiti, il cui obiettivo è di valutare la capacità dello studente di risolvere problemi inerenti agli argomenti del corso ed approfondire la conoscenza teorica del materiale trattato a lezione. Durante l'esame non è consentito l'uso di libri, appunti o supporti elettronici.
Lezione frontale alla lavagna
Italiano
La lista degli argomenti trattati sarà aggiornata regolarmente sulla piattaforma Moodle.
scritto
Programma definitivo.
Data ultima modifica programma: 06/04/2020