Dipartimento di Ingegneria informatica, automatica e gestionale

Linee di ricerca:

• Principi di analisi e progetto di algoritmi
• Algoritmica sperimentale
• Algoritmi di streaming e su memoria esterna per elaborazione di grandi moli di dati
• Algoritmi incrementali e strutture di dati dinamiche
• Algoritmi approssimati e on-line
• Teoria algoritmica dei giochi

Membri:
Giorgio Ausiello (leader), Fabrizio D’Amore, Camil Demetrescu, Stefano Leonardi, Alberto Marchetti-Spaccamela,
Umberto Nanni.

Dottorandi:
Donatella Firmani.

Post Doc:
Aris Anagnostopoulos, Vincenzo Bonifaci, Luigi Laura, Andrea Ribichini, Piotr Sankowski.

Attività di ricerca nel campo del progetto e dell'ingegneria degli algoritmi si è svolta presso il DIS fin dalla sua fondazione nei primi anni ottanta. Nei primi anni l'enfasi è stata posta soprattutto sugli aspetti teorici come ad esempio quelli legati alla nozione di riduzione 'approximation preserving' tra problemi di ottimizzazione e alla classificazione dei problemi di ottimizzazione sulla base delle loro proprietà di approssimabilità. Successivamente le attività di ricerca si sono evolute in varie direzioni in base alla evoluzione delle tecnologie dell'informazione e delle loro applicazioni. Nuove tematiche sono quindi state affrontate, come ad esempio algoritmi per grafi dinamici, algoritmi on-line, algoritmi su memoria esterna ed algoritmi capaci di analizzare grandi moli di dati in modalità di streaming. Anche l'enfasi dell'approccio è mutata, passando, in molti casi, dalla tradizionale analisi del caso pessimo all'analisi delle prestazioni sperimentali.

I risultati recenti più rilevanti includono contributi nelle seguenti aree:
- Principi di analisi e progetto di algoritmi: tecniche di riottimizzazione per problemi combinatori; modelli di calcolo per grandi moli di dati.
- Algoritmica sperimentale: implementazione e ingegnerizzazione di algoritmi e strutture di dati evoluti per problemi su grafi.
- Algoritmi di streaming e su memoria esterna per elaborazione di grandi moli di dati: algoritmi su memoria esterna e algoritmi di streaming per grafi di grandi dimensioni.
- Algoritmi incrementali e strutture di dati dinamiche: algoritmi incrementali per problemi di percorso in grafi.
- Algoritmi approssimati e on-line: algoritmi di scheduling, algoritmi per reti metaboliche, instradamento di veicoli, algoritmi approssimati per problemi di progetto di reti nel modello 'rent-or-buy', algoritmi on line per problemi di ottimizzazione stocastica come albero di Steiner e copertura di insiemi.
- Teoria algoritmica dei giochi: qualità di equilibri in giochi di formazione di reti in modelli restrittivi di comunicazione. 

In futuro abbiamo in programma di affrontare problemi fondamentali che si presentano in applicazioni emergenti riguardanti analisi e ottimizzazione di sistemi software e reti, sistemi real-time scheduling e allocazione di risorse. Particolare enfasi sarà data allo studio di problemi su grandi moli di dati con l'uso di piattaforme multi-core. In particolare i nostri obiettivi di ricerca includono:
-  Algoritmi di streaming e su memoria esterna per elaborazione di grandi moli di dati: algoritmi su memoria esterna e in modalita' streaming per problemi che sorgono nella analisi dinamica di grandi sistemi software e reti. Fra gli altri obiettivi intendiamo studiare nuovi approcci alla determinazione e all'ottimizzazione delle prestazioni sulla base di tecniche di streaming dimostrabilmente efficienti.
- Algoritmi incrementali e strutture di dati dinamiche: in questo ambito studieremo tecniche di propagazione dei cambiamenti in sistemi a vincoli su piattaforme multi-core.
- Algoritmi approssimati e on-line: in questo ambito intendiamo studiare la complessità e l'approssimabilità di problemi combinatori di allocazione di risorse con un focus particolare su problemi di scheduling real-time. In particolare intendiamo analizzare e progettare test di ammissibilità per lo scheduling di task su piattaforme multiprocessore. Approfondiremo inoltre lo studio di algoritmi on line per problemi di ottimizzazione stocastica. Infine considereremo problemi di ottimizzazione multi-obiettivo nella progettazione di reti.

Progetti:
MAINSTREAM: Algorithms for massive information structures and data streams
Maggio 2007- Febbraio 2009  -  PRIN MIUR

AEOLUS: Algorithmic principles for building overlay computers
Dicembre 2005 - Dicembre 2010  -   EU FP6 - FET

FRONTS:  Foundations of Adaptive Networked Societies of Tiny Artefacts
Marzo 2008 - Marzo 2012  -   EU FP7 - FET

SIMBIOSI: INRIA associated team
Gennaio 2009 - Gennaio 2011  -  INRIA

(future) link to web page