-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. 

-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, programmazione dinamica) e sulle strutture dati (liste e alberi).

Il corso approfondisce la teoria e la progettazione degli algoritmi, con un particolare focus sugli algoritmi per grafi (o reti). In parallelo, fornisce una rigorosa introduzione alle classi di complessità computazionale (come P, NP e le sottoclassi dei problemi NP-completi), strumenti fondamentali per classificare i problemi computazionali in base alla loro difficoltà.

Successivamente, si studieranno gli algoritmi di approssimazione, impiegati per ottenere soluzioni sub-ottimali a problemi di ottimizzazione computazionalmente complessi, e gli algoritmi randomizzati, che utilizzano scelte casuali per migliorare la qualità delle soluzioni o ridurre i tempi di calcolo.

I metodi e gli algoritmi trattati saranno applicati a problemi di ottimizzazione e machine learning di rilievo, offrendo così un quadro completo e applicato della materia.

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.

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