Circolazioni e omologia dei grafi

In questa tesi verrà trattato il problema di introdurre una teoria omologica sui grafi. Si vedranno i grafi come un 1-complessi simpliciali, e dunque l'idea sarà di applicare le conoscenze che si hanno di una teoria omologica generale ad un oggetto specifico, che è appunto il grafo.

Analisi di grafi su architetture a memoria distribuita

Questo lavoro di tesi tratta il tema delle reti complesse, mostrando i principali modelli di rete complessa quali: il modello Random, il modello Small-World ed il modello Scale-free; si introdurranno alcune metriche usate per descrivere le reti complesse quali la Degree centrality, la Closeness centrality e la Betweenness centrality; si descriveranno i problemi da tenere in considerazione durante la definizione e l’implementazione di algoritmi su grafi; i modelli di calcolo su cui progettare gli algoritmi per risolvere i problemi su grafi; un’analisi prestazionale degli algoritmi proposti per calcolare i valori di Beweenness centrality su grafi di medio-grandi dimensioni. Parte di questo lavoro di tesi è consistito nello sviluppo di LANA, LArge-scale Network Analyzer, un software che permette il calcolo e l’analisi di varie metriche di centralità su grafo.

Hemiklonale Vererbung im hybridogenetischen Rana grafi-Komplex (Anura: Ranidae)

Hemiklonale Vererbung im hybridogenetische Rana grafi-Komplex (Anura: Ranidae)Im Rahmen der vorliegenden Studie wurde eine großflächige Untersuchung an südfranzösischen Wasserfröschen durchgeführt. Es wurden 31 Populationen mit 918 Tieren beprobt und mit Referenzproben genetisch verglichen. Die Genotypen der Tiere wurden mittels Allozymelektrophorese an sieben diagnostischen Loci bestimmt. Für Teilproben wurde das Alter, die Fläche der Erythrocyten und der DNA-Gehalt bestimmt. Die wichtigsten Ergebnisse der unterschiedlichen methodischen Ansätze lassen sich wie folgt zusammenfassen:(1) Es wurden neben einem großen Anteil von R. grafi (452 Tiere), R. perezi (200 Tiere) und R. ridibunda (254 Tiere) auch ein R. esculenta und zwei R. lessonae in der Camargue nachgewiesen.(2) Die Geschlechterverhältnisse der einzelnen Taxa waren stark gestört. Dies gilt besonders für den Hybriden R. grafi mit einem Männchenanteil von nur 7,3%. Das Geschlechterverhältnis von R. ridibunda ist besonders in PGR-Population zu Gunsten von Weibchen verschoben. Eine Modellierung von Populationen zeigt, daß wahrscheinlich R. grafi-Männchen durch eine gestörte Gametogenese für die gestörten Geschlechtsverhältnisse seiner Parentalformen verantwortlich ist.(3) Die genetische Analyse zeigt eine unerwartet hohe genetische Variabilität von R. ridibunda im Vergleich zu R. perezi und eine geographische Varianz der genetischen Variabilität in allen untersuchten Taxa. Die genetische Variabilität zeigte bei allen Wasserfroschformen in der Camargue ein Maximum.(4) Die hohe genetische Variabilität geht hauptsächlich, neben Einführung von verschiedenen genetischen R. ridibunda-Linien, auf Introgression zurück.

Ottimalità dell'ottimalità - Complessità della riduzione su grafi di condivisione

Trent’anni or sono il concetto di ottimalità venne formulato in senso teorico da Lévy, ma solo un decennio dopo Lamping riesce a darne elegante implementazione algoritmica. Realizza un sistema di riduzione su grafi che si scoprirà poi avere interessanti analogie con la logica lineare presentata nello stesso periodo da Girard. Ma l’ottimalità è davvero ottimale? In altre parole, l’implementazione ottimale del λ calcolo realizzata attraverso i grafi di condivisione, è davvero la migliore strategia di riduzione, in termini di complessità? Dopo anni di infondati dubbi e di immeritato oblìo, alla conferenza LICS del 2007, Baillot, Coppola e Dal Lago, danno una prima risposta positiva, seppur parziale. Considerano infatti il caso particolare delle logiche affini elementare e leggera, che possiedono interessanti proprietà a livello di complessità intrinseca e semplificano l’arduo problema. La prima parte di questa tesi presenta, in sintesi, la teoria dell’ottimalità e la sua implementazione condivisa. La seconda parte affronta il tema della sua complessità, a cominciare da una panoramica dei più importanti risultati ad essa legati. La successiva introduzione alle logiche affini, e alle relative caratteristiche, costituisce la necessaria premessa ai due capitoli successivi, che presentano una dimostrazione alternativa ed originale degli ultimi risultati basati appunto su EAL e LAL. Nel primo dei due capitoli viene definito un sistema intermedio fra le reti di prova delle logiche e la riduzione dei grafi, nel secondo sono dimostrate correttezza ed ottimalità dell’implementazione condivisa per mezzo di una simulazione. Lungo la trattazione sono offerti alcuni spunti di riflessione sulla dinamica interna della β riduzione riduzione e sui suoi legami con le reti di prova della logica lineare.

Modelli e linguaggi per grafi multi-livello

I grafi sono molto utilizzati per la rappresentazione di dati, sopratutto in quelle aree dove l’informazione sull’interconnettività e la topologia dei dati è importante tanto quanto i dati stessi, se non addirittura di più. Ogni area di applicazione ha delle proprie necessità, sia in termini del modello che rappresenta i dati, sia in termini del linguaggio capace di fornire la necessaria espressività per poter fare interrogazione e trasformazione dei dati. È sempre più frequente che si richieda di analizzare dati provenienti da diversi sistemi, oppure che si richieda di analizzare caratteristiche dello stesso sistema osservandolo a granularità differenti, in tempi differenti oppure considerando relazioni differenti. Il nostro scopo è stato quindi quello di creare un modello, che riesca a rappresentare in maniera semplice ed efficace i dati, in tutte queste situazioni. Entrando più nei dettagli, il modello permette non solo di analizzare la singola rete, ma di analizzare più reti, relazionandole tra loro. Il nostro scopo si è anche esteso nel definire un’algebra, che, tramite ai suoi operatori, permette di compiere delle interrogazioni su questo modello. La definizione del modello e degli operatori sono stati maggiormente guidati dal caso di studio dei social network, non tralasciando comunque di rimanere generali per fare altri tipi di analisi. In seguito abbiamo approfondito lo studio degli operatori, individuando delle proprietà utili per fare delle ottimizzazioni, ragionando sui dettagli implementativi, e fornendo degli algoritmi di alto livello. Per rendere più concreta la definizione del modello e degli operatori, in modo da non lasciare spazio ad ambiguità, è stata fatta anche un’implementazione, e in questo elaborato ne forniremo la descrizione.

Dbms basati sui grafi: Analisi e prototipazione di neo4j.

L’obiettivo di questa tesi è quello di mettere a confronto due mondi: quello dei DBMS relazionali e quello dei DBMS a grafo, con lo scopo di comprendere meglio quest'ultimo. Perciò, sono state scelte le due tecnologie che meglio rappresentano i loro mondi: Oracle per gli RDBMS e Neo4j per i Graph DBMS. I due DBMS sono stati sottoposti ad una serie di interrogazioni atte a testare le performance al variare di determinati fattori, come la selettività, il numero di join che Oracle effettua, etc. I test svolti si collocano nell'ambito business intelligence e in particolare in quello dell’analisi OLAP.

Topologia dei complessi simpliciali casuali

La presente tesi si propone di fornire un breve compendio sulla teoria dei complessi casuali, ramo di recente sviluppo della topologia algebrica applicata. Nell'illustrare i risultati più significativi ottenuti in tale teoria, si è voluto enfatizzare le modalità che permettono di affrontare con strumenti probabilistici lo studio delle proprietà topologiche ed algebriche dei complessi casuali.