Complementi di algoritmi e strutture dati
A.A. 2022/2023
Obiettivi formativi
L'analisi degli algoritmi è una parte importante dell'informatica. Questo corso introduce gli studenti alle tecniche avanzate per il progetto e l'analisi di algoritmi, esplorando una varietà di applicazioni. In particolare, ci focalizzeremo su tre temi : complessità computazionale, algoritmi probabilistici, giochi e mercati.
Risultati apprendimento attesi
Al termine dell'insegnamento, gli studenti saranno in grado di: (1) descrivere le principali classi di complessità per i problemi di decisione e dimostrare alcune delle loro proprietà; (2) descrivere e analizzare numerosi algoritmi probabilistici; (3) comprendere alcuni dei principali concetti relativi alla teoria dei giochi e alla loro applicazione alle aste ed ai mercati digitali. Questi obiettivi verranno misurati attraverso una discussione orale la cui valutazione determinerà il voto finale.
Periodo: Secondo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Programma e organizzazione didattica
Edizione unica
Responsabile
Periodo
Secondo semestre
Programma
1. Complessità computazionale
- Riducibilità polinomiale tra problemi di decisione
- Le classi P e NP
- I problemi NP-completi
2. Algoritmi probabilistici
- Algoritmi Montecarlo e Las Vegas
- Le classi di complessità probabilistiche
- L'estrattore di von Neumann
- Il problema del coupon collector
- Reservoir sampling
- L'algoritmo di Karger per MinCut
- Algoritmi Hedge e Exp3 per decisioni sequenziali
3. Hashing e randomizzazione
- Hashing universale
- Conteggio approssimato: Count-Min Sketch
- Proiezioni casuali
4. Clustering e randomizzazione
- Correlation clustering
- K-Means++
5. Giochi, Aste e Mercati
- Il teorema minimax di Von Neumann
- Aste
- Matching markets
- Riducibilità polinomiale tra problemi di decisione
- Le classi P e NP
- I problemi NP-completi
2. Algoritmi probabilistici
- Algoritmi Montecarlo e Las Vegas
- Le classi di complessità probabilistiche
- L'estrattore di von Neumann
- Il problema del coupon collector
- Reservoir sampling
- L'algoritmo di Karger per MinCut
- Algoritmi Hedge e Exp3 per decisioni sequenziali
3. Hashing e randomizzazione
- Hashing universale
- Conteggio approssimato: Count-Min Sketch
- Proiezioni casuali
4. Clustering e randomizzazione
- Correlation clustering
- K-Means++
5. Giochi, Aste e Mercati
- Il teorema minimax di Von Neumann
- Aste
- Matching markets
Prerequisiti
E` fortemente consigliato il superamento degli esami seguenti: Matematica del continuo, Matematica del discreto, Algoritmi e strutture dati.
Metodi didattici
Lezioni frontali. Modalità di frequenza: facoltativa.
Materiale di riferimento
Il materiale di riferimento principale sono le dispense disponibili tramite il portale ariel.unimi.it/
Materiale aggiuntivo:
- Jon Kleinberg and Éva Tardos. Algorithm Design. Pearson International Edition, 2006.
- David Easley and Jon Kleinberg. Networks, Crowds, and Markets. Cambridge University Press, 2010
Materiale aggiuntivo:
- Jon Kleinberg and Éva Tardos. Algorithm Design. Pearson International Edition, 2006.
- David Easley and Jon Kleinberg. Networks, Crowds, and Markets. Cambridge University Press, 2010
Modalità di verifica dell’apprendimento e criteri di valutazione
L'esame consiste di una prova orale relativa agli argomenti trattati nell'insegnamento.
La valutazione, espressa in trentesimi, tiene conto del livello di padronanza degli argomenti, della chiarezza espositiva e della proprietà di linguaggio.
La valutazione, espressa in trentesimi, tiene conto del livello di padronanza degli argomenti, della chiarezza espositiva e della proprietà di linguaggio.
Siti didattici
Docente/i