Informatica Teorica
(Laurea Magistrale in Ing. Informatica - 1° anno)
Anno Accademico 2016-2017
Anni Accademici precedenti:
2011-2012
2012-2013
2013-2014
2014-2015
2015-2016
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: Maurizio Patrignani
In questa pagina potrete trovare:
Archivio avvisi
Il programma di massima del corso di Informatica Teorica è 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.
- Cardinalità di insiemi infiniti.
- 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.
- Macchine a registri (RAM): modelli di costo per RAM, modello a costi uniformi, modello a costi
logaritimici, RAM 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 Pspazio, Pspazio-completezza, teorema di Savitch, le classi L e NL, NL-completezza.
Materiale didattico (i link inattivi corrispondono a materiale in corso di revisione)
|
- I testi consigliati (non considerati indispensabili) sono:
- Slide del corso di Informatica Teorica:
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
- Gli studenti D.M 509/99 avranno compiti appositi
- Gli studenti che devono sostenere un compito integrativo da 7 CFU avranno compiti appositi (si prega di contattare il docente in anticipo)
Valutazione in itinere
Alternativamente all'esame ci si può avvalere della valutazione in itinere
(prove intermedie).
- Solo gli studenti D.M. 270/04 di "Informatica Teorica" possono fruire della valutazione in intinere. Per gli
studenti D.M. 509/99 (che hanno un diverso programma) 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 2017.
- Si prevedono 5 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 una prova a cui lo studente è stato assente).
- Le date (preliminari e soggette a conferma) delle prove intermedie sono le seguenti:
- Venerdì 28 ottobre 2016 dalle 18:00 alle 19:00 aule N10, N11, N1 di Via della Vasca Navale, 79.
Programma della prima prova - tutto il programma dall'inizio del corso fino al Pumping Lemma incluso
(proprietà di chiusura, proprietà decidibili e Myhill-Nerode esclusi).
Risultati.
Testo.
- Venerdì 18 novembre 2016 dalle 18:00 alle 19:00 aule N10, N11, N1 di Via della Vasca Navale, 79.
Programma della seconda prova - tutto il programma dall'inizio del corso fino
agli automi a pila (ambiguità delle grammatiche esclusa).
Risultati.
Testo.
- Venerdì 2 dicembre 2016 dalle 18:00 alle 19:00 aule N10, N11, N1 di Via della Vasca Navale, 79.
Programma della terza prova - tutto il programma dall'inizio del corso fino alle MT non deterministiche escluse.
Risultati.
Testo.
- Lunedì 9 gennaio 2016 dalle 18:00 alle 19:00 aula N18 di Via della Vasca Navale, 109.
Programma della quarta prova - tutto il programma dall'inizio del corso fino alla relazione tra RAM e MT esclusa.
Risultati.
Testo.
- Giovedì 26 gennaio 2017 dalle 18:00 alle 19:00 aule N15, N16 di Via della Vasca Navale, 109.
Programma della quinta prova - tutto il programma dall'inizio del corso.
Risultati.
Testo.
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):
Informatica Teorica
/ A cura di Giuseppe Di Battista
e Maurizio Patrignani / 6 settembre 2016