A study on set variable representations in constraint programming

Il lavoro presentato in questa tesi si colloca nel contesto della programmazione con vincoli, un paradigma per modellare e risolvere problemi di ricerca combinatoria che richiedono di trovare soluzioni in presenza di vincoli. Una vasta parte di questi problemi trova naturale formulazione attraverso il linguaggio delle variabili insiemistiche. Dal momento che il dominio di tali variabili può essere esponenziale nel numero di elementi, una rappresentazione esplicita è spesso non praticabile. Recenti studi si sono quindi focalizzati nel trovare modi efficienti per rappresentare tali variabili. Pertanto si è soliti rappresentare questi domini mediante l'uso di approssimazioni definite tramite intervalli (d'ora in poi rappresentazioni), specificati da un limite inferiore e un limite superiore secondo un'appropriata relazione d'ordine. La recente evoluzione della ricerca sulla programmazione con vincoli sugli insiemi ha chiaramente indicato che la combinazione di diverse rappresentazioni permette di raggiungere prestazioni di ordini di grandezza superiori rispetto alle tradizionali tecniche di codifica. Numerose proposte sono state fatte volgendosi in questa direzione. Questi lavori si differenziano su come è mantenuta la coerenza tra le diverse rappresentazioni e su come i vincoli vengono propagati al fine di ridurre lo spazio di ricerca. Sfortunatamente non esiste alcun strumento formale per paragonare queste combinazioni. Il principale obiettivo di questo lavoro è quello di fornire tale strumento, nel quale definiamo precisamente la nozione di combinazione di rappresentazioni facendo emergere gli aspetti comuni che hanno caratterizzato i lavori precedenti. In particolare identifichiamo due tipi possibili di combinazioni, una forte ed una debole, definendo le nozioni di coerenza agli estremi sui vincoli e sincronizzazione tra rappresentazioni. Il nostro studio propone alcune interessanti intuizioni sulle combinazioni esistenti, evidenziandone i limiti e svelando alcune sorprese. Inoltre forniamo un'analisi di complessità della sincronizzazione tra minlex, una rappresentazione in grado di propagare in maniera ottimale vincoli lessicografici, e le principali rappresentazioni esistenti.

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.

Programming Robots with an Agent-Oriented BDI-based Control Architecture: Explorations using the JaCa and Webots Platforms

La crescente disponibilità di dispositivi meccanici e -soprattutto - elettronici le cui performance aumentano mentre il loro costo diminuisce, ha permesso al campo della robotica di compiere notevoli progressi. Tali progressi non sono stati fatti unicamente per ciò che riguarda la robotica per uso industriale, nelle catene di montaggio per esempio, ma anche per quella branca della robotica che comprende i robot autonomi domestici. Questi sistemi autonomi stanno diventando, per i suddetti motivi, sempre più pervasivi, ovvero sono immersi nello stesso ambiente nel quale vivono gli essere umani, e interagiscono con questi in maniera proattiva. Essi stanno compiendo quindi lo stesso percorso che hanno attraversato i personal computer all'incirca 30 anni fa, passando dall'essere costosi ed ingombranti mainframe a disposizione unicamente di enti di ricerca ed università, ad essere presenti all'interno di ogni abitazione, per un utilizzo non solo professionale ma anche di assistenza alle attività quotidiane o anche di intrattenimento. Per questi motivi la robotica è un campo dell'Information Technology che interessa sempre più tutti i tipi di programmatori software. Questa tesi analizza per prima cosa gli aspetti salienti della programmazione di controllori per robot autonomi (ovvero senza essere guidati da un utente), quindi, come l'approccio basato su agenti sia appropriato per la programmazione di questi sistemi. In particolare si mostrerà come un approccio ad agenti, utilizzando il linguaggio di programmazione Jason e quindi l'architettura BDI, sia una scelta significativa, dal momento che il modello sottostante a questo tipo di linguaggio è basato sul ragionamento pratico degli esseri umani (Human Practical Reasoning) e quindi è adatto alla implementazione di sistemi che agiscono in maniera autonoma. Dato che le possibilità di utilizzare un vero e proprio sistema autonomo per poter testare i controllori sono ridotte, per motivi pratici, economici e temporali, mostreremo come è facile e performante arrivare in maniera rapida ad un primo prototipo del robot tramite l'utilizzo del simulatore commerciale Webots. Il contributo portato da questa tesi include la possibilità di poter programmare un robot in maniera modulare e rapida per mezzo di poche linee di codice, in modo tale che l'aumento delle funzionalità di questo risulti un collo di bottiglia, come si verifica nella programmazione di questi sistemi tramite i classici linguaggi di programmazione imperativi. L'organizzazione di questa tesi prevede un capitolo di background nel quale vengono riportare le basi della robotica, della sua programmazione e degli strumenti atti allo scopo, un capitolo che riporta le nozioni di programmazione ad agenti, tramite il linguaggio Jason -quindi l'architettura BDI - e perché tale approccio è adatto alla programmazione di sistemi di controllo per la robotica. Successivamente viene presentata quella che è la struttura completa del nostro ambiente di lavoro software che comprende l'ambiente ad agenti e il simulatore, quindi nel successivo capitolo vengono mostrate quelle che sono le esplorazioni effettuate utilizzando Jason e un approccio classico (per mezzo di linguaggi classici), attraverso diversi casi di studio di crescente complessità; dopodiché, verrà effettuata una valutazione tra i due approcci analizzando i problemi e i vantaggi che comportano questi. Infine, la tesi terminerà con un capitolo di conclusioni e di riflessioni sulle possibili estensioni e lavori futuri.

Reuse Mechanisms and Concurrency: From Actors to Agent-Oriented Programming

La presente tesi è dedicata al riuso nel software. Eccettuata un'introduzione organica al tema, l'analisi è a livello dei meccanismi offerti dai linguaggi di programmazione e delle tecniche di sviluppo, con speciale attenzione rivolta al tema della concorrenza. Il primo capitolo fornisce un quadro generale nel quale il riuso del software è descritto, assieme alle ragioni che ne determinano l'importanza e ai punti cruciali relativi alla sua attuazione. Si individuano diversi livelli di riuso sulla base dell'astrazione e degli artefatti in gioco, e si sottolinea come i linguaggi contribuiscano alla riusabilità e alla realizzazione del riuso. In seguito, viene esplorato, con esempi di codice, il supporto al riuso da parte del paradigma ad oggetti, in termini di incapsulamento, ereditarietà, polimorfismo, composizione. La trattazione prosegue analizzando differenti feature – tipizzazione, interfacce, mixin, generics – offerte da vari linguaggi di programmazione, mostrando come esse intervengano sulla riusabilità dei componenti software. A chiudere il capitolo, qualche parola contestualizzata sull'inversione di controllo, la programmazione orientata agli aspetti, e il meccanismo della delega. Il secondo capitolo abbraccia il tema della concorrenza. Dopo aver introdotto l'argomento, vengono approfonditi alcuni significativi modelli di concorrenza: programmazione multi-threaded, task nel linguaggio Ada, SCOOP, modello ad Attori. Essi vengono descritti negli elementi fondamentali e ne vengono evidenziati gli aspetti cruciali in termini di contributo al riuso, con esempi di codice. Relativamente al modello ad Attori, viene presentata la sua implementazione in Scala/Akka come caso studio. Infine, viene esaminato il problema dell'inheritance anomaly, sulla base di esempi e delle tre classi principali di anomalia, e si analizza la suscettibilità del supporto di concorrenza di Scala/Akka a riscontrare tali problemi. Inoltre, in questo capitolo si nota come alcuni aspetti relativi al binomio riuso/concorrenza, tra cui il significato profondo dello stesso, non siano ancora stati adeguatamente affrontati dalla comunità informatica. Il terzo e ultimo capitolo esordisce con una panoramica dell'agent-oriented programming, prendendo il linguaggio simpAL come riferimento. In seguito, si prova ad estendere al caso degli agenti la nozione di riuso approfondita nei capitoli precedenti.

Mimicking the one-dimensional marginal distributions of stochastic diffusions

In the large maturity limit, we compute explicitly the Local Volatility surface for Heston, through Dupire’s formula, with Fourier pricing of the respective derivatives of the call price. Than we verify that the prices of European call options produced by the Heston model, concide with those given by the local volatility model where the Local Volatility is computed as said above.

Game programming: Grafica 3d

Tesi riguardante la creazione di tutte le risorse grafiche necessarie ad un videogioco tridimensionale in prima persona con Blender e Unity3D. Gli argomenti trattati sono: prgettazione, 3D modeling, texturing e shading.

Game programming: sviluppo di un gioco

La tesi riguarda tutto il processo di progettazione di un videogioco e l'implementazione dello stesso. Gli argomenti trattati sono: Unity, Design & Gameplay e l'implementazioni del progetto.

Pricing in stochastic-local volatility models with default

In recent years is becoming increasingly important to handle credit risk. Credit risk is the risk associated with the possibility of bankruptcy. More precisely, if a derivative provides for a payment at cert time T but before that time the counterparty defaults, at maturity the payment cannot be effectively performed, so the owner of the contract loses it entirely or a part of it. It means that the payoff of the derivative, and consequently its price, depends on the underlying of the basic derivative and on the risk of bankruptcy of the counterparty. To value and to hedge credit risk in a consistent way, one needs to develop a quantitative model. We have studied analytical approximation formulas and numerical methods such as Monte Carlo method in order to calculate the price of a bond. We have illustrated how to obtain fast and accurate pricing approximations by expanding the drift and diffusion as a Taylor series and we have compared the second and third order approximation of the Bond and Call price with an accurate Monte Carlo simulation. We have analysed JDCEV model with constant or stochastic interest rate. We have provided numerical examples that illustrate the effectiveness and versatility of our methods. We have used Wolfram Mathematica and Matlab.

Stochastic local volatility model for fx markets

Questa tesi verte sullo studio di un modello a volatilità stocastica e locale, utilizzato per valutare opzioni esotiche nei mercati dei cambio. La difficoltà nell'implementare un modello di tal tipo risiede nella calibrazione della leverage surface e uno degli scopi principali di questo lavoro è quello di mostrarne la procedura.

New integer programming models for balanced multi-country kep

Le persone che soffrono di insufficienza renale terminale hanno due possibili trattamenti da affrontare: la dialisi oppure il trapianto di organo. Nel caso volessero seguire la seconda strada, oltre che essere inseriti nella lista d'attesa dei donatori deceduti, possono trovare una persona, come il coniuge, un parente o un amico, disposta a donare il proprio rene. Tuttavia, non sempre il trapianto è fattibile: donatore e ricevente possono, infatti, presentare delle incompatibilità a livello di gruppo sanguigno o di tessuto organico. Come risposta a questo tipo di problema nasce il KEP (Kidney Exchange Program), un programma, ampiamente avviato in diverse realtà europee e mondiali, che si occupa di raggruppare in un unico insieme le coppie donatore/ricevente in questa stessa situazione al fine di operare e massimizzare scambi incrociati di reni fra coppie compatibili. Questa tesi approffondisce tale questione andando a valutare la possibilità di unire in un unico insieme internazionale coppie donatore/ricevente provenienti da più paesi. Lo scopo, naturalmente, è quello di poter ottenere un numero sempre maggiore di trapianti effettuati. Lo studio affronta dal punto di vista matematico problematiche legate a tale collaborazione: i paesi che eventualmente accettassero di partecipare a un simile programma, infatti, devono avere la garanzia non solo di ricavarne un vantaggio, ma anche che tale vantaggio sia equamente distribuito fra tutti i paesi partecipanti.

Chargaff symmetric stochastic processes

Scopo della modellizzazione delle stringhe di DNA è la formulazione di modelli matematici che generano sequenze di basi azotate compatibili con il genoma esistente. In questa tesi si prendono in esame quei modelli matematici che conservano un'importante proprietà, scoperta nel 1952 dal biochimico Erwin Chargaff, chiamata oggi "seconda regola di Chargaff". I modelli matematici che tengono conto delle simmetrie di Chargaff si dividono principalmente in due filoni: uno la ritiene un risultato dell'evoluzione sul genoma, mentre l'altro la ipotizza peculiare di un genoma primitivo e non intaccata dalle modifiche apportate dall'evoluzione. Questa tesi si propone di analizzare un modello del secondo tipo. In particolare ci siamo ispirati al modello definito da da Sobottka e Hart. Dopo un'analisi critica e lo studio del lavoro degli autori, abbiamo esteso il modello ad un più ampio insieme di casi. Abbiamo utilizzato processi stocastici come Bernoulli-scheme e catene di Markov per costruire una possibile generalizzazione della struttura proposta nell'articolo, analizzando le condizioni che implicano la validità della regola di Chargaff. I modelli esaminati sono costituiti da semplici processi stazionari o concatenazioni di processi stazionari. Nel primo capitolo vengono introdotte alcune nozioni di biologia. Nel secondo si fa una descrizione critica e prospettica del modello proposto da Sobottka e Hart, introducendo le definizioni formali per il caso generale presentato nel terzo capitolo, dove si sviluppa l'apparato teorico del modello generale.

Stochastic modeling of bacterial protein domains distribution to predict horizontal gene transfer

In questo elaborato, abbiamo tentato di modellizzare i processi che regolano la presenza dei domini proteici. I domini proteici studiati in questa tesi sono stati ottenuti dai genomi batterici disponibili nei data base pubblici (principalmente dal National Centre for Biotechnology Information: NCBI) tramite una procedura di simulazione computazionale. Ci siamo concentrati su organismi batterici in quanto in essi la presenza di geni trasmessi orizzontalmente, ossia che parte del materiale genetico non provenga dai genitori, e assodato che sia presente in una maggiore percentuale rispetto agli organismi più evoluti. Il modello usato si basa sui processi stocastici di nascita e morte, con l'aggiunta di un parametro di migrazione, usato anche nella descrizione dell'abbondanza relativa delle specie in ambito delle biodiversità ecologiche. Le relazioni tra i parametri, calcolati come migliori stime di una distribuzione binomiale negativa rinormalizzata e adattata agli istogrammi sperimentali, ci induce ad ipotizzare che le famiglie batteriche caratterizzate da un basso valore numerico del parametro di immigrazione abbiano contrastato questo deficit con un elevato valore del tasso di nascita. Al contrario, ipotizziamo che le famiglie con un tasso di nascita relativamente basso si siano adattate, e in conseguenza, mostrano un elevato valore del parametro di migrazione. Inoltre riteniamo che il parametro di migrazione sia direttamente proporzionale alla quantità di trasferimento genico orizzontale effettuato dalla famiglia batterica.