“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]
Il problema Clique è notoriamente NP-completo: dato un grafo G=(V,E) e un intero positivo k, il problema chiede di verificare l'esistenza in G di un sottografo completo con k vertici, una clique di grado k. L'argomento della tesi è stato quello di studiare alcuni dei proncipali algoritmi esatti ed euristici per la soluzione del problema Clique: tra questi l'algoritmo Cliquer (un noto algoritmo efficiente per la ricerca esaustiva delle clique di grado k su un grafo G) ed un algoritmo originale di carattere esaustivo, oltre ad alcuni algoritmi approssimati che sfruttano approcci di tipo Montecarlo, di smantellamento (dismantling) e greedy.
Un moderno sistema informativo aziendale è spesso costituito da un insieme ampio ed eterogeneo di sistemi informatici connessi fra loro in rete, in grado di offrire servizi agli utenti implementando architetture differenti che coesistono sullo stesso ambiente. Il problema di garantire la sicurezza informatica in un simile contesto è assai complesso: in particolare per quanto riguarda la garanzia della riservatezza delle informazioni, si può focalizzare l'attenzione sulle procedure di autenticazione e di autorizzazione degli utenti. Tali processi possono essere semplificati (dal punto di vista tecnico e gestionale) mediante l'introduzione di infrastrutture di Identity and Access Management. Questi sistemi consentono di applicare all'intero sistema informativo il concetto di “controllo degli accessi basato sui ruoli” (RBAC - Role Based Access Control), che semplifica moltissimo la gestione dei permessi assegnati agli utenti per l'accesso a specifiche funzionalità offerte dalle diverse applicazioni.
Nella tesi, a valle di una descrizione ampia ed articolata delle differenti architetture di un sistema informativo aziendale e delle principali tecniche per consolidare la sicurezza del sistema stesso, si affronta il problema della definizione dei ruoli, mediante algoritmi di role mining, che ci consentono di affrontare il problema con tecniche di ottimizzazione combinatoria su grafi. [Sintesi|Slide]
Il Problema del Matrimonio Stabile (Stable Marriage Problem) è un problema classico di teoria dei giochi in cui si cerca un matching stabile secondo un determinato criterio, tra gli elementi di due insiemi distinti. È stato studiato fin dal 1962 quando David Gale e Lloyd Shapley, in un famoso articolo, proposero un algoritmo con cui si dimostrava la possibilità di individuare sempre una soluzione del problema. Questi studi, tra l'altro, sono valsi a Lloyd Shapley (insieme ad Alvin Roth) il Premio Nobel per l'Economia nel 2012. Nel 1971 McVitie e Wilson pubblicarono un algoritmo che consentiva di individuare tutte le soluzioni di una determinata istanza del problema del matrimonio stabile. Il problema, le sue generalizzazioni ed in particolare l'algoritmo di McVitie e Wilson sono l'argomento trattato in questa tesi.
Il problema dell'albero ricoprente di peso minimo è un problema classico di informatica e ottimizzazione combinatoria, che trova numerosissime applicazioni pratiche. Il problema classico è istanziato su un grafo non orientato; in questa tesi è stato studiato l'algoritmo di Chu-Liu-Edmonds per la costruzione di un albero ricoprente di peso minimo con radice su un grafo orientato, proponendone poi un'implementazione in Java come applicazione mobile in ambiente Android.
La tesi, in collaborazione con il dott. Stefano Guarino dello IAC/CNR, affronta il tema dell'individuazione di falsi profili nella rete di un social network, utilizzati per “attaccare” i profili onesti, influenzandoli o introducendo informazioni non pertinenti nell'ambito di una comunità di profili onesti. Le tecniche di individuazione dei falsi profili possono basarsi sul machine learning o su algoritmi, analizzati nell'ambito della tesi, basati sullo studio di alcune proprietà del grafo, come la conduttanza, o delle passeggiate aleatorie sul grafo stesso, come il tempo di mixing. [Sintesi|Slide]
La tesi di laurea magistrale in Scienze Computazionali, in collaborazione con il dott. Stefano Guarino dello IAC/CNR, affronta alcuni problemi di ottimizzazione combinatoria su grafi legati alla misurazione dell'influenza in un social network, formalizzando un modello e affrontando la soluzione per via algoritmica del cosiddetto Critical Node Detection Problem e del Influence Maximisation Problem; in particolare su quest'ultimo problema sono state realizzate delle simulazioni su grafi di grandi dimensioni. [Sintesi]
La tesi di laurea magistrale in Scienze Computazionali, in collaborazione con il dott. Stefano Guarino dello IAC/CNR, affronta lo studio della teoria assiomatica per la definizione del concetto di centralità su un grafo; gli assiomi presi in esame (Garg, Vigna e Boldi), da un punto di vista computazionale hanno risvolti differenti e non pienamente soddisfacenti; sono stati quindi proposti degli assiomi che generalizzano in parte definizioni precedenti, per superare alcuni dei limiti degli assiomi di Vigna e Boldi. [Sintesi]
La tesi di laurea magistrale in Matematica affronta il problema del password guessing a partire da un insieme di hash di password di un sistema informatico; applicando l'uso delle reti neurali GAN (generative adversarial network), viene studiato ed implementato con successo un approccio basato sul deep learning proposto nel 2019 da Ateniese ed altri. [Sintesi|Slide]
La tesi di laurea di primo livello in Matematica, affronta il problema dell'equipartizionamento ottimo di grafi con pesi non negativi assegnati ai vertici, con funzioni obiettivo Max-Min, Norma L1, Norma L2 e Norma L∞; vengono studiati gli algoritmi per la risoluzione del problema su cammini, applicando questo modello alla riduzione del numero di colori in un'immagine grafica digitale ad alta risoluzione, con l'intento di non deteriorare il contrasto dell'immagine stessa.
La tesi ha affrontato lo studio dell'algoritmo di Becker, Perl e Schach per il partizionamento di un albero con pesi assegnati ai vertici in p componenti connesse (sottoalberi) con l'obiettivo di minimizzare il peso della componente di peso massimo.
Un grafo planare è un grafo che è possibile disegnare sul piano senza mai intersecare due spigoli. La tesi ha affrontato lo studio dell'algoritmo Hopcroft e Tarjan del 1974, nella versione rivisitata da Kokay nel 1993, per determinare se un grafo è planare o meno.
Una buona colorazione di un grafo è una assegnazione del minimo numero di colori differenti ai suoi vertici, in modo tale che a nessuna coppia di vertici adiacenti sia assegnato lo stesso colore. Il numero cromatico di un grafo, indicato con χ(G), è il minimo numero di colori con cui può essere colorato un grafo. Nella tesi sono stati studiati il teorema del “cinque colori” e il teorema dei “quattro colori” e sono state analizzate le tecniche algoritmiche greedy e branch & bound per la colorazione di un grafo.
L'immersione su una griglia di un grafo planare è una rappresentazione del grafo ottenuta collocando i vertici nelle intersezioni delle linee di una griglia bidimensionale (un foglio a quadretti) e rappresentando gli spigoli come linee spezzate disposte lungo le linee della griglia. Non tutti i grafi planari possono essere rappresentati su una griglia bidimensionale; il problema ha una notevole ricaduta applicativa nella progettazione di circuiti elettronici integrati di grandi dimensioni. Nella tesi è stato affrontato lo studio di un algoritmo proposto da Aurora Morgana ed altri nel 2004, per costruire, se esiste, una rappresentazione di un grafo planare su una griglia bidimensionale, con il vincolo di operare al più una sola piega sugli spigoli del grafo.