Macchine di Schönhage e Complessità Computazionale implicita

Partendo dallo studio del modello computazionale introdotto da Schönhage, la presente tesi si propone di fornire una simulazione delle Evolving Graph Structures di Leivant e Marion che ne conservi le proprietà in termini di complessità computazionale.

Il problema della primalità in complessità computazionale

Questa tesi vuole fornire un'introduzione alla complessità computazionale e allo studio dei numeri primi riferito a questa materia. Si tratterà della Macchina di Turing e della sua importanza per calcolabilità e complessità, introducendo le classi P ed NP. Queste saranno approfondite studiando prima la classe di problemi NP-completi e successivamente fornendo alcuni esempi importanti. Nella parte finale ci si occuperà esplicitamente del problema dei numeri primi e si guarderà da vicino l'algoritmo AKS, dimostrandone la correttezza.

Isomorfismo tra alberi: algoritmi e complessità computazionale

La trattazione è volta all'esposizione dell'algoritmo di Lindell per determinare in logspazio se due alberi sono isomorfi. Un'ampia parte introduttiva richiama i prerequisiti teorici necessari alla comprensione della parte di esposizione dell'algoritmo.

Applicazione di un modello zero-dimensionale per la simulazione della detonazione

L’elaborato affronta la tematica della detonazione nel motore a combustione interna, al fine di individuare un modello che sia in grado di riprodurre il fenomeno in modo accurato, con la prospettiva di un uso a scopo predittivo. A tal proposito vengono presentati modelli basati su svariate metodologie: in particolar modo, accanto ai metodi basati sulle grandezze direttamente o indirettamente misurabili del motore ad accensione comandata, vengono presentati un metodo basato sull’applicazione delle reti neurali, una metodologia di controllo basata sull’approccio True Digital Control, e due metodi che si avvalgono di procedimenti di tipo puramente statistico (metodo dei minimi quadrati e metodo Monte Carlo) per ricavare alcune delle grandezze fondamentali per il calcolo della detonazione. Successivamente, dopo una breve parentesi sulle simulazioni di tipo 3D, vengono introdotti i modelli fisici zero-dimensionali. Uno di questi, basato su un indice (definito dal simbolo Kn) capace di dare una valutazione quantitativa del fenomeno, viene applicato ad un insieme di dati sperimentali provenienti dai test al banco di un motore Ducati 1200. I risultati dell’analisi vengono confrontati con le evidenze sperimentali, sottolineando la buona rispondenza delle simulazioni ad essi e di conseguenza la potenzialità di tali metodi, computazionalmente non onerosi e di rapida applicazione.

Algoritmi quantistici e classi di complessità

Solitamente il concetto di difficoltà è piuttosto soggettivo, ma per un matematico questa parola ha un significato diverso: anche con l’aiuto dei più potenti computer può essere impossibile trovare la soluzione di un sudoku, risolvere l’enigma del commesso viaggiatore o scomporre un numero nei suoi fattori primi; in questo senso le classi di complessità computazionale quantificano il concetto di difficoltà secondo le leggi dell’informatica classica. Una macchina quantistica, però, non segue le leggi classiche e costituisce un nuovo punto di vista in una frontiera della ricerca legata alla risoluzione dei celebri problemi del millennio: gli algoritmi quantistici implementano le proprietà straordinarie e misteriose della teoria dei quanti che, quando applicate lucidamente, danno luogo a risultati sorprendenti.

Programmazione funzionale in spazio logaritmico: una libreria di funzione aritmetiche

In questa Tesi forniamo una libreria di funzioni aritmetiche che operano in spazio logaritmico rispetto all'input. Partiamo con un'analisi dei campi in cui è necessario o conveniente porre dei limiti, in termini di spazio utilizzato, alla computazione di un determinato software. Vista la larga diffusione del Web, si ha a che fare con collezioni di dati enormi e che magari risiedono su server remoti: c'è quindi la necessità di scrivere programmi che operino su questi dati, pur non potendo questi dati entrare tutti insieme nella memoria di lavoro del programma stesso. In seguito studiamo le nozioni teoriche di Complessità, in particolare quelle legate allo spazio di calcolo, utilizzando un modello alternativo di Macchina di Turing: la Offline Turing Machine. Presentiamo quindi un nuovo “modello” di programmazione: la computazione bidirezionale, che riteniamo essere un buon modo di strutturare la computazione limitata in spazio. Forniamo poi una “guida al programmatore” per un linguaggio di recente introduzione, IntML, che permettere la realizzazione di programmi logspace mantenendo però il tradizionale stile di programmazione funzionale. Infine, per mostrare come IntML permetta concretamente di scrivere programmi limitati in spazio, realizziamo una libreria di funzioni aritmetiche che operano in spazio logaritmico. In particolare, mostriamo funzioni per calcolare divisione intera e resto sui naturali, e funzioni per confrontare, sommare e moltiplicare numeri espressi come parole binarie.

Principi e metodi della robotica evolutiva

L’intelligenza artificiale, ovvero lo studio e la progettazione di sistemi intelligenti, mira a riprodurre alcuni aspetti dell’intelligenza umana, come il linguaggio e il ragionamento deduttivo, nei computer. La robotica, invece, cerca spesso di ricreare nei robot comportamenti adattativi, come l’abilità di manipolare oggetti o camminare, mediante l’utilizzo di algoritmi in grado di generare comportamenti desiderati. Una volta realizzato uno di questi algoritmi specificamente per una certa abilità, si auspica che tale algoritmo possa essere riutilizzato per generare comportamenti più complessi fino a che il comportamento adattativo del robot non si mostri ad un osservatore esterno come intelligente; purtroppo questo non risulta sempre possibile e talvolta per generare comportamenti di maggiore complessità è necessario riscrivere totalmente gli algoritmi. Appare quindi evidente come nel campo della robotica l’attenzione sia incentrata sul comportamento, perché le azioni di un robot generano nuove stimolazioni sensoriali, che a loro volta influiscono sulle sue azioni future. Questo tipo di intelligenza artificiale (chiamata propriamente embodied cognition) differisce da quella propriamente detta per il fatto che l’intelligenza non emerge dall’introspezione ma dalle interazioni via via più complesse che la macchina ha con l’ambiente circostante. Gli esseri viventi presenti in natura mostrano, infatti, alcuni fenomeni che non sono programmati a priori nei geni, bensì frutto dell’interazione che l’organismo ha con l’ambiente durante le varie fasi del suo sviluppo. Volendo creare una macchina che sia al contempo autonoma e adattativa, si devono affrontare due problemi: il primo è relativo alla difficoltà della progettazione di macchine autonome, il secondo agli ingenti costi di sviluppo dei robot. Alla fine degli anni ’80 nasce la robotica evolutiva che, traendo ispirazione dall’evoluzione biologica, si basa sull’utilizzo di software in grado di rappresentare popolazioni di robot virtuali e la capacità di farli evolvere all’interno di un simulatore, in grado di rappresentare le interazioni tra mente e corpo del robot e l’ambiente, per poi realizzare fisicamente solo i migliori. Si utilizzano algoritmi evolutivi per generare robot che si adattano, anche dal punto di vista della forma fisica, all’ambiente in cui sono immersi. Nel primo capitolo si tratterà di vita ed evoluzione artificiali, concetti che verranno ripresi nel secondo capitolo, dedicato alle motivazioni che hanno portato alla nascita della robotica evolutiva, agli strumenti dei quali si avvale e al rapporto che ha con la robotica tradizionale e le sue declinazioni. Nel terzo capitolo si presenteranno i tre formalismi mediante i quali si sta cercando di fornire un fondamento teorico a questa disciplina. Infine, nel quarto capitolo saranno mostrati i problemi che ancora oggi non hanno trovato soluzione e le sfide che si devono affrontare trattando di robotica evolutiva.

Geophotohunt: Studio di algoritmi di confronto di immagini per realizzare una caccia al tesoro fotografica

Questo studio si propone di realizzare un’applicazione per dispositivi Android che permetta, per mezzo di un gioco di ruolo strutturato come caccia al tesoro, di visitare in prima persona città d’arte e luoghi turistici. Gli utenti finali, grazie alle funzionalità dell’app stessa, potranno giocare, creare e condividere cacce al tesoro basate sulla ricerca di edifici, monumenti, luoghi di rilevanza artistico-storica o turistica; in particolare al fine di completare ciascuna tappa di una caccia al tesoro il giocatore dovrà scattare una fotografia al monumento o edificio descritto nell’obiettivo della caccia stessa. Il software grazie ai dati rilevati tramite GPS e giroscopio (qualora il dispositivo ne sia dotato) e per mezzo di un algoritmo di instance recognition sarà in grado di affermare se la foto scattata rappresenta la risposta corretta al quesito della tappa. L’applicazione GeoPhotoHunt rappresenta non solo uno strumento ludico per la visita di città turistiche o più in generale luoghi di interesse, lo studio propone, infatti come suo contributo originale, l’implementazione su piattaforma mobile di un Content Based Image Retrieval System (CBIR) del tutto indipendente da un supporto server. Nello specifico il server dell’applicazione non sarà altro che uno strumento di appoggio con il quale i membri della “community” di GeoPhotoHunt potranno pubblicare le cacce al tesoro da loro create e condividere i punteggi che hanno totalizzato partecipando a una caccia al tesoro. In questo modo quando un utente ha scaricato sul proprio smartphone i dati di una caccia al tesoro potrà iniziare l’avventura anche in assenza di una connessione internet. L’intero studio è stato suddiviso in più fasi, ognuna di queste corrisponde ad una specifica sezione dell’elaborato che segue. In primo luogo si sono effettuate delle ricerche, soprattutto nel web, con lo scopo di individuare altre applicazioni che implementano l’idea della caccia al tesoro su piattaforma mobile o applicazioni che implementassero algoritmi di instance recognition direttamente su smartphone. In secondo luogo si è ricercato in letteratura quali fossero gli algoritmi di riconoscimento di immagini più largamente diffusi e studiati in modo da avere una panoramica dei metodi da testare per poi fare la scelta dell’algoritmo più adatto al caso di studio. Quindi si è proceduto con lo sviluppo dell’applicazione GeoPhotoHunt stessa, sia per quanto riguarda l’app front-end per dispositivi Android sia la parte back-end server. Infine si è passati ad una fase di test di algoritmi di riconoscimento di immagini in modo di avere una sufficiente quantità di dati sperimentali da permettere di effettuare una scelta dell’algoritmo più adatto al caso di studio. Al termine della fase di testing si è deciso di implementare su Android un algoritmo basato sulla distanza tra istogrammi di colore costruiti sulla scala cromatica HSV, questo metodo pur non essendo robusto in presenza di variazioni di luminosità e contrasto, rappresenta un buon compromesso tra prestazioni, complessità computazionale in modo da rendere la user experience quanto più coinvolgente.

Tecniche automatiche di mapping e localizzazione in ambienti indoor

Il mapping di grandezze fisiche risulta estremamente importante, essendo in grado di fornire un adeguato supporto per la localizzazione e il monitoraggio di parametri ambientali sensibili. Nel caso indoor, in assenza di un sistema di localizzazione di riferimento analogo al GPS per il caso outdoor, sfruttando appieno le potenzialità della sensoristica a bordo degli smartphone, si è fatto progressivamente strada il mapping di grandezze fisiche quali, ad esempio, il segnale Wi-Fi e il campo magnetico terrestre. In questo caso il mapping, senza richiedere alcuna infrastruttura e coadiuvato dall'utilizzo di dispositivi portatili largamente diffusi ad uso quotidiano, rappresenta una soluzione relativamente recente ridefinibile come Mobile Crowd Sensing. Il MCS rappresenta un nuovo paradigma di servizio, volto a sfruttare l'interconnettività tra dispositivi portatili per effettuare misurazioni di caratteristiche ambientali in maniera automatizzata, aggregandole in un sistema cloud usufruibile ad una vasta comunità. Tuttavia , il considerevole flusso di dati generato, la variabilità temporale delle grandezze di interesse e il rumore insito nelle misurazioni costituiscono problematiche fondamentali per l'utilizzo e la gestione delle misurazioni effettuate. Per tali motivi l'attività di tesi ha previsto i seguenti obiettivi: (i) fornire una panoramica delle principali tecniche e tecnologie di localizzazione volta a motivare l'importanza del mapping di grandezze fisiche ambientali; (ii) individuazione di grandezze fisiche appetibili per la creazione di mappe affidabili e realizzabili nei contesti applicativi più disparati, sfruttando risorse già presenti nell'ambiente; (iii) sviluppo di un algoritmo statistico in grado di fornire una stima accurata dell'andamento spaziale della grandezza di interesse attraverso un numero limitato di misurazioni, mantenendo la compatibilità con processi MCS e una bassa complessità computazionale. L’algoritmo sviluppato è stato validato attraverso simulazioni e misurazioni svolte in ambienti reali. In particolare, prove sperimentali sono state effettuate nell’arena Vicon nei laboratori DEI dell’Università di Bologna, sede Cesena, concepita dal gruppo di ricerca Casy.

Ricostruzione degli sforzi in elementi finiti di piastra

Nell’ambito dell’analisi computazionale delle strutture il metodo degli elementi finiti è probabilmente uno dei metodi numerici più efficaci ed impiegati. La semplicità dell’idea di base del metodo e la relativa facilità con cui può essere implementato in codici di calcolo hanno reso possibile l’applicazione di questa tecnica computazionale in diversi settori, non solo dell’ingegneria strutturale, ma in generale della matematica applicata. Ma, nonostante il livello raggiunto dalle tecnologie ad elementi finiti sia già abbastanza elevato, per alcune applicazioni tipiche dell’ingegneria strutturale (problemi bidimensionali, analisi di lastre inflesse) le prestazioni fornite dagli elementi usualmente utilizzati, ovvero gli elementi di tipo compatibile, sono in effetti poco soddisfacenti. Vengono in aiuto perciò gli elementi finiti basati su formulazioni miste che da un lato presentano una più complessa formulazione, ma dall’altro consentono di prevenire alcuni problemi ricorrenti quali per esempio il fenomeno dello shear locking. Indipendentemente dai tipi di elementi finiti utilizzati, le quantità di interesse nell’ambito dell’ingegneria non sono gli spostamenti ma gli sforzi o più in generale le quantità derivate dagli spostamenti. Mentre i primi sono molto accurati, i secondi risultano discontinui e di qualità scadente. A valle di un calcolo FEM, negli ultimi anni, hanno preso piede procedure di post-processing in grado, partendo dalla soluzione agli elementi finiti, di ricostruire lo sforzo all’interno di patch di elementi rendendo quest’ultimo più accurato. Tali procedure prendono il nome di Procedure di Ricostruzione (Recovery Based Approaches). Le procedure di ricostruzione qui utilizzate risultano essere la REP (Recovery by Equilibrium in Patches) e la RCP (Recovery by Compatibility in Patches). L’obbiettivo che ci si prefigge in questo lavoro è quello di applicare le procedure di ricostruzione ad un esempio di piastra, discretizzato con vari tipi di elementi finiti, mettendone in luce i vantaggi in termini di migliore accurattezza e di maggiore convergenza.

Progettazione e sviluppo di applicazioni distribuite su Web: da JavaScript a TypeScript

Il Web nel corso della sua esistenza ha subito un mutamento dovuto in parte dalle richieste del mercato, ma soprattutto dall’evoluzione e la nascita costante delle numerose tecnologie coinvolte in esso. Si è passati da un’iniziale semplice diffusione di contenuti statici, ad una successiva collezione di siti web, dapprima con limitate presenze di dinamicità e interattività (a causa dei limiti tecnologici), ma successivamente poi evoluti alle attuali applicazioni web moderne che hanno colmato il gap con le applicazioni desktop, sia a livello tecnologico, che a livello di diffusione effettiva sul mercato. Tali applicazioni web moderne possono presentare un grado di complessità paragonabile in tutto e per tutto ai sistemi software desktop tradizionali; le tecnologie web hanno subito nel tempo un evoluzione legata ai cambiamenti del web stesso e tra le tecnologie più diffuse troviamo JavaScript, un linguaggio di scripting nato per dare dinamicità ai siti web che si ritrova tutt’ora ad essere utilizzato come linguaggio di programmazione di applicazioni altamente strutturate. Nel corso degli anni la comunità di sviluppo che ruota intorno a JavaScript ha prodotto numerose librerie al supporto del linguaggio dotando così gli sviluppatori di un linguaggio completo in grado di far realizzare applicazioni web avanzate. Le recenti evoluzioni dei motori javascript presenti nei browser hanno inoltre incrementato le prestazioni del linguaggio consacrandone la sua leadership nei confronti dei linguaggi concorrenti. Negli ultimi anni a causa della crescita della complessità delle applicazioni web, javascript è stato messo molto in discussione in quanto come linguaggio non offre le classiche astrazioni consolidate nel tempo per la programmazione altamente strutturata; per questo motivo sono nati linguaggi orientati alla programmazione ad oggetti per il web che si pongono come obiettivo la risoluzione di questo problema: tra questi si trovano linguaggi che hanno l’ambizione di soppiantare JavaScript come ad esempio Dart creato da Google, oppure altri che invece sfruttano JavaScript come linguaggio base al quale aggiungono le caratteristiche mancanti e, mediante il processo di compilazione, producono codice JavaScript puro compatibile con i motori JavaScript presenti nei browser. JavaScript storicamente fu introdotto come linguaggio sia per la programmazione client-side, che per la controparte server-side, ma per vari motivi (la forte concorrenza, basse performance, etc.) ebbe successo solo come linguaggio per la programmazione client; le recenti evoluzioni del linguaggio lo hanno però riportato in auge anche per la programmazione server-side, soprattutto per i miglioramenti delle performance, ma anche per la sua naturale predisposizione per la programmazione event-driven, paradigma alternativo al multi-threading per la programmazione concorrente. Un’applicazione web di elevata complessità al giorno d’oggi può quindi essere interamente sviluppata utilizzando il linguaggio JavaScript, acquisendone sia i suoi vantaggi che gli svantaggi; le nuove tecnologie introdotte ambiscono quindi a diventare la soluzione per i problemi presenti in JavaScript e di conseguenza si propongono come potenziali nuovi linguaggi completi per la programmazione web del futuro, anticipando anche le prossime evoluzioni delle tecnologie già esistenti preannunciate dagli enti standard della programmazione web, il W3C ed ECMAScript. In questa tesi saranno affrontate le tematiche appena introdotte confrontando tra loro le tecnologie in gioco con lo scopo di ottenere un’ampia panoramica delle soluzioni che uno sviluppatore web dovrà prendere in considerazione per realizzare un sistema di importanti dimensioni; in particolare sarà approfondito il linguaggio TypeScript proposto da Microsoft, il quale è nato in successione a Dart apparentemente con lo stesso scopo, ma grazie alla compatibilità con JavaScript e soprattutto con il vasto mondo di librerie legate ad esso nate in questi ultimi anni, si presenta nel mercato come tecnologia facile da apprendere per tutti gli sviluppatori che già da tempo hanno sviluppato abilità nella programmazione JavaScript.

Sviluppo di metodologie per la simulazione di scambiatori di calore per motori di ultima generazione.

La riduzione dei consumi energetici è una problematica che riguarda appieno il campo dell'autotrazione, a fronte delle misure sempre più stringenti per il taglio delle emissioni di anidride carbonica. A tal scopo, il recupero di energia dai gas di scarico tramite ciclo Rankine appare la soluzione più vantaggiosa, a fronte di onerosità e complessità affrontabili nel breve periodo. L'obiettivo della presente tesi di laurea è lo sviluppo di metodologie per la simulazione di scambiatori di calore bifase per un sistema a ciclo Rankine, utilizzato per il recupero di energia in un'autovettura. Lo svolgimento di test per la validazione dei modelli utilizzati, è risultato fondamentale al fine di ottenere il setup idoneo per la simulazione termofluidodinamica del componente oggetto di studio.