ALGORITMI RANDOMIZZATI ED APPROSSIMATI
Anno accademico 2018/2019 - 1° anno - Curriculum Data ScienceCrediti: 6
Organizzazione didattica: 150 ore d'impegno totale, 102 di studio individuale, 24 di lezione frontale, 24 di esercitazione
Semestre: 2°
Obiettivi formativi
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.
Modalità di svolgimento dell'insegnamento
Lezioni frontali
Prerequisiti richiesti
Il corso presuppone una buona conoscenza di strumenti matematici discreti e continui, ed una conoscenza approfondita di algoritmi.
Frequenza lezioni
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 del corso
Contenuti di massima del Corso:
- Fondamenti di calcolo delle probabilità
- Analisi probabilistica di algoritmi
- Algoritmi randomizzati: Las Vegas e Montecarlo
- Introduzione ai problemi NP-hard e NP-completi
- Esempi di Algoritmi approssimati
Testi di riferimento
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
Programmazione del corso
| 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 |
Verifica dell'apprendimento
Modalità di verifica dell'apprendimento
L'esame consisterà in un progetto implementativo seguito da discussione orale.