complementi di algoritmi e strutture dati 6 crediti (48 ore), laurea triennale in Informatica Edizione 2022-23 DOCENTI: Nicolò Cesa-Bianchi e Emmanuel Esposito

Avvisi

• Le lezioni cominceranno il 28 Febbraio 2023 col seguente orario: martedì 16:30-18:30 e mercoledì 14:30-16:30.

Obiettivi

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, quest'anno ci focalizzeremo su tre temi : complessità computazionale, algoritmi probabilistici, giochi e mercati.

Programma

1. Cenni alla complessità computazionale (leggere anche KT 8, versione appunti: 20 marzo 2023)
   • Riducibilità polinomiale tra problemi di decisione
   • Le classi P e NP
   • I problemi NP-completi
2. Algoritmi probabilistici
   • Algoritmi Montecarlo e Las Vegas (versione del 20 marzo 2023)
   • Le classi di complessità probabilistiche (versione del 20 marzo 2023)
   • L'estrattore di von Neumann (versione del 15 giugno 2017)
   • Il problema del coupon collector (versione del 19 giugno 2017)
   • Reservoir sampling (versione del 17 marzo 2021)
   • L'algoritmo di Karger per il taglio minimo in un grafo (versione del 21 marzo 2023)
3. Hashing e randomizzazione
   • Hashing universale (versione del 6 aprile 2023)
   • Conteggio approssimato: Count-Min Sketch (versione del 29 marzo 2023)
   • Proiezioni casuali (versione del 7 aprile 2023)
4. Clustering e randomizzazione
   • Correlation clustering (versione del 22 aprile 2023)
   • k-Means
   • k-Means++
   • Hierarchical clustering
5. Giochi e mercati
   • Algoritmi Hedge e Exp3 per decisioni sequenziali (versione del 8 maggio 2023)
   • Aste (EK 9)
   • Ottimizzazione del prezzo base in aste al secondo prezzo (versione del 26 maggio 2023)
   • Il teorema Minimax di von Neumann (versione dell'11 giugno 2021)
   • Gestione di portafogli (versione del 6 giugno 2021)
   • Matching markets (EK 10)
   • Il teorema di Hall (versione dell'8 giugno 2021)

Avete trovato un errore nelle dispense? Segnalatelo al docente che ve ne sarà grato!
Grazie a Emmanuel Esposito per aver accuratamente segnalato vari errori!

Materiale bibliografico

• (KT) Jon Kleinberg and Éva Tardos. Algorithm Design. Pearson International Edition, 2006.
• (EK) David Easley and Jon Kleinberg. Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press, 2010.
• Dispense fornite dal docente.

Esami

L'esame consiste in una prova orale che comprende anche le dimostrazioni spiegate a lezione. La data viene fissata su appuntamento e il voto verrà verbalizzato nel primo appello utile.

Calendario lezioni

Sfogliate le pagine del calendario e cliccate sulle date per trovare i riassunti e le date delle prossime lezioni.