CALCOLABILITA' E LINGUAGGI FORMALI

Anno accademico
2018/2019 Programmi anni precedenti
Titolo corso in inglese
FORMAL LANGUAGES AND COMPUTABILITY
Codice insegnamento
CT0374 (AF:230279 AR:111540)
Modalità
In presenza
Crediti formativi universitari
6
Livello laurea
Laurea
Settore scientifico disciplinare
INF/01
Periodo
I Semestre
Anno corso
3
Sede
VENEZIA
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.
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
Un riassunto degli argomenti trattati sarà aggiornato regolarmente sulla piattaforma Moodle.
scritto
Programma definitivo.
Data ultima modifica programma: 17/09/2018