Complementi di algoritmi e strutture dati
A.A. 2020/2021
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
Qualora la situazione sanitaria non consentisse il regolare svolgimento delle lezioni in presenza, queste si svolgeranno in modalità sincrona sulla piattaforma Zoom sulla base dell'orario del secondo semestre. Al termine di ciascuna lezione, verrà reso disponibile a tutti gli studenti un link alla sua videoregistrazione. La modalità di erogazione e le istruzioni per la fruizione delle lezioni verranno rese note agli studenti attraverso avvisi sul sito dell'insegnamento (vedi sezione Materiale di Riferimento).
Il programma e il materiale di riferimento non subiranno variazioni.
Le modalità di verifica dell'apprendimento e i criteri di valutazione non subiranno variazioni, fermo restando che l'esame orale si svolgerà in presenza o tramite Zoom a seconda delle direttive vigenti al tempo dell'appello.
Il programma e il materiale di riferimento non subiranno variazioni.
Le modalità di verifica dell'apprendimento e i criteri di valutazione non subiranno variazioni, fermo restando che l'esame orale si svolgerà in presenza o tramite Zoom a seconda delle direttive vigenti al tempo dell'appello.
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.
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.
Docente/i