Informatica Teorica
(Laurea Magistrale in Ing. Informatica - 1° anno)
Anno Accademico 2017-2018
Anni Accademici precedenti:
2011-2012
2012-2013
2013-2014
2014-2015
2015-2016
2016-2017
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:
- Annuncio del 24/01/2018
Verbalizzazione degli esiti della valutazione in itinere
Gli studenti che intendano avvalersi del risultato conseguito nella valutazione in itinere devono obbligatoriamente:
(1) Prenotarsi all'esame per l'appello di febbraio.
(2) Presentarsi in uno dei seguenti orari di verbalizzazione:
- martedi' 20 febbraio ore 13:00 - ufficio del docente;
- venerdi' 23 febbraio ore 17:00 - ufficio del docente.
Gli studenti che si presenteranno all'esame scritto dell'appello di febbraio rifiuteranno implicitamente
il voto della valutazione in itinere.
|
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 2018.
- 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ì 27 ottobre 2017 dalle 16:00 alle 18:30 aule N15 e N16.
Programma della prima prova - tutto il programma dall'inizio del corso fino alle proprietà
decidibili dei linguaggi regolari escluse.
Risultati.
- Venerdì 17 novembre 2017 dalle 16:00 alle 18:30 aule N15 e N16.
Programma della seconda prova - tutto il programma dall'inizio del corso fino
all'algoritmo CYK.
Risultati.
- Venerdì 1 dicembre 2017 dalle 16:00 alle 18:30 aule N15 e N16.
Programma della terza prova - tutto il programma dall'inizio del corso fino alla decidibilita'.
Risultati.
- Venerdì 12 gennaio 2018 dalle 16:00 alle 18:30 aule N15 e N16.
Programma della quarta prova - tutto il programma dall'inizio del corso fino alla complessita' temporale inclusa.
Risultati.
- Venerdì 19 gennaio 2018 dalle 16:00 alle 18:30 aule N15 e N16.
Programma della quinta prova - tutto il programma dall'inizio del corso.
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):
Informatica Teorica
/ A cura di Giuseppe Di Battista
e Maurizio Patrignani / 16 settembre 2017