Ricerc@Sapienza

La progressiva disponibilità di sempre più ingenti quantità di dati (Big Data) dovuta ai processi di informatizzazione e digitalizzazione in atto a livello mondiale nei campi più disparati della società e dell'economia motiva, in modo sempre più prepotente, la necessità di sviluppare algoritmi efficienti non solo teoricamente ma anche, e soprattutto, nella pratica. Questo trend sta rivoluzionando il modo stesso con cui si concepiscono e sviluppano gli algoritmi, favorendo l'ingresso di fattori che consentano di meglio predire e stimare l'efficienza sperimentale di un algoritmo. Si diffondono poi nuovi paradigmi di calcolo basati su sistemi distribuiti per risolvere determinati problemi ad una frazione del tempo necessario rispetto ad un sistema tradizionale.

Il progetto sviluppa queste tematiche secondo tre direttrici:

1. Estrazione efficiente di k-mers da sequenze genomiche. Si considera un problema algoritmico comune in ambito bioinformatico e per il quale esistono soluzioni teoricamente efficienti. Per tale problema si intendono sviluppare degli algoritmi basati sul calcolo distribuito per abbattere i tempi di risoluzione rispetto agli approcci tradizionali

2. Complessità computazionale della soddisfacibilità e di
problemi su grafi. Lo studio della complessità di un algoritmo può fallire nello stimare il tempo di esecuzione dello stesso su istanze reali. Si considera una particolare tipologia di problemi, basati su grafi, per i quali si intende studiare la possibilità di ottenere una stima più fedele dell'efficienza di un algoritmo, pur senza implementarlo, mediante l'uso della proof complexity.

3. Misure di vitalità su grafi planari. Numerosi dei problemi computazionalmente più complessi fanno riferimento a strutture modellabili come grafi di grandi dimensioni, quali reti di TLC o reti sociali. Si intendono studiare delle misure di vitalità che consentano di determinare la robustezza di un grafo planare rispetto ad eventi di disconnessione di nodi o archi.