Automata, Languages, and Computing
(Laurea Magistrale in Ing. Informatica - 1° anno)
Anno Accademico 2021-2022
Anni Accademici precedenti (corso di Informatica Teorica):
2018-2019
2019-2020
2020-2021
Corso Next Generation Computing Models
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 21/09/2022
Esame del 22 settembre
L'esame si terra' in aula N13A.
|
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.
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. Per sola comodità di erogazione, tale prova è
suddivisa in due parti relative al primo e al secondo modulo
Valutazione in itinere
Alternativamente all'esame ci si può avvalere della valutazione in itinere (prove intermedie).
- Solo gli studenti di "Automata, Languages and Computing" possono fruire della valutazione in intinere.
Per gli studenti del corso spento di Informatica Teorica non è prevista.
- La valutazione in itinere non è mutualmente esclusiva rispetto a quella tradizionale,
tuttavia, lo studente che si presenta all'esame in un regolare appello rifiuta implicitamente
- il voto della valutazione in itinere.
- Il risultato della valutazione in itinere, qualora accettato dallo studente, sarà verbalizzato
esclusivamente nella prima sessione d'esame di febbraio 2022.
- Si prevedono 4 prove intermedie in tutto, distribuite nel primo semestre. Il programma di
ciascuna prova comprende tutto il programma svolto dal primo giorno di lezione fino alla lezione
immediatamente precedente la prova. Il voto finale si otterrà facendo la media dei voti delle
singole prove dopo aver scartato il voto più basso (oppure, non considerando la prova a cui
lo studente è stato assente).
- Le date (preliminari e soggette a conferma) delle prove intermedie sono le seguenti:
- Venerdì 5 novembre 2021, Aula N10, dalle 16:00 alle 18:00. Risultati.
- Venerdì 3 dicembre 2021, Aula N10, dalle 16:00 alle 18:00. Risultati.
- Venerdì 17 dicembre 2021, Aula N10, dalle 16:00 alle 18:00. Risultati.
- Venerdì 21 gennaio 2022, Aula N10, dalle 16:00 alle 18:00. Risultati
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