Università Roma Tre

1. Cenni di 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.

2. Teoria degli algoritmi e dell'ottimizzazione: richiami sugli algoritmi e sulla programmazione strutturata; complessità computazionale di un algoritmo, classi di complessità per problemi, le classi P, NP, NP-completo, 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, algoritmi per la generazione dell'insieme delle parti di un insieme finito, calcolo delle permutazioni e delle combinazioni degli elementi di un insieme, calcolo del coefficiente binomiale; il problema dei "quadrati latini" e il gioco del Sudoku; un algoritmo ricorsivo per la soluzione del gioco.

3. Problemi di ottimizzazione su grafi e reti di flusso: visita di grafi, verifica di proprietà fondamentali di un grafo: connessione, connessione forte, presenza di cicli. Ordinamento topologico di un grafo orientato aciclico.

Il problema della costruzione di un albero ricoprente di peso minimo (minimum spanning tree), algoritmo di Kruskal, algoritmo di Prim, formulazione del problema in termini di Programmazione Lineare Intera.

Ricerca di cammini minimi su un grafo pesato; cammino minimo con sorgente singola, algoritmo di Dijkstra, algoritmo di Bellman-Ford; cammino minimo tra tutte le coppie di vertici del grafo, algoritmi di programmazione dinamica, algoritmo di Floyd-Warshall, calcolo della chiusura transitiva di un grafo.

Reti di flusso e calcolo del flusso massimo su una rete, Teorema del flusso massimo e taglio minimo, algoritmo di Ford-Fulkerson, algoritmo di Edmonds-Karp, algoritmi di preflusso, algoritmi "push-relabel".

Problemi di partizionamento di grafi, alberi e cammini, problemi per il partizionamento ottimo di alberi e cammini in p componenti connesse, funzioni obiettivo, tecniche algoritmiche per la soluzione di questa classe di problemi (programmazione dinamica, programmazione lineare, shifting).

Problema del matrimonio stabile (stable marriage problem), definizione del problema e del criterio di stabilità del matching, applicazioni, algoritmo di Gale e Shapley.

4. Laboratorio di programmazione per l'implementazione degli algoritmi mediante programmi in linguaggio C in ambiente GNU/Linux e con il software Mathematica.

Cormen, Leiserson, Rivest, Stein, "Introduzione agli algoritmi e strutture dati", terza edizione, McGraw-Hill, 2010