Università Roma Tre

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.

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