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:
- ALC - Avviso del 12/10/2024
Sito del corso
Da oggi questo sito non e' piu' manutenuto. Tutte le informazioni sul corso si trovano su
moodle.
|
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:
Prova scritta
L'esame è costituito da una prova scritta con 8 domande e della durata di circa due ore.
Gli studenti che vorranno, potranno avvalersi del seguente ulteriore meccanismo di valutazione.
- Durante le lezioni verranno proposti esercizi da fare su moodle (domande in itinere) in tempo reale.
- Ciò potrà avvenire durante tutte le lezioni.
- La valutazione delle domande sarà sì/no.
- Coloro che avranno superato almeno l'ottanta per cento delle domande in itinere potranno fare,
solo al primo appello, un compito di 6 domande, con tre quarti del tempo e conseguendo il massimo punteggio (7,5/30) sulle due domande da non fare.
- Coloro che avranno superato almeno il quaranta per cento delle domande in itinere potranno fare,
solo al primo appello, un compito di 7 domande, con sette ottavi del tempo e conseguendo il massimo punteggio (3,75/30) sulla domanda da non fare.
- Potranno svolgere le domande in itinere solo coloro che saranno presenti a lezione.
- Per rilevare i presenti, in ogni lezione ci sarà un elenco nel quale ciascuno potrà segnalare la propria presenza.
- L’elenco dei presenti non sarà usato in nessun altro modo.
- Per svolgere le domande in itinere sarà necessario portare a lezione almeno uno smartphone o un laptop o un tablet.
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