abstract: Imagine that we have a piece of matter that can change its physical properties like its shape, density, conductivity, or color in a programmable fashion based on either user input or autonomous sensing. This is the vision behind what is commonly known as programmable matter. Envisioning systems of nano-sensors devices, programmable matter consists of systems of simple computational elements, called particles, that can establish and release bonds, compute, and can actively move in a self-organized way. In this dissertation the feasibility of solving fundamental problems relevant for programmable matter is investigated. As a model for such self-organizing particle systems (SOPS), the geometric amoebot model is introduced. In this model, particles only have local information and have modest computational power. They achieve locomotion by expanding and contracting, which resembles the behavior of amoeba. Under this model, efficient local-control algorithms for the leader election problem in SOPS are presented. As a central problem for programmable matter, shape formation problems are then studied. The limitations of solving the leader election problem and the shape formation problem on a more general version of the amoebot model are also discussed. The \smart paint" problem is also studied which aims at having the particles self-organize in order to uniformly coat the surface of an object of arbitrary shape and size, forming multiple coating layers if necessary. A Universal Coating algorithm is presented and shown to be asymptotically worst-case optimal both in terms of time with high probability and work. In particular, the algorithm always terminates within a linear number of rounds with high probability. A linear lower bound on the competitive gap between fully local coating algorithms and coating algorithms that rely on global information is presented, which implies that the proposed algorithm is also optimal in a competitive sense. Simulation results show that the competitive ratio of the proposed algorithm may be better than linear in practice. Developed algorithms utilize only local control, require only constant-size memory particles, and are asymptotically optimal in terms of the total number of particle movements needed to reach the desired shape configuration. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2017

Submitted by Fernando Souza (fernandoafsou@gmail.com) on 2017-08-17T15:58:41Z No. of bitstreams: 1 arquivototal.pdf: 2509071 bytes, checksum: 7e5e11344bc01beb22fdb94bee3ccdcf (MD5) / Made available in DSpace on 2017-08-17T15:58:41Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 2509071 bytes, checksum: 7e5e11344bc01beb22fdb94bee3ccdcf (MD5) Previous issue date: 2016-02-24 / This work deals with the development of a framework based on computational and optimization methods for algorithmic composition, more precisely, for the generation of guitar solos. The proposed approach was considered semiautomatic because it makes use of small melodic fragments (licks), previously created from human models. The solos generated are from the musical style Blues and they are applied over a well-known harmonic model called 12-Bar Blues. A licks database was created in which small instances containing a subset of them were randomly derived so as to diversify the possible candidates to be in the solo that will be generated. Once the instance is created, one solves an optimization problem that consists of determining the optimal sequence of a subset of licks by using a integer linear programming model. A set of rules was implemented for creating a matrix that de nes the transition cost between the licks. The outputs generated were stored in the MusicXML format and they can be read by most applications that provide support for this type of le and are capable of displaying it using the tablatures format. The solos created were evaluated by a sample of 173 subjects, classi ed as beginners, intermediates and professional musicians. A web application was developed to streamline the evaluation process. The results obtained show that the solos whose licks were optimally sequenced were statistically much better evaluated than those randomly sequenced, which indicates that the proposed methodology was capable of producing, on average, solos with a favorable percentage of acceptance. / Este trabalho trata do desenvolvimento de um framework baseado em m etodos computacionais e de otimização para a composição algoritmica, mais especifi camente, para a geração de solos de guitarra. A abordagem proposta foi considerada semiautomatica pois faz uso de pequenos fragmentos mel odicos (licks) previamente criados a partir de modelos humanos. Os solos gerados possuem caracter sticas do estilo musical Blues e s~ao aplicados sobre um modelo de harmonia bastante conhecido denominado 12-Bar Blues. Um banco de dados de licks foi criado, do qual são realizados sorteios de instâncias menores do conjunto, diversifi cando os possíveis candidatos a estarem no solo a ser gerado. De posse da inst^ancia, um problema de otimiza c~ao, que consiste em sequenciar de forma otimizada um subconjunto de licks, e resolvido utilizando um modelo de programa c~ao linear inteira. Implementou-se um conjunto de regras para a criação de uma matriz que de ne o custo de transição entre os licks. As sa das geradas s~ao armazenadas no formato MusicXML e podem ser lidas pela maioria dos aplicativos que possuam suporte a esse tipo de arquivo e disponibilizem visualiza c~ao no formato de tablaturas. Os solos criados foram avaliados por uma amostra de 173 indiv duos, classi cados como m usicos iniciantes, intermedi arios e pro fissionais. Uma aplicação web foi desenvolvida para agilizar o processo de avaliação. Os resultados obtidos demonstram que os solos cujos licks foram sequenciados de forma otimizada foram estatisticamente mais bem avaliados que aqueles sequenciados aleatoriamente, indicando que a metodologia proposta foi capaz de produzir, em m edia, solos com percentual de aceitação favorável.

Un certain nombre de travaux basés sur les réseaux de capteurs sans fil s'intéressent à la gestion de l'énergie de ces capteurs. Cette énergie est, de fait, un facteur critique dans le fonctionnement de ces réseaux. Une construction adéquate des clusters de capteurs est un très bon moyen pour minimiser la consommation de cette énergie. La problématique liée à ces réseaux réside ainsi souvent dans leur durée de vie mais aussi dans le nécessaire maintien de la connectivité entre tous les capteurs. Ces deux aspects sont étroitement liés. Dans cette thèse, nous nous sommes focalisés sur ces deux volets, dans le contexte de réseaux de capteurs statiques mais aussi celui de capteurs mobiles.Nous proposons, dans un premier temps, un algorithme hybride pour la mise en place des clusters et la gestions de ces clusters. L'originalité de cette solution réside dans la mise en place de zones géographiques de désignation des cluster heads mais aussi dans la transmission, dans les messages échangés, de la quantité d'énergie restante sur les capteurs. Ainsi, les données sur les capteurs permettront de désigner les cluster heads et leurs successeurs qui détermineront les seuils pour les autres capteurs et pour leur fonctionnement. L'algorithme est testé à travers de nombreuses simulations. La seconde partie du travail consiste à adapter notre premier algorithme pour les réseaux de capteurs mobiles. Nous in_uons sur la trajectoire des capteurs pour maintenir la connectivité et limiter la consommation d'énergie. Pour cela, nous nous inspirons de l'écho-localisation pratiquée par les chauvessouris. Nous nous sommes donc intéressés à la topologie changeante et dynamique dans les réseaux de capteurs. Nous avons analysé la perte d'énergie en fonction de la distance et de la puissance de transmission entre les n÷uds et le cluster head. Nous évaluons également notre algorithme sur des capteurs qui ont un déplacement aléatoire. Nous appliquons ces algorithmes à une simulation de _otte de drones de surveillance. / A number of works based on wireless sensor networks are interested in the energy management of these sensors. This energy is in fact a critical factor in the operation of these networks. Proper construction of sensor clusters is a great way to minimize the consumption of this energy. The problems related to these networks and often lies in their lifetime but also in the need to maintain connectivity between all transducers. These two aspects are closely linked. In this thesis, we focused on these two aspects in the context of static sensor networks but also of mobile sensors.We propose, as a _rst step, a hybrid algorithm for setting up clusters and the management of theseclusters. The uniqueness of this solution lies in the establishment of geographic areas for designation fcluster heads but also in transmission, in the exchanged messages, the amount of remaining energy on the sensors. Thus, the sensor data will designate the cluster heads and their successors will determine the thresholds for other sensors and for their operation. The algorithm is tested through many simulations. The second part of the work is to adapt our _rst algorithm for mobile sensor networks. We a_ect the trajectory of sensors to maintain connectivity and reduce energy consumption. For this, we are guided echo-location practiced by bats. We're interested in changing and dynamic topology in sensor networks. We analyzed the loss of energy as a function of the distance and the power transmission between the nodes and the head cluster. We also evaluate our algorithm on sensors that have a random move. We apply these algorithms to a _eet of surveillance drones simulation.

In order that epistemic formulas might be coupled with approximate databases, it is necessary to have a well-defined semantics for the knowledge operator and a method of reducing epistemic formulas to approximate formulas. In this thesis, two possible definitions of a semantics for the knowledge operator are proposed for use together with an approximate relational database: * One based upon logical entailment (being the dominating notion of knowledge in literature); sound and complete rules for reduction to approximate formulas are explored and found not to be applicable to all formulas. * One based upon algorithmic computability (in order to be practically feasible); the correspondence to the above operator on the one hand, and to the deductive capability of the agent on the other hand, is explored. Also, an inductively defined semantics for a"know whether"-operator, is proposed and tested. Finally, an algorithm implementing the above is proposed, carried out using Java, and tested.

La méthode du Pincement a été développée et utilisée dans le secteur de la pétrochimie. Le nombre de flux y est important et la consommation énergétique est un critère décisionnel fort. D'autres secteurs énergivores tels la métallurgie, la production de papier et de pâte à papier ou l'industrie agroalimentaire peuvent bénéficier de cette approche structurée. Par ailleurs, l'intégration d'utilités thermodynamiques complexes comme les pompes à chaleur ou les unités de cogénération peut réduire significativement la consommation d'énergie d'un procédé, sans avoir à en modifier la technologie.Un algorithme de conception d'un réseau d'échangeurs à partir de flux thermiques à été choisi dans la littérature, puis deux fonctionnalités lui ont été ajoutées : la différenciation des technologies d'échangeur et la prise en compte de flux "disponibilités" à température de sortie variable. Un module de présélection a été développé pour proposer et dimensionner des utilités thermodynamiques à partir de la grande courbe composite et d'un critère exergétique. Il est utilisé en amont de la conception du réseau d'échangeurs.Ces deux algorithmes ont été intégrés dans un logiciel dédié à l'intégration énergétique de procédés à partir des flux thermiques des opérations unitaires. Plusieurs validations ont été faites sur des cas théoriques de référence issus de la littérature ainsi que sur des cas industriels réels nécessitant la modélisation des procédés. L'enchainement des deux algorithmes débouche sur l'obtention de résultats concrets et technologiquement réalistes. L'amélioration apportée par les solutions est calculable à chaque étape. / The pinch analysis has been developed and exploited in the petrochemical sector. There are numerous heat fluxes and energy consumption is a strong decision criterion. Other energy-intensive sectors such as metallurgy, pulp and paper and food & drink industry can benefit from this systemic approach. Moreover, integration of complex thermodynamic utilities such heat pumps or Combined Heat and Power units can significantly reduce the energy consumption of a process, without having to interfere with the process technology.An algorithm for heat exchangers network design from heat fluxes was chosen in the literature and two features were added to it: Ability to pick different heat exchanger technology and creation of "availabilities" heat fluxes whose outlet temperature is variable. Preselection tool has been developed from grand composite curve and exergetic criterion to propose and pre-size thermodynamics utilities. It is used upstream of the heat exchangers network design step.These two algorithms have been integrated into a software for energy integration of process unit operations heat fluxes. Several validations were made on study cases from the literature as well as on industrial cases which require process modelling. The both algorithms sequence allows achieving practical and technologically feasible results. Improvement on energy consumption provided by the solutions can be calculated at each step.

Cette thèse montre la possibilité d’une application rigoureuse de la méthode d’intégrationnumérique double-exponentielle introduite par Takahasi et Morien 1974, et sa pertinence pour lescalculs à grande précision en théorie des nombres. Elle contient en particulier une étude détailléede cette méthode, des critères simples sur son champ d’application, et des estimations rigoureusesdes termes d’erreur.Des paramètres explicités et précis permettent de l’employer aisément pour le calcul garantide fonctions définies par des intégrales.Cette méthode est également appliquée en détail au calcul de transformées de Mellin inversesde facteurs gamma intervenant dans les calculs numériques de fonctions L. Par une étude unifiée,ce travail démontre la complexité d’un algorithme de M. Rubinstein et permet de proposer desalgorithmes de calcul de valeurs de fonctions L quelconques dont le résultat est garanti et dont lacomplexité est meilleure en la précision. / This thesis contains a detailed study of the so-called double exponential integration formulasintroduced by Takahasi and Moriin 1974,and provides explicit bounds forarigorous applicationof the method in number theory.Accurate parameters are given, which makes it possible to use it as a blackbox for the rigorouscomputation of functions defined by integrals.It also deals with numerical computations of L functions. The complexity of analgorithm dueto M. Rubinstein is proven. In the context of double-exponential transformation, a new algorithmis provided whose complexity is low in terms of precision.

The thesis analyses high frequency trading, specifically its main characteristics, which make it different from algorithmic trading. Furthermore, the thesis looks closer into major risks, which are new to market, and their impact on market quality and other investors. The next chapter is dedicated to trading strategies, which are typical for high frequency trading. In conclusion, there is discussed the impact on the market quality caused by high frequency trading, namely in terms of liquidity, volatility and price discovery.

Cette thèse concerne l'élaboration de stratégies de commande prédictive pour certaines classes de systèmes dynamiques continus, discrets et hybrides modélisés par des extensions de réseaux de Petri ad hoc. Pour les systèmes continus et en vue de limiter la complexité de calcul inhérente à la forme standard de la commande prédictive, plusieurs améliorations sont proposées. Celles-ci permettent de surmonter le problème de "hill climbing" caractéristique des trajectoires obtenues avec certains réseaux de Petri. Elles assurent également la possibilité d'implémenter la commande en temps réel en adaptant l'horizon de prédiction pour réduire la complexité algorithmique. Enfin, elles permettent de limiter la sollicitation des actionneurs tout en garantissant la stabilité asymptotique du système commandé. Pour les systèmes discrets temporisés et pour éviter l'exploration exhaustive du graphe d'atteignabilité, une méthode de commande est proposée, basée sur la commande prédictive appliquée à une approximation continue du système discret. Enfin pour les systèmes hybrides, une commande prédictive hybride est développée, inspirée de la commande prédictive continue. Les performances de ces différentes stratégies de commande sont évaluées et comparées avec différentes simulations numériques / This thesis concerns the development of predictive control strategies for some classes of continuous, discrete and hybrid dynamic systems modeled by specific extensions of Petri nets. For continuous systems and in order to limit the computational complexity inherent to the standard form of the predictive control, several improvements are proposed. These improvements allow overcoming the problem of hill climbing that characterizes trajectories obtained with some Petri nets. They also ensure the possibility to implement real-time control by adapting the prediction horizon in order to reduce the algorithmic complexity. Finally, they limit actuators solicitation while ensuring the asymptotic stability of the controlled system. For timed discrete systems and in order to avoid the exhaustive exploration of the reachability graph, a control method is proposed, based on the predictive control applied to a continuous approximation of the discrete system. Finally for hybrid systems, hybrid predictive control is developed, inspired by the continuous predictive control. The performance of these different control strategies are evaluated and compared to different numerical simulations.

In Finance, the use of Automated Trading Systems (ATS) on markets is growing every year and the trades generated by an algorithm now account for most of orders that arrive at stock exchanges (Kissell, 2020). Historically, these systems were based on advanced statistical methods and signal processing designed to extract trading signals from financial data. The recent success of Machine Learning has attracted the interest of the financial community. Reinforcement Learning is a subcategory of machine learning and has been broadly applied by investors and researchers in building trading systems (Kissell, 2020). In this thesis, we address the issue that deep reinforcement learning may be susceptible to sampling errors and over-fitting and propose a robust deep reinforcement learning method that integrates techniques from reinforcement learning and robust optimization. We back-test and compare the performance of the developed algorithm, Robust DDPG, with UBAH (Uniform Buy and Hold) benchmark and other RL algorithms and show that the robust algorithm of this research can reduce the downside risk of an investment strategy significantly and can ensure a safer path for the investor’s portfolio value.

This case study explored perceived artificial intelligence (AI) performance and intended future use (IFU) in users of AI-based applications. Users could become less motivated to use these applications if AIs do not clearly communicate their actions. A prototype, a user test, and a structured interview were iteratively developed. Eight students participated in the final iteration, which was thematically analyzed. The results indicate that an AI-based application that shows recommendations can positively affect perceived AI performance and IFU. Possibly, the recommendations increased users’ understanding of AI decisions, as well as their satisfaction. Therefore, recommendations could be a potential design element for increasing perceived AI performance and IFU. Finally, time-saving functionality is a design element that could lead to higher IFU in AI-based applications, possibly only for other tasks than examining recommendations. Further research needs to test these findings under different circumstances.