Obiettivi formativi

Fornire un'introduzione alla complessità strutturale con particolare attenzione alla teoria del NP-completezza e alla classificazione dei problemi in base alla loro approssimabilità

Attività formative

Il corso viene svolto in 50 ore di lezione frontale.

Programma del corso

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.