Algoritmi - COMPLESSITÀ (2010/2011)

Codice insegnamento
4S02709
Docente
Margherita Zorzi
crediti
6
Settore disciplinare
ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
Lingua di erogazione
Italiano
Periodo
I semestre dal 4-ott-2010 al 31-gen-2011.

Per visualizzare la struttura dell'insegnamento a cui questo modulo appartiene, consultare * organizzazione dell'insegnamento

Orario lezioni

I semestre
Giorno Ora Tipo Luogo Note
martedì 11.30 - 13.30 lezione Aula I dal 18-ott-2010  al 31-gen-2011
giovedì 14.30 - 17.30 lezione Aula C dal 18-ott-2010  al 31-gen-2011

Obiettivi formativi

In questo corso si introducono le nozioni principali della complessità strutturale dei problemi computazionali,con particolare attenzione alle relazioni tra le principali classi di complessità e alla teoria del NP-completezza. Lo scopo è quello di fornire agli studenti gli strumenti formali necessari per analizzare la difficoltà di risoluzione dei problemi da un punto di vista computazionale.

Programma

Si riporta una versione sintetica del programma d'esame. Per il programma preciso (con indicazioni utili per gli studenti), vedere il file pdf "Diario delle Lezioni".

1)Introduzione
Concetti di modello di calcolo, risorsa computazionale, algoritmo efficiente e problema trattabile.

2) Modelli di calcolo e complessità in tempo
Macchina di Turing (MdT) deterministica ad un nastro e a k nastri
Complessità in tempo rispetto al modello Mdt.
Classe di complessità TIME(f(n)).
Teorema di relazione polinomiale tra le computazioni delle macchine k-MdT e 1-MdT
Definizione Macchina ad accesso casuale RAM
Teoremi di simulazione MdT-RAM
Tesi del calcolo sequenziale e conseguenze.
Teorema dell'accelerazione lineare (linear speed-up) e sue conseguenze.
La classe di complessità P.
Esempi di problemi della classe P.
MdT non deterministica (NMdT).
La risorsa tempo nelle NMdT a k-nastri.
Classe di complessità NTIME(f(n)).
Esempi di algoritmi non deterministico computabile da una NMdT in tempo polinomiale.
Relazione tra NMdT e MdT.
La classe di complessità NP.
Caratterizzazione alternativa della classe NP: verificatori polinomiali.
La classe di complessità EXP.

4)Complessità in spazio
Concetto di complessità spaziale.
Macchina di Turing con input e output.
Classi di complessità SPACE(f(n)) e NSPACE(f(n)).
Teorema di compressione
Classi di complessità L e NL.
Esempi di problemi in L ed NL.
Relazione tra spazio e tempo di computazione per una MdT con I/O.

5)Relazioni tra classi di complessità
Concetto di funzione propria ed esempi di funzioni.
Il metodo di raggiungibilità.
Teorema di inclusione tra classi in tempo e in spazio.
Concetto di Macchina di Turing Universale.
Lemmi per il teorema di gerarchia temporale.
Teorema di gerarchia in tempo. Corollario P ⊂ EXP.
Teorema di gerarchia in spazio. Corollario L ⊂ PSPACE.
Il teorema del Gap.
Teorema di Savitch con Corollario. Corollario PSPACE=NPSPACE.

6)Riduzioni e completezza
Concetto di riduzione e di riduzione logaritmica in spazio.
Esempi di riduzione: HAMILTON PATH ≤log SAT, PATH ≤log CIRCUIT VALUE, CIRCUIT SAT ≤log SAT.
Esempio di riduzione per generalizzazione.
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.
Concetto di tabella di computazione.
Dimostrazione che CIRCUIT VALUE è P-completo.
Teorema di Cook.
Esempi di problemi NP-completi e riduzioni.

7)Cenni sulle classi complemento: Complemento e non determinismo
Classi complemento
NP e coNP

Testi di riferimento
Autore Titolo Casa editrice Anno ISBN Note
Christos H. Papadimitriou Computational complexity Addison Wesley 1994 0201530821

Modalità d'esame

Esame scritto, domande a risposta aperta.

Materiale didattico

Documenti