Programma corso di complessità 2003/2004

Obiettivi formativi

Il corso è costituito da un'introduzione alla complessità strutturale con particolare attenzione alla teoria del NP-completezza. Scopo di tale introduzione è fornire agli studenti gli strumenti necessari per comprendere e affrontare la difficoltà nel risolvere, da un punto di vista computazionale, alcuni problemi comuni.

Attività formative

Il corso viene svolto in 40 ore di lezione frontale.

Programma del corso

Lezione	Data	Argomento
1	lunedì 29/09/2003	Introduzione al corso Presentazione del corso: programma, testi di riferimento e modalità d'esame. Concetto intuitivo di modello di calcolo, risorsa computazionale, algoritmo efficiente e problema trattabile. Riferimenti: capitoli 3.1-3.3 di "Introduzione alla complessità computazionale". Richiamo al concetto di ordine di grandezza: O, Ω e Θ.
2	martedì 30/09/2003	Problemi computazionali: descrizione, istanze, codifica, relazione con i linguaggi. Esempi di problemi: RAGGIUNGIBILITÀ, MASSIMO FLUSSO e PRIMO.
3	mercoledì 01/10/2003	Modelli di calcolo Macchina di Turing (MdT): definizione, funzionamento, concetto di produzione e di computazione. Identità tra MdT e algoritmi. Macchina di Turing e linguaggi: differenza tra accettare e decidere un linguaggio. Estensione della MdT: Macchina di Turing a più nastri (k-MdT). Esercizi da svolgere: determinare configurazione istantanea di una k-MdT e determinare una MdT che sposta a destra di 1 carattere la stringa di input. Riferimenti: capitolo 2 di "Computational Complexity".
4	lunedì 06/10/2003	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. Teorema di relazione polinomiale tra le computazioni delle macchine k-MdT e MdT.
5	martedì 07/10/2003	Introduzione al modello di calcolo "Macchina ad accesso casuale" (RAM = Random Access Machine): concetti di configurazione, programma e computazione.
6	mercoledì 08/10/2003	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.
7	lunedì 13/10/2003	Teorema sul costo di simulazione di una MdT mediante un programma RAM. Teorema sul costo di simulazione di un programma RAM mediante una MdT (solo enunciato). Tesi del calcolo sequenziale e sue conseguenze.
8	martedì 14/10/2003	Teorema dello speed-up lineare e sue conseguenze.
9	mercoledì 15/10/2003	La classe di complessità `P`. Esempi di problemi della classe `P`: raggiungibilità (PATH). Problema del flusso massimo (MAX FLOW).
10	lunedì 20/10/2003	Insidie sui possibili algoritmi di risoluzione per MAX FLOW. Problema dell'accoppiamento perfetto. Esempio di problema presumibilmente non in `P`: problema del commesso viaggiatore (TS) Estensione della Macchina di Turing: Macchina di Turing non deterministica (NMdT).
11	martedì 21/10/2003	Classe di complessità `NTIME(n)`. La classe di complessità `NP`. Esempio di problema in `NP`: problema del commesso viaggiatore.
12	mercoledì 22/10/2003	Relazione tra NMdT e MdT. Caratterizzazione alternativa della classe `NP`: verificatori polinomiali. Complessità in spazio Concetto di complessità spaziale. Macchina di Turing con input e output.
13	lunedì 27/10/2003	Classi di complessità `SPACE(n)` e `NSPACE(n)`. Teorema di compressione (solo enunciato, dimostrazione per esercizio). Classi di complessità `L` e `NL`. Esempi di problemi: PALINDROME ∈ `L` e PATH ∈ `NL.` Teoremi di relazione tra spazio e tempo di computazione per una MdT con I/O.
14	martedì 28/10/2003	Relazioni tra classi di complessità Concetto di funzione propria ed esempi di funzioni. Concetto di macchine di Turing precise. Teorema sulle computazioni precise (solo enunciato).
15	mercoledì 29/10/2003	Il metodo di 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))})`. Concetto di Macchina di Turing Universale.
16	lunedì 03/11/2003	L'insieme `H_f`. Lemma 1 per il teorema di gerarchia temporale. Lemma 2 per il teorema di gerarchia temporale. Corollario `P ⊂ EXP`. Teorema di gerarchia spaziale (solo enunciato). Corollario `L ⊂ PSPACE`. Importanza delle funzioni proprie: teorema del gap (solo enunciato).
17	martedì 04/11/2003	Teorema di Savitch. Corollario `SPACE(f(n))=SPACE(f(n)²)`. Corollario `PSPACE=NPSPACE`.
18	mercoledì 05/11/2003	Ripasso concetto di funzione booleana, espressione booleana e circuito booleano. Definizione di SAT, CIRCUIT SAT, CIRCUIT VALUE. Riduzioni e completezza Concetto di riduzione.
19	lunedì 10/11/2003	Concetto di riduzione logaritmica in spazio. Esempio di riduzione: HAMILTON PATH ≤_log SAT, PATH ≤_log CIRCUIT VALUE, CIRCUIT SAT ≤_log SAT. Esempio di riduzione per generalizzazione.
20	martedì 11/11/2003	Proprietà delle riduzioni: transitiva e riflessiva. Concetto di completezza di un linguaggio. Concetto di chiusura rispetto alla riduzione. Chiusura delle classi `L, NL, P, NP, PSPACE e EXP`.
21	mercoledì 12/11/2003	Concetto di tabella di computazione. Dimostrazione che CIRCUIT VALUE è `P-completo`. Dimostrazione alternativa del teorema di Cook: CIRCUIT SAT è `NP-completo`.
22	lunedì 17/11/2003	Esempi di problemi `NP-completo` e loro riduzioni: SAT e sue varianti (3SAT, 3SAT con vincoli). Il caso 2SAT. Concetto di gadget e dimostrazione della completezza del problema dell'insieme di indipendenza (Independet Set). Problemi collegati: cricca (Clique) e ricoprimento di vertici (vertex cover).
23	martedì 18/11/2003	Cenni sulla completezza dei problemi: Massimo Taglio, K-Colorabilità, Circuito Hamiltoniano, Commesso viaggiatore, Accoppiamento tripartito.
24	mercoledì 19/11/2003	Cenni sulla completezza della Programmazione Lineare Intera e Zaino. Concetto di algoritmo pseudo polinomiale. Problemi fortemente NP-completi. Esercizi vari di riepilogo.