IN440 - Ottimizzazione Combinatoria

Cenni sulla teoria dei grafi: grafo, grafo orientato, albero, albero libero e con radice, connessione, connessione forte, aciclicità; isomorfismi tra grafi, planarità, Teorema di Kuratowski, formula di Eulero; colorazione di grafi, cammini euleriani, circuiti hamiltoniani.
Richiami sulla teoria degli algoritmi e sulla complessità computazionale: classi di complessità, la classe dei problemi NP, NP-completi, NP-hard. Problemi di decisione, di ricerca, di enumerazione e di ottimizzazione; problemi di programmazione non lineare, di programmazione convessa, di programmazione lineare e di programmazione lineare intera; problemi di ottimizzazione combinatoria. Richiami sugli elementi di calcolo combinatorio.
Problemi di ottimizzazione su grafi: visita di grafi, verifica di proprietà fondamentali, connessione, presenza di cicli, componenti fortemente connesse, ordinamento topologico di un grafo. Albero ricoprente di costo minimo (algoritmi di Kruskal e di Prim). Cammini di costo minimo (algoritmi di Dijkstra e di Bellman-Ford, tecnica della programmazione dinamica, algoritmo di Floyd-Warshall, calcolo della chiusura transitiva di un grafo). Reti di flusso e calcolo del massimo flusso su una rete, teorema del flusso massimo e del taglio minimo, algoritmo di Ford-Fulkerson, algoritmo di Edmonds-Karp, algoritmi di preflusso, algoritmi "push-relabel".
Problemi di partizionamento di grafi, alberi e cammini in componenti connesse, funzioni obiettivo e tecniche algoritmiche.
Problema del matrimonio stabile, generalizzazioni e applicazioni del problema, algoritmo di Gale e Shapley.
Codici di Huffman.
Laboratorio di programmazione per l'implementazione degli algoritmi in linguaggio Python e con l'ausilio del software Mathematica.

Competenze di teoria degli algoritmi e programmazione di base (IN110 - Algoritmi e strutture dati)

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, "Introduzione agli algoritmi", McGraw–Hill (Quarta edizione)

Dispense e altro materiale didattico fornito dal docente e reso disponibile sul sito web del corso (http://www.mat.uniroma3.it/users/liverani/IN440) e sulla piattaforma Microsoft Teams

C. H. Papadimitriou, K. Steiglitz, "Combinatorial Optimization. Algorithms and Complexity". Dover Publications, (1998).
R. J. Trudeau, "Introduction to Graph Theory". Dover Publications, (1993).
R. Diestel, "Graph Theory". Springer, (2000).

Il corso si svolge in presenza in modalità tradizionale in aula e nel laboratorio informatico.

Si suggerisce di frequentare le lezioni in aula (due volte a settimana) e nel laboratorio informatico (una volta a settimana).

L’esame orale, in cui saranno discussi alcuni degli algoritmi trattati nel corso è preceduto dalla presentazione e dalla discussione di una tesina scritta, su un argomento assegnato dal docente, in cui è richiesto, tra l’altro, di implementare in linguaggio Python gli algoritmi presenti nel materiale fornito dal docente per la preparazione della tesina stessa.

Cenni sulla teoria dei grafi: grafo, grafo orientato, albero, albero libero e con radice, connessione, connessione forte, aciclicità; isomorfismi tra grafi, planarità, Teorema di Kuratowski, formula di Eulero; colorazione di grafi, cammini euleriani, circuiti hamiltoniani.
Richiami sulla teoria degli algoritmi e sulla complessità computazionale: classi di complessità, la classe dei problemi NP, NP-completi, NP-hard. Problemi di decisione, di ricerca, di enumerazione e di ottimizzazione; problemi di programmazione non lineare, di programmazione convessa, di programmazione lineare e di programmazione lineare intera; problemi di ottimizzazione combinatoria. Richiami sugli elementi di calcolo combinatorio.
Problemi di ottimizzazione su grafi: visita di grafi, verifica di proprietà fondamentali, connessione, presenza di cicli, componenti fortemente connesse, ordinamento topologico di un grafo. Albero ricoprente di costo minimo (algoritmi di Kruskal e di Prim). Cammini di costo minimo (algoritmi di Dijkstra e di Bellman-Ford, tecnica della programmazione dinamica, algoritmo di Floyd-Warshall, calcolo della chiusura transitiva di un grafo). Reti di flusso e calcolo del massimo flusso su una rete, teorema del flusso massimo e del taglio minimo, algoritmo di Ford-Fulkerson, algoritmo di Edmonds-Karp, algoritmi di preflusso, algoritmi "push-relabel".
Problemi di partizionamento di grafi, alberi e cammini in componenti connesse, funzioni obiettivo e tecniche algoritmiche.
Problema del matrimonio stabile, generalizzazioni e applicazioni del problema, algoritmo di Gale e Shapley.
Codici di Huffman.
Laboratorio di programmazione per l'implementazione degli algoritmi in linguaggio Python e con l'ausilio del software Mathematica.

Competenze di teoria degli algoritmi e programmazione di base (IN110 - Algoritmi e strutture dati)

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, "Introduzione agli algoritmi", McGraw–Hill (Quarta edizione)

Dispense e altro materiale didattico fornito dal docente e reso disponibile sul sito web del corso (http://www.mat.uniroma3.it/users/liverani/IN440) e sulla piattaforma Microsoft Teams

C. H. Papadimitriou, K. Steiglitz, "Combinatorial Optimization. Algorithms and Complexity". Dover Publications, (1998).
R. J. Trudeau, "Introduction to Graph Theory". Dover Publications, (1993).
R. Diestel, "Graph Theory". Springer, (2000).

Il corso si svolge in presenza in modalità tradizionale in aula e nel laboratorio informatico.

Si suggerisce di frequentare le lezioni in aula (due volte a settimana) e nel laboratorio informatico (una volta a settimana).

L’esame orale, in cui saranno discussi alcuni degli algoritmi trattati nel corso è preceduto dalla presentazione e dalla discussione di una tesina scritta, su un argomento assegnato dal docente, in cui è richiesto, tra l’altro, di implementare in linguaggio Python gli algoritmi presenti nel materiale fornito dal docente per la preparazione della tesina stessa.

Cenni sulla teoria dei grafi: grafo, grafo orientato, albero, albero libero e con radice, connessione, connessione forte, aciclicità; isomorfismi tra grafi, planarità, Teorema di Kuratowski, formula di Eulero; colorazione di grafi, cammini euleriani, circuiti hamiltoniani.
Richiami sulla teoria degli algoritmi e sulla complessità computazionale: classi di complessità, la classe dei problemi NP, NP-completi, NP-hard. Problemi di decisione, di ricerca, di enumerazione e di ottimizzazione; problemi di programmazione non lineare, di programmazione convessa, di programmazione lineare e di programmazione lineare intera; problemi di ottimizzazione combinatoria. Richiami sugli elementi di calcolo combinatorio.
Problemi di ottimizzazione su grafi: visita di grafi, verifica di proprietà fondamentali, connessione, presenza di cicli, componenti fortemente connesse, ordinamento topologico di un grafo. Albero ricoprente di costo minimo (algoritmi di Kruskal e di Prim). Cammini di costo minimo (algoritmi di Dijkstra e di Bellman-Ford, tecnica della programmazione dinamica, algoritmo di Floyd-Warshall, calcolo della chiusura transitiva di un grafo). Reti di flusso e calcolo del massimo flusso su una rete, teorema del flusso massimo e del taglio minimo, algoritmo di Ford-Fulkerson, algoritmo di Edmonds-Karp, algoritmi di preflusso, algoritmi "push-relabel".
Problemi di partizionamento di grafi, alberi e cammini in componenti connesse, funzioni obiettivo e tecniche algoritmiche.
Problema del matrimonio stabile, generalizzazioni e applicazioni del problema, algoritmo di Gale e Shapley.
Codici di Huffman.
Laboratorio di programmazione per l'implementazione degli algoritmi in linguaggio Python e con l'ausilio del software Mathematica.

Competenze di teoria degli algoritmi e programmazione di base (IN110 - Algoritmi e strutture dati)

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, "Introduzione agli algoritmi", McGraw–Hill (Quarta edizione)

Dispense e altro materiale didattico fornito dal docente e reso disponibile sul sito web del corso (http://www.mat.uniroma3.it/users/liverani/IN440) e sulla piattaforma Microsoft Teams

C. H. Papadimitriou, K. Steiglitz, "Combinatorial Optimization. Algorithms and Complexity". Dover Publications, (1998).
R. J. Trudeau, "Introduction to Graph Theory". Dover Publications, (1993).
R. Diestel, "Graph Theory". Springer, (2000).

Il corso si svolge in presenza in modalità tradizionale in aula e nel laboratorio informatico.

Si suggerisce di frequentare le lezioni in aula (due volte a settimana) e nel laboratorio informatico (una volta a settimana).

L’esame orale, in cui saranno discussi alcuni degli algoritmi trattati nel corso è preceduto dalla presentazione e dalla discussione di una tesina scritta, su un argomento assegnato dal docente, in cui è richiesto, tra l’altro, di implementare in linguaggio Python gli algoritmi presenti nel materiale fornito dal docente per la preparazione della tesina stessa.