Informatica Teorica

Corso di Laurea in Ingegneria Informatica (magistrale)

 2010-2011, 6  crediti


Prof.  Alberto Marchetti Spaccamela



PROGRAMMA

PARTE I -  Algoritmi polinomiali
1. Introduzione al corso
2. Il problema matching  (accoppiamento) in grafi
3. Matching in grafi  bipartiti: cammini aumentanti, algoritmo di Edmonds e Karp
4.  Matching in grafi generali.
5. Il problema del massimo flusso: formaulazione primale duale, algoritmo di Ford e Fulkerson

Materiale didattico
Bipartite Matching, Ford and Fulkerson algorithm and Edmonds-Karp algorithm
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill.

Matching in General Graphs
by L. Lovasz, M. D. Plummer, Matching Theory, North-Holland Mathematics Studies 121

P. Sankoski: lucidi delle lezioni,   Introduzione, Matching, Flow, Esercizi


PARTE II - Algoritmi di approssimazione
1. Complessità di problemi di ottimizzazione: le classi P,  NP,  PSPACE; problemi completi, riduzioni fra problemi
2. Vari tipi di algoritmi di approssimazione: algoritmi approssimati, PTAS,  FPTAS e relativi esempi.
3. Classi di approssimabilità.
4. Primi risultati di non approssimabilità.
5. Tecniche fondamentali per algoritmi di approssimazione: algoritmi greedy, algoritmi sequenziali.
6. Programmazione dinamica e tecniche per schemi di approssimazione polinomiale e completamente polinomiale.
7. Tecniche basate su programmazione lineare e tecnica primale-duale;  max-flow, min cut theorem;  Vertex-cover;  analisi algoritmo greedy per Set-cover.
8. Problemi di progetto di reti:  Facility location. Steiner trees and Steiner forest.
9. Rounding probabilistico: rilassamento di programmazione lineare e rounding.  Set cover, Max Sat.
10. Algoritmi approssimati per problemi particolari: bin packing, scheduling, TSP, vertex cover, colorazione di grafi, Knapsack, max satisfiebility, set cover.

Materiale didattico
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti Spaccamela, M. Protasi, Complexity and Approximation, Springer, 1998

Il programma prevede i seguenti capitoli (accessibili on-line, per gentile concessione dell'editore):

    * Chapter 2: Design Techniques for Approximation Algorithms
    * Chapter 3: Approximation Classes
    * Chapter 4: Input-Dependent and Asymptotic Approximation
    * Chapter 5: Approximation through Randomization
    * References

A. Marchetti-Spaccamela: lucidi delle lezioni Introduzione agli algoritmi approssimati
S. Leonardi: lucidi delle lezioni, LP-approx, Facility locations, Steiner tree , Randomized rounding, Esercizi-net-design, Esercizi-randrounding
L.Becchetti: Esercizi-partition  


PARTE III - Teoria dei giochi
1. Approccio algorimico alla teoria dei giochi; giochi in forma normale. Strategie dominanti.
2. Equilibri di Nash puri e misti. Esistenza e calcolo degli equilibri
4. Efficienza degli equilibri e prezzo dell'anarchia
3. Esempi: dilemma prigioniero, chicken game, codnivisione della banda. 

Materiale didattico
V.Bonifaci: dispensa didattica1 ,  dispensa didattica2