“Ogni tanto è necessario dire delle cose difficili,
ma bisognerebbe dirle nel modo più semplice di cui si è capaci.”
−− Godfrey H. Hardy
Di seguito una breve descrizione delle tesi di laurea su argomenti di Informatica e Ottimizzazione Combinatoria dei miei studenti del Corso di Laurea in Matematica che ho seguito come relatore.
Studio dei principali algoritmi on-line per la visita di un grafo al fine di costruire uno spider in grado di analizzare la struttura dei collegamenti di un insieme di pagine presenti sul World Wide Web. [Sintesi]
Studio di algoritmi per il partizionamento di grafi con applicazioni sull'ottimizzazione del contrasto su immagini digitali. [Sintesi]
Studio degli algoritmi classici e di quelli proposti più recentemente per problemi di ottimizzazione del flusso su una rete. [Sintesi]
Studio e implementazione di algoritmi per la rappresentazione di grafi planari su griglie bidimensionali, anche con l'obiettivo di ridurre il numero di "piegature" degli spigoli del grafo.
Implementazione distribuita di algoritmi di calcolo numerico in linguaggio Java, con l'utilizzo della tecnologia RMI (remote method invocation). [Sintesi]
Studio di algoritmi per l'analisi di immagini grafiche tridimensionali. La tesi è stata realizzata in collaborazione con la Dott.ssa Rossella Cossu dello IAC-CNR.
Studio e implementazione di algoritmi in grado di stimare, con l'utilizzo della teoria delle catene di Marcov, il comportamento di un visitatore di un sito web, al fine di individuare le pagine più rilevanti all'interno del sito. [Slide]
La tesi, svolta in collaborazione con Poste Italiane, ha analizzato ed implementato gli algoritmi classici per problemi di distribuzione, producendo anche uno strumento software di simulazione scritto in linguaggio Java. [Sintesi|Slide]
Studio degli algoritmi genetici e applicazione al problema del partizionamento di alberi in componenti connesse, sulla base di differenti funzioni obiettivo che le componenti della partizione devono, a seconda dei casi, massimizzare o minimizzare. [Slide]
La tesi, svolta in collaborazione con il prof. Roberto Basili della Facoltà di Ingegneria dell'Università degli Studi di Roma "Tor Vergata", ha affrontato lo studio e la realizzazione di un complesso sistema per l'individuazione del significato semantico di testi liberi in lingua inglese.
La tesi, svolta in collaborazione con la prof.ssa Elisabetta Scoppola e con la dott.ssa Beatrice Ratti di Alenia Spazio, ha affrontato lo studio delle Reti di Petri e la costruzione di un modello di rete applicato alla modellizzazione del processo di gestione del ciclo di vita di una costellazione di satelliti geostazionari. [Sintesi|Slide]
Il grafo K(G) è il grafo ottenuto come intersezione delle clique di G. La tesi ha affrontato lo studio del comportamento di specifiche classi di grafi sottoposte all'applicazione iterata di tale operatore, analizzando in particolare il comportamento della cardinalità dell'insieme dei vertici del grafo. [Sintesi|Slide]
Studio degli algoritmi utilizzati dal motore di ricerca Google per classificare ed associare un indice denominato "page-rank" alle pagine del World Wide Web, al fine di individuare quelle più rilevanti. La tesi è stata svolta in collaborazione con il prof. Fabio Martinelli, relatore della tesi di laurea.
Studio di particolari strumenti teorici di network calculus per la stima e la simulazione del comportamento di reti di telecomunicazione satellitari, utilizzate per il trasporto di dati di tipo multimediale. La tesi è stata svolta in collaborazione con l'ing. Francesco Fedi e l'ing. Alessandro Pacaccio dell'azienda SSI (Space Software Italia), presso Alenia Spazio. [Slide]
Il problema del "matrimonio stabile" è un problema di matching classico, studiato a più riprese da diversi ricercatori di chiara fama (tra gli altri anche D. Knuth) fin dagli anni '60. La tesi ha affrontato lo studio e l'implementazione di alcuni algoritmi proposti di recente per la soluzione di istanze del problema con specifici vincoli caratteristici. [Sintesi|Slide]
Gli studi nel campo della biologia molecolare hanno portato negli ultimi anni ad affrontare problemi la cui complessità non è più soltanto di carattere chimico o biologico, ma anche di tipo computazionale: lo studio delle sequenze di DNA, alla base dell'analisi dei meccanismi di trasmissione delle caratteristiche genetiche all'interno di una stessa specie, può essere ricondotto infatti ad istanze di problemi di carattere combinatorio su un insieme di elementi di cardinalità elevatissima. Pertanto è di notevole interesse verificare come dallo studio di caratteristiche biologico-chimiche delle molecole del nostro organismo si possa passare ad affrontare problemi di ottimizzazione combinatoria o di teoria dei grafi. [Sintesi|Slide]
Dato un grafo G si definisce il grafo K(G) come il grafo intersezione delle clique di G; se G è isomorfo a K(G) (ad esempio come nel caso banale del ciclo C4) allora si dice che il grafo G è self-clique. La tesi affronta lo studio di alcune proprietà che conducono a delle condizioni sufficienti affinché un determinato grafo sia self-clique ed altre che consentono di attuare un procedimento costruttivo per ottenere un grafo dotato di tale proprietà.
Una partizione π di un grafo G in p componenti connesse è definito come una partizione dell'insieme dei vertici di G tale che ogni sottoinsieme della partizione induca un sottografo di G connesso. La ricerca della partizione può essere condizionata alla ricerca del valore ottimo di una funzione obiettivo f(π) calcolata in base alla partizione del grafo stesso. Si ottiene in questo modo un'interessante ed ampia classe di problemi di ottimizzazione combinatoria, utilizzati in numerosi contesti applicativi. L'argomento, che riveste una certa importanza nell'ambito dell'ottimizzazione combinatoria anche per le numerose e rilevanti ricadute applicative, è stato affrontato nel corso degli anni sotto numerosi punti di vista e con diversi obiettivi (Aparo, Becker, Lucertini, Pallottino, Perl, Simeone ed altri) migliorando e specializzando i primi risultati presenti in letteratura fin dagli anni '70. La tesi ha affrontato diversi problemi di partizionamento di cammini proponendo un'interessante generalizzazione dell'approccio basato sulla programmazione dinamica ed arrivando a proporre un algoritmo che migliora sensibilmente la complessità di precedenti algoritmi per la risoluzione del problema most uniform partition su cammini presenti in letteratura. [Sintesi|Slide]
Un grafo è spesso usato come un modello astratto per descrivere insiemi di oggetti e le relazioni fra di essi. Utilizzando un grafo per costruire il modello è possibile infatti identificare gli oggetti con i vertici del grafo e le “relazioni” o i “collegamenti” tra gli oggetti con gli spigoli del grafo. In questa tesi è stato affrontato il tema del Graph Drawing, ovvero della rappresentazione grafica dell'entità astratta grafo. A questo proposito è efficace la seguente affermazione: «Graph drawing is the art of drawing graphs in such a way that the relationship between the objects (in the graph) are easily understood by looking at the picture.»
L'argomento ha conosciuto uno sviluppo notevole negli ultimi anni, grazie soprattutto al crescente utilizzo di tecniche di disegno informatiche e la conseguente richiesta di algoritmi che automatizzassero la produzione dei disegni. Sono numerosi i punti di contatto con altre discipline e aree di studio, quali ad esempio l'Information Visualization, lo studio della percezione delle immagini, la topologia e la geometria dei grafi, la bioinformatica, la progettazione di interfacce per il disegno assistito. Nella tesi sono stati studiati algoritmi per la produzione automatica di layout specifici, ovvero layout che tengano conto di uno o più vincoli “estetici”, con una formulazione del problema in termini di ottimizzazione combinatoria. [Sintesi|Slide]
