Algoritmi e Complessità, 6CFU, A.A. 2003/2004

Argomenti trattati a lezione e docenti

1. 12 Gennaio 2004. Presentazione del corso (Policriti).
2. 19 Gennaio 2004. Problemi e Linguaggi. Problemi Decisionali e Funzionali. Macchina di Turing a k nastri. Principali definizioni. Simulazione in tempo quadratico di una k-MdT con una 1-MdT. (Dovier)
3. 21 Gennaio 2004. Il Teorema di Speed-up lineare ed il suo significato. Le classi P ed EXPTIME e la loro stabilità rispetto ai modelli 1-MdT e k-MdT. Il modello della RAM: definizioni principali. (Dovier)
4. 22 Gennaio 2004. 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. 26 Gennaio 2004. 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. (Dovier)
6. 28 Gennaio 2004. Funzioni di complessità proprie. Il linguaggio Hf e le sue conseguenze; in particolare l'inclusione stretta tra P e EXPTIME. (Dovier)
7. 29 Gennaio 2004. Pointer Machines. Principali definizioni e caratteristiche. Esempi del loro uso per lo studio di classi di complessità per problemi su alberi. (Dal Palù-Dovier)
8. 2 Febbraio 2004. Il "Gap Theorem". Classi in spazio deterministiche e non. Principali risultati. Le inclusioni L, NL, P, NP, PSPACE, NPSPACE, EXP. (Dovier)
9. 4 Febbraio 2004. Il Teorema di Savitch e PSPACE = NPSPACE. Classi complementari. Il Teorema di Immerman-Szelepscenyi e le sue conseguenze. (Dovier)
10. 5 Febbraio 2004. Riduzioni e Completezza. CIRCUIT VALUE e CIRCUIT SAT. I Teoremi di Cook. SAT e sua NP-completezza. (Dovier)
11. 9 Febbraio 2004. Introduzione al Quantum Computing. Quantum Bits, Quantum registers e quantum gates. Interferenza, Sovrapposizione e Parallelismo Quantistico. Computazione quantistica versus computazione classica e randomizzta. La radice del Not ed il Problema di Deutcsh. (Gentilini-Dovier)
12. 11 Febbraio 2004. 3SAT e 2SAT. Problemi L completi, NL-completezza di REACHABILITY, Co-NP Completezza di VALIDITY. QSAT: sua appartenenza a PSPACE. (Dovier)
13. 12 Febbraio 2004. PSPACE completezza di QSAT. Problemi EXPTIME e NEXPTIME completi. Quantum computing: algoritmo di Deutcsh-Josza. (Gentilini-Dovier)
14. 16 Febbraio 2004. L'algoritmo di Grover: descrizione, complessita', sua interpretazione geometrica ed ottimalita' (senza dim.) (Gentilini-Policriti)
15. 18 Febbraio 2004. cenni storici sul DNA computing; l'esperimento di Adleman per la determinazione di cammini hamiltoniani; descrizione del modello di calcolo su DNA. (Piazza-Dovier)
16. 19 Febbraio 2004. 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-Policriti)
17. 20 Febbraio 2004. Determinazione del periodo di una funzione e fattorizzazione nel modello quantistico. L'algoritmo di Shor. (Gentilini-Policriti)
18. 23 Febbraio 2004. Turing completezza del DNA computing (Piazza-Dovier).
19. 26 Febbraio 2004. La storia e lo stato del problema "P = NP?" (Policriti)
20. 1 Marzo 2004. La computazione parallela: questioni terminologiche fondamentali e introduzione al linguaggio/libreria MPI (Message Passing Interface). (Policriti)
21. 2 Marzo 2004. Complessità di Kolmogorov e limite inferiore per il problema del riconoscimento di palindromicità. Problemi di equivalenza di DFA e NFA e loro collocazione. (Bortolussi, Bresolin, Policriti)
22. 8 Marzo 2004. I primi programmi MPI, le primitive MPI_Send ed MPI_Recv, I/O. (Policriti)
23. 10 Marzo 2004. La comunicazione tra processi in MPI, il broadcasting, il modello butterfly. (Policriti)
24. 11 Marzo 2004. La compressione dei dati nei messaggi. il raggruppamento di dati non omogenei in MPI. (Policriti)

Testi e altro materiale didattico.