Dettagli sull'Insegnamento per l'A.A. 2018/2019

Prerequisiti

Algebra elementare delle matrici

Obiettivi

Formulare problemi di programmazione lineare intera, conoscere i principali problemi di ottimizzazione combinatoria, distinguerli in base alla loro complessità computazionale, conoscere i principali metodi di soluzione

Sillabo

• Grafi. Grafi finiti, copertura con vertici e con archi, grado. Grafi riflessivi e non, loopless, simmetrici, transitivi. Grafi regolari: esempi. Isomorfismo: esempi. Clique e insieme stabile. Grafo complemento. Passeggiate, cammini, circuiti e cicli. Grafo Euleriano e Hamiltoniano. Come rendere un grafo Euleriano. Teorema di Eulero (enunciato). Cammini e cicli Hamiltoniani. Connessione. Alberi e foreste. Grafi bipartiti e loro caratterizzazione. Colorazione di un grafo. Applicazioni.
• Problemi di ottimizzazione combinatoria (OC) e formulazioni come PL 01. Problemi di insieme trasversale, stabile, dominante in un grafo. Problemi di edge-cover e matching (perfetto). Formulazioni come PL 01. Esempi di applicazioni. Problema del cammino minimo: formulazione come PL 01 e suoi limiti. Problema dell'albero ricoprente. Forma generale di un problema di OC. Relazioni con problemi di programmazione lineare. Altri esempi di problemi di OC formulati come PL 01 (problema dell'isomorfismo di due grafi, PLA folding, taglio massimo etc.).
• Complessità computazionale. Complessità di un algoritmo e di un problema, esempi. Macchina di Turing. La classe P. Riduzioni polinomiali. La classe NP. Problema di soddisfacibilità. Teorema di Cook (enunciato), classe NP-complete. Esempi di riduzione: clique.
• Matrici totalmente unimodulari. Il metodo del simplesso in breve. problemi di PL in forma generale e standard, riduzioni; basi, soluzioni (ammissibili) di base. Matrici unimodulari e totalmente unimodulari. Condizione di interezza delle soluzioni di base. Condizioni necessarie o sufficienti di totale unimodularità.
• Programmazione dinamica. Da un ordine parziale a uno totale. Ordine topologico in un grafo, grafi diretti aciclici (DAG). Condizioni di Bellman. Formula di ricorrenza per il calcolo del miglior cammino in un DAG. Esempi di applicazione (copertura di un requisito al costo minimo, distanza di Levenshtein, Knapsack 01 etc.).
• Nozioni fondamentali di Teoria della Dualità nella PL. Poliedri convessi: forma algebrica e geometrica. Proiezione di un poliedro: Teorema di Fourier-Veronese's (enunciato). Sistemi compatibili di disequazioni lineari: metodo di eliminazione di Fourier-Motzkin, applicazione numerica e casi particolari. Dal Teorema di Fourier-Veronese alla Dualità nella PL. Teoremi dell'Alternativa: Teorema di Gale.
• Teoria del Matching. Numero di matching in un grafo e sue relazioni con numero di edge-cover, trasversale e di stabilità. Teoremi di Gallai. Relazioni primale-duale: Teoremi di Koenig del matching e dell'edge-cover. Matching bipartito e unimodularità totale. Percorsi aumentanti, caratterizzazione di un matching massimo. Matching bipartito: algoritmi combinatorici per il caso pesato e non pesato. Matching non bipartito: formulazione di Edmonds. Matrici bi-stocastiche: introduzione e definizioni. Quadrati magici aritmetici, loro costruzione. Quadrati semi-magici e matrici bi-stocastiche: Algoritmo di Sinkhorn. Caratterizzazione di matrici bi-stocastiche estremali: matching bipartito perfetto e matrici di permutazione.
• Matroidi e Algoritmo Greedy. Introduzione, motivazione, esempi. Insiemi massimi e massimali. Come ingannare l'Algoritmo Greedy. Sublclusione, proprietà di scambio, matroide. Caratterizzazione di un matroide: Teorema di Rado. Esempi di matroide (uniforme, grafico, vettoriale). Rappresentazione di matroidi: matroide grafico come matroide vettoriale.
• Algoritmi approssimanti. Introduzione agli algoritmi deterministici ad approssimazione garantita. Rapporto di approssimazione, schemi polinomiali di approssimazione. Primo esempio: TSP metrico. Algoritmo doppio-albero. Algoritmo di Christofides. Secondo esempio: Knapsack 01. Un algoritmo di programmazione dinamica su base utilità. Complessità. Scalatura dei coefficienti: schema di approssimazione completamente polinomiale.
• Algoritmi di enumerazione implicita. Ricerca per separazione. Albero di enumerazione per problemi di OC. Relazioni fra PL e PLI. Calcolo di limitazioni superiori o inferiori tramite PL e loro uso in un metodo di branch & bound. Esempio 1: 01-knapsack. Calcolo della limitazione superiore via PL, branching su variabile frazionaria. Limitazioni combinatorie. Esempio 2: TSP.

Descrittori di Dublino

Alla fine del corso, lo studente dovrebbe

Testi di riferimento

• Christos H. Papadimitriou, Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity , Prentice Hall (Dover reprint). 1982.    

Modalità d'esame

prova scritta (eventualmente suddivisa in prove parziali), prova orale

Aggiornamenti alla pagina del corso

• A.A. 2016/2017
• A.A. 2017/2018
• A.A. 2018/2019
• A.A. 2019/2020