ALGORITMI RANDOMIZZATI ED APPROSSIMATI

INF/01 - 6 CFU - 2° semestre

Docente titolare dell'insegnamento

VINCENZO CUTELLO

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.

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

Altro materiale didattico

Tutto il materiale didattico riguardante il corso sarà pubblicato su Studium.

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

* Conoscenze minime irrinunciabili per il superamento dell'esame.

N.B. La conoscenza degli argomenti contrassegnati con l'asterisco è condizione necessaria ma non sufficiente per il superamento dell'esame. Rispondere in maniera sufficiente o anche più che sufficiente alle domande su tali argomenti non assicura, pertanto, il superamento dell'esame.

Verifica dell'apprendimento

PROVE IN ITINERE

Non sono previste prove in itinere.

PROVE DI FINE CORSO

Non è prevista una prova di fine corso.

Apri in formato Pdf English version