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.
Studio e sviluppo di algoritmi distribuiti per grafi di grandi dimensioni
L¿attività di ricerca si concentrerà sullo sviluppo di una libreria di algoritmi distribuiti per grafi di grandi dimensioni. Si prenderà spunto dalle soluzioni presenti in letteratura, riformulandole attraverso il paradigma MapReduce ed implementandole sulla piattaforma Spark per mezzo del modello di programmazione Pregel, a sua volta basata sullo scambio di messaggi tra i vertici di un grafo distribuito. La libreria andrà ad integrarsi con il supporto attualmente presente in Spark, fornendo alla comunità scientifica la possibilità di adoperare i nuovi algoritmi, compatibilmente con le applicazioni già realizzate in passato e senza dover richiedere nozioni di programmazione distribuita.
Al fine di validare sperimentalmente il lavoro realizzato e consentire un reale miglioramento rispetto a strumenti esistenti in letteratura, sarà inoltre condotta una fase di analisi sperimentale nella quale si metteranno a confronto le prestazioni degli algoritmi realizzati con quelle di algoritmi equivalenti codificati all¿interno della piattaforma Neo4J. Quest¿ultima rappresenta la più evoluta implementazione ad oggi esistente di un database non distribuito basato su grafi ed implementa numerose soluzioni per il trattamento di istanze di grandi dimensioni in memoria secondaria. Scopo dell¿indagine sarà quindi quello di attestare la scalabilità delle soluzioni prodotte, misurarne i vantaggi rispetto alla soluzione non distribuita basata su Neo4J ed ottimizzarne le prestazioni per consentirne un reale utilizzo.
Studio di algoritmi concreti per la soluzione di problemi NP-completi
Analizzare gli algoritmi attraverso le dimostrazioni permette la verifica dei calcoli. Un programma può contenere errori, e anche se fosse verificato formalmente il contrario, l'esecuzione potrebbe comunque essere difettosa. La dimostrazione prodotta certifica la computazione stessa. In questo progetto tuttavia vogliamo guardare le dimostrazioni da un angolo meno ovvio: la loro relazione con la complessità computazionale.
L'uso della proof complexity per l'analisi degli algoritmi ha avuto un grande ruolo nell'evoluzione e l'analisi dei SAT solver e degli algoritmi basati sulla programmazione semidefinita positiva, tuttavia il successo è molto più limitato nel caso di algoritmi algebrici (basati su polinomial calculus) o dei solutori di programmi lineari interi.
Nel caso degli algoritmi algebrici non è ancora chiaro come renderli efficienti al di fuori di applicazioni molto specifiche. Idee che sono vantaggiose dal punto di vista teorico [deRezende et al. '21] in pratica non lo sono affatto. Uno studio in questo senso è necessario per migliorare la tecnologia di questi algoritmi, o per lo meno per poter analizzare meglio il loro comportamento.
I solutori di programmi lineari interi sono invece molto efficienti dal punto di vista pratico ma non è esattamente chiaro quali sono le idee che funzionano veramente. Lo studio delle dimostrazioni nel formato "Stabbing Plane" aiutare in questo senso.
Studio di algoritmi di massimo flusso e multiple-pairs shortest-paths su grafi planari.
Lo studio dei problemi di flusso su grafi planari, oltre ai risultati strettamente attinenti a problemi di flusso e di vitalità, ha ricadute sulla definizione di algoritmi per percorsi minimi, sia in contesti statici che dinamici.
Sono già in corso, da parte dei partecipanti al progetto, studi sulle caratteristiche di cammini minimi tra più coppie di vertici e sulla struttura del sottografo unione di tali cammini. Un problema analogo è stato studiato in [Takahashi], asserendo che l'unione dei cammini minimi tra k coppie di vertici sulla faccia esterna è una foresta. Questa affermazione è stata confutata dai partecipanti al progetto di ricerca attraverso l'individuazione di semplici controesempi, e sono in fase avanzata tentativi di caratterizzazione del grafo unione dei cammini minimi. Un risultato positivo in tal senso permetterebbe di applicare algoritmi efficienti per il calcolo di distanze (basati ad esempio sulla ricerca di least common ancestor in un albero) al grafo unione dei cammini minimi.