Learning for scheduling a portfolio of constraint solvers

Nel lavoro di tesi qui presentato si indaga l'applicazione di tecniche di apprendimento mirate ad una più efficiente esecuzione di un portfolio di risolutore di vincoli (constraint solver). Un constraint solver è un programma che dato in input un problema di vincoli, elabora una soluzione mediante l'utilizzo di svariate tecniche. I problemi di vincoli sono altamente presenti nella vita reale. Esempi come l'organizzazione dei viaggi dei treni oppure la programmazione degli equipaggi di una compagnia aerea, sono tutti problemi di vincoli. Un problema di vincoli è formalizzato da un problema di soddisfacimento di vincoli(CSP). Un CSP è descritto da un insieme di variabili che possono assumere valori appartenenti ad uno specico dominio ed un insieme di vincoli che mettono in relazione variabili e valori assumibili da esse. Una tecnica per ottimizzare la risoluzione di tali problemi è quella suggerita da un approccio a portfolio. Tale tecnica, usata anche in am- biti come quelli economici, prevede la combinazione di più solver i quali assieme possono generare risultati migliori di un approccio a singolo solver. In questo lavoro ci preoccupiamo di creare una nuova tecnica che combina un portfolio di constraint solver con tecniche di machine learning. Il machine learning è un campo di intelligenza articiale che si pone l'obiettivo di immettere nelle macchine una sorta di `intelligenza'. Un esempio applicativo potrebbe essere quello di valutare i casi passati di un problema ed usarli in futuro per fare scelte. Tale processo è riscontrato anche a livello cognitivo umano. Nello specico, vogliamo ragionare in termini di classicazione. Una classicazione corrisponde ad assegnare ad un insieme di caratteristiche in input, un valore discreto in output, come vero o falso se una mail è classicata come spam o meno. La fase di apprendimento sarà svolta utilizzando una parte di CPHydra, un portfolio di constraint solver sviluppato presso la University College of Cork (UCC). Di tale algoritmo a portfolio verranno utilizzate solamente le caratteristiche usate per descrivere determinati aspetti di un CSP rispetto ad un altro; queste caratteristiche vengono altresì dette features. Creeremo quindi una serie di classicatori basati sullo specifico comportamento dei solver. La combinazione di tali classicatori con l'approccio a portfolio sara nalizzata allo scopo di valutare che le feature di CPHydra siano buone e che i classicatori basati su tali feature siano affidabili. Per giusticare il primo risultato, eettueremo un confronto con uno dei migliori portfolio allo stato dell'arte, SATzilla. Una volta stabilita la bontà delle features utilizzate per le classicazioni, andremo a risolvere i problemi simulando uno scheduler. Tali simulazioni testeranno diverse regole costruite con classicatori precedentemente introdotti. Prima agiremo su uno scenario ad un processore e successivamente ci espanderemo ad uno scenario multi processore. In questi esperimenti andremo a vericare che, le prestazioni ottenute tramite l'applicazione delle regole create appositamente sui classicatori, abbiano risultati migliori rispetto ad un'esecuzione limitata all'utilizzo del migliore solver del portfolio. I lavoro di tesi è stato svolto in collaborazione con il centro di ricerca 4C presso University College Cork. Su questo lavoro è stato elaborato e sottomesso un articolo scientico alla International Joint Conference of Articial Intelligence (IJCAI) 2011. Al momento della consegna della tesi non siamo ancora stati informati dell'accettazione di tale articolo. Comunque, le risposte dei revisori hanno indicato che tale metodo presentato risulta interessante.

Il teorema della mappa di Riemann

Il teorema della mappa di Riemann è un risultato fondamentale dell'analisi complessa che afferma l'esistenza di un biolomorfismo tra un qualsiasi dominio semplicemente connesso incluso strettamente nel piano ed il disco unità. Si tratta di un teorema di grande importanza e generalità, dato che non si fa alcuna ipotesi sul bordo del dominio considerato. Inoltre ha applicazioni in diverse aree della matematica, ad esempio nella topologia: può infatti essere usato per dimostrare che due domini semplicemente connessi del piano sono tra loro omeomorfi. Presentiamo in questa tesi due diverse dimostrazioni del teorema.

Il teorema di Riemann-Roch

Superfici di Riemann compatte, divisori, Teorema di Riemann Roch, immersioni nello spazio proiettivo.

Analysis of the Kohn Laplacian on the Heisenberg Group and on Cauchy-Riemann Manifolds

The purpose of this study is to analyse the regularity of a differential operator, the Kohn Laplacian, in two settings: the Heisenberg group and the strongly pseudoconvex CR manifolds. The Heisenberg group is defined as a space of dimension 2n+1 with a product. It can be seen in two different ways: as a Lie group and as the boundary of the Siegel UpperHalf Space. On the Heisenberg group there exists the tangential CR complex. From this we define its adjoint and the Kohn-Laplacian. Then we obtain estimates for the Kohn-Laplacian and find its solvability and hypoellipticity. For stating L^p and Holder estimates, we talk about homogeneous distributions. In the second part we start working with a manifold M of real dimension 2n+1. We say that M is a CR manifold if some properties are satisfied. More, we say that a CR manifold M is strongly pseudoconvex if the Levi form defined on M is positive defined. Since we will show that the Heisenberg group is a model for the strongly pseudo-convex CR manifolds, we look for an osculating Heisenberg structure in a neighborhood of a point in M, and we want this structure to change smoothly from a point to another. For that, we define Normal Coordinates and we study their properties. We also examinate different Normal Coordinates in the case of a real hypersurface with an induced CR structure. Finally, we define again the CR complex, its adjoint and the Laplacian operator on M. We study these new operators showing subelliptic estimates. For that, we don't need M to be pseudo-complex but we ask less, that is, the Z(q) and the Y(q) conditions. This provides local regularity theorems for Laplacian and show its hypoellipticity on M.

Eulero, Mascheroni e Riemann costanti ed ipotesi

In questa tesi si descrivono la funzione zeta di Riemann, la costante di Eulero-Mascheroni e la funzione gamma di Eulero. Si riportano i legami tra questi e si illustra brevemente l'ipotesi di Riemann degli zeri non banali della funzione zeta, ovvero l'ipotesi della distribuzione dei numeri primi nella retta dei numeri reali.

Modellazione bidimensionale della propagazione nell'entroterra della inondazione da mare negli scenari dei previsti cambiamenti climatici

Le ricerche di carattere eustatico, mareografico, climatico, archeologico e geocronologico, sviluppatesi soprattutto nell’ultimo ventennio, hanno messo in evidenza che gran parte delle piane costiere italiane risulta soggetta al rischio di allagamento per ingressione marina dovuta alla risalita relativa del livello medio del mare. Tale rischio è la conseguenza dell’interazione tra la presenza di elementi antropici e fenomeni di diversa natura, spesso difficilmente discriminabili e quantificabili, caratterizzati da magnitudo e velocità molto diverse tra loro. Tra le cause preponderanti che determinano l’ingressione marina possono essere individuati alcuni fenomeni naturali, climatici e geologici, i quali risultano fortemente influenzati dalle attività umane soprattutto a partire dal XX secolo. Tra questi si individuano: - la risalita del livello del mare, principalmente come conseguenza del superamento dell’ultimo acme glaciale e dello scioglimento delle grandi calotte continentali; - la subsidenza. Vaste porzioni delle piane costiere italiane risultano soggette a fenomeni di subsidenza. In certe zone questa assume proporzioni notevoli: per la fascia costiera emiliano-romagnola si registrano ratei compresi tra 1 e 3 cm/anno. Tale subsidenza è spesso il risultato della sovrapposizione tra fenomeni naturali (neotettonica, costipamento di sedimenti, ecc.) e fenomeni indotti dall’uomo (emungimenti delle falde idriche, sfruttamento di giacimenti metaniferi, escavazione di materiali per l’edilizia, ecc.); - terreni ad elevato contenuto organico: la presenza di depositi fortemente costipabili può causare la depressione del piano di campagna come conseguenza di abbassamenti del livello della falda superficiale (per drenaggi, opere di bonifica, emungimenti), dello sviluppo dei processi di ossidazione e decomposizione nei terreni stessi, del costipamento di questi sotto il proprio peso, della carenza di nuovi apporti solidi conseguente alla diminuita frequenza delle esondazioni dei corsi d’acqua; - morfologia: tra i fattori di rischio rientra l’assetto morfologico della piana e, in particolare il tipo di costa (lidi, spiagge, cordoni dunari in smantellamento, ecc. ), la presenza di aree depresse o comunque vicine al livello del mare (fino a 1-2 m s.l.m.), le caratteristiche dei fondali antistanti (batimetria, profilo trasversale, granulometria dei sedimenti, barre sommerse, assenza di barriere biologiche, ecc.); - stato della linea di costa in termini di processi erosivi dovuti ad attività umane (urbanizzazione del litorale, prelievo inerti, costruzione di barriere, ecc.) o alle dinamiche idro-sedimentarie naturali cui risulta soggetta (correnti litoranee, apporti di materiale, ecc. ). Scopo del presente studio è quello di valutare la probabilità di ingressione del mare nel tratto costiero emiliano-romagnolo del Lido delle Nazioni, la velocità di propagazione del fronte d’onda, facendo riferimento allo schema idraulico del crollo di una diga su letto asciutto (problema di Riemann) basato sul metodo delle caratteristiche, e di modellare la propagazione dell’inondazione nell’entroterra, conseguente all’innalzamento del medio mare . Per simulare tale processo è stato utilizzato il complesso codice di calcolo bidimensionale Mike 21. La fase iniziale di tale lavoro ha comportato la raccolta ed elaborazione mediante sistema Arcgis dei dati LIDAR ed idrografici multibeam , grazie ai quali si è provveduto a ricostruire la topo-batimetria di dettaglio della zona esaminata. Nel primo capitolo è stato sviluppato il problema del cambiamento climatico globale in atto e della conseguente variazione del livello marino che, secondo quanto riportato dall’IPCC nel rapporto del 2007, dovrebbe aumentare al 2100 mediamente tra i 28 ed i 43 cm. Nel secondo e terzo capitolo è stata effettuata un’analisi bibliografica delle metodologie per la modellazione della propagazione delle onde a fronte ripido con particolare attenzione ai fenomeni di breaching delle difese rigide ed ambientali. Sono state studiate le fenomenologie che possono inficiare la stabilità dei rilevati arginali, realizzati sia in corrispondenza dei corsi d’acqua, sia in corrispondenza del mare, a discapito della protezione idraulica del territorio ovvero dell’incolumità fisica dell’uomo e dei territori in cui esso vive e produce. In un rilevato arginale, quale che sia la causa innescante la formazione di breccia, la generazione di un’onda di piena conseguente la rottura è sempre determinata da un’azione erosiva (seepage o overtopping) esercitata dall’acqua sui materiali sciolti costituenti il corpo del rilevato. Perciò gran parte dello studio in materia di brecce arginali è incentrato sulla ricostruzione di siffatti eventi di rottura. Nel quarto capitolo è stata calcolata la probabilità, in 5 anni, di avere un allagamento nella zona di interesse e la velocità di propagazione del fronte d’onda. Inoltre è stata effettuata un’analisi delle condizioni meteo marine attuali (clima ondoso, livelli del mare e correnti) al largo della costa emiliano-romagnola, le cui problematiche e linee di intervento per la difesa sono descritte nel quinto capitolo, con particolare riferimento alla costa ferrarese, oggetto negli ultimi anni di continui interventi antropici. Introdotto il sistema Gis e le sue caratteristiche, si è passati a descrivere le varie fasi che hanno permesso di avere in output il file delle coordinate x, y, z dei punti significativi della costa, indispensabili al fine della simulazione Mike 21, le cui proprietà sono sviluppate nel sesto capitolo.

Crittoanalisi Logica di DES

La crittografia ha sempre rivestito un ruolo primario nella storia del genere umano, dagli albori ai giorni nostri, e il periodo in cui viviamo non fa certo eccezione. Al giorno d'oggi, molti dei gesti che vengono compiuti anche solo come abitudine (operazioni bancarie, apertura automatica dell'auto, accedere a Facebook, ecc.), celano al loro interno la costante presenza di sofisticati sistemi crittografici. Proprio a causa di questo fatto, è importante che gli algoritmi utilizzati siano in qualche modo certificati come ragionevolmente sicuri e che la ricerca in questo campo proceda costantemente, sia dal punto di vista dei possibili nuovi exploit per forzare gli algoritmi usati, sia introducendo nuovi e sempre più complessi sistemi di sicurezza. In questa tesi viene proposto una possibile implementazione di un particolare tipo di attacco crittoanalitico, introdotto nel 2000 da due ricercatori dell'Università "La Sapienza" di Roma, e conosciuto come "Crittoanalisi Logica". L'algoritmo su cui è incentrato il lavoro è il Data Encryption Standard (DES), ostico standard crittografico caduto in disuso nel 1999 a causa delle dimensioni ridotte della chiave, seppur tuttora sia algebricamente inviolato. Il testo è strutturato nel seguente modo: il primo capitolo è dedicato ad una breve descrizione di DES e della sua storia, introducendo i concetti fondamentali con cui si avrà a che fare per l'intera dissertazione Nel secondo capitolo viene introdotta la Crittoanalisi Logica e viene fornita una definizione della stessa, accennando ai concetti matematici necessari alla comprensione dei capitoli seguenti. Nel capitolo 3 viene presentato il primo dei due software sviluppati per rendere possibile l'attuazione di questo attacco crittoanalitico, una libreria per la rappresentazione e la manipolazione di formule logiche scritta in Java. Il quarto ed ultimo capitolo descrive il programma che, utilizzando la libreria descritta nel capitolo 3, elabora in maniera automatica un insieme di proposizioni logiche semanticamente equivalenti a DES, la cui verifica di soddisfacibilità, effettuata tramite appositi tools (SAT solvers) equivale ad effettuare un attacco di tipo known-plaintext su tale algoritmo.

Famiglie Normali per Operatori Sub-ellittici e i Teoremi di Montel e Koebe

Scopo della tesi è di estendere un celebre teorema di Montel, sulle famiglie normali di funzioni olomorfe, all'ambiente sub-ellittico delle famiglie di soluzioni u dell'equazione Lu=0, dove L appartiene ad un'ampia classe di operatori differenziali alle derivate parziali reali del secondo ordine in forma di divergenza, comprendente i sub-Laplaciani sui gruppi di Carnot, i Laplaciani sub-ellittici su arbitrari gruppi di Lie, oltre all'operatore di Laplace-Beltrami su varietà di Riemann. A questo scopo, forniremo una versione sub-ellittica di un altro notevole risultato, dovuto a Koebe, che caratterizza le funzioni armoniche come punti fissi di opportuni operatori integrali di media con nuclei non banali. Sarà fornito anche un adeguato sostituto della formula integrale di Cauchy.

Gravità teleparallela

Questo elaborato espone l'equivalenza tra la relatività generale di Einstein e una teoria poco conosciuta chiamata Gravità Teleparallela. Sebbene possono sembrare diverse, esse sono due modi equivalenti di vedere l'universo, la prima con spaziotempo curvo, curvatura e traiettorie geodetiche; la seconda con spazio piatto e la curvatura che si comporta come una forza. Per queste teorie si rivelano fondamentali elementi di geometria differenziale e tensoriale, come i tensori metrici, tensori di Riemann, derivate covarianti, oltre ai concetti fisici di tetrade, connessioni di Lorentz, sistemi inerziali e non.

Numerical and experimental investigation of turbulent dissipation

Turbulent energy dissipation is presented in the theoretical context of the famous Kolmogorov theory, formulated in 1941. Some remarks and comments about this theory help the reader understand the approach to turbulence study, as well as give some basic insights to the problem. A clear distinction is made amongst dissipation, pseudo-dissipation and dissipation surrogates. Dissipation regulates how turbulent kinetic energy in a flow gets transformed into internal energy, which makes this quantity a fundamental characteristic to investigate in order to enhance our understanding of turbulence. The dissertation focuses on experimental investigation of the pseudo-dissipation. Indeed this quantity is difficult to measure as it requires the knowledge of all the possible derivatives of the three dimensional velocity field. Once considering an hot-wire technique to measure dissipation we need to deal with surrogates of dissipation, since not all the terms can be measured. The analysis of surrogates is the main topic of this work. In particular two flows, the turbulent channel and the turbulent jet, are considered. These canonic flows, introduced in a brief fashion, are often used as a benchmark for CFD solvers and experimental equipment due to their simple structure. Observations made in the canonic flows are often transferable to more complicated and interesting cases, with many industrial applications. The main tools of investigation are DNS simulations and experimental measures. DNS data are used as a benchmark for the experimental results since all the components of dissipation are known within the numerical simulation. The results of some DNS were already available at the start of this thesis, so the main work consisted in reading and processing the data. Experiments were carried out by means of hot-wire anemometry, described in detail on a theoretical and practical level. The study of DNS data of a turbulent channel at Re=298 reveals that the traditional surrogate can be improved Consequently two new surrogates are proposed and analysed, based on terms of the velocity gradient that are easy to measure experimentally. We manage to find a formulation that improves the accuracy of surrogates by an order of magnitude. For the jet flow results from a DNS at Re=1600 of a temporal jet, and results from our experimental facility CAT at Re=70000, are compared to validate the experiment. It is found that the ratio between components of the dissipation differs between DNS and experimental data. Possible errors in both sets of data are discussed, and some ways to improve the data are proposed.