Ricerc@Sapienza

La progressiva digitalizzazione dei processi produttivi e la definitiva trasformazione della nostra in una società basata sulla comunicazione stanno rendendo sempre più rilevante il ruolo assunto nella nostra vita dagli algoritmi e dalla loro capacità di anticipare, supportare o surrogare le nostre scelte.

La pervasività dello strumento algoritmico si scontra con l¿enorme mole di dati da analizzare, e con l¿esigenza di fornire risposte tempestive ed accurate. Da qui l¿esigenza di sviluppare strumenti con i quali caratterizzare, sempre più precisamente e concretamente, l¿efficienza di determinati algoritmi, specie se usati nella risoluzione di problemi difficili. Si rende poi necessario sviluppare nuovi approcci risolutivi, anche a problemi ampiamente studiati in letteratura, che sfruttino nuovi paradigmi di calcolo per garantire tempi di risposta altrimenti non ottenibili su questa scala.

In accordo a tale premessa, il progetto prevede tre direttrici:

-Studio e sviluppo di algoritmi distribuiti per grafi di grandi dimensioni. Si considerano diversi problemi algoritmici su grafo, per i quali si intendono sviluppare soluzioni efficienti basate su sistemi distribuiti. L¿efficienza delle soluzioni sviluppate sarà misurata confrontandone le prestazioni sperimentali con lo stato dell¿arte delle equivalenti soluzioni non distribuite.

-Studio di algoritmi concreti per la soluzione di problemi NP-completi. Scopo di questa attività è dimostrare che esistono problemi computazionali difficili, anche quando non ci sia una teoria come l'NP-completezza a supporto. Lo sono, ad esempio, per il tipo di algoritmi e strumenti adottati per risolverli.

-Studio di algoritmi di massimo flusso e multiple-pairs shortest-paths su grafi planari.
Ci si propone di estendere a grafi planari, eventualmente con limitazioni sui pesi, algoritmi noti per il calcolo di vitalità di nodi ed archi rispetto al flusso su grafi st-planari.