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

Agostino Dovier e Alberto Policriti

Argomenti trattati a lezione

1. 1 Marzo 2010 (Dovier). Introduzione al corso. Per approfondire: Kleinberg and Papadimitriou. Computability and Complexity e K. devlin, I problemi matematici del millennio

   RESTO DEL CORSO CON DATE E PROGRAMMA DA SISTEMARE

   Parte 1. Fondamenti della complessità computazionale e relative classi.

2. 10 Gennaio 2005. Presentazione del corso Problemi e Linguaggi. Problemi Decisionali e Funzionali. Macchina di Turing a k nastri. Principali definizioni. (Dovier)
3. 11 Gennaio 2005. Simulazione in tempo quadratico di una k-MdT con una 1-MdT. Il Teorema di Speed-up lineare ed il suo significato. (Dovier)
4. 12 Gennaio 2005. Il modello della RAM. Uso delle RAM per decidere linguaggi e delle MdT per calcolare funzioni RAM. Equivalenza computazionale (modulo polinomialità) dei due formalismi. Tesi di Church computazionale. (Dovier)
5. 17 Gennaio 2005. Le classi P ed EXPTIME e la loro stabilità rispetto ai modelli 1-MdT e k-MdT. Non determinismo: Macchina di Turing Non-Deterministica. NP. Dimostrazioni delle inclusioni P e NP, NP e EXPTIME. SAT e sua appartenenza ad NP. NP come Guess & Verify. Funzioni di complessità proprie. (Dovier)
6. 18 Gennaio 2005. Il linguaggio Hf e le sue conseguenze; in particolare l'inclusione stretta tra P e EXPTIME. Enunciato del GAP Theorem. Classi in spazio deterministiche e non. Principali risultati. Le inclusioni L, NL, P, NP, PSPACE, NPSPACE, EXP. (Dovier)
7. 19 Gennaio 2005. Il metodo di raggiungibilita'. Il Teorema di Savitch e PSPACE = NPSPACE. Il Teorema di Immerman-Szelepscenyi. (Dovier)
8. 24 Gennaio 2005. Classi complementari. Conseguenze del Teorema di Immerman-Szelepscenyi. Riduzioni e Completezza. CIRCUIT VALUE e CIRCUIT SAT. Loro rappresentazione su MdT. I Teoremi di Cook. (Dovier)
9. 25 Gennaio 2005. NP-completezza di SAT e 3SAT. Problemi L completi, NL-completezza di REACHABILITY e 2SAT. Co-NP Completezza di VALIDITY. QSAT e varianti. (Dovier)
10. 26 Gennaio 2005. QSAT: appartenenza a PSPACE sua completezza. Problemi EXPTIME e NEXPTIME completi. (Dovier)

    Parte 2. Nuovi formalismi per il calcolo.

11. 31 Gennaio 2005. Cenni storici sul DNA computing; l'esperimento di Adleman per la determinazione di cammini hamiltoniani; descrizione del modello di calcolo su DNA. (Piazza-D)
12. 1 Febbraio 2005. Limitazioni del modello di calcolo su DNA; il modello di calcolo ristretto; soluzione del problema di soddisfacibilita' di formule proposta da Lipton sul modello ristretto; classificazione degli algoritmi basati su DNA computing (volume costante/decrescente/misti, nozione di uniformita'). (Piazza-D)
13. 3 Febbraio 2005. Turing completezza del DNA computing. (Piazza-D)
14. 7 Febbraio 2005. Introduzione alla computazione quantistica. Quantum bit, registri, porte logiche e circuiti quantistici. Circuiti quantistici e universalita'. Simulazione di computazioni classiche e randomizzate nel modello computazionale quantistico. (Gentilini-P)
15. 8 Febbraio 2005. Introduzione agli algoritmi quantistici. Il problema di Deutsch e l'algoritmo di Deutsch-Josza. (Gentilini-P)
16. 9 Febbraio 2005. Algoritmi di ricerca nel modello computazionale quantistico: l'algoritmo di Grover. (Gentilini-P)
17. 14 Febbraio 2005. Il problema della fattorizzazione e l'algoritmo di Shor. (Gentilini-P)

    Parte 3. Algoritmi.

18. 15 Febbraio 2005. Algoritmo di Hopcroft. (Policriti)
19. 16 Febbraio 2005. Algoritmo di Paige-Tarjan. (Policriti)
20. 17 Febbraio 2005. Algoritmo di Paige-Tarjan-Bonic. (Policriti)
21. 21 Febbraio 2005. Cenni agli algoritmi di Karp e Rabin e di Knuth-Morris-Pratt. (Policriti)
22. 24 Febbraio 2005. Introduzione alle classi L, SL, NL, L^2 ed il problema STCONN. (Policriti)
23. 28 Febbraio 2005. La classe RL ed il problema USTCONN. (Policriti)
24. 1 Marzo 2005. La tecnica di Reingold per il problema USTCONN. (Policriti)
25. 3 Marzo 2005. Il teorema di Reingold L = SL. Valutazione del Corso. (Policriti)

Testi e altro materiale didattico.