Calcolabilita' e Complessita' (LS in Informatica) - a.a. 2009/10

Prerequisiti

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.

Obiettivi

Fornire nozioni e risultati fondamentali di calcolabilita' e complessita' computazionale.

Modalita' degli esami

L'esame si suddivide in una prova scritta ed una orale. Il regolamento didattico di Ateneo prevede che:

Programma

Testi di Riferimento

Altri testi, (*) indica che puo' rimpiazzare [P94]