Irene Finocchi

Prove finali e tesi di laurea

Una classica assunzione nella progettazione e nell'analisi di correttezza degli algoritmi e' 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 pero' 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) puo' 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 hanno natura sia compilativa (studio di modelli di calcolo che prendono in considerazione il verificarsi di errori di memoria) che sperimentale (tesi teoriche che prevedono la progettazione di nuovi algoritmi tolleranti ad errori di memoria, o tesi progettuali che prevedono l'implementazione, il tuning e l'analisi sperimentale di algoritmi noti).

Supponete di voler mantenere delle statistiche sul traffico instradato in Internet da un backbone server. La quantita' di dati che potreste trovarvi ad osservare ogni giorno puo' 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 memorizzare informazioni su ciascun pacchetto (ad esempio, l'origine e la destinazione). Un approccio piu' naturale sarebbe di processare ogni elemento dello stream nel momento in cui e' generato e scartarlo successivamente, mantenendo quindi solo uno sketch dei dati osservati. Algoritmi che operano eseguendo una (o poche) passate sequenziali sui dati ed usano una quantita' limitata di memoria di lavoro centrale sono detti algoritmi di streaming. Oltre al controllo del traffico di rete, altre applicazioni rilevanti includono il monitoraggio delle chiamate telefoniche, di aste on-line, di operazioni bancarie, di eventi atmosferici ed astronomici.

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. L'obiettivo delle tesi proposte in questo ambito e' lo studio, l'implementazione e l'analisi sperimentale di alcuni di questi algoritmi.

Il problema del calcolo del massimo flusso e' un classico problema di ottimizzazione combinatoria con innumerevoli applicazioni ed e' stato studiato fin dagli anni '60. Recentemente sono stati ottenuti alcuni miglioramenti teorici molto significativi, ad esempio per reti con capacita' unitarie e reti con capacita' intere non troppo grandi.

Le tesi proposte in questo ambito richiedono lo studio di alcuni di questi algoritmi (dovuti a ricercatori del calibro di Andrew Goldberg, David Karger, Satish Rao), e la loro implementazione ed analisi sperimentale su dati di test sintetici e reali.

I moderni ambienti di programmazione offrono tipicamente tool che producono in maniera automatica visualizzazioni di diversi aspetti statici del software, come grafi delle chiamate a funzione o diagrammi delle classi. Visualizzare il comportamento dinamico di un programma e' invece molto piu' difficile, poiche' richiede di monitorare continuamente l'ambiente di esecuzione ed aggiornare la visualizzazione consistentemente.

Il Leonardo Computing Environment e' progettato come un'architettura aperta, object-oriented, multi-piattaforma che integra in un framework unitario diverse tecniche per il debugging e la visualizzazione del software. In particolare, e' basato sul linguaggio di programmazione Vinci, che estende il linguaggio C con caratteristiche dei linguaggi dichiarativi ed orientati agli oggetti. L'ambiente e' correntemente sviluppato in Windows e Linux, ed informazioni specifiche possono essere reperite seguendo questo link.

Le tesi proposte in questo ambito prevedono lo sviluppo di specifiche parti del Leonardo Computing Environment, lavorando in C e/o nel linguaggio Vinci. Si richiedono dimestichezza con il C e buone capacita' implementative.