Scheda insegnamento
Teoria degli algoritmi
| anno accademico: | 2013/2014 |
| docente: | Alessandro Panconesi |
| corsi di laurea: | Matematica per le Applicazioni (magistrale), I anno Matematica (magistrale) |
| tipo di attività formativa: | affine e integrativa |
| crediti formativi: | 6 (48 ore di lezione) |
| raggruppamento disciplinare: | INF/01 Informatica |
| lingua di insegnamento: | italiano |
| periodo: | I sem (30/09/2013 - 17/01/2014) |
Aula ed orario di lezione
Frequenza: consigliata
Programma di massima del corso:
NP-completezza con cenni di teoria della complessità, Approssimazione dei problemi NP-hard: algoritmi e risultati di impossibilità, algoritmi probabilistici, algoritmi distribuiti
Testo consigliato:
D.Kozen, The design and analysis of algorithms, Springer-Verlag
V.Vazirani, Approximation algorithms, Springer-Verlag
Dubhashi & Panconesi, Concentration of measure for the analysis of randomized algorithms, Cambrdige University Press (cpdf fornito dal docente)
Modalità di erogazione: convenzionale
Risultati di apprendimento - Conoscenze acquisite:
scopo del corso è quello di dare un'idea della ricerca contemporanea in algoritmi attraverso una serie di "perle", esempi cioè che siano al contempo significativi ed eleganti, piuttosto che attraverso un trattamento sistematico.
Risultati di apprendimento - Competenze acquisite:
riduzioni tra problemi NP-hard, progettazione ed analisi di algoritmi probabilistici, di approssimazione e distribuiti
Studio personale: la percentuale prevista di studio personale sul totale dell'impegno richiesto è del 65%