Home page di Marco Liverani

Tesi di laurea in Matematica

“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.

  1. Daniela Fabrianesi, Un problema di cammino minimo ed una sua applicazione al World Wide Web, Novembre 1999

    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]

  2. Massimiliano Lorenzoni, Partizionamento ottimo di grafi ed applicazioni, Novembre 2000

    Studio di algoritmi per il partizionamento di grafi con applicazioni sull'ottimizzazione del contrasto su immagini digitali. [Sintesi]

  3. Patrizia Bellini, Recenti evoluzioni degli algoritmi di ottimizzazione discreta su reti di flusso con applicazioni, Novembre 2000

    Studio degli algoritmi classici e di quelli proposti più recentemente per problemi di ottimizzazione del flusso su una rete. [Sintesi]

  4. Patrizia Tropea, Immersione di grafi planari su griglie, Luglio 2001

    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.

  5. Cristiana Vigliaroli, Tecniche per il calcolo scientifico distribuito in Java, Novembre 2001

    Implementazione distribuita di algoritmi di calcolo numerico in linguaggio Java, con l'utilizzo della tecnologia RMI (remote method invocation). [Sintesi]

  6. Amelia Di Maio, Segmentazione di immagini a colori per lo studio del degrado di materiali lapidei, Febbraio 2002

    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.

  7. Giulio Simeone, Barriere assorbenti nelle Catene di Markov e una loro applicazione al Web, Luglio 2002

    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]

  8. Davide Rossi, Metodi di ottimizzazione per problemi di distribuzione, Luglio 2003

    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]

  9. Luca Rapposelli, Algoritmi genetici applicati a problemi di partizionamento su alberi, Ottobre 2003

    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]

  10. Giulio Zabeo, Tecniche di voting e di co-training per la disambiguazione semantica di parole in testi liberi, Ottobre 2003

    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.

  11. Maria Rosaria Montalto, Modellizzazione di una costellazione di satelliti tramite le Reti di Petri, Luglio 2004

    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]

  12. Barbara Burchielli, Studio del comportamento di grafi sotto l'applicazione iterata dell'operatore clique, Ottobre 2004

    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]

  13. Maria Cristina Brivio, Catene di Markov e pagerank di Google, Febbraio 2005

    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.

  14. Valentina Mei, Analisi e valutazione di un algoritmo di pianificazione per reti di telecomunicazione a qualità del servizio garantito, Maggio 2005

    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]

  15. Letizia Monaldi, Matching su grafi e alcune varianti del problema del matrimonio stabile, Maggio 2005

    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]

  16. Irene Olivieri, Problemi di ottimizzazione combinatoria ed algoritmi per il physical mapping del DNA, Maggio 2006

    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]

  17. Francesca Caselli, Problemi ed algoritmi per il riconoscimento e la costruzione di grafi self-clique, Luglio 2007

    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à.

  18. Natascia Piroso, Strategie risolutive e algoritmi per problemi di partizionamento ottimo di grafi, Luglio 2007

    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]

  19. Stefano Spensieri, Metodi e algoritmi per il Graph Drawing, Ottobre 2009

    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]

  20. Matteo Acclavio, Algoritmi efficienti per la soluzione del problema Clique, Febbraio 2011

    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.

  21. Laura Tiburzi, Modelli, algoritmi e strumenti per la sicurezza dei sistemi informativi complessi, Maggio 2011

    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]

  22. Marcello Caucci, Un algoritmo per il calcolo di tutte le soluzioni del Problema del Matrimonio Stabile, Febbraio 2013

    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.

  23. Chai Botta, The minimum spanning tree in a directed graph, Luglio 2013

    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.

  24. Matteo D'Angelo, Graph-Based Sybil Detection: a caccia di falsi profili nel grafo di un Social Network, Gennaio 2016

    La tesi, in collaborazione con il dott. Stefano Guarino, 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]

Author: Marco Liverani - Last modified: Saturday January 30, 2016 - URI: http://www.mat.uniroma3.it/users/liverani/tesi.shtml