Module page
Teoria degli algoritmi
| academic year: | 2013/2014 |
| instructor: | Alessandro Panconesi |
| degree courses: | Mathematics for applications (magistrale), I year Mathematics (magistrale) |
| type of training activity: | affine e integrativa |
| credits: | 6 (48 class hours) |
| scientific sector: | INF/01 Informatica |
| teaching language: | italiano |
| period: | I sem (30/09/2013 - 17/01/2014) |
Lecture meeting time and location
Presence: highly recommended
Module subject:
NP-completeness and Complexity Theory - Approximation algorithms for NP-hard probems: algorithms and hardness results - Probabilistic algorithms - Distributed algorithms
Suggested reading:
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)
Type of course: standard
Knowledge and understanding:
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.
Skills and attributes:
riduzioni tra problemi NP-hard, progettazione ed analisi di algoritmi probabilistici, di approssimazione e distribuiti
Personal study: the percentage of personal study required by this course is the 65% of the total.