Quelques algorithmes entre le monde des graphes et les nuages de points.

Le terme gridshell désigne une coque discrète qui est obtenue par déformation élastique d'une grille bidirectionnelle continue plane sans rigidité en cisaillement puis rigidifiée par une troisième direction de barres. Ainsi défini, un gridshell a un potentiel structural intéressant et peut répondre à des exigences architecturales complexes. La recherche de forme de ces structures a été menée à travers l'histoire principalement par deux méthodes, la méthode du filet inversé et la relaxation dynamique. Ces deux méthodes permettent d'obtenir une forme approchée de celle proposée par l'architecte, dérivant d'une grille à plat et de conditions aux limites partiellement ou complètement imposées. Dans le cadre de cette thèse, nous nous sommes intéressés à générer un gridshell sur une surface à forme et contours imposés. Un outil numérique se basant sur la méthode du compas a été développé. Il permet de mailler un réseau de Tchebychev sur une surface connaissant son équation cartésienne. Un autre outil permettant le maillage se basant sur un calcul en éléments finis explicite a été mis en œuvre. La particularité de cette technique est de pouvoir tenir en compte des propriétés mécaniques de la structure et de simuler le comportement du gridshell. Des applications des deux méthodes sur des formes architecturalement intéressantes ont permis de voir les limitations de la possibilité de mailler une forme avec un réseau de Tchebychev. La méthode du compas a ensuite été couplée à des algorithmes métaheuristiques types génétiques. L'algorithme résultant permet d'optimiser un gridshell en minimisant la courbure dans les barres et donc les contraintes dans la structure introduites lors de la mise en forme. Il a été mis en œuvre et testé pour plusieurs surfaces / Gridshells are often defined as structures that have the shape and rigidity of a double curvature shell but they consist of a grid and not a continuous surface. They are obtained by elastic deformation of a two-way grid initially flat. The deformed grid is then rigidified using a third direction of bars. Thus, a gridshell has an interesting structural potential and can respond to complex architectural requirements. Two methods have been used through out history for the form finding of gridshells, the inversion method and the dynamic relaxation method. Both techniques lead to a deformed grid which is a result of calculations. The form obtained is closed to the one proposed by the architect. A numerical tool based on the compass method is developed in this thesis. It allows mapping aTchebychev net on an imposed form and imposed boundary conditions.Another tool based on an explicit dynamic finite element calculationis proposed. The particularity of this technique is to be able to take into account the mechanical properties of the structure and to simulate the gridshell behavior. Applications of both methods on differents forms show the limitations of mapping a Tchebychev net on an imposed form. The compass method has been coupled with geneticalgorithms. The algorithm optimizes the gridshell by minimizing the curvature in bars in order not to break the bars during the construction. It has been implemented and tested on several surfaces

Dans le contexte actuel de compétitivité des marchés, la maîtrise et l'optimisation des processus de conception et de planification sont nécessaires pour garantir, d'une part la fiabilité et la qualité des produits systèmes ou services conçus et, d'autre part, le cycle de développement et les coûts. Ce constat impose de développer et d'améliorer les méthodes, modèles, techniques et outils relatifs aux processus de conception et de gestion ou de planification. Les travaux présentés dans cette thèse s'inscrivent dans ce contexte et proposent de mettre en relation ou encore de faire intéragir la configuration de produit avec la planification du projet de réalisation. Le but de ces travaux est d'apporter une aide à la décision pour le couplage de la configuration de produit et de la planification du projet associé, en exploitant deux outils issus de l'Intelligence Artificielle : les approches par contraintes et les algorithmes évolutionnaires. Cette aide à la décision est présentée en deux parties. La première partie décrit l'utilisation des approches par contraintes afin de permettre au décideur de configurer son produit et son projet de réalisation de manière simultanée et interactive. Pour ce faire, les techniques de propagation et de filtrage des contraintes sont exploitées spécifiquement. La deuxième partie s'intéresse à l'exploitation des algorithmes évolutionnaires pour optimiser l'espace de solutions selon les critères coût et délai afin de présenter au décideur, un ensemble réduit de solutions optimisées. Un algorithme SPEA2 modifié en intégrant des méthodes de filtrage dans ses opérateurs de parcours de l'espace de recherche y est présenté. Toutes nos propositions sont illustrées sur un exemple d'avion de tourisme et d'affaire. / In the actual context of market the control and optimization of design processes are essential to ensure on the one hand, the reliability and quality of products, on the other hand the development time and costs. This phenomenon involves the constant development of methodologies, in order to improve the diversity and quality of the product and at the same time to shorten their development time and decrease their cost The work presented in this thesis fits into this context and propose to associate products configuration and production process planning. The aim of this work is to provide decision support for the coupling of onfiguration products and the associate production process leveraging two tools of Artificial Intelligence : constraints approaches and evolutionary algorithms. This decision support is presented in two parts. The first part decribes the use of constraints approaches to allow decison-maker to configure product and its production process simultaneously and interactively. For this aim, propagation and filtring techniques are exploited specifically. The second part deals with the use of evolutionary algorithms to optimize the space solutions according to time and cost criteria in order to provide a small set of optimized solutions to the decision-maker. SPEA2 algorithm modified by incorporating filtering methods in its evolutionary operators. All our proposals ara illustrated on an exemple of light aitcraft.

Il existe de nombreuses méthodes d'optimisation du routage réseau en général. Dans cette thèse nous nous intéressons au développement d'algorithmes distribués permettant une stabilisation, au sens de Nash, des flux réseaux. Nous rappelons tout d'abord brièvement le contexte général d'Internet aujourd'hui et quelques notions de théorie des jeux. Nous présentons un jeu de tarification simple à deux joueurs, que la méthode des joueurs fictifs permet de faire converger. Puis nous présentons un jeu de routage plus complexe, à n joueurs, basé sur le modèle de Wardrop, ainsi qu'un algorithme de comportement distribué qui permet au système de converger vers un équilibre de Wardrop (équilibre social). Ces équilibres sont confondus avec les équilibres de Nash dans le cas limite où un joueur représente une partie infinitésimale du trafic. Nous présentons ensuite un raffinement de notre représentation initiale du problème, qui permet une diminution de sa complexité, en terme de dimension des espaces de stratégies et de temps de calcul. Nous montrons qu'il s'agit d'une bonne heuristique d'approximation de la première méthode trop coûteuse, sa qualité dépend d'un unique paramètre. Enfin, nous concluons par la présentation de résultats de simulation qui montrent que notre méthode distribuée est effectivement capable d'apprendre les meilleurs équilibres du système. / There are several approaches for optimizing network routing in general. In this document, we are interested in developping distributed algorithms able to stabilize the network flows in the sense of Nash. We introduce the general context of the Internet today along with a few key-notions in game theory. We show a simple two-player tarification game that the fictitious player dynamics is able to solve. Then, we introduce a more complex routing game with n players based on the Wardrop model and a distributed learning algorithm that allows the system to converge towards Wardop equilibria (social equilibrium). These equilibria also are Nash equilibria in the limit case where a player is an infinitesimal part of the network flow. We present a refinement of our initial representation of the problem that narrows down its complexity, in terms of the size of the strategy space and computation time. We show that it is a good heuristic for approximating the previous method, its quality relies upon only one parameter. Finally, we conclude with simulations results, showing that our distributed method is able to learn the best equilibriua of the system.

ALICE est dédié à l'étude d'un état de la matière nucléaire dans lequel les quarks et les gluons ne sont plus confinés dans les hadrons, qui est appelé Quark Gluon Plasma (QGP). La production de bottomonia (états liés beauté antibeauté) est sensible au QGP parce-que les états du bottomonium sont formés avant la formation du QGP et traversent le plasma pendant son évolution. L'objectif principal de cette thèse est la mesure des modification des mésons Upsilon dans le canal de désintégration en deux muons en collisions Pb-Pb à √SNN = 5.02 TeV. En outre, un nouveau framework pour l'analyse des performances des détecteurs utilisés pour l'identification des muons a été réalisé et utilisé pour l'analyse des données du RUN1 et RUN2 du LHC. Enfin, et avec l’objectif d’optimiser des résultats de l’analyse, un nouvel algorithme d’identification de muons a été développé. Cet algorithme deviendra nécessaire pour faire face aux nouvelles conditions de prise de données du RUN3, pendant lequel une reconstitution quasi-en ligne du détecteur est prévue. / ALICE is devoted to the study of a deconfined state of nuclear matter called Quark Gluon Plasma (QGP), in which quarks and gluons behave as free particles. The bottomonium (bound states of beauty-anti beauty quark) production is affected by the presence of the QGP, since bottomonium states are produced sooner than the QGP and witness the whole evolution of the plasma. In this analysis the data coming from Pb-Pb collisions have been analysed in order to detect possible modifications of the production rates in the dimuon decay channel, with respect to the rates observed in proton-proton collisions. Furthermore, the performances of the detectors involved in the muon identification during the LHC RUN1 and RUN2 has been tested using a new analysis framework implemented as part of this thesis. Finally, in order to optimize the results of future analyses, a new muon identification algorithm has been developed and tested. This algorithm will become necessary in the LHC RUN3 running conditions, when the much higher luminosity will require a quasi online reconstruction of data.

Dans le cours des dernières années, la traçabilité s’est positionnée au cœur de plusieurs enjeux fondamentaux pour les entreprises. Cependant, cette notion est encore aujourd’hui vue comme une contrainte, servant uniquement à respecter des impositions légales et à rappeler des produits non-conformes. Dans ce projet, nous nous sommes attachés à élargir la définition de traçabilité aux domaines de la prévision et de la protection, pour qu’elle ne soit plus perçue comme une obligation supplémentaire à assumer, mais comme un véritable argument d’avantage concurrentiel. Ces travaux de recherche sont consacrés à l’exploitation des informations de traçabilité par l’utilisation des techniques d’intelligence artificielle et de recherche opérationnelle, afin de proposer des actions d’amélioration en production et en logistique. Ils ont été menés en collaboration avec la société ADENTS International, experte en traçabilité. Ce projet est composé de deux principaux axes de travail : l’un portant sur le diagnostic de la criticité d’une production, en fonction des informations de traçabilité et l’autre sur les actions à entreprendre par rapport à ce diagnostic. Dans le premier, nous remarquons l’importance de la notion de dispersion de matières premières et des composants, ainsi que celle des écarts en termes de qualité et de sécurité. Dans le second, nous nous intéressons d’avantage à la notion de rappel de produits, visant une gestion de transformations adaptée en aval de la production, afin de minimiser ces rappels. Pour la mise en place de ces deux grandes activités, nous nous sommes engagés à proposer des modèles et des méthodes flexibles et réactives, pouvant s’adapter à la versatilité ontologique des flux d’informations de traçabilité / The recent product traceability requirements demonstrate an industrial need to improve the information management strategies within traceability systems in order to evolve from reactivity to proactivity. The aim of this work is to exploit the recently available real-time access to traceability information. We propose the utilization of artificial intelligence and operational research techniques to analyse the information and therefore suggest improvement actions. This research project is composed of two main activities: first, the diagnosis of the criticality value associated to a production regarding the traceability information and second, the actions to undertake as a result of this diagnosis. One of the issues studied in this thesis is the problem of minimizing the size of products recall. Initially the problem of raw materials dispersion minimization is analysed. Then a result of the dispersion rate along with other production criteria are evaluated in order to determine a risk level criterion in terms of quality and security that we name “production criticality”. This criterion is used subsequently to optimize deliveries dispatch with the purpose of minimizing the number of batch recalls in case of crisis. This is achieved by implementing flexible and reactive tools

Nous présentons dans cette thèse intitulée "Développement d'algorithmes répartis corrects par construction" nos travaux sur le développement et la vérification formels d'algorithmes répartis. Nous nous intéressons à ces algorithmes, à cause de la difficulté de leur vérification et validation. Pour analyser ces algorithmes, nous avons choisi d'utiliser Event B pour le raffinement de modèles, la vérification de propriétés de sûreté, et TLA, pour la vérification des propriétés temporelles (vivacité et équité). Nous nous sommes focalisé sur le paradigme de correction-par-construction, basé sur la modélisation par raffinement, la preuve de propriétés, ainsi que la réutilisation de modèles/preuves/propriétés (~ patrons de conception) pour guider le développement formel des algorithmes étudiés. Nous avons mis en place un paradigme de développement lors duquel un algorithme réparti est dans un premier temps caractérisé par les services qu'il fournit, et qui sont ensuite exprimés par des propriétés de vivacité, guidant la construction des modèles Event B de cet algorithme. Les règles d'inférence de TLA nous permettent ensuite de détailler les propriétés de vivacité, et de guider le développement formel par raffinement de l'algorithme. Ce paradigme, appelé "service-as-event", est caractérisé par des diagrammes d'assertions permettant de représenter les propriétés de vivacité (en prenant en compte l'équité) des algorithmes répartis étudiés, de comprendre leurs mécanismes. Ce paradigme nous a permis d'analyser des algorithmes de routage (Anycast RP de Cisco Systems et XY pour les réseaux-sur-puce (NoC)), des algorithmes de snapshot et des algorithmes d'auto-stabilisation. / The subject of this thesis is the formal development and verification of distributed algorithms. We are interested in this topic, because proving that a distributed algorithm satisfies given specification and properties is a difficult task. We choose to use the Event B method (refinement, safety properties) and the temporal logic TLA (fairness, liveness properties) for modelling the distributed algorithms. There are several existing approaches for formalising distributed algorithms, and we choose to focus on the "correct-by-construction" paradigm, which is characterised by the use of model refinement, proof of properties (safety, liveness) and reuse of formal models/proofs/properties, developments (~ design patterns) for modelling distributed algorithms. Our works introduce a paradigm which allows us to describe an algorithm with a set of services/functionalities, which are then expressed using liveness properties. These properties guide us in developing the formal Event B models of the studied algorithms. Inference rules from TLA allow to decompose the liveness properties, therefore detailing the services and guiding the refinement process. This paradigm, called "service-as-event" is also characterized by (assertions) diagrams, which allow to graphically represent liveness properties (with respect to fairness hypotheses) and detail the mecanisms and functioning of the studied distributed algorithms. The "service-as-event" paradigm allowed us to develop and verify the following algorithms : routing algorithms, such as Anycast RP (Cisco Systems), XY for Networks-on-Chip (NoC), snapshot and self-* algorithms.

L’évolution des services en ligne et l’avènement du big data ont favorisé l’introduction de l’internet dans tous les aspects de notre vie : la communication et l’échange des informations (exemple, Gmail et Facebook), la recherche sur le web (exemple, Google), l’achat sur internet (exemple, Amazon) et le streaming vidéo (exemple, YouTube). Tous ces services sont hébergés sur des sites physiques appelés centres de données ou data centers qui sont responsables de stocker, gérer et fournir un accès rapide à toutes les données. Tous les équipements constituants le système d’information d’une entreprise (ordinateurs centraux, serveurs, baies de stockage, équipements réseaux et de télécommunications, etc) peuvent être regroupés dans ces centres de données. Cette évolution informatique et technologique a entrainé une croissance exponentielle des centres de données. Cela pose des problèmes de coût d’installation des équipements, d’énergie, d’émission de chaleur et de performance des services offerts aux clients. Ainsi, l’évolutivité, la performance, le coût, la fiabilité, la consommation d’énergie et la maintenance sont devenus des défis importants pour ces centres de données. Motivée par ces défis, la communauté de recherche a commencé à explorer de nouveaux mécanismes et algorithmes de routage et des nouvelles architectures pour améliorer la qualité de service du centre de données. Dans ce projet de thèse, nous avons développé de nouveaux algorithmes et architectures qui combinent les avantages des solutions proposées, tout en évitant leurs limitations. Les points abordés durant ce projet sont: 1) Proposer de nouvelles topologies, étudier leurs propriétés, leurs performances, ainsi que leurs coûts de construction. 2) Conception des algorithmes de routage et des modèles pour réduire la consommation d’énergie en prenant en considération la complexité, et la tolérance aux pannes. 3) Conception des protocoles et des systèmes de gestion de file d’attente pour fournir une bonne qualité de service. 4) Évaluation des nouveaux systèmes en les comparants à d’autres architectures et modèles dans des environnements réalistes. / The increasing trend to migrate applications, computation and storage into more robust systems leads to the emergence of mega data centers hosting tens of thousands of servers. As a result, designing a data center network that interconnects this massive number of servers, and providing efficient and fault-tolerant routing service are becoming an urgent need and a challenge that will be addressed in this thesis. Since this is a hot research topic, many solutions are proposed like adapting new interconnection technologies and new algorithms for data centers. However, many of these solutions generally suffer from performance problems, or can be quite costly. In addition, devoted efforts have not focused on quality of service and power efficiency on data center networks. So, in order to provide a novel solution that challenges the drawbacks of other researches and involves their advantages, we propose to develop new data center interconnection networks that aim to build a scalable, cost-effective, high performant and QoS-capable networking infrastructure. In addition, we suggest to implement power aware algorithms to make the network energy effective. Hence, we will particularly investigate the following issues: 1) Fixing architectural and topological properties of the new proposed data centers and evaluating their performances and capacities of providing robust systems under a faulty environment. 2) Proposing routing, load-balancing, fault-tolerance and power efficient algorithms to apply on our architectures and examining their complexity and how they satisfy the system requirements. 3) Integrating quality of service. 4) Comparing our proposed data centers and algorithms to existing solutions under a realistic environment. In this thesis, we investigate a quite challenging topic where we intend, first, to study the existing models, propose improvements and suggest new methodologies and algorithms.

Dans des systèmes numériques essentiellement latents, compenser la latence n’est pastrivial, en particulier lorsque les graphes de routage du signal sont complexes commec’est souvent le cas dans une station audionumérique (DAW).Tandis que le problème général est de nature mathématique, des complicationsapparaissent dans la conception de systèmes audio en temps réel à cause des contraintesdu matériel, de l’architecture du système, ou de l’ingénierie.Pour construire un système fournissant une compensation de latence sur l’intégralitédu graphe avec possibilité de connecter n’importe quelle source à n’importe quelledestination, uniquement décrire les mécanismes est insuffisant. Le système completdoit être conçu d’un bloc à l’aide de prototypes pour prendre en compte les limitationsdu monde réel.Cette recherche a été menée en utilisant Ardour, une station audionumériquelibrement disponible sous licence libre GPL. Cette thèse est autant un rapport deconception qu’une documentation de recherche.Une analyse complète des éléments de base et de leurs interactions est présentée.La plupart ont été implémentés au delà de la démonstration de faisabilité, dans lebut de combler l’écart entre les systèmes professionnels de production audio et ladocumentation librement accessible pour la recherche et le développement.Même si elle s’attache ostensiblement à Ardour, cette thèse décrit les conceptgénériques des station audio tels que les Ports, les pistes (Tracks), les bus (Busses)et les processeurs de traitement numériques du signal (Processors) ainsi que lesinteractions opérationnelles entre eux.Les concepts de base communs à toutes les entrées/sorties numériques sont expliquésainsi que les sources de latence. Les graphes de traitement et de latence sont illustréspour présenter une vue d’ensemble.Les problèmes généraux rencontrés lors de l’alignement temporel, tant local que / In inherently latent digital systems it is not trivial to compensate for latency, particularlyin situations of complex signal routing graphs as is the case in a Digital AudioWorkstation.While the general problem is of mathematical nature, design complexities arisein real-time audio systems due to constraints by hardware, system-architecture andengineering.To construct a system providing for full-graph latency compensation with anywhereto-anywhere routing capabilities, it is insufficient to merely describe mechanisms.The complete system has to be designed as one and prototyped to take real-worldlimitations into account.This research was carried out using Ardour, a digital audio workstation, whichis freely available under the GPL free-software licence. This thesis is as much adesign-report as it is research documentation.A complete breakdown of building-blocks and interaction is presented, most of whichhas also been implemented beyond a proof-of-concept with the goal to bridge the gapbetween professional audio production systems and freely accessible documentationfor research and development.While ostensibly focusing on Ardour, this thesis describes generic concepts of AudioWorkstations like Ports, Tracks, Busses, and DSP Processors, as well as operationalinteraction between them.Basic concepts common to all digital I/O processes an,d sources of latency areexplained, and process- and latency graphs are illustrated to provide a completepicture. General issues related to time-alignment, both local, and global, as wellas more DAW specific cases like parameter-automation and parallel-execution arediscussed. Algorithms are modelled with pseudocode where appropriate and applicationprogramming interfaces are presented as examples to concepts throughout the text.

Convex geometries are combinatorial structures; they capture in an abstract way the essential features of convexity in Euclidean space, graphs or posets for instance. A convex geometry consists of a finite ground set plus a collection of subsets, called the convex sets and satisfying certain axioms. In this work, we study two natural problems on convex geometries. First, we consider the maximum-weight convex set problem. After proving a hardness result for the problem, we study a special family of convex geometries built on split graphs. We show that the convex sets of such a convex geometry relate to poset convex geometries constructed from the split graph. We discuss a few consequences, obtaining a simple polynomial-time algorithm to solve the problem on split graphs. Next, we generalize those results and design the first polynomial-time algorithm for the maximum-weight convex set problem in chordal graphs. Second, we consider the realizability problem. We show that deciding if a given convex geometry (encoded by its copoints) results from a point set in the plane is ER-hard. We complete our text with a brief discussion of potential further work. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished