Permutation classes, sorting algorithms, and lattice paths

A permutation is said to avoid a pattern if it does not contain any subsequence which is order-isomorphic to it. Donald Knuth, in the first volume of his celebrated book "The art of Computer Programming", observed that the permutations that can be computed (or, equivalently, sorted) by some particular data structures can be characterized in terms of pattern avoidance. In more recent years, the topic was reopened several times, while often in terms of sortable permutations rather than computable ones. The idea to sort permutations by using one of Knuth’s devices suggests to look for a deterministic procedure that decides, in linear time, if there exists a sequence of operations which is able to convert a given permutation into the identical one. In this thesis we show that, for the stack and the restricted deques, there exists an unique way to implement such a procedure. Moreover, we use these sorting procedures to create new sorting algorithms, and we prove some unexpected commutation properties between these procedures and the base step of bubblesort. We also show that the permutations that can be sorted by a combination of the base steps of bubblesort and its dual can be expressed, once again, in terms of pattern avoidance. In the final chapter we give an alternative proof of some enumerative results, in particular for the classes of permutations that can be sorted by the two restricted deques. It is well-known that the permutations that can be sorted through a restricted deque are counted by the Schrӧder numbers. In the thesis, we show how the deterministic sorting procedures yield a bijection between sortable permutations and Schrӧder paths.

Interpreting Judgements using Knowledge Representation Methods and Computational Models of Argument

The goal of the present research is to define a Semantic Web framework for precedent modelling, by using knowledge extracted from text, metadata, and rules, while maintaining a strong text-to-knowledge morphism between legal text and legal concepts, in order to fill the gap between legal document and its semantics. The framework is composed of four different models that make use of standard languages from the Semantic Web stack of technologies: a document metadata structure, modelling the main parts of a judgement, and creating a bridge between a text and its semantic annotations of legal concepts; a legal core ontology, modelling abstract legal concepts and institutions contained in a rule of law; a legal domain ontology, modelling the main legal concepts in a specific domain concerned by case-law; an argumentation system, modelling the structure of argumentation. The input to the framework includes metadata associated with judicial concepts, and an ontology library representing the structure of case-law. The research relies on the previous efforts of the community in the field of legal knowledge representation and rule interchange for applications in the legal domain, in order to apply the theory to a set of real legal documents, stressing the OWL axioms definitions as much as possible in order to enable them to provide a semantically powerful representation of the legal document and a solid ground for an argumentation system using a defeasible subset of predicate logics. It appears that some new features of OWL2 unlock useful reasoning features for legal knowledge, especially if combined with defeasible rules and argumentation schemes. The main task is thus to formalize legal concepts and argumentation patterns contained in a judgement, with the following requirement: to check, validate and reuse the discourse of a judge - and the argumentation he produces - as expressed by the judicial text.

Use of shared memory in the context of embedded multi-core processors: exploration of the technology and its limits

Modern embedded systems embrace many-core shared-memory designs. Due to constrained power and area budgets, most of them feature software-managed scratchpad memories instead of data caches to increase the data locality. It is therefore programmers’ responsibility to explicitly manage the memory transfers, and this make programming these platform cumbersome. Moreover, complex modern applications must be adequately parallelized before they can the parallel potential of the platform into actual performance. To support this, programming languages were proposed, which work at a high level of abstraction, and rely on a runtime whose cost hinders performance, especially in embedded systems, where resources and power budget are constrained. This dissertation explores the applicability of the shared-memory paradigm on modern many-core systems, focusing on the ease-of-programming. It focuses on OpenMP, the de-facto standard for shared memory programming. In a first part, the cost of algorithms for synchronization and data partitioning are analyzed, and they are adapted to modern embedded many-cores. Then, the original design of an OpenMP runtime library is presented, which supports complex forms of parallelism such as multi-level and irregular parallelism. In the second part of the thesis, the focus is on heterogeneous systems, where hardware accelerators are coupled to (many-)cores to implement key functional kernels with orders-of-magnitude of speedup and energy efficiency compared to the “pure software” version. However, three main issues rise, namely i) platform design complexity, ii) architectural scalability and iii) programmability. To tackle them, a template for a generic hardware processing unit (HWPU) is proposed, which share the memory banks with cores, and the template for a scalable architecture is shown, which integrates them through the shared-memory system. Then, a full software stack and toolchain are developed to support platform design and to let programmers exploiting the accelerators of the platform. The OpenMP frontend is extended to interact with it.

Experimental Analysis and Numerical Simulation of Quench in Superconducting HTS Tapes and Coils

The quench characteristics of second generation (2 G) YBCO Coated Conductor (CC) tapes are of fundamental importance for the design and safe operation of superconducting cables and magnets based on this material. Their ability to transport high current densities at high temperature, up to 77 K, and at very high fields, over 20 T, together with the increasing knowledge in their manufacturing, which is reducing their cost, are pushing the use of this innovative material in numerous system applications, from high field magnets for research to motors and generators as well as for cables. The aim of this Ph. D. thesis is the experimental analysis and numerical simulations of quench in superconducting HTS tapes and coils. A measurements facility for the characterization of superconducting tapes and coils was designed, assembled and tested. The facility consist of a cryostat, a cryocooler, a vacuum system, resistive and superconducting current leads and signal feedthrough. Moreover, the data acquisition system and the software for critical current and quench measurements were developed. A 2D model was developed using the finite element code COMSOL Multiphysics R . The problem of modeling the high aspect ratio of the tape is tackled by multiplying the tape thickness by a constant factor, compensating the heat and electrical balance equations by introducing a material anisotropy. The model was then validated both with the results of a 1D quench model based on a non-linear electric circuit coupled to a thermal model of the tape, to literature measurements and to critical current and quench measurements made in the cryogenic facility. Finally the model was extended to the study of coils and windings with the definition of the tape and stack homogenized properties. The procedure allows the definition of a multi-scale hierarchical model, able to simulate the windings with different degrees of detail.

Design the support for granting required sla in public cloud environments based on cloud foundry

Through the use of Cloud Foundry "stack" concept, a new isolation is provided to the application running on the PaaS. A new deployment feature that can easily scale on distributed system, both public and private clouds.

Operating System Contribution to Composable Timing Behaviour in High-Integrity Real-Time Systems

The development of High-Integrity Real-Time Systems has a high footprint in terms of human, material and schedule costs. Factoring functional, reusable logic in the application favors incremental development and contains costs. Yet, achieving incrementality in the timing behavior is a much harder problem. Complex features at all levels of the execution stack, aimed to boost average-case performance, exhibit timing behavior highly dependent on execution history, which wrecks time composability and incrementaility with it. Our goal here is to restitute time composability to the execution stack, working bottom up across it. We first characterize time composability without making assumptions on the system architecture or the software deployment to it. Later, we focus on the role played by the real-time operating system in our pursuit. Initially we consider single-core processors and, becoming less permissive on the admissible hardware features, we devise solutions that restore a convincing degree of time composability. To show what can be done for real, we developed TiCOS, an ARINC-compliant kernel, and re-designed ORK+, a kernel for Ada Ravenscar runtimes. In that work, we added support for limited-preemption to ORK+, an absolute premiere in the landscape of real-word kernels. Our implementation allows resource sharing to co-exist with limited-preemptive scheduling, which extends state of the art. We then turn our attention to multicore architectures, first considering partitioned systems, for which we achieve results close to those obtained for single-core processors. Subsequently, we shy away from the over-provision of those systems and consider less restrictive uses of homogeneous multiprocessors, where the scheduling algorithm is key to high schedulable utilization. To that end we single out RUN, a promising baseline, and extend it to SPRINT, which supports sporadic task sets, hence matches real-world industrial needs better. To corroborate our results we present findings from real-world case studies from avionic industry.

Differenti approcci all'evoluzione di internet

Poiché internet interconnette miliardi di terminali on-line per fornire informazioni sempre più sofisticate, le infrastrutture dovranno essere sufficientemente "intelligenti" per gestire in tempo reale un enorme flusso di dati. Esistono due possibili approcci per sviluppare la nuova architettura, conosciuti come clean-state (PURSUIT e NetInf) ed overlay (DONA e NDN): con il primo metodo è necessario riprogettare l'intero stack protocollare mentre il secondo consente di creare un'infrastruttura avvalendosi delle funzionalità di una rete IP.

A new class of bragg stacks and its principle application

This work is focused on the development of high quality nanoporous 1D photonic crystals –so called Bragg stacks – made by spin-coating of approximately 25 nm large SiO2 and TiO2 nanoparticles bearing interparticle voids large enough to infiltrate reactive species. Therefore, the first part of this work describes the synthesis of well-dispersed TiO2 nanoparticles in this size range (the corresponding SiO2 nanoparticles are commercially available). In the second part, a protocol was developed to prepare nanoporous Bragg stacks of up to 12 bilayers with high quality and precision. Tailor-made Bragg stacks were prepared for different applications such as (i) a surface emitting feedback laser with a FWHM of only 6 nm and (ii) an electrochromic device with absorption reversibly switchable by an external electrical bias independently of the Bragg reflection. In the last chapter, the approach to 1D photonic crystals is transferred to 1D phononic crystals. Contrast in the modulus is achieved by spin-coating SiO2 and PMMA as high and low moduli material. This system showed a band gap of fg = 12.6 GHz with a width of Dfg/fg = 4.5 GHz.

Sistemi Informatici Mobili e Realtà Aumentata a supporto del lavoro cooperativo in scenari d'emergenza: studio e realizzazione di un caso applicativo

Scopo primario della tesi è studiare e progettare un sistema informatico che proponga un buon livello di innovazione tecnologica in relazione al contesto applicativo di riferimento, ovvero relativamente al supporto al lavoro cooperativo di operatori in scenari d'emergenza. In particolare, la tesi si concentra sul'ecosistema software che ruota attorno al singolo operatore con l'obiettivo di dotarlo di uno strumento informatico che gli consenta di avvalersi di un efficace ed efficiente supporto per l'esecuzione delle proprie azioni sul campo (in generale, per la prima assistenza ai pazienti, triage e monitoraggio di parametri vitali). A tal proposito, l'ambito tecnologico di riferimento è quello del Pervasive Mobile Computing, con specifico riferimento ai sistemi context-aware e a quelli con comportamenti fortemente autonomi. Inoltre, al fine di dotare l'operatore di un supporto per l'interazione con il sistema stesso in modalità hands-free, sono stati analizzati i dispositivi wearable di tipo "see-through"; in particolare, i recenti glasses per realtà aumentata. La progettazione del sistema e il conseguente sviluppo del prototipo (che implementa le caratteristiche più significative ed innovative), è stata guidata da un'ispirazione basata sul modello ad agenti (integrato a quello ad oggetti), rivisitando opportunamente l'utilizzo dei componenti offerti dalla tecnologia Android, al fine di ottenere un prodotto software robusto e modulare facilmente manutenibile ed estendibile. Infine, per garantire a ciascun operatore rapida fruibilità del sistema sono state sfruttate le potenzialità offerte dall'uso di smartcard NFC ed inoltre è stato progettato un protocollo di comunicazione ad hoc, basato su stack Bluetooth, per l'integrazione degli AR-Glasses all'intero sistema.

Integrating wireless sensor networks and internet of things: A coap-based approach

L'obiettivo su cui è stata basata questa Tesi di Laurea è stato quello di integrare la tecnologia delle Wireless Sensor Networks (WSN) al contesto dell'Internet delle cose (IoT). Per poter raggiungere questo obiettivo, il primo passo è stato quello di approfondire il concetto dell'Internet delle cose, in modo tale da comprendere se effettivamente fosse stato possibile applicarlo anche alle WSNs. Quindi è stata analizzata l'architettura delle WSNs e successivamente è stata fatta una ricerca per capire quali fossero stati i vari tipi di sistemi operativi e protocolli di comunicazione supportati da queste reti. Infine sono state studiate alcune IoT software platforms. Il secondo passo è stato quindi di implementare uno stack software che abilitasse la comunicazione tra WSNs e una IoT platform. Come protocollo applicativo da utilizzare per la comunicazione con le WSNs è stato usato CoAP. Lo sviluppo di questo stack ha consentito di estendere la piattaforma SensibleThings e il linguaggio di programmazione utilizzato è stato Java. Come terzo passo è stata effettuata una ricerca per comprendere a quale scenario di applicazione reale, lo stack software progettato potesse essere applicato. Successivamente, al fine di testare il corretto funzionamento dello stack CoAP, è stata sviluppata una proof of concept application che simulasse un sistema per la rilevazione di incendi. Questo scenario era caratterizzato da due WSNs che inviavano la temperatura rilevata da sensori termici ad un terzo nodo che fungeva da control center, il cui compito era quello di capire se i valori ricevuti erano al di sopra di una certa soglia e quindi attivare un allarme. Infine, l'ultimo passo di questo lavoro di tesi è stato quello di valutare le performance del sistema sviluppato. I parametri usati per effettuare queste valutazioni sono stati: tempi di durata delle richieste CoAP, overhead introdotto dallo stack CoAP alla piattaforma Sensible Things e la scalabilità di un particolare componente dello stack. I risultati di questi test hanno mostrato che la soluzione sviluppata in questa tesi ha introdotto un overheadmolto limitato alla piattaforma preesistente e inoltre che non tutte le richieste hanno la stessa durata, in quanto essa dipende dal tipo della richiesta inviata verso una WSN. Tuttavia, le performance del sistema potrebbero essere ulteriormente migliorate, ad esempio sviluppando un algoritmo che consenta la gestione concorrente di richieste CoAP multiple inviate da uno stesso nodo. Inoltre, poichè in questo lavoro di tesi non è stato considerato il problema della sicurezza, una possibile estensione al lavoro svolto potrebbe essere quello di implementare delle politiche per una comunicazione sicura tra Sensible Things e le WSNs.

Sviluppo e verifica di un framework basato su logica computazionale per la selezione dinamica di web services tramite informazioni

La presenza sempre più massiccia di fornitori di servizi basati su web service ha portato in rilievo uno dei limiti di questo approccio, l’impossibilità di rendere automatizzabili i task di ricerca, invocazione e orchestrazione dei servizi. Il raggiungimento di questo obiettivo risulta impossibile a causa della mancanza di informazioni comprensibili ad una macchina attraverso le quali un agente software può effettuare delle scelte tra vari servizi esposti. Il fallimento della “ricerca intelligente” di un servizio pubblicato sta nella stessa modellazione dei servizi. I linguaggi attualmente disponibili permettono di modellare un servizio solo dal punto di vista sintattico. Definire le operazioni proposte, il tipo di parametri accettati e il tipo di output prodotto non è sufficiente a comprendere cosa il servizio può fare. I web services semantici consentono di superare questo limite fornendo uno stack semantico, il quale ha il compito di racchiudere le informazioni relative ai servizi, il loro funzionamento e gli obiettivi raggiungibili organizzando la conoscenza in ontologie. La formalizzazione dei modelli ontologici e la loro integrazione con i servizi esistenti è uno dei problemi più interessanti che ha catturato l’attenzione di numerosi studi di settore. Negli ultimi anni numerose sono state le soluzioni proposte. Tra queste si possono considerare due principali vie di sviluppo che hanno visto un’intensa attività sperimentale. Il primo scenario è volto a modellare in maniera formale la conoscenza legata ai servizi esposti, il secondo integra i servizi già esistenti con nuove strutture semantiche in modo da conservare le infrastrutture presenti. Entrambi i filoni hanno come scopo quello di fornire la conoscenza adatta a sistemi esperti che consentano di automatizzare la ricerca dei servizi in base ai desideri dei clienti, permettendo la loro composizione dinamica basata su un’interazione utile e indipendente dai protocolli che vincolano il trasporto delle informazioni.

LoneStar : Design and evaluation of an energy-efficient, disk-based archival storage system

Bandlaufwerke waren bisher die vorherrschende Technologie, um die anfallenden Datenmengen in Archivsystemen zu speichern. Mit Zugriffsmustern, die immer aktiver werden, und Speichermedien wie Festplatten die kostenmäßig aufholen, muss die Architektur vor Speichersystemen zur Archivierung neu überdacht werden. Zuverlässigkeit, Integrität und Haltbarkeit sind die Haupteigenschaften der digitalen Archivierung. Allerdings nimmt auch die Zugriffsgeschwindigkeit einen erhöhten Stellenwert ein, wenn aktive Archive ihre gesamten Inhalte für den direkten Zugriff bereitstellen. Ein band-basiertes System kann die hierfür benötigte Parallelität, Latenz und Durchsatz nicht liefern, was in der Regel durch festplattenbasierte Systeme als Zwischenspeicher kompensiert wird.rnIn dieser Arbeit untersuchen wir die Herausforderungen und Möglichkeiten ein festplattenbasiertes Speichersystem zu entwickeln, das auf eine hohe Zuverlässigkeit und Energieeffizienz zielt und das sich sowohl für aktive als auch für kalte Archivumgebungen eignet. Zuerst analysieren wir die Speichersysteme und Zugriffsmuster eines großen digitalen Archivs und präsentieren damit ein mögliches Einsatzgebiet für unsere Architektur. Daraufhin stellen wir Mechanismen vor um die Zuverlässigkeit einer einzelnen Festplatte zu verbessern und präsentieren sowie evaluieren einen neuen, energieeffizienten, zwei- dimensionalen RAID Ansatz der für „Schreibe ein Mal, lese mehrfach“ Zugriffe optimiert ist. Letztlich stellen wir Protokollierungs- und Zwischenspeichermechanismen vor, die die zugrundeliegenden Ziele unterstützen und evaluieren das RAID System in einer Dateisystemumgebung.

Il processo di semplificazione di Meteor nello sviluppo di applicazioni web. L'esempio di Pachirajs.

L'obbiettivo di questa tesi è mostrare come attualmente sia possibile creare applicazioni web in maniera semplice e veloce, tramite l'utilizzo del framework Meteor.

Bluetooth per TuCSoN mobile: panorama tecnologico ed esperimenti

La tesi analizza lo stack di comunicazione Bluetooth e le possibili estensioni di TuCSoN per permettere il suo utilizzo. Come risultato di questo lavoro, sono state realizzate delle librerie software che permettono lo scambio di messaggi tra TuCSoN su Android e dispositivi Bluetooth.

Implementazione di un algoritmo di navigazione autonoma di alto livello e sviluppo software di una Control Ground Station

Caratteristiche hardware di un rover terrestre (progetto SHERPA). Implementazione tramite il framework ROS di un algoritmo di alto livello di navigazione autonoma basato su due possibili algoritmi di basso livello: LOS (Lightweight Object Streaming developed by BlueBotics) o Navigation Stack. Sviluppo di una Control Ground Station (Java) basata su: protocollo SSH2 oppure sfruttando la libreria LOS.