Algoritmi e Complessità, 6CFU, A.A. 2009/2010

Agostino Dovier e Alberto Policriti

Indicazioni sull'esame.

L'esame consta di una prova orale su tutto il contenuto del corso con data da fissare mediante appuntamento.

Facoltativamente lo studente può presentare un argomento non trattato nel corso concordato preventivamente coi docenti. L'approfondimento non è condizione necessaria né sufficiente per conseguire il massimo punteggio.

Programma:

Parte 1. Fondamenti della complessità computazionale in tempo e spazio e relative classi.

Parte 2. P ed NP. Tassonomia dei problemi NP-completi.

Parte 3. Approfondimenti e formalismi alternativi per il calcolo.

Argomenti trattati a lezione

  1. 1 Marzo 2010 (Dovier). Introduzione al corso.
    Per approfondire [ 3 ] e [ 4 ].
  2. 4 Marzo 2010 (Dovier). Problemi e Linguaggi. Problemi Decisionali e Funzionali. Macchina di Turing a k nastri. Principali definizioni.
  3. 8 marzo 2010 (Dovier). Simulazione in tempo quadratico di una k-MdT con una 1-MdT. Il Teorema di Speed-up lineare ed il suo significato.
  4. 11 Marzo 2010 (Dovier). Il modello della RAM. Sintassi e semantica.
  5. 15 Marzo 2010 (Dovier). Uso delle RAM per decidere linguaggi e delle MdT per calcolare funzioni RAM. Equivalenza computazionale (modulo polinomialità) dei due formalismi. Tesi di Church computazionale.
  6. 18 Marzo 2010. I ora. Guido Gherardi (Univ. di Bologna): COMPUTAZIONI (IM)POSSIBILI SUL CONTINUO.
    II ora. (Dovier) Le classi P ed EXPTIME e la loro stabilità rispetto ai modelli 1-MdT e k-MdT. Non determinismo: Macchina di Turing Non-Deterministica. Definizione della classe NP.
  7. 22 Marzo 2010. (Dovier) Dimostrazioni delle inclusioni P e NP, NP e EXPTIME. Macchina di Turing universale. Codifica universale di alfabeti, stati e input. Simulazione e sua complessità.
  8. 29 Marzo 2010 (Dovier). Funzioni di complessità proprie. Il linguaggio Hf e le sue conseguenze; in particolare l'inclusione stretta tra P e EXPTIME. Il GAP Theorem.
  9. 8 Aprile 2010 (Dovier). Classi in spazio deterministiche e non. Principali risultati. Il metodo di raggiungibilita'. Le inclusioni L, NL, P, NP, PSPACE, NPSPACE, EXP.
  10. 12 Aprile 2010 (Policriti). Introduzione alla classe NP; problemi astratti/concreti; codifiche (ragionevoli); funzioni di conversione polinomiali.
  11. 15 Aprile 2010 (Dovier). Raggiungibilita' in spazio logaritmico su macchina non deterministica. Il Lemma di Savitch e le sue principali conseguenze.
  12. 19 Aprile 2010 (Dovier). Classi complementari. Il Teorema di Immerman-Szelepscenyi e le sue principali conseguenze. Il diagramma di Venn delle classi principali.
  13. 22 Aprile 2010 (Policriti). Problemi e linguaggi; proprieta' di chiusura; definizione di P; algoritmi di verifica e certificati; definizione di NP e riduzioni polinomiali; la classe NPC.
  14. 26 Aprile 2010 (Policriti). Il problema CIRCUIT-SAT e la sua appartenenza ad NPC; il problema SAT e la riduzione di CIRCUIT-SAT a SAT.
  15. 29 Aprile 2010 (Policriti). Il problema SAT e i problemi 3-CNF-SAT e 2-CNF-SAT. Riduzioni e soluzioni polinomiali.
  16. 3 Maggio 2010 (Policriti). I problemi CLIQUE, VERTEX-COVER e HAMILTONIAN in NPC.
  17. 7 Maggio 2010 (Policriti). I problemi Traveling Salesman e Set Covering, e cenni a K-coloring. Il X problema di Hilbert [5]. Introduzione. Insiemi diofantei.
  18. 10 Maggio 2010 (Policriti). Codifica della coppia e Teorema cinese del resto.
  19. 13 Maggio 2010 (Policriti). L'equazione di Pell e 17 Lemmi per la soluzione del X problema di Hilbert.
  20. 17 Maggio 2010 (Policriti). I rimanenti 7 lemmi. La funzione esponenziale, il fattoriale ed il prodotto.
  21. 20 Maggio 2010 (Policriti). Equivalenza tra insiemi diofantei e funzioni ricorsive. L'indecidibilità del X problema di Hilbert. Considerazioni circa gradi e dimensioni del polinomio.
  22. 24 Maggio 2010 (Dovier). Il no-free-lunch (NFL) Theorem per l'ottimizzazione combinatoria [6]. Valutazione del corso.
  23. 27 Maggio 2010. (Carla Piazza) DNA computing.
  24. 3 Giugno 2010. Visione del documentario Julia Robinson and Hilbert's Tenth Problem con introduzione di A. Policriti. (dettagli) e Trailer.

Testi e altro materiale didattico.

  1. C. H. Papadimitriou. Computational Complexity. Addison Wesley, 1995.
  2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein. Introduction to Algorithms (Second Edition). MIT Press and McGraw-Hill.
  3. Kleinberg and Papadimitriou. Computability and Complexity
  4. K. Devlin, I problemi matematici del millennio
  5. Martin D. Davis, Hilbert's Tenth Problem is Unsolvable Award: Lester R. Ford Year of Award: 1974 The American Mathematical Monthly, vol. 80, 1973, pp. 233-269 Una sua presentazione
  6. David H. Wolpert and William G. Macready. NO FREE LUNCH THEOREMS FOR OPTIMIZATION IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 1, NO. 1, APRIL 1997 67