Corso di: RICERCA OPERATIVA II
Laurea in Informatica
Anno accademico: 2003-2004
Docente: Marco Locatelli
INDICE
Obiettivi del corso
Il corso si propone di presentare agli studenti diversi classi di problemi
di ottimizzazione che occorrono frequentemente nella pratica, evidenziando
sia gli aspetti di complessitá di tali problemi sia quelli relativi
alle metodologie di risoluzione.
Prerequisiti del corso
Corso di Ricerca Operativa 1.
Modalità d'esame
L'esame sará costituito da una parte scritta con esercizi relativi
al programma svolto. La parte orale sará facoltativa per gli studenti
che supereranno l'esame con votazione non inferiore al 18.
Libri di testo
Programma dettagliato del corso
Problemi di ottimizzazione combinatoria. Breve introduzione alla complessitá:
classi P e NP, problemi NP-copmpleti, algoritmi di approssimazione, tecniche
euristiche. Studio di diversi problemi nella classe P: flusso massimo,
matching, trasporto, assegnamento, flusso a costo minimo. Problemi NP-completi,
metodi esatti: branch-and-bound e programmazione dinamica. Applicazioni
al problema dello zaino. Il problema del commesso viaggiatore: algoritmo
di approssimazione nel caso metrico. Il problema di facility location.
Ottimizzazione continua.
|