Bibliografia ed altri riferimenti

Il testo di riferimento per il corso IN440 è il seguente: Cormen, Leiserson, Rivest, Stein, Introduzione agli algoritmi e strutture dati, quarta edizione, McGraw-Hill, 2023.

La maggior parte degli argomenti trattati durante le lezioni del corso sono presenti in questo libro. Per ulteriori approfondimenti si riporta di seguito un'ampia bibliografia di riferimento sui temi della teoria della complessità, degli algoritmi e dell'ottimizzazione e alcune dispense sulle lezioni del corso IN440.

Riferimenti bibliografici

Ottimizzazione combinatoria

1. Ottavio D'Antona, Introduzione alla Matematica Discreta, Apogeo, 1999.
2. Peter Gritzmann, René Brandenberg, Alla ricerca della via più breve. Un'avventura matematica, Springer, 2005.
3. Donald E. Knuth, Stable Marriage and Its Relation to Other Combinatorial Problems, American Mathematical Society, 1997.
4. Bernhard Korte, Jens Vygen, Ottimizzazione Combinatoria, Springer, 2011.
5. Christos H. Papadimitriou, Kenneth Steiglitz, Combinatorial Optimization. Algorithms and Complexity, Dover Publications, 1998.
6. Antonio Sassano, Modelli e algoritmi della Ricerca Operativa, Franco Angeli, 1999.
7. Sriram Pemmaraju, Stephen Skiena, Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Cambridge University Press, 2003.

Teoria dei grafi

1. Reinhard Diestel, Graph Theory, Springer, 2000 (versione elettronica del testo).
2. Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1999.
3. Richard J. Trudeau, Introduction to Graph Theory, Dover Publications, 1993.

Teoria degli algoritmi

1. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, Data structures and algorithms, Addison-Wesley, 1983.
2. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli algoritmi e strutture dati, Terza edizione, McGraw-Hill, 2010.
3. P. Crescenzi, G. Gambosi, R. Grossi, Strutture dati e algoritmi, Pearson - Addison Wesley, 2006 (http://www.algoritmica.org).
4. Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, Algoritmi e strutture dati, McGraw-Hill, 2004.
5. Marco Liverani, Qual è il problema? - Metodi, strategie risolutive, algoritmi, Mimesis, 2005 (http://www.quadernoaquadretti.it/...).
6. Robert E. Tarjan, Data Structures and Network Algorithms, SIAM, 1983.

Programmazione

1. A. Kelley, I. Pohl, C, didattica e programmazione, Quarta edizione, Pearson - Addison Wesley, 2004 (http://hpe.pearsoned.it/...).
2. H.M. Deitel, P.J. Deitel, C, corso completo di programmazione, Seconda edizione, Apogeo, 2004 (http://www.apogeonline.com/libri/88-503-2254-2/scheda).
3. Marco Liverani, Programmare in C, guida al linguaggio attraverso esercizi svolti e commentati, Seconda edizione, Esculapio, 2013 (http://www.editrice-esculapio.com/liverani-programmare-in-c/).

 

Dispense del corso

1. Algoritmi e complessità computazionale (aggiornamento del 23/2/2014)

Algoritmi, pseudo-codifica degli algoritmi, principi della programmazione strutturata. Problemi decidibili e indecidibili, complessità computazionale di un algoritmo, algoritmi polinomiali e super-polinomiali; notazioni O(f(n)), Ω(f(n)), Θ(f(n)). Limite inferiore alla complessità dell'algoritmo risolutivo per il problema dell'ordinamento; classi di complessità per problemi: le classi P, NP, NP-completa e NP-hard. Vedi anche gli Appunti sulla calcolabilità.

2. Insiemi ed elementi di calcolo combinatorio (aggiornamento del 2/3/2014)

Insiemi, operazioni sugli insiemi, corrispondenze e relazioni tra insiemi, cardinalità; insieme delle parti; permutazioni, disposizioni semplici e con ripetizioni, combinazioni semplici, coefficiente binomiale; il gioco del Sudoku, algoritmo ricorsivo per la soluzione del Sudoku.

3. Ottimizzazione Combinatoria con Mathematica (aggiornamento del 15/3/2014)

Introduzione all'uso del pacchetto software Mathematica; il package Combinatorica contenente una libreria di funzioni per il calcolo combinatorio e le operazioni sui grafi.

4. Elementi di Teoria dei Grafi (aggiornamento del 5/3/2014)

Grafi, grafi orientati, grafi completi, grado dei vertici di un grafo; cammini e cicli, cicli hamiltoniani, circuiti euleriani, grafi connessi e fortemente connessi; isomorfismi tra grafi, planarità, Teorema di Kuratowski; operazioni tra grafi; alberi, alberi con radice, foreste.

5. Problemi di Ottimizzazione e Programmazione Lineare (aggiornamento del 13/4/2014)

Problemi in forma decisionale, di ricerca, di enumerazione e di ottimizzazione; formulazione generale di un problema di ottimizzazione; formulazione di un problema di programmazione matematica: problemi di programmazione non lineare, di programmazione convessa, di programmazione lineare; problemi di programmazione lineare intera, il metodo del simplesso, esempi.

7. Cammini di costo minimo (aggiornamento del 29/12/2017)

Problema del cammino di costo minimo da una sorgente singola, gli algoritmi di Dijkstra e di Bellman-Ford, problema del cammino di costo minimo per tutte le coppie di vertici del grafo, tecnica di programmazione dinamica, algoritmo di Floyd-Warshall, algoritmo per il calcolo della chiusura transitiva di un grafo.

10. Partizionamento ottimo di grafi in componenti connesse (aggiornamento del 10/5/2014)

Problemi di partizionamento di grafi, problemi di p-partizionamento di grafi in componenti connesse, problemi di clustering e di equipartizione, metodi risolutivi ed algoritmi, complessità dei problemi, applicazioni ed esempi.

11. Il problema del matrimonio stabile (aggiornamento del 11/5/2014)

Definizione del problema del matrimonio stabile, esempi; generalizzazioni del problema, applicazioni; l'algoritmo risolutivo di Gale e Shapley, proprietà dell'algoritmo.

 

Slide delle lezioni

• Introduzione al corso. Presentazione del corso, orari e argomenti delle lezioni, testi, modalità di esame.
• Complessità computazionale. Problemi e algoritmi, complessità computazionale di un algoritmo, complessità computazionale di un problema, classi di complessità P, NP, NP-complete, NP-hard.
• Insiemi e calcolo combinatorio. Insiemi, insieme delle parti, permutazioni di un insieme, disposizioni, combinazioni, coefficiente binomiale, triangolo di Tartaglia, quadrati latini, il gioco del Sudoku.
• Introduzione alla teoria dei grafi. Principali definizioni e proprietà dei grafi, alberi, cammini, grafi Hamiltoniani, grafi Euleriani, clique, grafi clique-iterati, grafi multipartiti, isomorfismi tra grafi, grafi planari, colorazione di grafi.
• Algoritmi elementari su grafi. Algoritmi di visita in ampiezza e in profondità di un grafo, componenti fortemente connesse di un grafo orientato, punti di articolazione, ponti, alberi binari di ricerca.
• Ottimizzazione combinatoria e programmazione matematica. Tipi di problema, i problemi di ottimizzazione, problemi di programmazione matematica, di programmazione convessa, di programmazione lineare, cenni sul metodo del simplesso.
• Alberi ricoprenti di costo minimo. Alberi ricoprenti, il problema del minimum spanning tree, algoritmo di Kruskal, Algoritmo di Prim, Algoritmo di Boruvka-Sollin.
• Cammini di costo minimo. Il problema del calcolo dei cammini di costo minimo da una singola sorgente, algoritmo di Dijkstra, algoritmo di Bellman-Ford, programmazione dinamica, calcolo dei cammini di costo minimo fra tutte le coppie di vertici di un grafo, algoritmo All Pairs Shortest Path, algoritmo di Floyd-Warshall, chiusura transitiva di un grafo orientato.
• Flusso massimo su una rete. Reti di flusso, capacità della rete, flusso, capacità residua e cammini aumentanti, algoritmo di Ford e Fulkerson, Teorema del Flusso Massimo e Taglio Minimo, algoritmo di Edmonds-Karp, algoritmo Push-Relabel.
• Partizionamento di grafi in componenti connesse. Definizione dei problemi di equipartizione di un grafo e di clustering, funzioni obiettivo, strategie per la costruzione di algoritmi risolutivi, equipartizione di alberi e di cammini.
• Problemi di matching e il matrimonio stabile. Definizione del problema del matrimonio stabile, generalizzazioni del problema, esempi, algoritmo di Gale & Shapley.
• Codici di Huffman. Codici, codici a lunghezza fissa e variabile, codici prefissi, algoritmo per la costruzione di un codice di Huffman.
• Algoritmi approssimanti per problemi NP-completi. Algoritmi approssimanti, rapporto di approssimazione, algoritmi approssimanti per il problema della copertura di vertici (vertex cover), algoritmi approssimanti per il problema della copertura di insiemi (set cover).
• Riepilogo degli argomenti. Riepilogo degli argomenti trattati nelle lezioni del corso IN440.
• Linguaggio Python. Introduzione alla programmazione in linguaggio Python, sintassi generale, strutture di controllo, variabili e strutture dati di base.
• Grafica in linguaggio Python. La libreria Python MatPlotLib e il modulo PyLab, la libreria Graphics, esempi.
• Strutture dati in Python. La libreria pythonds, gli oggetti per la rappresentazione delle strutture dati di pila (stack), coda (queue), coda a doppia entrata (deque), albero binario di ricerca, heap binario, grafo.
• Wolfram Mathematica. Introduzione all'utilizzo del software Wolfram Mathematica, modalità di utilizzo generale, operazioni su insiemi, operazioni su grafi, visualizzazione di grafi e alberi.
• Introduzione a Latex. Linguaggi di mark-up, TeX e LaTeX, modelli di documento in Latex, struttura di un documento (articolo), sintassi generale dei comandi Latex, tag per la formattazione del testo, tag per liste ed elenchi, figure e note a pié di pagina, pseudo-codice di algoritmi, codice di programmi.