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.
Il corso viene svolto in 40 ore di lezione frontale.
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 viaggiatoreRelazione 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à. |
16 | giovedì 07/11/2002 |
L'insieme |
17 | venerdì 08/11/2002 |
Lemma 2 per il teorema di gerarchia temporale. Corollario |
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. |