Complementi di Algoritmi e Strutture Dati (3CFU)

Programma

versione PDF

Flusso massimo [1, cap 26.1, 26.2, 26.3]
   - Reti di flusso [1, cap 26.1]
   - Algoritmo di Ford-Fulkerson [1, cap 26.2]
   - Massimo matching in grafi bipartiti [1, cap 26.3]
Richiami su complessità di problemi di ottimizzazione e algoritmi approssimati [2, cap 1]
   - Analisi di algoritmi e complessità dei problemi [2, cap 1.1]
   - Classi di complessità dei problemi di decisione [2, cap 1.2]
   - Riducibilità tra problemi [2, cap 1.3]
   - Complessità di problemi di ottimizzazione [2, cap 1.4]
   - Algoritmi approssimati [2, introduzione cap 2]
Tecniche di progettazione di algoritmi approssimati [2, cap 2]
   - Tecniche greedy (knapsack, independent set, TSP) [2, cap 2.1]
   - Algoritmi sequenziali (scheduling di jobs in macchine identiche) [2, cap 2.2 esclusi 2.2.2 e 2.2.3]
   - Local search (cut, TSP) [2, cap 2.3]
   - Algoritmi basati su programmazione lineare [2, cap 2.4]
   - Programmazione dinamica (knapsack) [2, cap 2.5]
Esempi di algoritmi approssimati [3, cap 1,2]
- Vertex Cover [3, cap 1]
- Set Cover [3, cap 2]

[1] T. Cormen, C. Leiserson, R. Rivest, C. Stein,
Introduzione agli algoritmi, seconda edizione
McGraw-Hill, 2005,
[2] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi,
Complexity And Approximation. Combinatorial Optimization Problems And Their Approximability Properties,
Springer, 1999
[3] V. Vazirani,
Approximation Algorithms,
Springer, 2003
Per il materiale didattico rivolgersi al docente

L'esame consiste in una prova orale che verterà sui Punti 1, 3 e 4 del programma.

Per poter sostenere l'esame contattare il docente:

Studio: Facoltà di Ingegneria, edificio vecchio, ingresso centrale, piano -1, porta a destra (Laboratorio di informatica)
Telefono: 0862 434471
E-mail: gianlorenzo DOT dangelo AT univaq DOT it