ALGORITMI RANDOMIZZATI ED APPROSSIMATI

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:

• 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

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.

L'esame consisterà in un progetto implementativo seguito da discussione orale.