Calcolabilita' e Complessita' (Laurea Specialistica) - a.a. 2003/04
IMPORTANTE. Giovedi' 18 Dicembre saranno consegnati dei questionari
per il monitoraggio dell'attivita' didattica, da compilare in aula
(tempo di compilazione < 30 min).
Matematica Discreta (Logica Matematica), Programmazione, Algoritmi e
Strutture Dati.
Fornire nozioni e risultati fondamentali di calcolabilita' e
complessita' computazionale.
L'esame si suddivide in una prova scritta ed una orale. Per la prova
scritta si danno in genere 2 ore. Durante lo scritto e' possibile
consultare dispense e libri. E' possibile conservare il voto dello
scritto negli appelli successivi, basta non ritentarlo (o non
cosegnarlo). Tuttavia, alla fine di ogni anno accademico (dopo
l'appello di Gennaio-Febbraio) viene fatto un reset dei voti.
- modelli di calcolo:
TM, RAM, funzioni calcolabili, complessita' tempo e spazio, relazione
tra i due modelli di calcolo, Tesi di Church e Tesi di Church estesa.
- calcolabilita':
funzioni calcolabili, problemi/sottoinsiemi decidibili e
semidecidibili, riducibilita' tra problemi, codifica delle TM, TM
universale, esempi di problemi non (semi)decidibili, proprieta' di
chiusura dei sottoinsiemi (semi)decidibili.
- complessita':
classi di complessita', relazioni tra classi di complessita' ed
O-notazione, classi naturali di complessita' (P, NP), teorema di Cook,
esempi di problemi NP-completi.
- panoramica su altri argomenti di complessita':
accenni ad altri modelli di calcolo (per algoritmi probabilistici e
paralleli), e relative classi di complessita'.
- [P94] C.Papadimitriou. Computational Complexity.
Addision-Wesley, 1994.
(CH 1-3, 7-9)
Laurea Specialistica in Informatica
