Conoscenza e capacità di comprensione (knowledge and understanding): saranno acquisite le conoscenze relative alla progettazione ed analisi di Algoritmi randomizzati ed approssimati.
Capacità di applicare conoscenza e comprensione (applying knowledge and understanding): saranno acquisite le capacità per applicare le nozioni imparate in vari campi ad in particolare la risoluzione di problemi combinatorialmente molto difficili.
Autonomia di giudizio (making judgements): Lo studente sarà in grado di valutare la possibilità di sviluppare algoritmi randomizzati e approssimati nella risoluzione algoritmica di problemi in diversi ambiti applicativi.
Abilità comunicative (communication skills): saranno acquisite le necessarie abilità comunicative ed un'adeguata appropriatezza espressiva nella comunicazione di problematiche inerenti gli algoritmi avanzati e le loro applicazioni.
Capacità di apprendimento (learning skills): lo studente avrà la capacita di adattare le conoscenze acquisite anche a nuovi contesti e di comprendere i limiti di applicabilità delle tecniche algoritmiche.
Lezioni frontali
Il corso presuppone una buona conoscenza di strumenti matematici discreti e continui, ed una conoscenza approfondita di algoritmi.
La frequenza è consigliata. Le lezioni permettono di cogliere meglio gli argomenti trattati e l'idea generale che tiene legati i diversi temi e forniscono riferimenti e digressioni utili.
Contenuti di massima del Corso:
Saranno utilizzate parti dei seguenti testi di riferimento
1. TH Cormen, CE Leiserson, RL Rivest, C Stein, Introduzione agli Algoritmi e strutture dati
2. R Motwani, P Raghavan, Randomized Algorithms
3. DP Williamson, DB Shmoys, The Design of Approximation Algorithms
Tutto il materiale didattico riguardante il corso sarà pubblicato su Studium.
Argomenti | Riferimenti testi | |
1 | Introduzione alla probabilità | 1. Appendice C |
2 | Analisi Probabilistica di Algoritmi | 1. Cap. 5 |
3 | Algoritmi Randomizzati | 1. Cap. 5 e 2. Cap. 1-4 |
4 | Introduzione alla NP-Completezza | 1. Cap. 34 |
5 | Algoritmi di approssimazione | 1. Cap. 35 e 3 Cap. 1-3 |
L'esame consisterà in un progetto implementativo seguito da discussione orale.