L'insegnamento è organizzato come segue:

Obiettivi formativi

Modulo: ALGORITMI
-------
Acquisire un'adeguata conoscenza dei principali paradigmi avanzati di algoritmi per problemi di ottimizzazione combinatorica con particolare attenzione per i paradigmi che permettono di determinare soluzione approssimante per problemi di ottimizzazione combinatoria difficili.


Modulo: COMPLESSITÀ
-------
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

Modulo: ALGORITMI
-------
Richiamo dei principali concetti inerenti ai problemi computazionali: descrizione, istanze, codifica, modelli precisi e modelli approssimati. Problemi computazioni di ottimizzazione. Esempi di problemi computazionali.
Richiamo dei principali concetti inerenti agli algoritmi: risorse computazionali, codifica dell'input, dimensione dell'input, definizione di tempo computazionale. Analisi caso peggiore e caso medio. Tempo di calcolo e ordini di grandezza: possibili insidie.
Tempi di calcolo e miglioramenti hardware: relazioni principali. Algoritmi efficienti e problemi trattabili.

Paradigma divide et impera
--------------------------
Richiamo struttura. Analisi complessità. Esempi di applicazione: prodotto tra due numeri, Prodotto fra due matrici.
Introduzione al problema della mediana e, generalizzazione, al problema della selezione. Risoluzione del problema della selezione.

Paradigma greedy
----------------
Richiamo struttura. Esempio di applicazione per il problema dell'albero minimo di ricoprimento. Richiamo sulla struttura dati per insiemi disgiunti. Esempio di applicazione per il problema dei cammini minimi da sorgente singola (algoritmo di Dijkstra).
Introduzione ai matroidi: definizione, proprietà fondamentali. Problema del Massimo di un matroide pesato. Dimostrazione che la tecnica greedy determina sempre la soluzione ottima per il problema del Massimo di un matroide pesato.
Valutazione due soluzioni all'esercizio di ricerca elemento in una matrice ordinata.
Uso dei matroidi per la risoluzione del problema di programmazione di task unitari su singolo processore. Limiti della rappresentazione con i matroidi. Esempi di problemi risolvibili con tecnica greedy che non sono rappresentabili da matrodidi.
Approfondimento: Codifica di Huffman.

Tecnica backtracking
--------------------
Introduzione. Schema generale. Aspetti cruciali.
Applicazione della tecnica al problema dello zaino con ripetizione. Analisi correttezza e complessità.
Introduzione uso della tecnica al problema dell'inviluppo convesso: algoritmo di Graham. Uso della tecnica backtracking al problema del string matching: algoritmo di Knuth, Morris & Pratt.

Tecnica branch & bound
----------------------
Introduzione. Schema generale. Aspetti cruciali.
Scelta ordine di visita dei figli: strategia hill climbing. Tecnica come nuova tecnica ricerca in un albero: strategia best-first.
Applicazione della tecnica al problema dell'assegnamento e al problema dello zaino.
Applicazione della tecnica al problema del commesso viaggiatore come esempio di funzione lower bound non banale.

Paradigma programmazione dinamica
---------------------------------
Introduzione. Schema generale. Aspetti cruciali. Applicazione della tecnica al problema della massima sottosequenza crescente. Applicazione della tecnica al problema del string matching approssimato e al problema dello zaino.
Analisi di esempi di applicazione. Pattern ricorrenti per la determinazione di sottoproblemi.
Tecnica memoization (annotazione)
Introduzione e analisi vantaggi svantaggi.

Algoritmi probabilistici
------------------------
Definizione. Algoritmi probabilistici numerici, algoritmi di Monte Carlo e algoritmi di Las Vegas. Esempi di problemi risolti con tali algoritmi: Buffon's needle, Pattern Matching e Universal hashing.


Tecnica ricerca locale
----------------------
Introduzione e studio caso applicazione al problema dell'albero minimo di ricoprimento. Risoluzione del problema dell'ordinamento mediante tecnica di ricerca locale: ordinamento per inserimento e ShellSort.
Tecniche avanzate di ricerca locale: Simulated annealing e Tabù search.


Algoritmi di approssimazione
----------------------------
Classi NPO e PO. Errore relatio e indice di performance. Algorimo r-approssimante. Problema r-approssimabile.
Studio dell'approssimabilità del problema Min Vertex Cover: dall'algoritmo greedy all'algoritmo pseudo-casuale.


Modulo: COMPLESSITÀ
-------
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

Bibliografia

Modalità d'esame

Modulo: ALGORITMI
-------
Prova scritta, parte della prova complessiva del corso qualifying Algoritmi (altro modulo: Complessità).


Modulo: COMPLESSITÀ
-------
Esame scritto, domande a risposta aperta.