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

Prerequisiti

Elementi di algebra lineare, operazioni elementari con matrici e vettori di dimensione finita.

Obiettivi

Comprendere il ruolo di modelli di ottimizzazione combinatoria in applicazioni tecnico-scientifiche. Formulare e risolvere problemi di ottimizzazione combinatoria come ottimizzazione lineare 01. Familiarizzare con alcuni algoritmi fondamentali per problemi particolari.

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à.
• 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.
• Algoritmi approssimanti. Introduzione agli algoritmi deterministici ad approssimazione garantita. Rapporto di approssimazione, schemi polinomiali di approssimazione. TSP metrico: Algoritmo doppio-albero. Algoritmo di Christofides. Knapsack 01: Un algoritmo di programmazione dinamica su base utilità. Complessità. Schemi 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.
• Modelli decisionali e data analysis: singolo-multi decisore, singolo-multi obiettivo. Modelli descrittivi, predittivi e prescrittivi, esempi. Regressione lineare e non lineare come programmazione lineare, metodo dei minimi quadrati. Problemi di classificazione (p-mediana, p-centro). Separazione e Sovrapposizione.

Modalità d'esame

Prova scritta (eventualmente suddivisibile in due prove parziali) + prova orale

Note

• Ricevimento studenti: giovedì dalle 14:00 alle 15:30

Aggiornamenti alla pagina del corso

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