Calcolabilita' e Complessita' (LS in Informatica) - a.a. 2009/10
Matematica Discreta (Logica Matematica), Programmazione, Algoritmi e
Strutture Dati (Complementi di Algoritmi e Strutture Dati).
I corsi indicati tra parentesi sono caldamente consigliati, anche se
formalmente non sono propedeutici.
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 dopo l'appello di Settembre viene fatto un
reset dei voti non registrati sul libretto.
- La prova orale si puo' sostenere solo se si e' superato la prova
scritta (puo' essere ammesso alla prova orale anche chi ha ottenuto un
voto di poco inferiore al 18). La prova orale puo' avere i seguenti
esiti: 1) lo studente si ritira prima che la prova sia conclusa (esito
RITIRATO); 2) il docente ritiene la prova insufficiente (esito
RESPINTO); 3) il docente assegna un voto complessivo (maggiore o
uguale a 18/30) da registrare sul libretto.
Nei casi 1) e 2) lo studente deve rifare la prova orale, ma puo'
essere conservato l'ultimo scritto, nel caso 3) lo studente puo'
accettare il voto o rifiutarlo (e' simile al caso 1).
Il regolamento didattico di Ateneo prevede che:
- uno studente puo' tentare lo scritto (=consegnarlo) fino a 3 volte in un anno accademico
- uno studente puo' tentare l'orale fino a 3 volte in un anno accademico,
tuttavia e' a discrezione del docente se permettere di rifiutare un
voto sufficiente (caso 3 sopra, io lo consento almeno una volta).
- richiami di logica:
logica booleana, logica del primo ordine, soddisfacibilita' e
validita', dimostrabilita' e teoremi di soundness e completeness,
teorema di incompletezza (per il modello standard di PA).
- 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, 4-6, 7-9)
Altri testi, (*) indica che puo' rimpiazzare [P94]
- R.J. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, 1988.
- E. Börger, Computability, Complexity, Logic, North-Holland, 1989.
- *A. Bernasconi, B. Codenotti, Introduzione alla Complessità Computazionale, Springer, 1998.
- T.H. Cormen, C.E. Leiserson, L.R. Rivest, Introduction to Algorithms, MIT Press, 1990.
- M.R. Garey, D.S. Johnson, Computers and Intractability, Freeman & Co., 1979.
- N.D. Jones, Computability and Complexity, MIT Press, 1997.
- H.R. Lewis, Ch.H. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1981.
- R. Sommerhalden, S.C. van Westrhenen, The Theory of Computability, Addison-Wesley, 1988.
- *C. Toffalori, F. Corradini, S. Leonesi, S. Mancini, Teoria della Computabilita' e della Complessita', McGraw-Hill, 2005.