CALCOLABILITA' E LINGUAGGI FORMALI

Anno accademico
2024/2025 Programmi anni precedenti
Titolo corso in inglese
FORMAL LANGUAGES AND COMPUTABILITY
Codice insegnamento
CT0374 (AF:542936 AR:218244)
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 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à 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 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. La prova scritta valuta il raggiungimento dei risultati di apprendimento da i) a v).Durante l'esame non è consentito l'uso di libri, appunti o supporti elettronici.
Lezione frontale alla lavagna. Assegnazione di esercizi per casa.
Italiano
La lista degli argomenti trattati sarà aggiornata regolarmente sulla piattaforma Moodle.
scritto
Programma definitivo.
Data ultima modifica programma: 28/06/2024