Obiettivi formativi

Fornire un'introduzione alla complessità strutturale con particolare attenzione alla teoria del NP-completezza. Fornire brevi cenni agli algoritmi probabilistici come strumento per risolvere problemi NP-completi.

Attività formative

Il corso viene svolto in 40 ore di lezione frontale.

Programma del corso

Lezione Data Argomento
1 lunedì
30/09/2002		 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".
2 giovedì
03/10/2002		 Problemi computazionali: descrizione, istanze, codifica, relazione con i linguaggi.
Richiamo al concetto di ordine di grandezza: O, Ω e Θ.
3 venerdì
04/10/2002		 Modelli di calcolo
Macchina di Turing (MdT). 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). Riferimenti: capitolo 2 di "Computational Complexity".
4 lunedì
07/10/2002		 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 equivalenza tra k-MdT e MdT.
5 giovedì
10/10/2002		 Introduzione al modello di calcolo "Macchina ad accesso casuale" (RAM = Random Access Machine): concetti di configurazione, programma e computazione.
6 venerdì
11/10/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.
7 lunedì
14/10/2002		 Teorema sul costo di simulazione di una MdT mediante un programma RAM.
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.
8 giovedì
17/10/2002		 La classe di complessità P.
Esempi di problemi della classe P: raggiungibilità (PATH).
9 venerdì
18/10/2002		 Non tenuta per sciopero.
10 lunedì
21/10/2002		 Problema del flusso massimo (MAX FLOW) e insidie sui possibili algoritmi di risoluzione. Problema dell'accoppiamento perfetto.
11 giovedì
24/10/2002		 Estensione della Macchina di Turing: Macchina di Turing non deterministica (NMdT).
Classe di complessità NTIME(n).
La classe di complessità NP.
12 venerdì
25/10/2002		 Esempi di problemi della classe NP: problema del commesso viaggiatore
Relazione tra NMdT e MdT.
13 lunedì
28/10/2002		 Caratterizzazione alternativa della classe NP: verificatori polinomiali.
Complessità in spazio
Concetto di complessità spaziale. Macchina di Turing con input e output.
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 giovedì
31/10/2002		 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 lunedì
04/11/2002

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 giovedì
07/11/2002

L'insieme Hf.
Lemma 1 per il teorema di gerarchia temporale.
17 venerdì
08/11/2002

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).
Teorema di Savitch. Corollario SPACE(f(n))=SPACE(f(n)2). Corollario PSPACE=NPSPACE.
18 lunedì
11/11/2002		 Ripasso concetto di funzione booleana, espressione booleana e circuito booleano.
Definizione di SAT, CIRCUIT SAT, CIRCUIT VALUE.
Riduzioni e completezza
Concetto di riduzione e di riduzione logaritmica in spazio.
Esempio di riduzione: HAMILTON PATH ≤log SAT.
19 giovedì
14/11/2002		 Esempi di riduzioni: PATH ≤log CIRCUIT VALUE, CIRCUIT SAT ≤log SAT.
Esempio di riduzione per generalizzazione.
20 venerdì
15/11/2002		 Proprietà delle riduzioni: transativa e riflessiva.
Concetto di completezza di un linguaggio. Concetto di chiusura rispetto alla riduzione. Chiusura delle classi L, NL, P, NP, PSPACE e EXP.
Concetto di Tabella di computazione (tableau).
21 lunedì
18/11/2002		 CIRCUIT VALUE è P-completo.
Dimostrazione alternativa del teorema di Cook: SAT è NP-completo.
22 giovedì
21/11/2002		 Esempi di problemi NP-completo e loro riduzioni: SAT e sue varianti (3SAT, 3SAT con vincoli). Il caso 2SAT.
23 venerdì
22/11/2002		 Concetto di gadget e dimostrazione della completezza del problema dell'insieme di indipendenza (Independet Set). Problema colleagato: cricca (Clique). Cenni sulla completezza dei problemi: Massimo Taglio, K-Colorabilità, Circuito Hamiltoniano, Commesso viaggiatore, Accoppiamento tripartito, Programmazione Lineare Intera e Zaino.
24 lunedì
25/11/2002		 Esercizi vari di riepilogo.