-Conoscenze di base in algebra, analisi e probabilità: È richiesto che lo studente abbia familiarità con le dimostrazioni per induzione e per assurdo, con i concetti di variabile aleatoria e valore atteso. È inoltre preferibile che lo studente possieda conoscenze preliminari sulla ricerca operativa, come ad esempio la programmazione lineare.

-Padronanza di almeno un linguaggio di programmazione.

-Analisi asintotica della complessità degli algoritmi.

-È preferibile che lo studente abbia già conoscenze di base sulle principali tecniche algoritmiche (ricorsione, paradigma divide-et-impera, greedy e programmazione dinamica) e sulle strutture dati (liste e alberi).

Il corso offre un approfondimento delle principali tecniche algoritmiche, con particolare attenzione agli algoritmi su grafi e alla complessità computazionale. Inoltre, fornisce una panoramica delle tecniche algoritmiche più avanzate, riguardanti in particolare la progettazione e l'analisi di algoritmi di approssimazione, utilizzati per trovare soluzioni sub-ottimali a problemi computazionalmente difficili, e di algoritmi randomizzati, che sfruttano scelte casuali per risolvere problemi in modo più efficiente. Queste tecniche saranno applicate a diversi problemi di ottimizzazione e di machine learning di rilevante interesse.

Al termine del corso, lo studente:

-sarà in grado di definire le direzioni principali per affrontare un dato problema computazionale, sia di interesse teorico che pratico;
-con le capacità di problem solving acquisite, saprà applicare autonomamente, in modo versatile e con rigore, le tecniche algoritmiche apprese;
-quando necessario o preferibile, sarà in grado di esplorare e approfondire nuovi approcci algoritmici, al di là di quelli studiati durante il corso.

Lezioni teoriche frontali corredate da alcuni esercizi.

Si richiede che lo studente prepari e svolga un seminario su argomenti correlati alle tematiche trattate durante il corso, previo accordo con il docente.

Testo di riferimento:

- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Livio Colussi, Achille Frigeri: INTRODUZIONE AGLI ALGORITMI E STRUTTURE DATI 4/ED. McGraw-Hill, 2023. 

Alcuni argomenti più specifici del corso sono trattati nei seguenti testi:

-Jon Kleinberg, Éva Tardos. ALGORITHM DESIGN: PEARSON NEW INTERNATIONAL EDITION. Pearson, 2013.

-David B. Shmoys, David P. Williamson. THE DESIGN OF APPROXIMATION ALGORITHMS. Cambridge University Press, 2015.

-Tor Lattimore, Csaba Szepesvári. BANDIT ALGORITHMS. Cambridge University Press, 2020. 

Ulteriori informazioni sul materiale didattico consigliato saranno fornite durante il corso.