Nous cherchons dans cette thèse à calculer les stratégies gagnantes de jeux combinatoires avec un programme informatique. Nous montrons comment les découpages qui apparaissent au sein de certains jeux impartiaux peuvent être utilisés pour accélérer les calculs. Nous détaillons en particulier l'utilisation du concept d'arbre canonique réduit dans les calculs en version misère. Ces méthodes ont été appliquées avec succès au calcul de deux jeux impartiaux en apparence très différents : le Sprouts, où les joueurs relient des points par des lignes, et le Cram, qui consiste à remplir un plateau avec des dominos. Nous exposons ensuite une méthode originale de suivi des calculs de jeux, avec des interactions en temps réel par l'opérateur humain. Enfin, nous décrivons l'architecture du programme modulaire qui nous a permis de réaliser de nombreux calculs différents au sein d'un cadre commun, et qui pourrait être étendu à l'avenir à d'autres jeux ou algorithmes.

Cette thèse s’intéresse à la question de l’évaluation des Systèmes Multi-Agents (SMA). Les caractéristiques propres que possèdent ces derniers, notamment en termes d’autonomie, de distribution, de dynamique et de socialité, ont grandement contribué à l’élargissement de leurs champs d’application, mais en contrepartie, elles ont rendu leur analyse plus ardue. Ainsi, les méthodes d’évaluation dans les systèmes informatiques classiques s’avèrent insuffisantes à analyser les SMA, étant donné qu’elles ne tiennent pas compte de leurs spécificités. L’objectif de cette thèse consiste donc à proposer une approche générique pour l’évaluation des SMA en se basant sur la mesure de leurs caractéristiques fonctionnelles. A cet effet, le besoin de disposer d’informations sur l’exécution du système à évaluer est manifeste. C’est dans ce cadre qu’une nouvelle approche d’observation des SMA est proposée. Les résultats de ces observations sont exploités pour construire une abstraction du système sous forme d’un modèle, lequel est étudié pour définir les mesures de performances. L’analyse se focalise sur deux caractéristiques essentielles, à la base de la dynamique et de la socialité des SMA : la communication et l’organisation. Les expérimentations de la solution proposée portent sur deux applications multi-agents. La première est une application de diagnostic des pannes dans un environnement industriel et la seconde est une application de pilotage et de gestion de la production dans les chaînes logistiques. / This thesis focuses on the issue of MultiAgent Systems (MAS) evaluation. The MAS own characteristics, namely autonomy, distribution, dynamicity and sociality, have greatly contributed to the expansion of their application scope; but in return they made their analysis more difficult. Thus, evaluation methods in classic computer systems are insufficient to analyse MAS, since they do not take into account their specificities. The objective of this thesis is to provide a generic approach for the evaluation of MAS by measuring their functional characteristics. To this end, the need for information about the execution of the system to be evaluated is evident. In this context, a new approach to observe MAS is proposed. The results of these observations are exploited to build an abstraction model of the system which is studied in order to define performance metrics. The analysis focuses on two key characteristics, at the basis on the dynamics and sociality in MAS: communication and organization. The experiments of the proposed solution are performed on two multiagent applications. The first is an application of fault diagnosis in an industrial environment and the second is an application of control and production planning in supply chains.

Je souhaite réaliser un modèle théorique optimal pour les protocoles de partage de secret quantique basé sur l'utilisation des états graphes. Le paramètre représentatif d'un partage de secret à seuil est, entre autres la taille du plus grand ensemble de joueurs qui ne peut pas accéder au secret. Je souhaite donc trouver un famille de protocoles pour laquelle ce paramètre est le plus petit possible. J'étudie également les liens entre les protocoles de partage de secret quantique et des familles de courbes en géométrie algébrique. / I want to realize an optimal theoretical model for quantum secret sharing protocols based on graph states. The main parameter of a threshold quantum secret sharing scheme is the size of the largest set of players that can not access the secret. Thus, my goal is to find a collection of protocols for which the value of this parameter is the smallest possible. I also study the links between quantum secret sharing protocols and families of curves in algebraic geometry.

Dans cette thèse nous étudions le groupe quantique d’automorphismes des graphes finis, introduit par Banica et Bichon. Dans un premier temps nous montrerons un théorème de structure du groupe quantique d’automorphismes du produit lexicographique de deux graphes finis réguliers, qui généralise un résultat classique de Sabidussi. Ce théorème donne une condition nécessaire et suffisante pour que ce groupe quantique s’exprime comme le produit en couronne libre des groupes quantiques d’automorphismes de ces deux graphes. Dans un deuxième temps, nous expliciterons certaines améliorations de résultats de Banica, Bichon et Chenevier permettant d’obtenir des critères de non symétrie quantique sur les graphes, à l’aide des outils développés par les auteurs susmentionnés.Enfin, pour poursuivre ces recherches, nous développerons une autre méthode utilisant la dualité de Tannaka-Krein et inspirée de l’étude des groupes quantiques compacts orthogonaux par Banica et Speicher. Celle-ci nous permettra, à l’aide d’une étude orbitale approfondie des graphes sommets-transitifs, d’énoncer une condition suffisante pour qu’un graphe ait des symétries quantiques ; condition qui a vocation à être aussi nécessaire mais ceci reste une conjecture à ce stade. / In this thesis we study the quantum automorphism group of finite graphs, introduces by Banica and Bichon. First we will prove a theorem about the structure of the quantum automorphism group of the lexicographic product of two finite regular graphs. It is a quantum generalization of a classical result of Sabidussi. This theorem gives a necessary and sufficient condition for this quantum group to be discribe as the free wreath product of the quantum automorphism groups of these two graphs. Then, we will give some improvement of Banica, Bichon and Chenevier results, to obtain a quantum non-symmetry criteria on graphs, using tools developped by the above authors. Finally, to continue this research, we will describe another method using Tannaka-Krein duality and inspired by the study of orthogonal compact groups by Banica and Speicher. This will enable us, with a thorough orbital study of vertex-transitive graphs, to state a sufficient condition for a graph to have quantum symmetries ; condition which is intended to be also necessary but this remains conjecture at this point.

Le problème de placement sur deux dimensions consiste à décider s’il existe un rangement d’objets rectangulaires dans une boîte donnée. C’est un problème combinatoire difficile (à la complexité du respect des capacités s’ajoute celle du positionnement des objets).Dans cette thèse, nous considérons les variantes sans rotation des objets et avec ou sansoptimisation de la valeur des objects placés.Nous menons une étude exploratoire des méthodologies qui peuvent être développéesà l’interface de la programmation mathématique, de l’optimisation combinatoire et de lathéorie des graphes. Notre objectif est aussi de développer des approches non basées surune discrétisation de la boîte, les plus performantes à l’heure actuelle.Dans ce mémoire, nous effectuons d’abord une étude théorique des qualités de bornesqui peuvent être obtenues avec les différentes formulations classiques. Au cours de cetteétude, nous renforçons certaines de ces formulations et en proposons de nouvelles formulations. Une étude qualitative des bornes issues de la relaxation linéaire des formulationstestés sur des jeux d’instances classiques de la littérature confirme l’étude théorique. Cetteétude permet de se rendre compte des facteurs déterminant la qualité des bornes et desenjeux à relever par la programmation mathématique.Par la suite, nous avons développé et testé deux approches de résolution innovantes.L’une est basée sur la décomposition de Dantzig-Wolfe associée à un branchement surles contraintes disjonctives de non recouvrement des objets. Cette approche a permis uneamélioration des résultats obtenus par la programmation mathématique.L’autre approche constitue en une approche combinatoire basée sur diverses caractérisations des graphes d’intervalles (modélisant le chevauchement des objets selon leurprojection sur chaque axe). Un premier algorithme est basé sur l’énumération de matricesde uns-consécutifs. Un autre utilise des arbres étiquetés pour éliminer plus efficacement lescas de symétries entre placements. Ces approches ont l’avantage de ne pas dépendre d’unediscrétisation du conteneur / The two dimensional orthogonal packing problem consists in deciding whether thereexists a packing of rectangular items in a given bin. This is a hard combinatorial problem(in addition to capacity constraints, one has to face the complexity of item positionning).In this thesis, we consider the case without item rotation and with or without packingvalue optimization.We explore methodologies at the interface of mathematical programming, combinatorial optimization and graph theory. Our aim is also to develop approaches not based on abin discretization (i.e. an alternative to such methods that are currently the most effective).In this work, we perform a theorical study of the quality of bounds of differents classicalformulations. We tighten some formulations and we propose new formulations. We perform a numerical study to test bound quality on classical instances. This study permits toidentify the determinant factor in the quality of mathematical programming formulations.We develop and test two resolution approaches. The first is based on Dantzig-Wolfedecomposition associated with a branching on no-overlapping disjunctive constraints. Thisapproach permits to improve results obtained by mathematical programming.The second approach establish a combinatorial approach based on multiple intervalgraph caracterization (modelling the item no-overlapping according to their projection oneach axis). The first algorithm is based on consecutive ones matrices enumeration. An otheruse labelled tree to eliminate more efficiently symmetry in packing. These approaches haveto advantage of being independent from bin discretization

Dans cette thèse, nous étudions les aspects structurels et algorithmiques de différents problèmes de théorie des graphes. Rappelons qu’un graphe est un ensemble de sommets éventuellement reliés par des arêtes. Deux sommets sont adjacents s’ils sont reliés par une arête.<p>Tout d’abord, nous considérons les deux problèmes suivants :le problème de vertex cover et celui de dominating set, deux cas particuliers du problème de hitting set. Un vertex cover est un ensemble de sommets qui rencontrent toutes les arêtes alors qu’un dominating set est un ensemble X de sommets tel que chaque sommet n’appartenant pas à X est adjacent à un sommet de X. La version connexe de ces problèmes demande que les sommets choisis forment un sous-graphe connexe. Pour les deux problèmes précédents, nous examinons le prix de la connexité, défini comme étant le rapport entre la taille minimum d’un ensemble répondant à la version connexe du problème et celle d’un ensemble du problème originel. Nous prouvons la difficulté du calcul du prix de la connexité d’un graphe. Cependant, lorsqu’on exige que le prix de la connexité d’un graphe ainsi que de tous ses sous-graphes induits soit borné par une constante fixée, la situation change complètement. En effet, pour les problèmes de vertex cover et de dominating set, nous avons pu caractériser ces classes de graphes pour de petites constantes.<p>Ensuite, nous caractérisons en termes de dominating sets connexes les graphes Pk- free, graphes n’ayant pas de sous-graphes induits isomorphes à un chemin sur k sommets. Beaucoup de problèmes sur les graphes sont étudiés lorsqu’ils sont restreints à cette classe de graphes. De plus, nous appliquons cette caractérisation à la 2-coloration dans les hypergraphes. Pour certains hypergraphes, nous prouvons que ce problème peut être résolu en temps polynomial.<p>Finalement, nous travaillons sur le problème de Pk-hitting set. Un Pk-hitting set est un ensemble de sommets qui rencontrent tous les chemins sur k sommets. Nous développons un algorithme d’approximation avec un facteur de performance de 3. Notre algorithme, basé sur la méthode primal-dual, fournit un Pk-hitting set dont la taille est au plus 3 fois la taille minimum d’un Pk-hitting set. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

We present new approaches to define and analyze geometric graphs. <p><p>The region-counting distances, introduced by Demaine, Iacono and Langerman, associate to any pair of points (p,q) the number of items of a dataset S contained in a region R(p,q) surrounding (p,q). We define region-counting disks and circles, and study the complexity of these objects. Algorithms to compute epsilon-approximations of region-counting distances and approximations of region-counting circles are presented.<p><p>We propose a definition of the locality for properties of geometric graphs. We measure the local density of graphs using the region-counting distances between pairs of vertices, and we use this density to define local properties of classes of graphs.<p>We illustrate the locality by introducing the local diameter of geometric graphs: we define it as the upper bound on the size of the shortest path between any pair of vertices, expressed as a function of the density of the graph around those vertices. We determine the local diameter of several well-studied graphs such as the Theta-graph, the Ordered Theta-graph and the Skip List Spanner. We also show that various operations, such as path and point queries using geometric graphs as data structures, have complexities which can be expressed as local properties.<p><p>A family of proximity graphs, called Empty Region Graphs (ERG) is presented. The vertices of an ERG are points in the plane, and two points are connected if their neighborhood, defined by a region, does not contain any other point. The region defining the neighborhood of two points is a parameter of the graph. This family of graphs includes several known proximity graphs such as Nearest Neighbor Graphs, Beta-Skeletons or Theta-Graphs. We concentrate on ERGs that are invariant under translations, rotations and uniform scaling of the vertices. We give conditions on the region defining an ERG to ensure a number of properties that might be desirable in applications, such as planarity, connectivity, triangle-freeness, cycle-freeness, bipartiteness and bounded degree. These conditions take the form of what we call tight regions: maximal or minimal regions that a region must contain or be contained in to make the graph satisfy a given property. We show that every monotone property has at least one corresponding tight region; we discuss possibilities and limitations of this general model for constructing a graph from a point set.<p><p>We introduce and analyze sigma-local graphs, based on a definition of locality by Erickson, to illustrate efficient construction algorithm on a subclass of ERGs. / Doctorat en sciences, Spécialisation Informatique / info:eu-repo/semantics/nonPublished

Les algorithmes distribués de consensus sont des algorithmes itératifs de faible complexité où les nœuds de capteurs voisins interagissent les uns avec les autres pour parvenir à un accord commun sans unité coordinatrice. Comme les nœuds dans un réseau de capteurs sans fil ont une puissance de calcul et une batterie limitées, ces algorithmes distribués doivent parvenir à un consensus en peu de temps et avec peu d’échange de messages. La première partie de cette thèse s’est basée sur l’étude et la comparaison des différents algorithmes de consensus en mode synchrone et asynchrone en termes de vitesse de convergence et taux de communications. La seconde partie de nos travaux concerne l’application de ces algorithmes de consensus au problème de la détection de trous de couverture dans les réseaux de capteurs sans fil.Ce problème de couverture fournit aussi le contexte de la suite de nos travaux. Il se décrit comme étant la façon dont une région d’intérêt est surveillée par des capteurs. Différentes approches géométriques ont été proposées mais elles sont limitées par la nécessité de connaitre exactement la position des capteurs ; or cette information peut ne pas être disponible si les dispositifs de localisation comme par exemple le GPS ne sont pas sur les capteurs. À partir de l’outil mathématique appelé topologie algébrique, nous avons développé un algorithme distribué de détection de trous de couverture qui recherche une fonction harmonique d’un réseau, c’est-à-dire annulant l’opérateur du Laplacien de dimension 1. Cette fonction harmonique est reliée au groupe d’homologie H1 qui recense les trous de couverture. Une fois une fonction harmonique obtenue, la détection des trous se réalise par une simple marche aléatoire dans le réseau. / Distributed consensus algorithms are iterative algorithms of low complexity where neighboring sensors interact with each other to reach an agreement without coordinating unit. As the nodes in a wireless sensor network have limited computing power and limited battery, these distributed algorithms must reach a consensus in a short time and with little message exchange. The first part of this thesis is based on the study and comparison of different consensus algorithms synchronously and asynchronously in terms of convergence speed and communication rates. The second part of our work concerns the application of these consensus algorithms to the problem of detecting coverage holes in wireless sensor networks.This coverage problem also provides the context for the continuation of our work. This problem is described as how a region of interest is monitored by sensors. Different geometrical approaches have been proposed but are limited by the need to know exactly the position of the sensors; but this information may not be available if the locating devices such as GPS are not on the sensors. From the mathematical tool called algebraic topology, we have developed a distributed algorithm of coverage hole detection searching a harmonic function of a network, that is to say canceling the operator of the 1-dimensional Laplacian. This harmonic function is connected to the homology group H1 which identifies the coverage holes. Once a harmonic function obtained, detection of the holes is realized by a simple random walk in the network.

La compréhension des processus conduisant à la construction d’une ville nécessite une approche pluridisciplinaire, dont les prismes utilisés ici sont l’archéologie, l’histoire, les mathématiques, la géographie et la géomatique. Les sources doivent être multiples, archéologiques, écrites, fiscales, iconographiques, planimétriques et les échelles variées, de la maison au territoire. La ville de Saint-Antonin-Noble-Val, deuxième agglomération du Rouergue au bas Moyen Âge, dont le développement est étroitement lié à la gestion du réseau hydrographique, constitue l’espace-laboratoire de cette recherche. Ce bourg monastique représente un véritable creuset pour la mise en place d’une nouvelle méthodologie élaborée pour étudier le phénomène urbain médiéval. Les sources fiscales médiévales et modernes, traditionnellement utilisées pour l’étude des paysages, sont modélisées sous forme de graphes d’adjacence des parcelles afin de percevoir les dynamiques de l’espace urbain sur le temps long. La comparaison des parcellaires entre le bas Moyen Âge et le XIXe siècle, rendue possible par l’utilisation de la théorie des graphes et le croisement avec les données archéologiques, permet d’approcher les modalités d’aménagement d’un territoire urbain. / Understanding the process leading to the construction of a city requires a multidisciplinary approach. Herein are included disciplines such as archeology, history, mathematics, geography and geomatic. The sources should be diverse (archaeological, written, tax, iconographic, planimetric) and the scales varied, from the house to the territory. The city of Saint-Antonin-Noble-Val, whose development was closely related to the hydrographic network management, was the second largest city of Rouergue in the Late Middle Ages; it constitutes this research lab-area. With the example of this monastic town, a new methodology developed to study medieval urban phenomenon is provided. In order to perceive the dynamics of urban space over time, both medieval and modern tax sources, traditionally used for landscape study, are modeled as adjacency graphs of the plots. The comparison between the cadastral allotment of the Late Middle Ages and the XIXth century is achieved using the graph theory and its intersections with available archaeological data; it allows to approach the arrangement modalities of an urban area.

Les historiens et archéologues ont efficacement mis à profit les travaux réalisés dans le domaine des SIG pour répondre à leurs propres problématiques. Pour l'historien, un Système d’Information Géographique est avant tout un outil de compréhension des phénomènes sociaux.De nombreuses sources géohistoriques sont aujourd'hui mises à la disposition des chercheurs: plans anciens, bottins, etc. Le croisement de ces sources d'informations diverses et hétérogènes soulève de nombreuses questions autour des dynamiques urbaines.Mais les données géohistoriques sont par nature imparfaites, et pour pouvoir être exploitées, elles doivent être spatialisées et qualifiées.L'objectif de cette thèse est d'apporter une solution à ce verrou par la production de données anciennes de référence. En nous focalisant sur le réseau des rues de Paris entre la fin du XVIIIe et la fin du XIXe siècles, nous proposons plus précisément un modèle multi-représentations de données agrégées permettant, par confrontation d'observations homologues dans le temps, de créer de nouvelles connaissances sur les imperfections des données utilisées et de les corriger. Nous terminons par tester le rôle de référentiel géohistorique des données précédemment qualifiées et enrichies en spatialisant et intégrant dans le modèle de nouvelles données géohistoriques de types variés (sociales et spatiales), en proposant de nouvelles approches d'appariement et de géocodage / The increasing availability of geohistorical data, particularly through the development of collaborative projects is a first step towards the design of a representation of space and its changes over time in order to study its evolution, whether social, administrative or topographical.Geohistorical data extracted from various and heterogeneous sources are highly inaccurate, uncertain or inexact according to the existing terminology. Before being processed, such data should be qualified and spatialized.In this thesis, we propose a solution to this issue by producing reference data. In particular, we focus on Paris historical street networks and its evolution between the end of the XVIIIth and the end of the XIXth centuries.Our proposal is based on a merged structure of multiple representations of data capable of modelling spatial networks at different times, providing tools such as pattern detection in order to criticize, qualify and eventually correct data and sources without using ground truth data but the comparison of data with each other through the merging process.Then, we use the produced reference data to spatialize and integrate other geohistorical data such as social data, by proposing new approaches of data matching and geocoding