Conoscenza dei concetti di base della Matematica.

l corso ha l'obiettivo di fornire una panoramica dei concetti fondamentali dell’Ottimizzazione Combinatoria e di alcuni degli algoritmi principali per la soluzione di problemi combinatori.

Conoscenze e comprensione: Risultati fondamentali e avanzati di Ottimizzazione Combinatoria e problematiche di ricerca classiche e attuali.

Capacità di applicare conoscenze e comprensione: * essere in grado di produrre dimostrazioni rigorose e descrizioni formali di algoritmi per problemi combinatori; * essere in grado di formalizzare e risolvere problemi di moderata difficoltà nell’ambito della Ottimizzazione Combinatoria. * essere capaci di leggere e comprendere, in modo autonomo, testi avanzati e articoli di ricerca nell’ambito della Ottimizzazione Combinatoria.

Autonomia di giudizio: L’esposizione dei contenuti e delle argomentazioni sarà svolta in modo da migliorare la capacità dello studente di identificare gli elementi rilevanti in situazioni e problemi anche in contesti non matematici, nonché di riconoscere ragionamenti logici erronei.

Abilità comunicative: La presentazione degli argomenti sarà svolta in modo da consentire l’acquisizione di una buona capacità di comunicare in modo chiaro e privo di ambiguità problemi, idee e soluzioni riguardanti la Ottimizzazione Combinatoria, ad un pubblico specializzato o generico.

Capacità di apprendimento: Sarà sollecitato l’approfondimento di argomenti, correlati con l’insegnamento, al fine di stimolare lo studio autonomo su testi avanzati e su articoli di ricerca.

Lezioni frontali ed esercitazioni in aula.

Esame orale. La prova verifica l’abilità di esporre in modo chiaro e rigoroso alcuni contenuti del corso.

Gli studenti dovranno prenotarsi all’esame, utilizzando esclusivamente le modalità on-line previste dal sistema VOL.

Problemi e algoritmi dell’Ottimizzazione Combinatoria: introduzione e richiami di metodi e modelli della Ricerca Operativa.

Il paradigma algoritmico Primale-Duale: descrizione; applicazione al problema di cammino minimo; applicazione al problema di massimo flusso. Algoritmi Primali-Duali per massimo flusso e cammino minimo: Ford-Fulkerson e Dijkstra. Algoritmi Primali-Duali per flusso a costo minimo.

Algoritmi e complessità computazionale: algoritmi polinomiali; non-polinomialità del metodo del simplesso; il metodo dell’ellissoide per la Programmazione Lineare; algoritmi efficienti per il problema di massimo flusso.

Il problema del Matching: matching bipartito e sua correlazione con il problema di flusso su reti; matching non-bipartito e blossoms; matching pesato (cenni); il metodo ungherese per il problema di assegnamento; matching pesato non-bipartito (cenni).

Matroidi: alberi ricoprenti; algoritmo Greedy.

Algoritmi di approssimazione ed euristiche: il problema di copertura con nodi come esempio; algoritmi di approssimazione per il problema del commesso viaggiatore.

C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization – Algorithms and Complexity, Dover Publications, Mineola, N.Y. 1998