Possibili argomenti di tesi sono brevemente descritti di seguito. Oltre all'interesse e all'entusiasmo per lo studio di risultati scientifici, le tesi richiedono una solida preparazione acquisita negli esami di programmazione e di algoritmi e strutture dati e la capacità di affrontare e comprendere testi in inglese.

Alcuni argomenti offrono ottime opportunità di ricerca, anche in prospettiva di un dottorato. Per maggiori informazioni (o se avete una vostra proposta che ritenete possa interessarmi) speditemi mail per concordare un appuntamento.

Analisi dinamica del software

L'analisi dinamica dei programmi comprende lo sviluppo di tecniche e strumenti (come profiler, debugger, invariant checker) volti all'analisi del software mediante informazioni raccolte a tempo di esecuzione. Due questioni chiave in tale ambito sono: 1) come ottenere tracce di esecuzione minimizzando l'impatto sul software osservato, e 2) come analizzare ed estrarre dalle tracce di esecuzione informazioni rilevanti senza incidere eccessivamente sulle prestazioni dell'applicazione.

Mentre l'esecuzione di un programma può essere monitorata usando sistemi automatici di instrumentazione, quali Intel PIN o Valgrind, la fase di analisi e mining delle tracce acquisite presenta innumerevoli sfide di carattere algoritmico. Ad esempio, supponiamo di dover sviluppare un tool che analizzi i pattern di accesso a memoria di un processo: tale tool deve essere in grado di gestire enormi flussi di dati, generati al volo dal monitoraggio dei bus dati ed indirizzi (tipicamente al tasso di diversi MB al secondo!). La taglia dei dati raccolti è tale da richiedere tecniche algoritmiche sofisticate per estrarre al volo le informazioni di interesse e/o strutture dati efficienti per indicizzare e memorizzare dati su disco. Le routine di analisi devono inoltre essere molto efficienti: essendo inserite inline nel programma in esecuzione, possono facilmente avere un forte impatto negativo sulle prestazioni, rendendo il tool scarsamente applicabile in pratica.

Le tesi proposte in questo ambito propongono di investigare come recenti risultati nel campo della teoria degli algoritmi per la gestione di grandi moli di dati possano essere applicati al progetto ed all'implementazione di strumenti di analisi dinamica dei programmi. L'ambito è nuovo e promettente, presenta innumerevoli problemi aperti, e riveste grande interesse scientifico, oltre che in aziende come Microsoft Research. Le tesi offrono un buon mix di teoria ed applicazione, richiedendo di studiare e sviluppare tecniche algoritmiche avanzate e prevedendo la realizzazione di veri e propri tool di analisi basati su sistemi di instrumentazione come PIN e Valgrind.

MapReduce e big data systems

MapReduce è un modello di programmazione proposto nel 2004 da Google per processare dati distribuiti su larga scala. Un algoritmo in MapReduce si basa su due costrutti di programmazione semplici ed eleganti, le funzioni map e reduce. Sebbene restrittivi, tali costrutti sono abbastanza potenti da poter esprimere task del mondo reale numerosi e di svariata natura.

I programmi scritti nello stile funzionale di MapReduce sono automaticamente parallelizzati e possono essere eseguiti su grandi cluster di computer. Il sistema si fa carico del partizionamento dei dati di input, dello scheduling dei task sulle macchine del cluster e di possibili fallimenti di nodi del cluster, permettendo anche a programmatori con poca esperienza di utilizzare facilmente le risorse di grandi sistemi distribuiti.

Oltre a quella di Google, esistono varie implementazioni del modello MapReduce, tra cui Hadoop, l'implementazione open-source di Apache, integrata anche nell'infrastruttura per cloud computing di Amazon (Amazon EC2). Esistono inoltre numerosi sistemi che estondono e migliorano diversi aspetti di MapReduce (ad esempio, Spark).

Le tesi proposte in questo ambito spaziano da aspetti teorici ad aspetti progettuali e sperimentali, ed offrono ottime possibilità di ricerca:

Mining data streams

Supponete di voler mantenere delle statistiche sul traffico instradato in Internet da un backbone server. La quantità di dati che potreste trovarvi ad osservare ogni giorno può facilmente raggiungere l'ordine dei GigaByte: questi dati passano attraverso il server pacchetto per pacchetto, come uno stream continuo e possibilmente infinito. E' improbabile, o addirittura impossibile, che abbiate a disposizione una memoria abbastanza grande per mantenere informazioni su ciascun pacchetto (ad esempio, l'origine e la destinazione). Un approccio più naturale sarebbe di processare ogni elemento dello stream nel momento in cui è generato e scartarlo successivamente, mantenendo quindi solo uno sketch dei dati osservati.

Ma cosa è possibile calcolare se non possiamo neppure memorizzare l'input? Algoritmi che eseguono una sola passata sequenziale sui dati ed usano una quantità limitata di memoria di lavoro centrale sono detti algoritmi di streaming. Nonostante le pesanti restrizioni sulle risorse di spazio e di tempo imposte dal modello di data stream, molti problemi di sintesi dei dati e calcolo di statistiche sono stati affrontati con successo.

Oltre al controllo del traffico di rete, applicazioni rilevanti per algoritmi di streaming includono il monitoraggio delle chiamate telefoniche, di aste on-line, di operazioni bancarie, di eventi atmosferici ed astronomici, e l'analisi dinamica del software: tool come profiler, debugger, sistemi per intrusion detection devono monitorare il traffico sui bus di dati e di indirizzi a tassi dell'ordine di molti MB al secondo, avendo il minimo impatto sulle prestazioni dell'applicazione monitorata.

L'obiettivo delle tesi proposte in questo ambito è di studiare, implementare, ingegnerizzare ed analizzare sperimentalmente alcuni di questi algoritmi, con particolare riferimento al loro uso nell'ambito dell'analisi dinamica dei programmi.

Algoritmi tolleranti ad errori di memoria

Una classica assunzione nella progettazione e nell'analisi di correttezza degli algoritmi è che il contenuto della memoria non cambi durante l'esecuzione di un algoritmo se non quando sia esplicitamente sovrascritto dall'algoritmo stesso. Le memorie poco costose e di grandi dimensioni usate in alcune moderne piattaforme di calcolo sono però soggette ad errori (bit-flip) che potrebbero modificare il contenuto di alcune locazioni in maniera impredicibile ed irreparabile. In tali circostanze, il comportamento degli algoritmi e delle strutture dati classiche (come quelli studiati nei corsi di Algoritmi I e II) può essere del tutto compromesso. Cosa accade, ad esempio, nell'algoritmo di ricerca binaria se alcuni valori dell'array si alterano? O in una lista concatenata se anche un solo puntatore si corrompe?

Le tesi proposte in questo ambito prevedono lo studio di modelli di calcolo che prendono in considerazione il verificarsi di errori di memoria, la progettazione di nuovi algoritmi tolleranti ad errori di memoria, e/o l'implementazione, il tuning e l'analisi sperimentale di algoritmi noti.