ALGORITHMS FOR MODERN HARDWARE

Nell'era dell'Informatica moderna, ci troviamo costantemente di fronte a una sfida fondamentale: come possiamo archiviare, recuperare e processare in modo efficiente volumi di dati che spingono al limite il nostro hardware? Questo corso presenta tecniche algoritmiche avanzate e le strutture dati necessarie per rispondere a questa domanda.
Le tecniche insegnate in questo corso non sono infatti semplici curiosità teoriche; sono gli elementi costitutivi fondamentali dei sistemi che alimentano il mondo digitale. Gli algoritmi tradizionali spesso assumono che la memoria sia uniforme e infinita. Tuttavia, nella realtà, i cache-miss sono costosi, l'I/O del disco rappresenta un enorme collo di bottiglia e i vincoli di memoria dettano la progettazione del sistema. Questo corso colma il divario tra la progettazione teorica degli algoritmi e le prestazioni dei sistemi nel mondo reale. Imparerai a pensare criticamente al tradeoff spazio-tempo e a progettare algoritmi che siano allo stesso tempo ottimizzati per la cache ed efficienti in termini di spazio.

Le competenze acquisite in questo corso sono molto ricercate nell'ingegneria del software, in data science e nella programmazione di sistemi. I concetti si applicano direttamente a diversi domini, quali:

- Motori di Ricerca e Information Retrieval: Compressione di indici invertiti e risoluzione rapida delle query.
- Database: Utilizzo dell'ordinamento in memoria esterna per tabelle enormi e filtri probabilistici per evitare costose letture da disco.
- Bioinformatica: Utilizzo di strutture dati succinte e hashing perfetto minimo per indicizzare massicce sequenze di DNA in RAM.
- Reti: Impiego di filtri probabilistici veloci e compatti (XOR/Fuse) per l'instradamento dei pacchetti ad alta velocità e per decisioni di caching.

Al termine di questo corso, avrai una profonda comprensione di come ingegnerizzare algoritmi che gestiscano con eleganza ed efficienza i massicci dataset di domani.

Conoscenza e comprensione

Lo studente:
- conosce le metodologie per la progettazione e lo sviluppo di sistemi informatici relativi alla "Data Engineering";
- conosce le tecniche per valutare le prestazioni, la scalabilità e l'affidabilità di software e algoritmi per l'analisi di dati massicci;
- sviluppa le proprie abilità nel campo della programmazione imparando tecniche di calcolo e conoscenze algoritmiche allo stato dell'arte;
- conosce ambienti di programmazione e algoritmi per l'analisi di dati massicci.

Capacità di applicare conoscenza e comprensione

Lo studente:
- è in grado di progettare e sviluppare sistemi per l'archiviazione, la gestione e l'analisi di dati su larga scala;
- è in grado di utilizzare tecniche di programmazione avanzate nei settori del calcolo ad alte prestazioni e degli algoritmi per l'analisi di grandi quantità di dati;
- è in grado di verificare i requisiti funzionali e non funzionali (prestazioni) di un algoritmo;
- è in grado di accedere alla letteratura scientifica per identificare potenziali soluzioni a problemi con metodi innovativi allo stato dell'arte.

Autonomia 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ù adatti per risolvere un determinato problema.
- Analizzare rigorosamente le prestazioni degli algoritmi (tempo di esecuzione, spazio utilizzato, *cache-miss*).
- Leggere e comprendere in modo indipendente articoli di ricerca nel settore.
- Implementare algoritmi esistenti e progettarne di nuovi.

È raccomandata la padronanza dei seguenti prerequisiti per il completamento con successo del corso. Gli studenti che non hanno familiarità con questi argomenti sono caldamente incoraggiati a ripassarli in anticipo per garantire una piena partecipazione alle lezioni. Il docente rivedrà i prerequisiti necessari.

- Teoria della probabilità (argomenti trattati in CT0675)
- Algoritmi e strutture dati (argomenti trattati in CT0667)
- Programmazione, preferibilmente in C/C++ (argomenti trattati in CT0665 e CT0442)
- Matematica discreta (argomenti trattati in CT0434)

Query su array
- Somme prefisse: alberi di Fenwick, alberi di segmenti, e alberi larghi di segmenti.
- Range min/max queries con tavole sparse.
- Indici succinti Rank e Select.

Algoritmi di compressione dati
- Codici per interi: unario, gamma e delta di Elias, Golomb-Rice, Golomb esponenziale, Fibonacci, variable-byte, contenuto informativo ed entropia, disuguaglianza di Kraft-McMillan.
- Codifiche di sequenze: strategie "folklore" (blocking, patching, codici semplici), Elias–Fano, codifica interpolativa binaria, codici ad accesso diretto.
- Compressori statistici: Shannon–Fano, Huffman, codifica aritmetica.
- Compressori basati su dizionario: LZ77, LZSS, LZ78, LZW.

Algoritmi in memoria esterna
- Modello I/O e limiti fondamentali dell'I/O.
- Ordinamento per fusione.
- Ordinamento per distribuzione.
- Limite inferiore sugli I/O per l'ordinamento.
- Ordinamento di stringhe in memoria esterna.

Hashing
- Hashing dinamico: tabelle hash sparse/dense, Robin Hood hashing, design a tavola svizzera, cuckoo hashing.
- Funzioni di hash perfetto minimo: posizionamento dei bucket, fingerprinting, ipergrafi casuali.
- Filtri probabilistici oltre Bloom: filtri cuckoo
, XOR e Fuse.

Note e lucidi forniti dal professore.

L'esame consiste in due parti:
1. Codifica di soluzioni a problemi assegnati durante le lezioni: fino a 12 punti. Agli studenti viene chiesto di risolvere individualmente esercizi sugli argomenti del corso.
2. Esame orale: fino a 18 punti. L'esame orale inizia con la discussione della soluzione degli esercizi. Vengono poi poste allo studente alcune domande sugli argomenti del corso.

Extra: fino a 3 punti saranno assegnati agli studenti che partecipano a competizioni ICPC, come SWERC.

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.

Esercizi di coding (massimo 12 punti):
- accuratezza della soluzione, uso delle risorse computazionali, qualità della relazione (peso 80%)
- originalità della soluzione (peso 20%).

Esame orale (massimo 18 punti):
- conoscenza: enunciati e dimostrazioni dei risultati teorici (peso 40%),
- dettaglio e completezza delle risposte (peso 40%)
- capacità comunicativa, incluso l'uso della terminologia specifica relativa agli algoritmi e alle strutture dati per dati massicci (peso 20%).

Gli argomenti sono esposti usando il proiettore e la lavagna.