Università Roma Tre

RICHIAMI DI ANALISI COMBINATORIA, ELEMENTI DI TEORIA DEI GRAFI. RICHIAMI SULLA TEORIA DEGLI ALGORITMI E DELLA COMPLESSITÀ COMPUTAZIONALE, SUI PROBLEMI INTRATTABILI E SULLE CLASSI DI COMPLESSITÀ P, NP, NP-COMPLETE, NP-HARD.
INTRODUZIONE AI PROBLEMI DI OTTIMIZZAZIONE E DI OTTIMIZZAZIONE COMBINATORIA SU INSIEMI A VARIABILI DISCRETE. CENNI SULLA PROGRAMMAZIONE LINEARE; PROGRAMMAZIONE DINAMICA. PROBLEMI DI FLUSSO MASSIMO SU RETI. ALBERI RICOPRENTI DI PESO MINIMO PER GRAFI PESATI. PROBLEMI DI CAMMINO MINIMO. PROBLEMI DI MATCHING. PARTIZIONAMENTO OTTIMO DI GRAFI. ALGORITMI APPROSSIMANTI PER PROBLEMI NP-COMPLETI.

1. CORMEN, LEISERSON, RIVEST, STEIN, INTRODUZIONE AGLI ALGORITMI E STRUTTURE DATI, TERZA EDIZIONE, MCGRAW-HILL, 2010
2. TRUDEAU, INTRODUCTION TO GRAPH THEORY, DOVER PUBLICATIONS, 1993
3. GIBBONS, ALGORITMIC GRAPH THEORY, CAMBRIDGE UNIVERSITY PRESS, 1999
4. PAPADIMITRIOU, STEIGLITZ, COMBINATORIAL OPTIMIZATION – ALGORITHMS AND COMPLEXITY, DOVER PUBLICATIONS, 1998
5. LIVERANI, QUAL È IL PROBLEMA – METODI, STRATEGIE RISOLUTIVE, ALGORITMI, MIMESIS, 2005.