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.

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.

Righe spettrali: formazione, shift ed allargamento

In questo breve elaborato si vuole spiegare l’importanza dello studio di un corpo celeste mediante l’osservazione del suo spettro ovvero un grafico del flusso emesso in funzione della frequenza o della lunghezza d’onda nel quale sono presenti righe spettrali, formate dall’interazione tra materia e radiazione, a causa dell’assorbimento od emissione di fotoni a seguito di transizioni elettroniche, ma anche vibrazionali e rotazionali per le molecole. In particolare, dall’analisi delle righe spettrali si traggono diverse informazioni sull’oggetto, quali, la composizione e l’abbondanza delle specie chimiche che lo compongono in base al tipo di righe presenti e alla loro intensità, si deduce la temperatura e la pressione dell’oggetto studiato dalla larghezza di queste, ancora, informazioni sul moto relativo e la distanza dall’osservatore misurando lo shift delle righe; infine densità e campi magnetici del mezzo interstellare. Per molti oggetti astronomici, troppo distanti, lo studio dello spettro è l’unico modo per trarre conclusioni sulla loro natura. Per questo, nel primo capitolo si ricava l’equazione del trasporto radiativo, soffermandosi sui processi che regolano l’assorbimento e l’emissione di energia. Il secondo capitolo invece, tratta il caso particolare delle atmosfere stellari, nel quale si ricava, con una serie di approssimazioni fatte sull’equazione del trasporto radiativo, quale parte osserviamo di una stella e dove si formano le righe spettrali. Successivamente ci si è concentrati sui meccanismi che portano alla formazione delle righe spettrali, analizzando sia le transizioni radiative con i coefficienti di Einstein, sia quelle collisionali, e distinguendo tra transizioni permesse o proibite con le regole di selezione. Infine si sono esaminate le informazioni che si possono ricavare dalle righe spettrali, approfondendo sui fenomeni di shift e modifica di queste, descrivendo più nel dettaglio la riga a 21 cm dell’atomo di idrogeno, fondamentale in astrofisica.