Acquisire competenze sulle principali tecniche di risoluzione per problemi di ottimizzazione combinatoria; approfondire le competenze sulla teoria dei grafi; acquisire competenze tecniche avanzate per la progettazione, l'analisi e l'implementazione al calcolatore di algoritmi per la risoluzione di problemi di ottimizzazione su grafi, alberi e reti di flusso.
Curriculum
scheda docente materiale didattico
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.
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
Programma
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.
Testi Adottati
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, "Introduzione agli algoritmi", McGraw–Hill (Terza 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
Bibliografia Di Riferimento
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).Modalità Erogazione
Il corso si svolge in presenza in modalità tradizionale in aula e nel laboratorio informatico. Le lezioni saranno registrate e rese disponibili sulla piattaforma Teams, ma si raccomanda la frequenza in presenza.Modalità Frequenza
La frequenza delle lezioni del corso è fortemente consigliata, ma non è obbligatoria.Modalità Valutazione
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. scheda docente materiale didattico
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.
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
Mutuazione: 20410626 IN440 - OTTIMIZZAZIONE COMBINATORIA in Scienze Computazionali LM-40 LIVERANI MARCO
Programma
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.
Testi Adottati
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, "Introduzione agli algoritmi", McGraw–Hill (Terza 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
Bibliografia Di Riferimento
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).Modalità Erogazione
Il corso si svolge in presenza in modalità tradizionale in aula e nel laboratorio informatico. Le lezioni saranno registrate e rese disponibili sulla piattaforma Teams, ma si raccomanda la frequenza in presenza.Modalità Frequenza
La frequenza delle lezioni del corso è fortemente consigliata, ma non è obbligatoria.Modalità Valutazione
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. scheda docente materiale didattico
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.
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
Programma
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.
Testi Adottati
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, "Introduzione agli algoritmi", McGraw–Hill (Terza 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
Bibliografia Di Riferimento
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).Modalità Erogazione
Il corso si svolge in presenza in modalità tradizionale in aula e nel laboratorio informatico. Le lezioni saranno registrate e rese disponibili sulla piattaforma Teams, ma si raccomanda la frequenza in presenza.Modalità Frequenza
La frequenza delle lezioni del corso è fortemente consigliata, ma non è obbligatoria.Modalità Valutazione
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.