Il teorema di Cook-Levin e i SAT-solver

In questa tesi è trattato il tema della soddisfacibilità booleana o proposizionale, detta anche SAT, ovvero il problema di determinare se una formula booleana è soddisfacibile o meno. Soddisfacibile significa che è possibile assegnare le variabili in modo che la formula assuma il valore di verità vero; viceversa si dice insoddisfacibile se tale assegnamento non esiste e se quindi la formula esprime una funzione identicamente falsa. A tal fine si introducono degli strumenti preliminari che permetteranno di affrontare più approfonditamente la questione, partendo dalla definizione basilare di macchina di Turing, affrontando poi le classi di complessità e la riduzione, la nozione di NP-completezza e si dimostra poi che SAT è un problema NP-completo. Infine è fornita una definizione generale di SAT-solver e si discutono due dei principali algoritmi utilizzati a tale scopo.

Modellazione e simulazione di un quadricottero multirotore

Descrizione e analisi del movimento di piattaforme multirotore tramite modellazione e simulazione computazionale. In particolare è stata analizzata l’attitudine di un quadricottero privo di sistema di controllo automatico. Per la scrittura e l’implementazione degli algoritmi risolutivi è stato utilizzato l’ambiente Matlab. Il codice realizzato permette, dopo successiva introduzione di alcune variabili realative a velivolo ed assetto, di ottenere l’evoluzione di parametri di volo che descrivono lo stato del drone nel tempo attraverso una progressiva integrazione numerica. In questo modo è possibile simulare teoricamente qualunque modello di quadricottero conoscendo i suoi parametri costruttivi, ottenendo così una modellazione preliminare da lanciare nel simulatore. Nella tesi viene utilizzato un unico modello realizzato in CAD Solidworks da cui sono stati ricavati i dati necessari. La tesi si compone di una trattazione semplificata di fattibilità di manovre semplici di un multirotore di tipo quadricottero con un approccio di Eulero-Newton ed, in seguito, in presenza di un carico sospeso tramite cavo considerato inestensibile, si sono analizzate delle evoluzioni nel tempo con un’approccio questa volta lagrangiano. Infine vengono trattati brevemente osservazioni conclusive e possibili sviluppi di questo lavoro di tesi.

Analisi e applicazione dei processi di data mining al flusso informativo di sistemi real-time: Implementazione e analisi di un algoritmo autoadattivo per la ricerca di frequent patterns su macchine automatiche.

Analisi e applicazione dei processi di data mining al flusso informativo di sistemi real-time. Implementazione e analisi di un algoritmo autoadattivo per la ricerca di frequent patterns su macchine automatiche.

Analisi e applicazione dei processi di data mining al flusso informativo di sistemi real-time: Adattamento di un algoritmo di apprendimento automatico per la caratterizzazione e la ricerca di frequent patterns su macchine automatiche

La tesi da me svolta durante questi ultimi sei mesi è stata sviluppata presso i laboratori di ricerca di IMA S.p.a.. IMA (Industria Macchine Automatiche) è una azienda italiana che naque nel 1961 a Bologna ed oggi riveste il ruolo di leader mondiale nella produzione di macchine automatiche per il packaging di medicinali. Vorrei subito mettere in luce che in tale contesto applicativo l’utilizzo di algoritmi di data-mining risulta essere ostico a causa dei due ambienti in cui mi trovo. Il primo è quello delle macchine automatiche che operano con sistemi in tempo reale dato che non presentano a pieno le risorse di cui necessitano tali algoritmi. Il secondo è relativo alla produzione di farmaci in quanto vige una normativa internazionale molto restrittiva che impone il tracciamento di tutti gli eventi trascorsi durante l’impacchettamento ma che non permette la visione al mondo esterno di questi dati sensibili. Emerge immediatamente l’interesse nell’utilizzo di tali informazioni che potrebbero far affiorare degli eventi riconducibili a un problema della macchina o a un qualche tipo di errore al fine di migliorare l’efficacia e l’efficienza dei prodotti IMA. Lo sforzo maggiore per riuscire ad ideare una strategia applicativa è stata nella comprensione ed interpretazione dei messaggi relativi agli aspetti software. Essendo i dati molti, chiusi, e le macchine con scarse risorse per poter applicare a dovere gli algoritmi di data mining ho provveduto ad adottare diversi approcci in diversi contesti applicativi: • Sistema di identificazione automatica di errore al fine di aumentare di diminuire i tempi di correzione di essi. • Modifica di un algoritmo di letteratura per la caratterizzazione della macchina. La trattazione è così strutturata: • Capitolo 1: descrive la macchina automatica IMA Adapta della quale ci sono stati forniti i vari file di log. Essendo lei l’oggetto di analisi per questo lavoro verranno anche riportati quali sono i flussi di informazioni che essa genera. • Capitolo 2: verranno riportati degli screenshoot dei dati in mio possesso al fine di, tramite un’analisi esplorativa, interpretarli e produrre una formulazione di idee/proposte applicabili agli algoritmi di Machine Learning noti in letteratura. • Capitolo 3 (identificazione di errore): in questo capitolo vengono riportati i contesti applicativi da me progettati al fine di implementare una infrastruttura che possa soddisfare il requisito, titolo di questo capitolo. • Capitolo 4 (caratterizzazione della macchina): definirò l’algoritmo utilizzato, FP-Growth, e mostrerò le modifiche effettuate al fine di poterlo impiegare all’interno di macchine automatiche rispettando i limiti stringenti di: tempo di cpu, memoria, operazioni di I/O e soprattutto la non possibilità di aver a disposizione l’intero dataset ma solamente delle sottoporzioni. Inoltre verranno generati dei DataSet per il testing di dell’algoritmo FP-Growth modificato.

Ottimizzazione della selezione del decadimento D0->K+K- e D0->pi+pi- ad LHCb mediante un'analisi multivariata

L'esperimento LHCb è stato progettato per eseguire misure di altissima precisione nel settore della fisica dei quark pesanti al Large Hadron Collidere del CERN. Sfruttando l'alta sezione d'urto di produzione di charm nelle interazioni protone-protone ad LHC e utilizzando la statistica raccolta durante il RUN-1, corrispondente ad una luminosità integrata di 3 fb{-1}, l'esperimento LHCb ha realizzato le misure più precise al mondo in questo settore. In particolare i decadimenti del mesone D0 in due corpi carichi senza leptoni nello stato finale hanno permesso di realizzare misure di violazione di CP} che raggiungono precisioni inferiori al 0.1 %. Da pochi mesi LHCb ha iniziato la seconda fase di presa dati, chiamata RUN-2, raccogliendo dati dalle interazioni protone-protone ad una energia nel centro di massa di sqrt{s}=13 TeV, superiore a quella del RUN-1. Le misure attuali di violazione di CP nel settore del charm, sono consistenti con l'ipotesi di non violazione. Il Modello Standard, pur con grandi incertezze teoriche, prevede una violazione di CP molto piccola, pertanto per verificare o meno l'esistenza di taleviolazione, sarà necessario sfruttare al massimo la statistica che verrà raccolta durante il RUN-2, ottimizzando gli algoritmi di selezione dei canali di interesse. In questa tesi verrà presentata uno studio preliminare che ha lo scopo di ottimizzare, mediante una tecnica di analisi multivariata, la selezione dei decadimenti D^*pm-> D0(K+K-)pi_s^pm e D^*pm}-> D0(pi+pi-)pi_s^pm} in previsione della prossima presa dati.

MR spectroscopy in human prostate: in vitro and in vivo measurements to optimize new quantification algorithms

Il cancro della prostata (PCa) è il tumore maligno non-cutaneo più diffuso tra gli uomini ed è il secondo tumore che miete più vittime nei paesi occidentali. La necessità di nuove tecniche non invasive per la diagnosi precoce del PCa è aumentata negli anni. 1H-MRS (proton magnetic resonance spectroscopy) e 1H-MRSI (proton magnetic resonance spectroscopy imaging) sono tecniche avanzate di spettroscopia in risonanza magnetica che permettono di individuare presenza di metaboliti come citrato, colina, creatina e in alcuni casi poliammine in uno o più voxel nel tessuto prostatico. L’abbondanza o l’assenza di uno di questi metaboliti rende possibile discriminare un tessuto sano da uno patologico. Le tecniche di spettroscopia RM sono correntemente utilizzate nella pratica clinica per cervello e fegato, con l’utilizzo di software dedicati per l’analisi degli spettri. La quantificazione di metaboliti nella prostata invece può risultare difficile a causa del basso rapporto segnale/rumore (SNR) degli spettri e del forte accoppiamento-j del citrato. Lo scopo principale di questo lavoro è di proporre un software prototipo per la quantificazione automatica di citrato, colina e creatina nella prostata. Lo sviluppo del programma e dei suoi algoritmi è stato portato avanti all’interno dell’IRST (Istituto Romagnolo per lo Studio e la cura dei Tumori) con l’aiuto dell’unità di fisica sanitaria. Il cuore del programma è un algoritmo iterativo per il fit degli spettri che fa uso di simulazioni MRS sviluppate con il pacchetto di librerie GAMMA in C++. L’accuratezza delle quantificazioni è stata testata con dei fantocci realizzati all’interno dei laboratori dell’istituto. Tutte le misure spettroscopiche sono state eseguite con il nuovo scanner Philips Ingenia 3T, una delle machine di risonanza magnetica più avanzate per applicazioni cliniche. Infine, dopo aver eseguito i test in vitro sui fantocci, sono stati acquisiti gli spettri delle prostate di alcuni volontari sani, per testare se il programma fosse in grado di lavorare in condizioni di basso SNR.

Analisi statica equivalente per strutture dotate di smorzatori viscosi

L’installazione di smorzatori viscosi sulle strutture permette di dissipare l’energia che il sisma trasmette, senza provocare danni o rotture degli elementi strutturali principali. Questi dispositivi sono stati l'oggetto di numerosi lavori di ricerca dal 1980 fino ad oggi e l'efficacia nel mitigare gli effetti dell’azione sismica su strutture edilizie è stata ampiamente dimostrata. La maggior parte delle teorie scientifiche per la progettazione e l'ottimizzazione degli smorzatori si basano sofisticati algoritmi, portando talvolta a complessi procedure. L'applicazione di tali algoritmi richiede spesso competenze computazionali e di tempo eccessive. Il fine della tesi è quello di proporre un metodo pratico, cioè diretto e immediato per aiutare gli ingegneri per effettuare analisi sismiche su strutture intelaiate dotate di smorzatori viscosi e di dimensionare tali dispositivi. Tale metodo è stato l’oggetto del lavoro di ricerca scientifica trattato nell’articolo: “Equivalent Static Analyses of framed structures with added viscous dampers” di Palermo et al., 2015. Si riesce così ad estendere così il concetto di analisi statica equivalente anche per strutture dotate di smorzatori viscosi, definendo in maniera intuitiva sia le configurazioni di idealizzazione della strutture durante il sisma sia l’ idealizzazione dell’effetto del sisma sulla struttura. In questi anni di lavoro di ricerca, sono stati proposti vari metodi per il dimensionamento degli smorzatori viscosi. Tra questi, il prof. Ing. Silvestri (Silvestri et al., 2010) ha proposto un approccio progettuale diretto, chiamato "five step procedure” che mira a guidare l'ingegnere professionista, dalla scelta del target di prestazioni alle identificazioni della caratteristiche meccaniche di smorzatori viscosi trovabili in commercio. La procedura originale (Silvestri et al., 2010, Silvestri et al., 2011, Palermo et al., 2013), anche se per lo più basata su espressioni analitiche, richiede ancora lo sviluppo di analisi numeriche Time-History di modelli FEM, al fine di valutare le forze massime negli smorzatori aggiunti. Verrà spiegato e proposto un metodo semplificato (“Direct five step procedure for the dimensioning of added viscous dampers” Palermo et al., 2015) che consente ottenere direttamente, tramite una semplice formula, le forze massime degli smorzatori (spesso un parametro chiave della valutazione del costo degli smorzatori), senza eseguire simulazioni numeriche. Infine, si è applicato il metodo semplificato proposto di analisi statica equivalente per strutture equipaggiate di smorzatori viscosi ad un edificio reale.

L'algoritmo bionomico per il Traveling Salesman Problem

In questa tesi viene presentato un nuovo metaeuristico per la risoluzione del Traveling Salesman Problem (TSP) simmetrico. Tale metodo, detto algoritmo bionomico, è una variante dell'algoritmo genetico che usa un metodo innovativo di generazione del parents set. Nella tesi vengono proposti diversi metodi di crossover specifici per il TSP ma che possono essere facilmente estesi per altri problemi di ottimizzazione combinatoria. Tali metodi sono stati sperimentati su un insieme di problemi test, i risultati computazionali mostrano l'efficienza dei metodi proposti. In particolare uno dei metodi domina gli altri sia per la miglior qualità delle soluzioni prodotte che per il minor tempo di calcolo impiegato.

Analisi della qualità locale per aumentare l'accuratezza nel riconoscimento di impronte digitali

Il riconoscimento di impronte digitali viene largamente utilizzato in molteplici ambiti, dai sistemi di sicurezza alle applicazioni forensi. La maggior parte dei sistemi automatici di riconoscimento si basa sull'estrazione e il confronto delle minuzie nelle impronte digitali, ma l’accuratezza di queste operazioni peggiora sensibilmente in presenza di impronte di scarsa qualità, fino ad arrivare anche a compromettere il riconoscimento stesso. In questo lavoro di tesi ci si è posto come obiettivo il miglioramento delle prestazioni di un algoritmo di estrazione delle minuzie, attraverso l’utilizzo di varie tecniche per l’analisi di qualità locale delle impronte digitali.

NeverAlone - applicazione mobile per la sicurezza personale

L'applicazione implementata in questa tesi è stata sviluppata per la piattaforma Android ed ha origine da un idea del Sig. Marco Casadio. Lo scopo principale è quella di monitorare l'attività sportiva e di chiamare aiuto in caso di incidente o malore. L'elaborato è stato ottimizzato per supportare un set predefinito di sport, e la tesi ne illustra gli algoritmi.

Applicazione mobile per la somministrazione e il monitoraggio di piani alimentari

L'applicazione consente di gestire i piani alimentari forniti dal medico, visualizzare i pasti proposti e scegliere quali gruppi si mangia durante il giorno. La dispensa consente di visualizzare quali cibi sono all'interno del piano alimentare dando la possibilità di selezionarli. Grazie a degli algoritmi e a degli esami in laboratorio è possibile visualizzare la lista dei cibi più consigliati per il proprio organismo così da favorire il consumo di cibi sani.

Caratterizzazione fisica di apparati per tomosintesi digitale della mammella

In questo lavoro di tesi sono state studiate le caratteristiche di una macchina per tomosintesi Fujifilm AMULET Innovality in uso presso l'Istituto Scientifico Romagnolo per lo Studio e la Cura dei Tumori (I.R.S.T.) di Meldola. Le valutazioni sono state fatte utilizzando diversi fantocci, uno dei quali costruito durante il lavoro di tesi. Per la valutazione delle immagini di mammografia digitale e di tomosintesi sono state seguite le linee guida della International Electrotechnical Commission (IEC) e della European Reference Organisation for Quality Assured Breast Screening and Diagnostic Services (EUREF). Per lo studio delle mammografie digitali sono stati valutati, utilizzando i software COQ e ImageJ, i parametri di NPS, MTF e DQE. Per lo studio delle immagini di tomosintesi sono stati appositamente sviluppati degli algoritmi in linguaggio Java, integrati poi all'interno del software COQ. Il programma sviluppato ha permesso di valutare ASF, MTF, NPS e omogeneità delle immagini ricostruite.

Applicazioni e implementazioni della computazione quantistica

Questa tesi introduce le basi della teoria della computazione quantistica, partendo da un approccio teorico-matematico al concetto di qubit per arrivare alla schematizzazione di alcuni circuiti per algoritmi quantistici, analizzando la differenza tra le porte logiche classiche e la loro versione quantistica. Segue poi una lista descrittiva di possibili applicazioni dei computer quantistici, divise per categorie, e i loro vantaggi rispetto ai computer classici. Tra le applicazioni rientrano la crittografia quantistica, gli algoritmi di fattorizzazione e del logaritmo discreto di Shor, il teletrasporto di informazione quantistica e molte altre. La parte più corposa della tesi riguarda le possibili implementazioni, ovvero come realizzare praticamente un computer quantistico rendendo entità fisiche i qubit. Di queste implementazioni vengono analizzati i vari aspetti necessari alla computazione quantistica, ovvero la creazione di stati iniziali, la misura di stati finali e le trasformazioni unitarie che rappresentano le porte logiche quantistiche. Infine vengono elencate le varie problematiche del modello preso in considerazione. Infine vengono citati alcuni esperimenti e modelli recenti che potrebbero vedere una realizzazione su scala industriale nei prossimi anni.

Applicazioni di realtà aumentata in ambito museale

La realtà aumentata, unitamente a quella mista, stanno rapidamente prendendo pieno all'interno di molti aspetti della vita umana. Scopo di questo lavoro è di analizzare tecnologie e tecniche esistenti al fine di applicarle ad un caso reale, la rilevazione e la sovrapposizione di un oggetto digitale tridimensionale ad uno presente in un museo.

Geodetiche su superfici dello spazio euclideo tridimensionale

In questa tesi si studiano le geodetiche sulle superfici dello spazio euclideo tridimensionale. Tali curve, che godono di proprietà analoghe a quelle delle rette nel piano, vengono definite come quelle particolari curve sulle superfici il cui campo dei vettori tangenti e' parallelo, cioè ha derivata covariante nulla. Sulle superfici di rotazione le geodetiche sono tutti i meridiani, i paralleli aventi vettori tangenti paralleli all'asse di rotazione e tutte le curve soddisfacenti la condizione di Clairaut. Dopo aver studiato le geodetiche su alcune superfici significative si introduce la nozione di mappa esponenziale che permetterà di dimostrare le proprietà di minimo locale delle geodetiche.