Algoritmi e Complessità, 6CFU, A.A. 2003/2004
Argomenti trattati a lezione
Parte 1. Fondamenti della complessità computazionale e
relative classi.
- 10 Gennaio 2005. Presentazione del corso
Problemi e Linguaggi. Problemi Decisionali
e Funzionali. Macchina di Turing a k nastri.
Principali definizioni. (Dovier)
- 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)
- 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)
- 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)
- 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)
- 19 Gennaio 2005.
Il metodo di raggiungibilita'.
Il Teorema di Savitch e PSPACE = NPSPACE.
Il Teorema di Immerman-Szelepscenyi. (Dovier)
- 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)
- 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)
- 26 Gennaio 2005.
QSAT: appartenenza a
PSPACE sua completezza.
Problemi EXPTIME e NEXPTIME completi. (Dovier)
Parte 2. Nuovi formalismi per il calcolo.
- 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)
- 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)
- 3 Febbraio 2005.
Turing completezza del DNA computing.
(Piazza-D)
- 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)
- 8 Febbraio 2005.
Introduzione agli algoritmi quantistici.
Il problema di Deutsch e l'algoritmo di Deutsch-Josza.
(Gentilini-P)
- 9 Febbraio 2005.
Algoritmi di ricerca nel modello computazionale quantistico: l'algoritmo di Grover.
(Gentilini-P)
- 14 Febbraio 2005.
Il problema della fattorizzazione e l'algoritmo di Shor.
(Gentilini-P)
Parte 3. Algoritmi.
- 15 Febbraio 2005. Algoritmo di Hopcroft.
(Policriti)
- 16 Febbraio 2005.
Algoritmo di Paige-Tarjan.
(Policriti)
- 17 Febbraio 2005.
Algoritmo di Paige-Tarjan-Bonic.
(Policriti)
- 21 Febbraio 2005.
Cenni agli algoritmi di Karp e Rabin e di Knuth-Morris-Pratt.
(Policriti)
- 24 Febbraio 2005.
Introduzione alle classi L, SL, NL, L^2 ed il problema STCONN.
(Policriti)
- 28 Febbraio 2005.
La classe RL ed il problema USTCONN.
(Policriti)
- 1 Marzo 2005.
La tecnica di Reingold per il problema USTCONN.
(Policriti)
- 3 Marzo 2005.
Il teorema di Reingold L = SL.
Valutazione del Corso.
(Policriti)
Testi e altro materiale didattico.
Home page