Codice insegnamento

4S02709

Docente

Ferdinando Cicalese

Crediti

6

Lingua di erogazione

Italiano

Settore Scientifico Disciplinare (SSD)

ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI

Periodo

II semestre dal 2 mar 2020 al 12 giu 2020.

Orario Lezioni Moodle Seminari 0

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

Obiettivi formativi

Il corso si propone di fornire le basi teoriche della complessità computazionale con particolare attenzione alla teoria della NP-completezza; nozioni di algoritmi di approssimazione ed approcci di base per l'analisi di algoritmi di approssimazione per problemi "difficili".

Al termine del corso lo studente dovrà dimostrare di avere acquisito le conoscenze necessarie per definire formalmente un problema computazionale, anche in un contesto di ricerca, e procedere all'analisi della quantità di risorse necessarie alla sua risoluzione.

Questa conoscenze consentiranno allo studente di avvalersi di riduzioni quali tecniche standard della teoria della Complessità per analizzare la natura dei problemi computazionali e valutare quali possano essere approcci alternativi alla sua risoluzione (approssimazione, parametrizzazione) in assenza di soluzioni in assoluto efficienti.

Al termine del corso lo studente sarà in grado di: i) classificare problemi computazionalmente intrattabili; ii) comprendere e verificare la correttezza di una prova formale; ii) leggere e comprendere un articolo scientifico in cui venga proposto un nuovo algoritmo con associata analisi della complessità.

Programma

Concetto di modello di calcolo, risorsa computazionale, algoritmo efficiente e problema trattabile.

Relazioni tra problemi computazionali. Riduzioni polinomiale tra problemi computazionali.
Le classi P, NP e co-NP. Concetto di completezza. Dimostrazioni di NP-completezza: il teorema di Cook; dimostrazioni mediante riduzioni polinomiali. Differenza tra Problemi di Ricerca e Problemi di Decisione. Self-reducibility dei problemi NP-completi ed esistenza di problemi non self-reducible. Richiami di teoria della computabilità: macchine di Turing e diagonalizzazione. Teoremi di Gerarchia rispetto al tempo. Esistenza di problemi intermedi nell'ipotesi P diverso da NP

Complessità di spazio: modelli e differenze fondamentali tra misure di tempo e spazio. Le classi NL ed L e relazioni con la classe P. La centralità del problema Reachability. Completezza per le classi di complessità di spazio. Riduzioni log-space. NL-completezza di reachability. Non-determinismo e complessità di spazio. Il teorema di Savitch. Il teorema di Immerman-Szlepcsenyi. Le classe PSPACE e NPSPACE ed esempi e riduzioni per dimostrare PSPACE-completezza.

Introduzione all'approssimazione. Problemi di Ottimizzazione. Esempi di algoritmi di approssimazione. Classificazione dei problemi rispetto alla possibilità di fornire approssimazioni più o meno buone. Classi di problemi: APX, PTAS, FPTAS. Nozioni di inapprossimabilita: la tecnica del gap per provare inapprossimabilità, e cenni di riduzioni che preservano l'approssimabilità. Esempi di uso della randomizzazione per la risoluzione di problemi computazionale difficili.

Prerequisiti raccomandati
-------------------------
Per seguire con profitto l'insegnamento è raccomandato che lo studente abbia già acquisito competenze in:
1. Comuni strutture dati astratte come lista, stack, code, alberi, heap.
2. Rappresentazione di grafi e principali algoritmi sui grafi:
2.1 Visita di grafi: BFS, DFS.
2.2 Ordinamento topologico. Componenti connesse.
2.3 Alberi di copertura di costo minimo. Algoritmi di Kruskal e Prim.
2.4 Cammini minimi da singola sorgente: Algoritmi di Dijkstra e Bellman-Ford.
2.5 Cammini minimi per tutte le coppie: Algoritmi di Floyd-Warshall e Johnson.
2.6 Flusso massimo. Algoritmo di Ford-Fulkerson.
Un testo consigliato per rivedere tali concetti è "Introduction to Algorithms" di T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stein (3 ed.).

Modalità d'esame

L'esame è volto ad accertare che gli studenti abbiano sufficiente padronanza delle classi di complessità fondamentali e degli strumenti per l'analisi e classificazione della complessità computazionale di un problema.

L'esame consiste in una prova scritta con quesiti aperti. Tipicamente la prova include alcuni esercizi obbligatori ed altri esercizi a scelta. Gli esercizi obbligatori verificano le capacità di sintesi: riproduzione di (semplici varianti di) relazioni e o algoritmi visti a lezione per problemi classici; gli esercizi a scelta verificano le capacità analitiche dello studente di modellare un nuovo problema e analizzarne la complessità computazionale mediante l'uso di riduzioni.

Il voto ottenuto concorre per il 50% a determinare il voto finale per l'esame di Algoritmi, che è dato dalla media aritmetica dei voti conseguiti per il modulo Algoritmi e per il modulo Complessità.