ADVANCED ALGORITHMS

Il corso affronta tecniche avanzate nell'ambito degli algoritmi randomizzati e delle strutture dati compresse, con particolare focus sul problema del pattern matching su dati compressi (stringhe e grafi) e algoritmi randomizzati/analisi probabilistica per problemi computazionali nei grafi.

Conoscenza e comprensione
Lo studente:

- conosce le metodologie di progettazione e sviluppo di sistemi informatici relativi a Massive Data;
- conosce le tecniche per la valutazione delle prestazioni, della scalabilità, e dell'affidabilità di software e algoritmi per analizzare dati massivi;

- sviluppa le proprie competenze nell'ambito della programmazione acquisendo padronanza delle tecniche di calcolo e la conoscenza di algoritmi, allo stato dell'arte;
- conosce ambienti di programmazione e algoritmi per l’analisi di dati massivi;

Capacità di applicare conoscenza e comprensione
Lo studente:

- è in grado di progettare e sviluppare sistemi per la memorizzazione, gestione e analisi di dati su larga scala;
- è in grado di progettare e valutare sistemi altamente scalabili;
- è in grado di usare tecniche di programmazione avanzata negli ambiti del calcolo ad alte prestazioni e algoritmi per l'analisi di elevate moli di dati;

- è in grado di verificare i requisiti funzionali e non funzionali (prestazioni) di un algoritmo;
- è in grado di accedere alla letteratura scientifica per individuare potenziali soluzioni a problemi con metodi innovativi allo stato dell'arte.

Capacità di giudizio:
Al termine del corso lo studente sarà in grado di utilizzare le conoscenze acquisite per:
- Identificare l'algoritmo e la struttura dati più adatta a risolvere una determinata problematica nell'ambito dei massive data.
- Leggere e comprendere in modo indipendente articoli di ricerca nel settore.
- Implementare algoritmi esistenti e progettarne di nuovi.

algoritmi e strutture dati di base
basi di information theory

Parte 1
+ introduzione al problema del pattern matching, soluzioni classiche
+ tecniche di compressione del suffix array: entropia (Compressed Suffix Array) e repetition-aware (r-index, Suffixient Array)
+ indici compressi su grafi etichettati

Parte 2
+ Concentration Bounds
+ Processi casuali sulle reti
- Diffusione delle informazioni nelle reti
- Random Walks, tempo di copertura
+ Framework dei pesi moltiplicativi
- Previsione con expert advice
- Risoluzione di Covering/Packing LP e diffusione equa delle informazioni
- Boosting, dimensione VC e PAC learning

articoli di ricerca originali

L'esame consiste in una prova orale. Durante la prova lo studente potrà esporre un articolo di ricerca scelto nell'ambito degli argomenti del corso. In alternativa, verranno fatte domande sugli argomenti esposti a lezione.

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.

- conoscenze: enunciati e dimostrazioni dei risultati teorici (range 40%),
- dettaglio e completezza delle risposte (range 40%),
- capacità di comunicazione, compreso l'uso di terminologia specifica relativa ad algoritmi e strutture di dati per dati massivi (range 20%).

Gli argomenti del corso verranno presentati utilizzando la lavagna e slides preparate dal docente.