Complementi di algoritmi e strutture dati
A.A. 2024/2025
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 può essere seguito come corso singolo.
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
- Algoritmi Hedge e Exp3 per decisioni sequenziali
- Aste
- Ottimizzazione del prezzo base in aste al secondo prezzo
- Il teorema Minimax di von Neumann
- Gestione di portafogli
- Matching markets
- Il teorema di Hall
- 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
- Algoritmi Hedge e Exp3 per decisioni sequenziali
- Aste
- Ottimizzazione del prezzo base in aste al secondo prezzo
- Il teorema Minimax di von Neumann
- Gestione di portafogli
- Matching markets
- Il teorema di Hall
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/
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.
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Docente:
Cesa Bianchi Nicolo' Antonio
Turni:
Turno
Docente:
Cesa Bianchi Nicolo' AntonioDocente/i