Reti di flusso: il problema del flusso massimo, flusso massimo e taglio minimo, applicazioni. Algoritmi di approssimazione: tecniche greedy, programmazione lineare. Introduzione agli algoritmi genetici. Algoritmi di ricerca locale. Algoritmi randomizzati.
J. Kleinberg, E. Tardos "Algorithm Design", Addison-Wesley, 2006
Obiettivi Formativi
Conoscenze:
Reti di flusso e applicazioni. Algoritmi di approssimazione. Algoritmi genetici. Algoritmi di ricerca locale. Algoritmi randomizzati
Competenze acquisite:
Applicazioni dell'algoritmo per la determinazione del flusso massimo. Modalita' di sviluppo e di valutazione di algoritmi per il calcolo di soluzioni approssimate. Tecniche avanzate di sviluppo di algoritmi.
Capacità acquisite al termine del corso:
Capacita' di valutare la bonta' di un algoritmo di approssimazione
Prerequisiti
Corsi vincolanti: Algoritmi e Strutture Dati
Corsi raccomandati:Progettazione di Algoritmi e Complessita' Computazionale
Metodi Didattici
Numero di ore totali del corso: 150
Numero di ore per studio personale e altre attività formative di tipo individuale: 102
Numero di ore relative alle attività in aula: 48
Altre Informazioni
Orario di ricevimento
Mercoledi', dalle 10.00 alle 11.00 oppure previo appuntamento via e-mail.
Modalità di verifica apprendimento
Modalità:
Orale
Programma del corso
Contenuti del corso (programma dettagliato):
Reti di flusso: il problema del flusso massimo, flusso massimo e taglio minimo, applicazioni. Algoritmi di approssimazione: tecniche greedy, programmazione lineare. Introduzione agli algoritmi genetici. Algoritmi di ricerca locale. Algoritmi randomizzati.