Modelli e Complessità di Calcolo

Nuovo Ordinamento

a.a. 2007-2008




Modalità d'esame:

In ogni appello ci sarà una prova scritta contenente sia esercizi che domande di teoria. Il voto conseguito alla scritto è il voto definitivo. Gli studenti che prendano un voto inferiore o uguale a 23 possono chiedere di sostenere una prova orale (il cui voto farà media con il voto della prova scritta) nello stesso appello o in uno dei successivi.


Programma d'esame:

Testi di riferimento:

Programma dettagliato:
  1. Concetti matematici di base.
    [AdG] - Cap. 1 tutto
  2. Macchine di Turing e T-Calcolabilità.
    [AdG] - Cap. 5: sezioni 5.1, 5.2, 5.3, 5.4, 5.5, 5.6, 5.8 (solo enunciato del teorema 5.7), 5.9, 5.10 e 5.11.
  3. Macchine a registri.
    [AdG] - Cap. 6: sezioni 6.1, 6.2 e 6.3.
  4. Funzioni ricorsive, Formalismo di McCarthy, SLF, LISP
    [AdG] - Cap. 6: sezioni 6.4 e 6.6, 6.7.
    [AL] - tutto.
  5. Teoria generale della calcolabilità
    [AdG] - Cap. 7: sezioni 7.1, 7.2 (solo enunciati dei teoremi 7.1, 7.2 e 7.3), 7.3, 7.4, 7.5 e 7.6, 7.7.
    [PCP] - tutto.
  6. Complessità di calcolo
    [AgG] - Cap. 8: sezioni 8.1, 8.2, 8.3, 8.5, 8.6 (senza dimostrazione dei teoremi 8.5 e 8.6), 8.7, 8.8 e 8.9.
    [AgG] - Cap. 9: sezioni 9.1, 9.3, 9.4 (esclusa la dimostrazione del Teorema 9.7), 9.5 (esclusa la Sottosezione 9.5.3), 9.6 (solo definizioni 9.14, 9.15 e Teorema 9.13).
    [ALM] - Sezione 3, per esercizi sulle riduzioni.