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À NP, NP-COMPLETE, NP-HARD. INTRODUZIONE AI PROBLEMI DI OTTIMIZZAZIONE E DI OTTIMIZZAZIONE COMBINATORIA SU INSIEMI E 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, SECONDA EDIZIONE, MCGRAW-HILL, 2005
2. TRUDEAU, INTRODUCTION TO GRAPH THEORY, DOVER PUBLICATIONS, 1993
3. GIBBONS, ALGORITHMIC GRAPH THEORY, CAMBRIDGE UNIVERSITY PRESS, 1999
4. PAPADIMITRIOU, STEIGLITZ, COMBINATORIAL OPTIMIZATION. ALGORITHMS AND COMPLEXITY, DOVER PUBLICATIONS, 1998