Fornire un'introduzione alla complessità strutturale con particolare attenzione alla teoria del NP-completezza e alla classificazione dei problemi in base alla loro approssimabilità
Il corso viene svolto in 50 ore di lezione frontale.
| N° | Data | Argomento |
|---|---|---|
| 1 | martedì 09/4/2002 | Introduzione al corso Concetto intuitivo di modello di calcolo, risorsa computazionale, algoritmo efficiente e problema trattabile. |
| 2 | mercoledì 10/4/2002 | Problemi: descrizione, codifica, istanze, relazione con i
linguaggi, algoritmi risolutori. Richiamo al concetto di ordine di grandezza. Modelli di calcolo Macchina di Turing (TM). MdT come algoritmi. |
| 3 | giovedì 11/4/2002 | Macchina di Turing e linguaggi: differenza tra accettare e
decidere un linguaggio. Estensione della TM: Macchina di Turing a più nastri (k-TM). Complessità in tempo Concetto di complessità temporale. Classe di complessità TIME(n). Esempio di macchina di turing per decidere il linguaggio delle stringhe binarie palindrome. |
| 4 | martedì 16/4/2002 | Teorema di equivalenza tra k-TM e TM. Introduzione al modello di calcolo Macchina ad accesso casuale (RAM): concetti di configurazione, programma e computazione. |
| 5 | mercoledì 17/4/2002 | Macchina ad accesso casuale (RAM): tempo di computazione secondo
il criterio di costo uniforme e costo logaritmico. Ipotesi
necessarie per poter utilizzare il criterio del costo uniforme. Esempio di programma RAM per calcolare il prodotto di due interi. Teorema sulla simulazione di una MdT con un programma RAM. |
| 6 | giovedì 18/4/2002 | Teorema sul costo di simulazione di un programma RAM mediante
una MdT. Tesi del calcolo sequenziale e sue conseguenze. Teorema dello speed-up lineare e sue conseguenze. La classe di complessità P. Esempi di problemi della classe P: raggiungibilità. |
| 7 | martedì 23/4/2002 | Problema del flusso massimo e insidie sui possibili algoritmi di
risoluzione. Problema dell'accoppiamento perfetto. |
| 8 | mercoledì 24/4/2002 | Estensione della Macchina di Turing: Macchina di Turing non
deterministica (NDTM). Classe di complessità NTIME(n). Relazione tra NDTM e TM. La classe di complessità NP. Esempi di problemi della classe NP. |
| 9 | martedì 30/4/2002 | Complessità in spazio Concetto di complessità spaziale. Classi di complessità SPACE(n) e NSPACE(n). Teorema di compressione. Classi di complessità L e NL con esempi di due problemi. Relazioni tra classi di complessità Concetto di funzione propria ed esempi di funzioni proprie. |
| 10 | giovedì 02/5/2002 | Concetto di macchine precise. Classi parametriche. Classi complementari. Definizione di SAT e SAT COMPLEMENTARE. Concetto di Macchina di Turing Universale. L'insieme Hf. |
| 11 | martedì 07/5/2002 | Teorema di gerarchia temporale e spaziale. Inclusioni strette: P ⊂ EXP e L ⊂ PSPACE. Teorema del gap e importanza delle funzioni proprie. |
| 12 | mercoledì 08/5/2002 | Il metodo della raggiungibilità Teorema di inclusione tra classi in tempo e in spazio: NTIME(f(n)) ⊆ SPACE (f(n)), NSPACE(f(n)) ⊆ TIME(k( log n + f(n) )). Esercizio: QBF (Quantified Boolean Formulae) ∈ PSPACE. |
| 13 | giovedì 09/5/2002 | Teorema di Savitch. Corollario SPACE (f(n)) = NSPACE (f(n)). Chiusura delle classi spazio non deterministiche rispetto al complento. Ripasso concetto di funzione booleana, espressione booleana e circuito booleano. |
| 14 | martedì 14/5/2002 | Riduzioni e completezza Concetto di riduzione, riduzione logaritmica in spazio. Esempi di riduzioni: HAMILTON ≤ log SAT , PATH ≤log CIRCUIT VALUE , CIRCUIT SAT ≤log SAT. |
| 15 | mercoledì 15/5/2002 | Esempio di riduzione per generalizzazione. Proprietà delle riduzioni. Concetto di completezza. Concetto di chiusura rispetto alla riduzione. |
| 16 | giovedì 16/5/2002 | Chiusura delle classi P, NP, coNP, L, NL, PSPACE e EXP. Concetto di Tabella di computazione (tableau). Dimostrazione CIRCUIT VALUE è NP-Completo. |
| 17 | martedì 21/5/2002 | Dimostrazione alternativa del teorema di Cook e primo problema
NP-completo: SAT. Esempi di problemi NP-completi e loro riduzioni:
SAT e sue varianti (3SAT, 3SAT con vincoli). Il caso 2SAT. |
| 18 | giovedì 23/5/2002 | Concetto di gadget e dimostrazione della completezza del
problema MAX-2SAT. Esempi di problemi NP-completi e loro riduzioni: Clique, Vertex Cover e Independent Set. |
| 19 | martedì 28/5/2002 | Il problema del CUT e sue varianti: MIN-CUT, MAX-CUT e BISECTION
MAX. Cenni sulla dimostrazione della NP-completezza del problema Hamiltoniano mediante l'uso del gadget diamante. Problema della k-colorabilità di un grafo per k=2,3 e 4. Analisi di complessità dei problemi TRIPARTITE MATCHING, SET COVERING e EXACT COVER BY 3 SET. Analisi del problema della PROGRAMMAZIONE LINEARE INTERA e sua riduzione al SET COVERING. |
| 20 | mercoledì 29/5/2002 | Algoritmi probabilistici. Definizione di Macchina di Turing probabilistica e concetto di accettazione. Classe di complessità Bounded Probability of error (BPP). |
| 21 | giovedì 30/5/2002 | Lemma di amplificazione con dimostrazione. Il problema della primalità di un numero. Algoritmi MonteCarlo. Classe di complessità RP. Relazioni tra le classi P, NP, RP, BPP. |
| 22 | martedì 04/6/2002 | Concetto di algoritmo di approssimazione. Concetto di errore relativo e indice di prestazione. Esempio di algoritmi di approssimazione (ε-approssimati) per il problema VERTEX COVER e INDEPENDENT SET. |
| 23 | mercoledì 05/6/2002 | Classificazione di problemi in base alla loro
approssimabilità: classi APX, PTAS e FPTAS. Concetto di
riduzione che preserva l'approssimabilità. Risultati principali sulla non approssimabilità. |
| 24 | giovedì 06/6/2002 | Esercizi vari. |