Ingegneria degli algoritmi (Algorithm Engineering)

Algoritmi e strutture dati, linguaggi di programmazione (C), reti

Per richiamare  concetti di Algoritmi si suggerisce di seguire le Video Lectures di Erik Demaine e Charles Leiserson

Offrire agli studenti strumenti e tecniche algoritmiche avanzate per progettare, analizzare e realizzare soluzioni efficienti per lo storage, l'analisi e la ricerca in massive datasets.

algoritmi e strutture dati efficienti per la gestione di grandi quantità di dati (big data) riguardati: stringhe, interi, elementi geometrici, alberi e grafi

capacità di progettare e analizzare strutture dati e algoritmi sofisticati per big data

In questo corso studieremo, progetteremo e analizzeremo (con modelli teorici e attraverso risultati sperimentali) soluzioni algoritmiche e strutture dati avanzate per la risoluzione efficiente di problemi combinatori che coinvolgono vari tipi di dato? quali interi, stringhe, punti (geometrici), alberi, grafi. Il progetto interesserà alcuni modelli di calcolo? RAM, 2-level memory, cache-oblivious, streaming? al fine di ottenere soluzioni algoritmiche le cui valutazioni teoriche ben riflettono le loro prestazioni reali, poiché tengono conto delle caratteristiche architetturali e della gerarchia di memoria dei moderni PC. Ogni lezione seguirà un approccio problem-driven che inizia considerando un problema reale, lo astrae in modo combinatorio, e poi procede al progetto e analisi di soluzioni algoritmiche tese a minimizzare l'uso di alcune risorse computazionali quali: tempo, spazio, communicazione, I/O, etc. Alcune soluzioni viste in classe saranno discusse anche a livello sperimentale al fine di introdurre degli strumenti appropriati per l' ingegnerizzazione e il tuning del codice.

1. RAM model: Data compression, Data processing (randomized, adaptive, self-adjusting), Data indexing and searching over atomic items, strings, geometric points, trees and graphs
2. 2-level memory model: Definition and properties, Data sorting and permuting, Data indexing and searching over atomic items and strings, Data sketching: bloom filters and count-min sketch
3. Streaming model: sampling, scanning, sketching.

note del docente

L'esame consiste di una prova scritta e di una prova orale.