Le trading algorithmique utilisé à des fins spéculatives a pris un véritable essor depuis les années 2000, en optimisant d'abord l'exécution sur les marchés d'ordres issus de décisions humaines d'arbitrage ou d'investissement, puis en exécutant une stratégie d'investissement pré-programmée ou systématique où l'humain est cantonné au rôle de concepteur et de superviseur. Et ce, malgré les mises en garde des partisans de l'Efficient Market Hypothesis (EMH) qui indiquent que pourvu que le marché soit efficient, la spéculation est vaine.Le Human Computation (HC) est un concept singulier, il considère le cerveau humain comme le composant unitaire d'une machine plus vaste, machine qui permettrait d'adresser des problèmes d'une complexité hors de portée des calculateurs actuels. Ce concept est à la croisée des notions d'intelligence collective et des techniques de Crowdsourcing permettant de mobiliser des humains (volontaires ou non, conscients ou non, rémunérés ou non) dans la résolution d'un problème ou l'accomplissement d'une tâche complexe. Le projet Fold-it en biochimie est ainsi venu apporter la preuve indiscutable de la capacité de communautés humaines à constituer des systèmes efficaces d'intelligence collective, sous la forme d'un serious game en ligne.Le trading algorithmique pose des difficultés du même ordre que celles rencontrées par les promoteurs de Fold-it et qui les ont conduits à faire appel à la CPU humaine pour progresser de façon significative. La question sera alors de savoir où et comment utiliser le HC dans une discipline qui se prête très mal à la modélisation 3D ou à l'approche ludique afin d'en mesurer l'efficacité.La qualification et la transmission de l'information par réseaux sociaux visant à alimenter un système de trading algorithmique et fondé sur ce principe de HC constituent la première expérimentation de cette thèse. L'expérimentation consistera à analyser en temps réel le buzz Twitter à l'aide de deux méthodes différentes, une méthode asémantique qui cible les événements inattendus remontés par le réseau Twitter (comme l'éruption du volcan islandais en 2010) et une méthode sémantique plus classique qui cible des thématiques connues et anxiogènes pour les marchés financiers. On observe une amélioration significative des performances des algorithmes de trading uniquement sur les stratégies utilisant les données de la méthode asémantique.La deuxième expérimentation de HC dans la sphère du trading algorithmique consiste à confier l'optimisation de paramètres de stratégies de trading à une communauté de joueurs, dans une démarche inspirée du jeu Fold-it. Dans le jeu en ligne baptisé Krabott, chaque solution prend la forme d'un brin d'ADN, les joueurs humains sont alors sollicités dans les phases de sélection et de reproduction des individus-solutions.Krabott démontre la supériorité des utilisateurs humains sur la machine dans leurs capacités d'exploration et leurs performances moyennes quelle que soit la façon dont on compare les résultats. Ainsi, une foule de plusieurs centaines de joueurs surperforme systématiquement la machine sur la version Krabott V2 et sur l'année 2012, résultats confirmés avec d'autres joueurs sur la version Krabott V3 en 2012-2013. Fort de ce constat, il devient possible de construire un système de trading hybride homme-machine sur la base d'une architecture de HC où chaque joueur est la CPU d'un système global de trading.La thèse conclut sur l'avantage compétitif qu'offrirait la mise en œuvre d'une architecture de HC à la fois sur l'acquisition de données alimentant les algorithmes de trading et sur la capacité d'un tel système à optimiser les paramètres de stratégies existantes. Il est pertinent de parier à terme sur la capacité de la foule à concevoir et à maintenir de façon autonome des stratégies de trading algorithmique, dont la complexité finirait par échapper totalement à la compréhension humaine individuelle. / Algorithmic trading, designed for speculative purposes, really took off in the early 2000's, first for optimizing market orders based on human decisions and then for executing trading strategies in real time. In this systematic trading approach, human intervention is limited to system supervision and maintenance. The field is growing even though the Efficient Market Hypothesis says that in an efficient market, speculation is futile.Human Computation is an unusual concept which considers human brains as a part of a much larger machine, with the power to tackle problems that are too big for today's computers. This concept is at the crossroads between two older ideas: collective intelligence and crowdsourcing able to involve humans (whether they are paid or not, they realize it or not) in problem solving or to achieve a complex task. The Fold-it project in biochemistry proved the ability of a human community to set up an efficient collective intelligence system based on a serious online game.Algorithmic trading is on same difficulty level of complexity as the problem tackled by Fold-it's creators. In that case “human CPU” really helped in solving 3D puzzles. The question is whether Human Computation could be used in algorithmic trading even though there are no 3D structures or user-friendly puzzles to deal with.The first experiment in this thesis is based on the idea that information flows in social media may provide input to algorithmic trading systems based on Human Computation principles. Twitter, the micro blogging platform, was chosen in order to track (1) words that may have an impact of financial markets and (2) unexpected events such as the eruption of the Icelandic volcano. We demonstrate that a significant increase in P&L can be achieved in the second case by treating the unexpected events as alerts.The second experiment with Human Computation in algorithmic trading aims to get a community of internet users to optimize parameters of the trading strategies, in the way that the Fold-it game did. In this online game called “Krabott” solutions are presented as friendly virtual bots each containing a specific set of parameters for a particular trading strategy in its DNA. Humans who are playing the game, interact in the selection and reproduction steps for each new “Krabott”.In this game the Krabotts “bred” by players outperformed those resulting from a computer optimization process. We tested two different versions of Krabott during the years 2012 and 2013, and in both cases the population bred by the players outperformed the “computer only” ones. This suggests that it may be possible to set up a whole hybrid human-computer system based on Human Computation where each player is a kind of single CPU within a global trading system.The thesis concludes by discussing the types of competitive advantages that structures based on Human Computation have for data acquisition into a trading system or for optimizing the parameters of existing trading strategies. Going further we expect that in the years to come Human Computation will be able to set up and update algorithmic trading strategies, whose complexity exceeds what an individual person could comprehend.

Les nombres p-adiques sont un analogue des nombres réels plus proche de l’arithmétique. L’avènement ces dernières décennies de la géométrie arithmétique a engendré la création de nombreux algorithmes utilisant ces nombres. Ces derniers ne peuvent être de manière générale manipulés qu’à précision finie. Nous proposons une méthode, dite de précision différentielle, pour étudier ces problèmes de précision. Elle permet de se ramener à un problème au premier ordre. Nous nous intéressons aussi à la question de savoir quelles bases de Gröbner peuvent être calculées sur les p-adiques. / P-Adic numbers are a field in arithmetic analoguous to the real numbers. The advent during the last few decades of arithmetic geometry has yielded many algorithms using those numbers. Such numbers can only by handled with finite precision. We design a method, that we call differential precision, to study the behaviour of the precision in a p-adic context. It reduces the study to a first-order problem. We also study the question of which Gröbner bases can be computed over a p-adic number field.

Avec l’émergence du calcul haute-performance (HPC) et des applications Big Data, de nouvelles problématiques cruciales sont apparues. Parmi elles on trouve le problème du transfert de données, c’est-à-dire des communications entre machines, qui peut génerer des délais lors de gros calculs en plus d’avoir un impact sur la consommation énergétique. La réplication, que ce soit de tâches ou de fichiers, est un facteur qui accroît ces communications, tout en étant un outil quasi-indispensable pour améliorer le parallélisme du calcul et la résistance aux pannes. Dans cette thèse nous nous intéressons à la réplication de fichiers et à son impact sur les communications au travers de deux problèmes. Dans le premier, la multiplication de matrices en parallèle, le but est de limiter autant que possible ces réplications pour diminuer la quantité de données déplacées. Dans le second, l’ordonnancement de la phase « Map » de MapReduce, il existe une réplication initiale qu’il faut utiliser au mieux afin d’obtenir l’ordonnancement le plus rapide ou entraînant le moins de création de nouvelles copies. En plus de la réplication, nous nous intéressons aussi à la comparaison entre stratégies d’ordonnancement statiques (allocations faites en amont du calcul) et dynamiques (allocations faites pendant le calcul) sur ces deux problèmes avec pour objectif de créer des stratégies hybrides mélangeant les deux aspects. Pour le premier problème, le produit de matrices en parallèle, nous nous ramenons à un problème de partition de carré où l’équilibrage de charge est donné en entrée. Cet équilibrage donné, le but est de minimiser la somme des semi-paramètres des rectangles couvrant des zones ainsi créés. Ce problème a déjà été étudié par le passé et nous démontrons de nouveaux résultats. Nous proposons ainsi deux nouveaux algorithmes d’approximation, l’un fondé sur une stratégie récursive et l’autre sur l’usage d’une courbe fractale. Nous présentons également une modélisation alternative, fondée sur un problème similaire de partition de cube, dont nous prouvons la NP-complétude tout en fournissant deux algorithmes d’approximation. Pour finir, nous réalisons également une implémentation pratique du produit de matrices en utilisant nos stratégies d’allocation grâce à la librairie StarPU. Les résultats expérimentaux montrent une amélioration du temps de calcul ainsi qu’une diminution significative des transferts de données lorsqu’on utilise une stratégie statique d’allocation couplée à une technique de vol de tâches. Pour le second problème, l’ordonnancement de la phase « Map » de MapReduce, plusieurs copies des fichiers d’entrée sont distribuées parmi les processeurs disponibles. Le but ici est de faire en sorte que chaque tâche soit attribuée à un processeur possédant son fichier d’entrée tout en ayant le meilleur temps de calcul total. Une autre option étudiée est d’autoriser les tâches nonlocales (attribués à des processeurs ne possédant pas leurs fichiers d’entrée) mais d’en limiter le nombre. Dans cette thèse nous montrons premièrement qu’un algorithme glouton pour ce problème peut être modélisé par un processus de « balls-in-bins » avec choix, impliquant une surcharge (nombre de tâches supplémentaires par rapport à la moyenne) en O(mlogm) où m est le nombre de processeurs. Secondement, dans le cas où les tâches non-locales sont interdites, nous relions le problème à celui de l’orientation de graphes, ce qui permet d’obtenir des algorithmes optimaux et polynomiaux et l’existence d’une assignation presque parfaite avec forte probabilité. Dans le cas où les tâches non locales sont autorisées, nous proposons également des algorithmes polynomiaux et optimaux. Finalement, nous proposons un ensemble de simulations pour montrer l’efficacité de nos méthodes dans le cas de tâches faiblement hétérogènes. / The increasing importance of High Performance Computing (HPC) and Big Data applications creates new issues in parallel computing. One of them is communication, the data transferred from a processor to another. Such data movements have an impact on computational time, inducing delays and increase of energy consumption. If replication, of either tasks or files, generates communication, it is also an important tool to improve resiliency and parallelism. In this thesis, we focus on the impact of the replication of input files on the overall amount of communication. For this purpose, we concentrate on two practical problems. The first one is parallel matrix multiplication. In this problem, the goal is to induce as few replications as possible in order to decrease the amount of communication. The second problem is the scheduling of the “Map” phase in the MapReduce framework. In this case, replication is an input of the problem and this time the goal is to use it in the best possible way. In addition to the replication issue, this thesis also considers the comparison between static and dynamic approaches for scheduling. For consistency, static approaches compute schedules before starting the computation while dynamic approaches compute the schedules during the computation itself. In this thesis we design hybrid strategies in order to take advantage of the pros of both. First, we relate communication-avoiding matrix multiplication with a square partitioning problem, where load-balancing is given as an input. In this problem, the goal is to split a square into zones (whose areas depend on the relative speed of resources) while minimizing the sum of their half-perimeters. We improve the existing results in the literature for this problem with two additional approximation algorithms. In addition we also propose an alternative model using a cube partitioning problem. We prove the NP-completeness of the associated decision problem and we design two approximations algorithms. Finally, we implement the algorithms for both problems in order to provide a comparison of the schedules for matrix multiplication. For this purpose, we rely on the StarPU library. Second, in the Map phase of MapReduce scheduling case, the input files are replicated and distributed among the processors. For this problem we propose two metrics. In the first one, we forbid non-local tasks (a task that is processed on a processor that does not own its input files) and under this constraint, we aim at minimizing the makespan. In the second problem, we allow non-local tasks and we aim at minimizing them while minimizing makespan. For the theoretical study, we focus on tasks with homogeneous computation times. First, we relate a greedy algorithm on the makespan metric with a “ball-into-bins” process, proving that this algorithm produces solutions with expected overhead (the difference between the number of tasks on the most loaded processor and the number of tasks in a perfect distribution) equal to O(mlogm) where m denotes the number of processors. Second, we relate this scheduling problem (with forbidden non-local tasks) to a problem of graph orientation and therefore prove, with the results from the literature, that there exists, with high probability, a near-perfect assignment (whose overhead is at most 1). In addition, there are polynomial-time optimal algorithms. For the communication metric case, we provide new algorithms based on a graph model close to matching problems in bipartite graphs. We prove that these algorithms are optimal for both communication and makespan metrics. Finally, we provide simulations based on traces from a MapReduce cluster to test our strategies with realistic settings and prove that the algorithms we propose perform very well in the case of low or medium variance of the computation times of the different tasks of a job.

Avec l’explosion de la quantité de données biologiques disponible, développer de nouvelles méthodes de traitements efficaces est une problématique majeure en bioinformatique. De nombreuses structures biologiques sont modélisées par des structures arborescentes telles que les structures secondaires d’ARN et l’architecture des plantes. Ces structures contiennent des motifs répétés au sein même de leur structure mais également d’une structure à l’autre. Nous proposons d’exploiter cette propriété fondamentale afin d’améliorer le stockage et le traitement de tels objets.En nous inspirant du principe de filtres sur les séquences, nous définissons dans cette thèse une méthode de filtrage sur les arborescences ordonnées permettant de rechercher efficacement dans une base de données un ensemble d’arborescences ordonnées proches d’une arborescence requête. La méthode se base sur un découpage de l’arborescence en graines et sur une recherche de graines communes entre les structures. Nous définissons et résolvons le problème de chainage maximum sur des arborescences. Nous proposons dans le cas des structures secondaires d’ARN une définition de graines (l−d) centrées.Dans un second temps, en nous basant sur des techniques d’instanciations utilisées, par exemple, en infographie et sur la connaissance des propriétés de redondances au sein des structures biologiques, nous présentons une méthode de compression permettant de réduire l’espace mémoire nécessaire pour le stockage d’arborescences non-ordonnées. Après une détermination des redondances nous utilisons une structure de données plus compacte pour représenter notamment l’architecture de la plante, celle-ci pouvant contenir des informations topologiques mais également géométriques. / The explosion of available biological data urges the need for bioinformatics methods. Manybiological structures are modeled by tree structures such as RNA secondary structure and plantsarchitecture. These structures contain repeating units within their structure, but also betweendifferent structures. We propose to exploit this fundamental property to improve storage andtreatment of such objects.Following the principle of sequence filtering, we define a filtering method on ordered treesto efficiently retrieve in a database a set of ordered trees close from a query. The method isbased on a decomposition of the tree into seeds and the detection of shared seeds between thesestructures. We define and solve the maximum chaining problem on trees. We propose for RNAsecondary structure applications a definition of (l−d) centered seed.Based on instantiation techniques used for instance in computer graphics and the repetitivenessof biological structures, we present a compression method which reduces the memoryspace required for plant architecture storage. A more compact data structure is used in order torepresent plant architecture. The construction of this data structure require the identification ofinternal redundancies and taking into account both topological and geometrical informations.

Cette thèse est consacrée au problème d'ordonnancement de tâches qui consiste à minimiser la somme de l'énergie consommée et le temps d'attente pondéré total, et l'aborde de deux différents points de vue : centralisé et décentralisé. Pour l'approche décentralisée, nous avons défini deux types de jeux qui diffèrent dans les actions proposées aux joueurs et avons cherché des moyens de facturer l'énergie consommée aux utilisateurs pour les inciter à adopter un bon comportement. Concrètement nous nous intéressons à l'existence d'équilibres de Nash purs, au temps de convergence vers ces équilibres, et au rapport entre l'énergie consommée et le montant des factures. Pour l'approche centralisée, nous avons réduit le problème de minimisation à un problème d'ordonnancement plus classique avec une fonction de pénalité de retard polynomiale concave, pour lequel peu résultats ont été connus. Après avoir établi un état de l'art sur la famille de problèmes d'ordonnancement pour plusieurs fonctions de pénalité élémentaires et montré qu'une technique de preuve de NP-complétude classique échoue ici, nous nous sommes intéressés à sa résolution exacte. Pour améliorer les performances de l'algorithme A* dans ce contexte, nous avons montré des résultats de règles de dominance. Concrètement, nous avons cherché à déterminer les conditions sous lesquelles une solution optimale devrait ordonnancer une paire de tâches dans un certain ordre. Ces résultats sont appuyés par une étude expérimentale qui évalue l'impact pratique de ces nouvelles règles, par rapport aux règles existantes. / This thesis focuses on a job scheduling problem with the goal of minimizing the sum of energy consumption and the weighted flow time from two different approaches: centralized and decentralized. In the decentralized setting, we defined two games which differ in the strategies players can choose from and designed cost sharing mechanisms, charging the consumed energy to the users in order to incentive a socially desirable behavior. More precisely we were interested in the existence of pure Nash equilibria, in the convergence time, and the ratio between the consumed energy and the total charged amount. On the other side, for the centralized approach, we reduced the minimization problem to a classical scheduling problem with a polynomial concave penalty function, for which little results were known. We established a state of the art for a family of scheduling problems of this form with different penalty functions and showed that a classical NP-completeness proof technique fails here. Finally we addressed the exact resolution of the problem using the algorithm A*. In this context, we showed new order dominance rules. More precisely, we characterized the conditions under which any optimal solution must schedule a job pair in a certain order. In addition we carried out a computational experience to evaluate the practical impact of these new rules compared to the existing ones.

Dans cette thèse, nous nous intéressons au calcul du groupe de classes d'un corps de nombres. Nous débutons par décrire un algorithme de réduction du polynôme de définition d'un corps de nombres. Il existe une infinité de polynômes qui définissent un corps de nombres fixé, avec des coefficients arbitrairement gros. Notre algorithme calcule celui qui a les plus petits coefficients. L'avantage de connaître un petit polynôme de définition est qu'il simplifie les calculs entre éléments de ce corps de nombres, en impliquant des quantités plus petites. En outre, la connaissance d'un tel polynôme permet l'utilisation d'algorithmes plus efficaces que dans le cas général pour calculer le groupe de classes. L'algorithme général pour calculer la structure du groupe de classes repose sur la réduction d'idéaux, vus comme des réseaux. Nous décrivons et simplifions l'algorithme présenté par Biasse et Fieker en 2014 à ANTS et approfondissons l'analyse de complexité. Nous nous sommes aussi intéressés au cas des corps de nombres définis par un polynôme à petits coefficients. Nous décrivons un algorithme similaire au crible par corps de nombres (NFS) dont la complexité en fonction des paramètres du corps de nombres peut atteindre L(1/3). Enfin, nos algorithmes peuvent être adaptés pour résoudre un problème lié : le Problème de l'Idéal Principal. Étant donné n'importe quelle base d'un idéal principal (généré par un seul élément), nous sommes capables de retrouver ce générateur. Cette application de nos algorithmes fournit une attaque efficace contre certains schémas de chiffrement homomorphe basés sur ce problème. / In this thesis, we focus on class group computations in number fields. We start by describing an algorithm for reducing the size of a defining polynomial of a number field. There exist infinitely many polynomials that define a specific number field, with arbitrarily large coefficients, but our algorithm constructs the one that has the absolutely smallest coefficients. The advantage of knowing such a ``small'' defining polynomial is that it makes calculations in the number field easier because smaller values are involved. In addition, thanks to such a small polynomial, one can use specific algorithms that are more efficient than the general ones for class group computations. The generic algorithm to determine the structure of a class group is based on ideal reduction, where ideals are viewed as lattices. We describe and simplify the algorithm presented by Biasse and Fieker in 2014 at ANTS and provide a more thorough complexity analysis for~it. We also examine carefully the case of number fields defined by a polynomial with small coefficients. We describe an algorithm similar to the Number Field Sieve, which, depending on the field parameters, may reach the hope for complexity L(1/3). Finally, our results can be adapted to solve an associated problem: the Principal Ideal Problem. Given any basis of a principal ideal (generated by a unique element), we are able to find such a generator. As this problem, known to be hard, is the key-point in several homomorphic cryptosystems, the slight modifications of our algorithms provide efficient attacks against these cryptographic schemes.

Les systèmes à grande échelle comme les Grilles ou les Nuages (Clouds) mettent à disposition pour les utilisateurs des ressources informatiques hétérogènes. Dans les Nuages, les accès aux ressources sont orchestrés par des contrats permettant de définir un niveau de qualité de service (temps de réponse, disponibilité ...) que le fournisseur doit respecter. Ma thèse a donc contribué à concevoir de nouveaux algorithmes distribués de verrouillage de ressources dans les systèmes large échelle en prenant en compte des notions de qualité de service. Dans un premier temps, mes travaux de thèse se portent sur des algorithmes distribués de verrouillage ayant des contraintes en termes de priorités et de temps. Deux algorithmes d'exclusion mutuelle ont été proposés : un algorithme prenant en compte les priorités des clients et un autre pour des requêtes avec des dates d'échéance. Dans un second temps, j'ai abordé le problème de l'exclusion mutuelle généralisée pour allouer de manière exclusive plusieurs types de ressources hétérogènes. J'ai proposé un nouvel algorithme qui réduit les coûts de synchronisation en limitant la communication entre processus non conflictuels. Tous ces algorithmes ont été implémentés et évalués sur la plateforme nationale Grid 5000. Les évaluations ont montré que nos algorithmes satisfaisaient bien les contraintes applicatives tout en améliorant de manière significative les performances en termes de taux d'utilisation et de temps de réponse. / Distributed large-scale systems such as Grids or Clouds provide large amounts of heterogeneous computing resources. Clouds manage ressource access by contracts that allow to define a quality of service (response time, availability, ...) that the provider has to respect. My thesis focuses on designing new distributed locking algorithms for large scale systems that integrate notions of quality of service. At first, my thesis targets distributed locking algorithms with constraints in terms of priorities and response time. Two mutual exclusion algorithms are proposed: a first algorithm takes into account client-defined priorities and a second one associates requests with deadlines. I then move on to a generalized mutual exclusion problem in order to allocate several types of heterogeneous resources in a exclusive way. I propose a new algorithm that reduces the cost of synchronization by limiting communication between non-conflicting processes.All algorithms have been implemented and evaluated over the national platform Grid 5000. Evaluations show that our algorithms satisfy applicative constraints while improving performance significatively in terms of resources use rate and response time.

Le dessin computationnel de protéine, ou CPD, est une technique qui permet de modifier les protéines pour leur conférer de nouvelles propriétés, en exploitant leurs structures 3D et une modélisation moléculaire. Pour rendre la méthode de plus en plus prédictive, les modèles employés doivent constamment progresser. Dans cette thèse, nous avons abordé le problème de la représentation explicite de la flexibilité du squelette protéique. Nous avons développé une méthode de dessin "multi-états", qui se base sur une bibliothèque discrète de conformations du squelette, établie à l'avance. Dans un contexte de simulation Monte Carlo, le paysage énergétique d'une protéine étant rugueux, les changements de squelettes ne peuvent etre acceptés que moyennant certaines précautions. Aussi, pour explorer ces conformations, en même temps que des mutations et des mouvements de chaînes latérales, nous avons introduit un nouveau type de déplacement dans une méthode Monte Carlo existante. Il s'agit d'un déplacement "hybride", où un changement de squelette est suivi d'une courte relaxation Monte Carlo des chaînes latérales seules, après laquelle un test d'acceptation est effectué. Pour respecter une distribution de Boltzmann des états, la probabilité doit avoir une forme précise, qui contient une intégrale de chemin, difficile à calculer en pratique. Deux approximations sont explorées en détail: une basée sur un seul chemin de relaxation, ou chemin "générateur" (Single Path Approximation, ou SPA), et une plus complexe basée sur un ensemble de chemins, obtenus en permutant les étapes élémentaires du chemin générateur (Permuted Path Approximation, ou PPA). Ces deux approximations sont étudiées et comparées sur deux protéines. En particulier, nous calculons les énergies relatives des conformations du squelette en utilisant trois méthodes différentes, qui passent réversiblement d'une conformation à l'autre en empruntent des chemins très différents. Le bon accord entre les méthodes, obtenu avec de nombreuses paramétrisations différentes, montre que l'énergie libre se comporte bien comme une fonction d'état, suggérant que les états sont bien échantillonnés selon la distribution de Boltzmann. La méthode d'échantillonnage est ensuite appliquée à une boucle dans le site actif de la tyrosyl-ARNt synthétase, permettant d'identifier des séquences qui favorisent une conformation, soit ouverte, soit fermée de la boucle, permettant en principe de contrôler ou redessiner sa conformation. Nous décrivons enfin un travail préliminaire visant à augmenter encore la flexibilité du squelette, en explorant un espace de conformations continu et non plus discret. Ce changement d'espace oblige à restructurer complètement le calcul des énergies et le déroulement des simulations, augmente considérable le coût des calculs, et nécessite une parallélisation beaucoup plus agressive du logiciel de simulation. / Computational protein design is a method to modify proteins and obtain new properties, using their 3D structure and molecular modelling. To make the method more predictive, the models need continued improvement. In this thesis, we addressed the problem of explicitly representing the flexibility of the protein backbone. We developed a "multi-state" design approach, based on a small library of backbone conformations, defined ahead of time. In a Monte Carlo framework, given the rugged protein energy landscape, large backbone motions can only be accepted if precautions are taken. Thus, to explore these conformations, along with sidechain mutations and motions, we have introduced a new type of Monte Carlo move. The move is a "hybrid" one, where the backbone changes its conformation, then a short Monte Carlo relaxation of the sidechains is done, followed by an acceptation test. To obtain a Boltzmann sampling of states, the acceptation probability should have a specific form, which involves a path integral that is difficult to calculate. Two approximate forms are explored: the first is based on a single relaxation path, or "generating path" (Single Path Approximation or SPA). The second is more complex and relies on a collection of paths, obtained by shuffling the elementary steps of the generating path (Permuted Path Approximation or PPA). These approximations are tested in depth and compared on two proteins. Free energy differences between the backbone conformations are computed using three different approaches, which move the system reversibly from one conformation to another, but follow very different routes. Good agreement is obtained between the methods and a wide range of parameterizations, indicating that the free energy behaves as a state function, as it should, and strongly suggesting that Boltzmann sampling is verified. The sampling method is applied to the tyrosyl-tRNA synthetase enzyme, allowing us to identify sequences that prefer either an open or a closed conformation of an active site loop, so that in principle we can control, or design the loop conformation. Finally, we describe preliminary work to make the protein backbone fully flexible, moving within a continuous and not a discrete space. This new conformational space requires a complete reorganization of the energy calculation and Monte Carlo simulation scheme, increases simulation cost substantially, and requires a much more aggressive parallelization of our software.

Le projet scientifique dans lequel s’inscrit ma thèse a pour objectif l’élaboration d’algorithmes distribués et efficaces pour les réseaux informatiques. Ce projet vise une catégorie particulière des algorithmes distribués, dits auto-stabilisants. Il s’agit d’algorithmes ayant pour propriété de retrouver un comportement correct suite à une panne dans le réseau et ce, sans aucune intervention humaine. Le travail effectué en collaboration avec mes directeurs de thèse s’est concentré, plus précisément, autour des problèmes de couplage, de cliques et des paradigmes de publications-souscriptions dans ce domaine de l’informatique théorique. Dans un premier temps on a traité le problème du couplage maximal dans sa version anonyme, en fournissant un algorithme auto-stabilisant probabiliste et efficace. Ces travaux sont parus dans le journal PPL. De plus, on s’est intéressé au problème du couplage dans sa version maximum identifiée. Son travail améliore le dernier algorithme présent dans la littérature pour l’approximation de ce type de couplage au 2/3 de la solution optimale. Ces travaux sont parus dans une conférence internationale OPODIS. Par ailleurs, j'ai eu l’opportunité de collaborer en Allemagne avec Prof. Volker Turau au sein du groupe de télématique de l’Université technique de Hambourg. Le cadre de cette collaboration a été les algorithmes auto-stabilisants pour les paradigmes de publication-souscription. Cela a abouti à un algorithme efficace pour la version en canal de ce problème, introduisant la notion de raccourci pour le routage de messages dans ces paradigmes. Les résultats ont fait l’objet d’un Brief Announcement et d’un papier, publiés dans des conférences internationales, SSS et NetSyS. J'ai aussi bénéficié d’une collaboration avec Mr. Gerry Siegemund qui a été accueilli au laboratoire d’Informatique de l’École Polytechnique. Il a été question de trouver un algorithme efficace et auto-stabilisant pour la partition d’un réseau en cliques. Cette collaboration a eu pour résultat un algorithme pour le problème améliorant le dernier en date. Ce résultat est en cours de rédaction pour soumission à une conférence internationale. / The main focus of my thesis is the design of an efficient kind of distributed algorithms, known as: Self-stabilizing. These algorithms have the property to recover from faults in the environment they're executed in, and this without any human intervention. Recovering here, means converging toward a pre-defined, correct configuration. In this setting, I was mainly interested by the problems of matching in graphs, clique partitions and publication subscription paradigms. For the maximal version of the matching problem in anonymous graphs, we achieved a more efficient randomized, self-stabilizing algorithm. This work is published in a journal version in PPL. The maximum version of the same problem, but in an identified setting, led to the design of an efficient self-stabilizing algorithm that approximates the optimal solution up to the 2/3. This result was published at OPODIS. During a research visit at TUHH, Hamburg, Germany. Together with Pr. Volker Turau we tackled the problem of self-stabilizing publish/subscribe paradigms. This led to an algorithm introducing the new notion of short-cuts in this type of structures and was published under a brief announcement and a regular paper at SSS and NetSyS. In collaboration with Mr. Siegemund, then a visiting researcher at LIX, École Polytechnique, we worked on an efficient self-stabilizing algorithm for clique partitions. This work is still in progress and in preparation for an eventual publication.

En informatique, les images sont numériques et donc composées de pixels en 2D et de voxels en 3D. Dans une scène virtuelle 3D, il est impossible de manipuler directement les objets comme des ensembles de voxels en raison du trop gros volume de données. Les objets sont alors polyédrisés, c'est-à-dire remplacés par une collection de facettes. Pour ce faire, il est primordial de savoir décider si un sous-ensemble de voxels peut être transformé en une facette dans la représentation polyédrique. Ce problème est appelé reconnaissance de plans discrets. Pour le résoudre, nous mettons en place un nouvel algorithme spécialement adapté pour les ensembles de voxels denses dans une boite englobante. Notre méthode atteint une complexité quasi-linéaire dans ce cas et s'avère efficace en pratique. En parallèle, nous nous intéressons à un problème algorithmique annexe intervenant dans notre méthode de reconnaissance de plans discrets. Il s'agit de calculer les deux enveloppes convexes des points de Z2 contenus dans un domaine vertical borné et situés de part et d'autre d'une droite quelconque. Nous proposons une méthode de complexité optimale et adaptative pour calculer ces enveloppes convexes. Nous présentons le problème de manière détournée : déterminer le nombre rationnel à dénominateur borné qui approxime au mieux un nombre réel donné. Nous établissons le lien entre ce problème numérique et son interprétation géométrique dans le plan. Enfin, nous proposons indépendamment un nouvel algorithme pour calculer l'épaisseur d'un ensemble de points dans le réseau Zd. Notre méthode est optimale en 2D et gloutonne mais efficace en dimension supérieure