Corso di Ottimizzazione Combinatoria (IN440)

Bibliografia ed altri riferimenti

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

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à computazionaleFormato PDF (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àFormato PDF.
2. Insiemi ed elementi di calcolo combinatorioFormato PDF (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 MathematicaFormato PDF (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 GrafiFormato PDF (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 LineareFormato PDF (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 minimoFormato PDF (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 connesseFormato PDF (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 stabileFormato PDF (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

Università degli Studi Roma Tre - Dipartimento di Matematica e Fisica - Corso di laurea in Matematica - Corso di Ottimizzazione Combinatoria (IN440)

Author: Marco Liverani - Last modified: Friday May 28, 2021 - Document URI: https://www.mat.uniroma3.it/users/liverani/IN7/bibliografia.shtml