Il corso è costituito da un'introduzione alla complessità strutturale, con particolare attenzione alla teoria del NP-completezza, e da un'introduzione alla analisi di complessità dei problemi rispetto alla loro approssimabilità computazionale.
Scopo di tale introduzione è fornire agli studenti gli strumenti necessari per comprendere e affrontare la difficoltà nel risolvere alcuni problemi comuni da un punto di vista computazionale.
Il corso viene svolto in 40 ore di lezione frontale.
Il programma è diviso in lezioni. La colonna Rif. libro indica i paragrafi o i capitoli del libro di Christos H. Papadimitriou, "Computational complexity", Addison Wesley, 1994.
| N. |
Data Luogo |
N. ore | Argomento | Rif. libro | Firma |
|---|---|---|---|---|---|
| 1 |
27/09/04 Aula 'C' |
2 |
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. Richiamo del concetto di ordine di grandezza: O, Ω e Θ. Richiamo dei concetti principali inerenti all'espressioni booleane. |
Cap. 1 e cap. 4 | Roberto Posenato |
| 2 |
28/09/04 Aula 'C' |
1 | Problemi computazionali: descrizione, istanze, codifica, relazione con i linguaggi. Esempi di problemi: RAGGIUNGIBILITÀ (PATH), MASSIMO FLUSSO (MAX FLOW) e SODDISFACIBILITÀ (SAT). | Cap. 1 | Roberto Posenato |
| 3 |
29/09/04 Aula 'C' |
2 |
Modelli di calcolo Macchina di Turing (MdT): definizione, funzionamento, concetto di configurazione, produzione e di computazione. Esempio di MdT. MdT e linguaggi: differenza tra accettare e decidere un linguaggio. |
Cap. 2 | Roberto Posenato |
| 4 |
04/10/04 Aula 'C' |
2 |
Estensione della MdT: MdT a più nastri (k-MdT). Complessità in tempo La risorsa computazionale tempo. Classe di complessità TIME(). Teorema di relazione polinomiale tra le computazioni delle macchine k-MdT e MdT (idea della dimostrazione). Introduzione al modello di calcolo "Macchina ad accesso casuale" (RAM = Random Access Machine): concetti di configurazione, programma e computazione. |
Cap. 2 | Roberto Posenato |
| 5 |
05/10/04 Aula 'C' |
1 | 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. | Cap. 2 | Roberto Posenato |
| 6 |
06/10/04 Aula 'C' |
2 |
Esempio di programma RAM per calcolare il prodotto di due interi. Teorema sul costo di simulazione di una MdT mediante un programma RAM (idea della dimostrazione). Teorema sul costo di simulazione di un programma RAM mediante una MdT (solo enunciato). Tesi del calcolo sequenziale e sue conseguenze. |
Cap. 2 | Roberto Posenato |
| 7 |
11/10/04 Aula 'C' |
2 |
Teorema dell'accelerazione lineare (linear speed-up) e sue conseguenze. La classe di complessità P. Esempio di problemi della classe P: PATH. |
Cap. 2 | Roberto Posenato |
| 8 |
12/10/04 Aula 'C' |
1 | Esempio di problema della classe P: MAX FLOW. Insidie sui possibili algoritmi di risoluzione per MAX FLOW. | Cap. 1 | Roberto Posenato |
| 9 |
13/10/04 Aula 'C' |
2 |
Esempio di problema della classe P: ACCOPPIAMENTO PERFETTO (PERFECT MATCHING). Estensione della MdT: MdT non deterministica (NMdT). La risorsa tempo nelle NMdT a k-nastri. Classe di complessità NTIME(). Esempio di algoritmo non deterministico computabile da una NMdT: algoritmo per SODDISFACIBILITÀ (SAT). |
Cap. 1 e 2 | Roberto Posenato |
| 10 |
18/10/04 Aula 'C' |
2 |
Relazione tra NMdT e MdT. La classe di complessità NP. Relazione tra NP e P. Esempio di problema in NP: problema del COMMESSO VIAGGIATORE (TSP). |
Cap. 2 | Roberto Posenato |
| 11 |
19/10/04 Aula 'C' |
1 | Caratterizzazione alternativa della classe NP: verificatori polinomiali. | non presente | Roberto Posenato |
| 12 |
20/10/04 Aula 'C' |
2 |
La classe di complessità EXP. Complessità in spazio Concetto di complessità spaziale. Macchina di Turing con input e output. Classi di complessità SPACE() e NSPACE(). Teorema di compressione (solo enunciato, dimostrazione per esercizio). Classi di complessità L e NL. Esempi di problemi: PALINDROME ∈ L e PATH ∈ NL. |
In parte nel cap. 2. | Roberto Posenato |
| 13 |
25/10/04 Aula 'C' |
2 |
Teoremi di relazione tra spazio e tempo di computazione per una MdT con I/O. Relazioni tra classi di complessità Concetto di funzione propria ed esempi di funzioni. Il teorema del gap di Borodin. |
Cap. 7 | Roberto Posenato |
| 14 |
26/10/04 Aula 'C' |
1 | 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))). | Cap. 7 | Roberto Posenato |
| 15 |
27/10/04 Aula 'C' |
2 |
Concetto di Macchina di Turing Universale. L'insieme Hf. Lemma 1 per il teorema di gerarchia temporale. Lemma 2 per il teorema di gerarchia temporale. |
Cap. 7 | Roberto Posenato |
| 16 |
02/11/04 Aula 'C' |
1 |
Teorema di gerarchia in tempo: versione lasca e versione stretta. Corollario P ⊂ EXP. Teorema di gerarchia spaziale (solo enunciato). Corollario L ⊂ PSPACE. |
Cap. 7 | Roberto Posenato |
| 17 |
03/11/04 Aula 'C' |
2 |
Teorema di Savitch. Corollario SPACE(f(n))=SPACE(f(n)2).
Corollario PSPACE=NPSPACE. Riduzioni e completezza Concetto di riduzione e di riduzione logaritmica in spazio. |
Cap. 7 | Roberto Posenato |
| 18 |
08/11/04 Aula 'C' |
2 |
Esempio di riduzione: HAMILTON PATH ≤log SAT,
PATH ≤log CIRCUIT VALUE,
CIRCUIT SAT ≤log SAT. Esempio di riduzione per generalizzazione. |
Cap. 8 | Roberto Posenato |
| 19 |
09/11/04 Aula 'C' |
1 |
Proprietà delle riduzioni: transitiva e riflessiva. Concetto di completezza di un linguaggio. |
Cap. 8 | Roberto Posenato |
| 20 |
10/11/04 Aula 'C' |
0 | Lezione sospesa per protesta contro il cosidetto DDL Moratti sull'ordinamento giuridico universitario. | Roberto Posenato | |
| 20 |
15/11/04 Aula 'C' |
2 |
Concetto di chiusura rispetto alla riduzione.
Chiusura delle classi L, NL, P, NP, PSPACE e EXP. Concetto di tabella di computazione. Dimostrazione che CIRCUIT VALUE è P-completo. |
Cap. 8 | Roberto Posenato |
| 21 |
16/11/04 Aula 'C' |
1 | Dimostrazione alternativa del teorema di Cook: CIRCUIT SAT è NP-completo. | Cap. 9 | Roberto Posenato |
| 22 |
17/11/04 Aula 'C' |
2 |
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 (INDEPENDENT SET). |
Cap. 9 | Roberto Posenato |
| 23 |
22/11/04 Aula 'C' |
2 | Problemi collegati: CRICCA (CLIQUE) e RICOPRIMENTO DI VERTICI (VERTEX COVER). Cenni sulla completezza dei problemi: MASSIMO TAGLIO, K-COLORABILITÀ, CIRCUITO HAMILTONIANO, COMMESSO VIAGGIATORE, ACCOPPIAMENTO TRIDIMENSIONALE. | Cap. 9 | Roberto Posenato |
| 24 |
23/11/04 Aula 'C' |
1 | Cenni sulla completezza della PROGRAMMAZIONE LINEARE INTERA, ZAINO e RIEMPIMENTO DEI CESTINI (BIN PACKING). Concetto di algoritmo pseudo polinomiale. Problemi fortemente NP-completi. Altri problemi NP-completi secondo la classificazione di Garey e Johnson. | Cap. 13 | Roberto Posenato |
| 25 |
24/11/04 Aula 'C' |
2 |
Algoritmi di approssimazione e classi di complessità
approssimate Concetto di soluzione approssimata e di algoritmo approssimante. Esempi. Concetto di classificazione dei problemi in base alla loro approssimabilità computazionale. Principali classi di approssimazione computazionale: PTAS, APX, NPO. Esempi di problemi approssimabili e non approssimabili. |
Cap. 13 | Roberto Posenato |