Rassegna di strutture dati e algoritmi per l'indicizzazione di basi di dati.

La frenetica evoluzione sociale e culturale, data dal crescente e continuo bisogno di conoscenza dell’uomo, ha portato oggi a navigare in un oceano sconfinato di dati e informazioni. Esse assumono una propria peculiare importanza, un valore sia dal punto di vista del singolo individuo, sia all’interno di un contesto sociale e di un settore di riferimento specifico e concreto. La conseguente mutazione dell’interazione e della comunicazione a livello economico della società, ha portato a parlare oggi di economia dell’informazione. In un contesto in cui l’informazione rappresenta la risorsa principale per l’attività di crescita e sviluppo economico, è fondamentale possedere la più adeguata strategia organizzativa per la gestione dei dati grezzi. Questo per permetterne un’efficiente memorizzazione, recupero e manipolazione in grado di aumentare il valore dell’organizzazione che ne fa uso. Un’informazione incompleta o non accurata può portare a valutazioni errate o non ottimali. Ecco quindi la necessità di gestire i dati secondo specifici criteri al fine di creare un proprio vantaggio competitivo. La presente rassegna ha lo scopo di analizzare le tecniche di ottimizzazione di accesso alle basi di dati. La loro efficiente implementazione è di fondamentale importanza per il supporto e il corretto funzionamento delle applicazioni che ne fanno uso: devono garantire un comportamento performante in termini di velocità, precisione e accuratezza delle informazioni elaborate. L’attenzione si focalizzerà sulle strutture d’indicizzazione di tipo gerarchico: gli alberi di ricerca. Verranno descritti sia gli alberi su dati ad una dimensione, sia quelli utilizzati nel contesto di ricerche multi dimensionali (come, ad esempio, punti in uno spazio). L’ingente sforzo per implementare strutture di questo tipo ha portato gli sviluppatori a sfruttare i principi di ereditarietà e astrazione della programmazione ad oggetti al fine di ideare un albero generalizzato che inglobasse in sé tutte le principali caratteristiche e funzioni di una struttura di indicizzazione gerarchica, così da aumentarne la riusabilità per i più particolari utilizzi. Da qui la presentazione della struttura GiST: Generalized Search Tree. Concluderà una valutazione dei metodi d’accesso esposti nella dissertazione con un riepilogo dei principali dati relativi ai costi computazionali, vantaggi e svantaggi.

Impatto della propagazione elettromagnetica sulle prestazioni delle reti M3N

Con il termine Smart Grid si intende una rete urbana capillare che trasporta energia, informazione e controllo, composta da dispositivi e sistemi altamente distribuiti e cooperanti. Essa deve essere in grado di orchestrare in modo intelligente le azioni di tutti gli utenti e dispositivi connessi al fine di distribuire energia in modo sicuro, efficiente e sostenibile. Questo connubio fra ICT ed Energia viene comunemente identificato anche con il termine Smart Metering, o Internet of Energy. La crescente domanda di energia e l’assoluta necessità di ridurre gli impatti ambientali (pacchetto clima energia 20-20-20 [9]), ha creato una convergenza di interessi scientifici, industriali e politici sul tema di come le tecnologie ICT possano abilitare un processo di trasformazione strutturale di ogni fase del ciclo energetico: dalla generazione fino all’accumulo, al trasporto, alla distribuzione, alla vendita e, non ultimo, il consumo intelligente di energia. Tutti i dispositivi connessi, diventeranno parte attiva di un ciclo di controllo esteso alle grandi centrali di generazione così come ai comportamenti dei singoli utenti, agli elettrodomestici di casa, alle auto elettriche e ai sistemi di micro-generazione diffusa. La Smart Grid dovrà quindi appoggiarsi su una rete capillare di comunicazione che fornisca non solo la connettività fra i dispositivi, ma anche l’abilitazione di nuovi servizi energetici a valore aggiunto. In questo scenario, la strategia di comunicazione sviluppata per lo Smart Metering dell’energia elettrica, può essere estesa anche a tutte le applicazioni di telerilevamento e gestione, come nuovi contatori dell’acqua e del gas intelligenti, gestione dei rifiuti, monitoraggio dell’inquinamento dell’aria, monitoraggio del rumore acustico stradale, controllo continuo del sistema di illuminazione pubblico, sistemi di gestione dei parcheggi cittadini, monitoraggio del servizio di noleggio delle biciclette, ecc. Tutto ciò si prevede possa contribuire alla progettazione di un unico sistema connesso, dove differenti dispositivi eterogenei saranno collegati per mettere a disposizione un’adeguata struttura a basso costo e bassa potenza, chiamata Metropolitan Mesh Machine Network (M3N) o ancora meglio Smart City. Le Smart Cities dovranno a loro volta diventare reti attive, in grado di reagire agli eventi esterni e perseguire obiettivi di efficienza in modo autonomo e in tempo reale. Anche per esse è richiesta l’introduzione di smart meter, connessi ad una rete di comunicazione broadband e in grado di gestire un flusso di monitoraggio e controllo bi-direzionale esteso a tutti gli apparati connessi alla rete elettrica (ma anche del gas, acqua, ecc). La M3N, è un’estensione delle wireless mesh network (WMN). Esse rappresentano una tecnologia fortemente attesa che giocherà un ruolo molto importante nelle futura generazione di reti wireless. Una WMN è una rete di telecomunicazione basata su nodi radio in cui ci sono minimo due percorsi che mettono in comunicazione due nodi. E’ un tipo di rete robusta e che offre ridondanza. Quando un nodo non è più attivo, tutti i rimanenti possono ancora comunicare tra di loro, direttamente o passando da uno o più nodi intermedi. Le WMN rappresentano una tipologia di rete fondamentale nel continuo sviluppo delle reti radio che denota la divergenza dalle tradizionali reti wireless basate su un sistema centralizzato come le reti cellulari e le WLAN (Wireless Local Area Network). Analogamente a quanto successo per le reti di telecomunicazione fisse, in cui si è passati, dalla fine degli anni ’60 ai primi anni ’70, ad introdurre schemi di rete distribuite che si sono evolute e man mano preso campo come Internet, le M3N promettono di essere il futuro delle reti wireless “smart”. Il primo vantaggio che una WMN presenta è inerente alla tolleranza alla caduta di nodi della rete stessa. Diversamente da quanto accade per una rete cellulare, in cui la caduta di una Base Station significa la perdita di servizio per una vasta area geografica, le WMN sono provviste di un’alta tolleranza alle cadute, anche quando i nodi a cadere sono più di uno. L'obbiettivo di questa tesi è quello di valutare le prestazioni, in termini di connettività e throughput, di una M3N al variare di alcuni parametri, quali l’architettura di rete, le tecnologie utilizzabili (quindi al variare della potenza, frequenza, Building Penetration Loss…ecc) e per diverse condizioni di connettività (cioè per diversi casi di propagazione e densità abitativa). Attraverso l’uso di Matlab, è stato quindi progettato e sviluppato un simulatore, che riproduce le caratteristiche di una generica M3N e funge da strumento di valutazione delle performance della stessa. Il lavoro è stato svolto presso i laboratori del DEIS di Villa Grifone in collaborazione con la FUB (Fondazione Ugo Bordoni).

Sviluppo di algoritmi per l'automazione di misure industriali

Oggi, grazie al continuo progredire della tecnologia, in tutti i sistemi di produzione industriali si trova almeno un macchinario che permette di automatizzare determinate operazioni. Alcuni di questi macchinari hanno un sistema di visione industriale (machine vision), che permette loro di osservare ed analizzare ciò che li circonda, dotato di algoritmi in grado di operare alcune scelte in maniera automatica. D’altra parte, il continuo progresso tecnologico che caratterizza la realizzazione di sensori di visione, ottiche e, nell’insieme, di telecamere, consente una sempre più precisa e accurata acquisizione della scena inquadrata. Oggi, esigenze di mercato fanno si che sia diventato necessario che macchinari dotati dei moderni sistemi di visione permettano di fare misure morfometriche e dimensionali non a contatto. Ma le difficoltà annesse alla progettazione ed alla realizzazione su larga scala di sistemi di visione industriali che facciano misure dimensioni non a contatto, con sensori 2D, fanno sì che in tutto il mondo il numero di aziende che producono questo tipo di macchinari sia estremamente esiguo. A fronte di capacità di calcolo avanzate, questi macchinari necessitano dell’intervento di un operatore per selezionare quali parti dell’immagine acquisita siano d’interesse e, spesso, anche di indicare cosa misurare in esse. Questa tesi è stata sviluppata in sinergia con una di queste aziende, che produce alcuni macchinari per le misure automatiche di pezzi meccanici. Attualmente, nell’immagine del pezzo meccanico vengono manualmente indicate le forme su cui effettuare misure. Lo scopo di questo lavoro è quello di studiare e prototipare un algoritmo che fosse in grado di rilevare e interpretare forme geometriche note, analizzando l’immagine acquisita dalla scansione di un pezzo meccanico. Le difficoltà affrontate sono tipiche dei problemi del “mondo reale” e riguardano tutti i passaggi tipici dell’elaborazione di immagini, dalla “pulitura” dell’immagine acquisita, alla sua binarizzazione fino, ovviamente, alla parte di analisi del contorno ed identificazione di forme caratteristiche. Per raggiungere l’obiettivo, sono state utilizzate tecniche di elaborazione d’immagine che hanno permesso di interpretare nell'immagine scansionata dalla macchina tutte le forme note che ci siamo preposti di interpretare. L’algoritmo si è dimostrato molto robusto nell'interpretazione dei diametri e degli spallamenti trovando, infatti, in tutti i benchmark utilizzati tutte le forme di questo tipo, mentre è meno robusto nella determinazione di lati obliqui e archi di circonferenza a causa del loro campionamento non lineare.

Sviluppo di algoritmi di RCP per la stima della coppia indicata erogata da un motore a combustione interna.

Combustion control is one of the key factors to obtain better performances and lower pollutant emissions for diesel, spark ignition and HCCI engines. An algorithm that allows estimating, as an example, the mean indicated torque for each cylinder, could be easily used in control strategies, in order to carry out cylinders trade-off, control the cycle to cycle variation, or detect misfires. A tool that allows evaluating the 50% of Mass Fraction Burned (MFB50), or the net Cumulative Heat Release (CHRNET), or the ROHR peak value (Rate of Heat Release), could be used to optimize spark advance or to detect knock in gasoline engines and to optimize injection pattern in diesel engines. Modern management systems are based on the control of the mean indicated torque produced by the engine: they need a real or virtual sensor in order to compare the measured value with the target one. Many studies have been performed in order to obtain an accurate and reliable over time torque estimation. The aim of this PhD activity was to develop two different algorithms: the first one is based on the instantaneous engine speed fluctuations measurement. The speed signal is picked up directly from the sensor facing the toothed wheel mounted on the engine for other control purposes. The engine speed fluctuation amplitudes depend on the combustion and on the amount of torque delivered by each cylinder. The second algorithm processes in-cylinder pressure signals in the angular domain. In this case a crankshaft encoder is not necessary, because the angular reference can be obtained using a standard sensor wheel. The results obtained with these two methodologies are compared in order to evaluate which one is suitable for on board applications, depending on the accuracy required.

Implementazione automatica di protocolli di interazione AUML mediante reti di Petri

Questa tesi si basa su una serie di lavori precedenti, volti ad analizzare la correlazione tra i modelli AUML e le reti di Petri, per riuscire a fornire una metodologia di traduzione dai primi alle seconde. Questa traduzione permetterà di applicare tecniche di model checking alle reti così create, al fine di stabilire le proprietà necessarie al sistema per poter essere realizzato effettivamente. Verrà poi discussa un'implementazione di tale algoritmo sviluppata in tuProlog ed un primo approccio al model checking utilizzando il programma Maude. Con piccole modifiche all'algoritmo utilizzato per la conversione dei diagrammi AUML in reti di Petri, è stato possibile, inoltre, realizzare un sistema di implementazione automatica dei protocolli precedentemente analizzati, verso due piattaforme per la realizzazione di sistemi multiagente: Jason e TuCSoN. Verranno quindi presentate tre implementazioni diverse: la prima per la piattaforma Jason, che utilizza degli agenti BDI per realizzare il protocollo di interazione; la seconda per la piattaforma TuCSoN, che utilizza il modello A&A per rendersi compatibile ad un ambiente distribuito, ma che ricalca la struttura dell'implementazione precedente; la terza ancora per TuCSoN, che sfrutta gli strumenti forniti dalle reazioni ReSpecT per generare degli artefatti in grado di fornire una infrastruttura in grado di garantire la realizzazione del protocollo di interazione agli agenti partecipanti. Infine, verranno discusse le caratteristiche di queste tre differenti implementazioni su un caso di studio reale, analizzandone i punti chiave.

Studio di Mutazioni Geniche e Variazioni Copy-Number implicate nel deficit combinato degli Ormoni Ipofisari(CPHD)

La crescita normale di un individuo è il risultato dell’azione coordinata di molteplici ormoni e recettori codificati da geni e a tal proposito, discreto interesse è stato dato ai geni tipici dell’asse del GH. Tuttavia altri geni, più a monte di questi e responsabili dello sviluppo dell’ipofisi contribuiscono alla crescita normale o patologica. Alcuni geni studiati sono POU1F1, PROP1, LHX3, LHX4, HESX1, SOX3 e svariate loro mutazioni sono state identificate come causa di panipopituarismo (CPHD=Combined Pituitary Hormone Deficiency). In realtà la ricerca genetica non spiega ancora molte anomalie ipofisarie e molte mutazioni devono ancora essere identificate. Uno degli scopi del dottorato, svoltosi nel laboratorio di Genetica molecolare di Pediatria, è stata l’identificazione di mutazioni geniche da un gruppo di pazienti CPHD considerando in particolare i geni POU1F1, LHX3, SOX3, non ancora messi a punto presso il laboratorio. L’approccio sperimentale si è basato sulle seguenti fasi: prelievo delle informazioni di sequenza da GeneBank, progettazione di primers per amplificare le porzioni esoniche, messa a punto delle fasi della PCR e del sequenziamento, analisi della sequenza e confronto con le informazioni di sequenza depositate allo scopo di rintracciare eventuali mutazioni o varianti. La bassa percentuale di mutazioni in questi geni non ha permesso finora di rintracciare mutazioni nelle porzioni esoniche salvo che in un soggetto, nell’esone 6 di LHX3b (nuova mutazione, recessiva eterozigote, c.1248A>G implicata nella mutazione p.T377A della sequenza proteica). Un metodo di screening di questa mutazione impiegando l’enzima di restrizione SacII è stato usato, senza rilevare nessun altra occorrenza dell’allele mutato in 53 soggetti di controllo. Oltre alla messa a punto del sequenziamento e di alcune tecniche di analisi di singoli SNP o piccoli INDELs per i 3 geni, la ricerca svolta è stata orientata all’impiego di metodi di rilevamento di riarrangiamenti genetici comportanti ampie delezioni e/o variazioni del copy-number di esoni/interi geni detto MLPA (Multiplex Ligation-dependent Probe Amplification) e progettato da MRC-Holland. Il sequenziamento infatti non permette di rilevare tali alterazioni quando sono ampie ed in eterozigosi. Per esempio, in un’ampia delezione in eterozigosi, l’intervallo delimitato dai primers usati per la PCR può non includere totalmente la porzione interessata da delezione su un cromosoma cosicché la PCR ed il sequnziamento si basano solo sulle informazioni dell’altro cromosoma non deleto. Un vantaggio della tecnica MLPA, è l’analisi contemporanea di una quarantina di siti posti su svariati geni. Questa metodo tuttavia può essere affetto da un certo margine di errore spesso dipendente dalla qualità del DNA e dovrebbe essere affiancato e validato da altre tecniche più impegnativa dal punto di vista sperimentale ma più solide, per esempio la Real Time PCR detta anche PCR quantitativa (qPCR). In laboratorio, grazie all’MLPA si è verificata la condizione di delezione eterozigote di un paziente “storico” per il gene GH1 e la stessa mutazione è stata rilevata anche con la qPCR usando lo strumento Corbett Rotor Gene 6000 (Explera). Invece un’analisi solo con la qPCR di variazioni del copy-number (CNV) per SOX3 in pazienti maschili non ha ancora evidenziato anomalie. Entrambe le tecniche hanno aspetti interessanti, il miglior approccio al momento sembra un’analisi iniziale di pazienti con l’MLPA, seguita dalla verifica di un eventuale esito anomalo impiegando la real-time PCR.

Algoritmi esatti per il Job Shop Scheduling: approcci Mathematical Programming

In questa tesi ci occuperemo di fornire un modello MIP di base e di alcune sue varianti, realizzate allo scopo di comprenderne il comportamento ed eventualmente migliorarne l’efficienza. Le diverse varianti sono state costruite agendo in particolar modo sulla definizione di alcuni vincoli, oppure sui bound delle variabili, oppure ancora nell’obbligare il risolutore a focalizzarsi su determinate decisioni o specifiche variabili. Sono stati testati alcuni dei problemi tipici presenti in letteratura e i diversi risultati sono stati opportunamente valutati e confrontati. Tra i riferimenti per tale confronto sono stati considerati anche i risultati ottenibili tramite un modello Constraint Programming, che notoriamente produce risultati apprezzabili in ambito di schedulazione. Un ulteriore scopo della tesi è, infatti, comparare i due approcci Mathematical Programming e Constraint Programming, identificandone quindi i pregi e gli svantaggi e provandone la trasferibilità al modello raffrontato.