Automata, Languages, and Computing
(Laurea Magistrale in Ing. Informatica - 1° anno)
Anno Accademico 2024-2025
Anni Accademici precedenti (corso di Informatica Teorica):
2019-2020
2020-2021
2021-2022
2022-2023
2023-2024
Corso Quantum Computing
Informazioni sugli obiettivi formativi, sui docenti, sull'orario delle lezioni e sul calendario
degli esami sono disponibili nella pagina del Collegio Didattico di Ingegneria Informatica.
Docente: Giuseppe Di Battista
In questa pagina potrete trovare:
Archivio avvisi
Il programma di massima del corso di Automata, Languages, and Computing è il seguente:
- Proprietà elementari dei linguaggi: operazioni su linguaggi, operatore
di Kleene, espressioni regolari, cardinalità dei linguaggi
- Grammatiche formali: grammatiche di Chomsky, produzioni, riconoscimento di linguaggi.
- Linguaggi regolari: automi a stati finiti, relazioni tra automi e linguaggi regolari, pumping
lemma, chiusura dei linguaggi regolari, espressioni regolari e linguaggi regolari, decidibilità
e linguaggi regolari, teorema di Myhill-Nerode.
- Linguaggi non contestuali: automi a pila non deterministici, relazioni tra automi e linguaggi CF,
pumping lemma, chiusura e decidibilità, ambiguità.
- Macchine di Turing (MT) e Turing calcolabilità: funzionamento delle MT, MT multinastro,
MT non deterministiche, descrizione linearizzata delle MT, MT universale, il problema della fermata,
calcolabilità secondo Turing, teorema di Rice, linguaggi di tipo 0 e MT.
- Teoria della complessità: tipologie di problemi, problemi di decisione, complessità
e problemi di decisione su linguaggi, classi di complessità, relazioni
elementari tra classi di complessità, riducibilità, completezza, la classe NP, NP-completezza,
esempi di problemi NP-completi. La classe PSPACE.
|
Materiale didattico (i link inattivi corrispondono a materiale in corso di revisione)
|
- I testi consigliati (non considerati indispensabili) sono:
- Slide del corso di Automata, Languages, and Computing:
- 010-presentazione-del-corso-32.pdf
- 020-linguaggi-e-grammatiche-25.pdf
- 022-espressioni-regolari-07.pdf
- 025-grammatiche-formali-02.pdf
- 025-cardinalita-transfinite-07.pdf
- 030-linguaggi regolari-26.pdf
- 035-automi-a-stati-finiti-02.pdf
- 040-proprieta-linguaggi-regolari-23.pdf
- 045-chiusura-pumping-lemma-regolari-03.pdf
- 055-gramm-exp-reg-03.pdf
- 057-proprieta-decidibili-linguaggi-regolari-01.pdf
- 065-myhill-nerode-02.pdf
- 050-linguaggi-non-contestuali-15.pdf
- 060-automi-a-pila-17.pdf
- 090-macchine-di-turing-24.pdf
- 100-decidibilita-10.pdf
- 110-riducibilita-16.pdf
- 120-rice-07.pdf
- 130-macchine-di-turing-e-linguaggi-08.pdf
- 140-macchine-registri-10.pdf
- 150-complessita-temporale-13.pdf
- 115-np-completezza-02.pdf
- 160-complessita-spaziale-15.pdf
Prova scritta
L'esame è costituito da una prova scritta.
Esempi di prove d'esame
Le seguenti prove d'esame si riferiscono al corso di Informatica Teorica I (Ord. D.M. 509/99), corrispondente grosso modo alla prima parte del corso attuale, e sono fornite a titolo d'esempio.
- Prove d'esame di Informatica Teorica I (Ord. D.M. 509/99):
Le seguenti prove d'esame si riferiscono al corso di Informatica Teorica II (Ord. D.M. 509/99), corrispondente grosso modo alla seconda parte del corso attuale, e sono fornite a titolo d'esempio.
- Prove d'esame di Informatica Teorica II (Ord. D.M. 509/99):
Automata, Languages, and Computing
/ A cura di Giuseppe Di Battista
e Maurizio Patrignani / 22 settembre 2021