ALGORITHMIC TECHNIQUES FOR AI, GAMES AND NETWORKS

Il corso presenta una varietà di approcci algoritmici per problemi computazionali inerenti ai moderni sistemi digitali. Ciò include problemi computazionali del mondo reale che si verificano nel contesto di reti quali i social network e le reti stradali. Passiamo poi alle tecniche algoritmiche applicate ai giochi, ovvero contesti computazionali caratterizzati da più giocatori con incentivi potenzialmente divergenti. Introduciamo poi tecniche algoritmiche che sono alla base di alcuni approcci moderni di machine learning, come multiplicative weights udpate. Trattando questi metodi, il corso esamina gli algoritmi fondamentali alla base di molte delle importanti infrastrutture digitali odierne. Questo corso adotta un approccio matematicamente rigoroso: presentiamo le tecniche algoritmiche, ne dimostriamo la correttezza e ne analizziamo formalmente la performance.

Conoscenza e comprensione:
Lo studente:
- conosce le tecniche algoritmiche utilizzate nei moderni sistemi computazionali;
- conosce le tecniche per dimostrare la correttezza di tali approcci algoritmici;
- conosce le tecniche per valutarne la performance, la scalabilità e l'affidabilità

Capacità di applicare conoscenza e comprensione:
Lo studente:
- è in grado di progettare e sviluppare algoritmi per problemi computazionali che sorgono nei moderni ambienti computazionali;
- è in grado di analizzare gli algoritmi sviluppati in termini di correttezza e scalabilità;
- è in grado di leggere la letteratura scientifica su argomenti correlati e di cogliere le tecniche presentate.

Capacità di giudizio:
Al termine del corso lo studente sarà in grado di utilizzare le conoscenze acquisite per:
- Identificare gli algoritmi più adatti a risolvere determinati problemi nel contesto delle reti, dell'IA e dei giochi
- Dimostrare rigorosamente affermazioni sul comportamento di un algoritmo (in particolare la correttezza)
- Analizzare rigorosamente le prestazioni degli algoritmi (tempo di esecuzione, approssimazione, probabilità di successo nel caso di algoritmi randomizzati)

Si raccomanda una solida conoscenza dei seguenti prerequisiti:
- Algoritmi e strutture dati (argomenti trattati nel corso CT0667)
- Teoria della probabilità (argomenti trattati nel corso CT0675)
- Matematica discreta (argomenti trattati nel corso CT0434)

+ Processi random sulle reti
- Diffusione delle informazioni nelle reti
- Concentration bounds
- Random walks, tempo di copertura

+ Algoritmi per grafi specifici del mondo reale
- Reti sociali (centrality measures, triangle counting, clustering coefficients)
- Percorsi più brevi nei grafi stradali (transit nodes, highway dimension)
- Congestion games

+ Reti di flusso
- Max Flow (Ford Fulkerson) and Min Cut (Karger)
- Min-Cost Flow (ciclo di costo negativo)

+ Problemi di selezione online
- Secretary Problems
- Principio di Yao

+ Multiplicative Weights Framework
- Previsione con consulenza di esperti
- Risoluzione di giochi a somma zero
- Boosting

+ Learning
- sample complexity
- Dimensione VC e PAC learning

- appunti del docente
- articoli di ricerca originali forniti durante il corso

L'esame si articola in due parti, entrambe obbligatorie. Per superare il corso è necessario superare entrambe le parti (con un punteggio >= 18/30). Se questa condizione è soddisfatta, il voto finale corrisponde alla media dei due voti ottenuti nelle due parti (arrotondata per eccesso).

1. Esame scritto. L'esame scritto consisterà in domande a scelta multipla e domande aperte volte a verificare che lo studente abbia acquisito le conoscenze presentate nel corso. Durante il corso verranno distribuiti regolarmente esercizi di tipo simile.

2. Esame orale. L'esame orale deve essere sostenuto dopo la consegna dell'esame scritto e può essere sostenuto solo se l'esame scritto è stato superato con almeno 18/30. L'esame inizia con un breve e semplice test di screening (diverse domande brevi, circa 10 minuti) volto a verificare le conoscenze di base del materiale del corso. Successivamente lo studente presenterà in modo approfondito (circa 20 minuti) alla lavagna un argomento del corso a sua scelta (eventualmente interrotto o seguito da domande relative alla presentazione).

scritto e orale

Il/la docente ha il dovere di vigilare affinché siano rispettate le regole di autenticità e originalità delle prove d'esame. Di conseguenza, nei casi in cui vi sia il sospetto di un comportamento irregolare, l'esame può prevedere un ulteriore approfondimento, contestuale alla prova d'esame, che potrà essere realizzato anche in modalità differente rispetto alle modalità sopra riportate.

28-30L: lo studente padroneggia gli argomenti presentati nel corso;
è in grado di ragionare in modo algoritmico e di formulare ragionamenti formali riguardo alla correttezza e alle garanzie di prestazione degli algoritmi;
la sua esposizione è molto chiara e accademica

26-27: lo studente ha una buona conoscenza degli argomenti presentati nel corso;
riesce generalmente a ragionare in modo algoritmico e a formulare ragionamenti formali riguardo alla correttezza e alle garanzie di prestazione degli algoritmi;
la sua esposizione è molto chiara

24-25: lo studente non conosce in modo approfondito tutti gli argomenti presentati nel corso;
riesce per lo più a ragionare in modo algoritmico e a formulare ragionamenti formali riguardo alla correttezza e alle garanzie di prestazione degli algoritmi;
la sua esposizione è chiara

22-23: lo studente ha una conoscenza per lo più superficiale degli argomenti presentati nel corso;
solitamente riesce a ragionare in modo algoritmico e a formulare ragionamenti formali riguardo alla correttezza e alle garanzie di prestazione degli algoritmi;
la sua esposizione non è sempre chiara

18-21: lo studente ha una conoscenza molto superficiale degli argomenti presentati nel corso;
ha difficoltà a ragionare in modo algoritmico e a formulare ragionamenti formali riguardo alla correttezza e alle garanzie di prestazione degli algoritmi;
la sua esposizione è confusa

Insegnamento organizzato in lezioni frontali ed esercizi su carta.

Il corso si terrà in lingua inglese.