Ottimizzazione Combinatoria

Antonio Frangioni      Tel. 0502212789

Programmazione Matematica

Fornire gli strumenti per realizzare algoritmi di ottimizzazne combinatoria.

Attraverso la presentazione e l'analisi di vari esempi, il corso si propone di fornire allo/a studente/essa gli strumenti per concepire e realizzare algoritmi di ottimizzazione.

The course is intended to provide the instruments to onceive and realize algorithms for solving combinatorialoptimization problems. This is mainly done by presenting and analyzing various examples.

1. Introduzione (2 ore)
   • Problemi e loro rappresentazione (problemi di ottimo, problemi decisionali, rappresentazione dei problemi, spazio degli stati, grafi AND/OR)
   • Algoritmi (richiami di teoria della complessità computazionale, algoritmi esatti ed algoritmi approssimati, misure di errore e schemi di approssimazione)

2. Strutture di dati (3 ore)
   • Rappresentazione di insiemi disgiunti (algoritmi UNION-FIND)
   • Code di priorità (liste, d-heap, heap sinistri)

3. Algoritmi Greedy (6 ore)
   • Algoritmo Greedy (struttura generale e sua complessita)
   • Matroidi (definizione e principali proprietà)
   • Albero di copertura minima (algoritmi di Kruskal e di Prim)
   • Problemi di assegnamento su grafi bipartiti convessi
   • Problema di ordinamento e problema dello zaino (analisi dell'errore relativo ed esempi di schemi di approssimazione polinomiali)

4. Algoritmi di ricerca locale (8 ore)
   • Ricerca locale (intorni, struttura generale del metodo)
   • "Tabu search" e "Simulated annealing"
   • Problema del Commesso Viaggiatore
   • Problemi di localizzazione
   • Flusso massimo

5. Ipergrafi orientati e loro applicazioni (6 ore)
   • Concetti di base ed esempi di applicazioni
   • Cammini, tagli, alberi
   • Problemi di ottimizzazione su ipergrafi
   • Uso degli ipergrafi per modellizzare e risolvere problemi di soddisfattibilità
   • Applicazioni alle basi di dati relazionali

(Le ore indicate includono le esercitazioni)