Cette thèse explore des problématiques liées aux jeux. Les jeux qui nous intéressent sont ceux pour lesquels il n'y a pas d'information cachée: tout les joueurs ont accès à toute l'information relative au jeu; il n'y a pas non plus d'aléa. Certains jeux de société (comme les échecs ou le go) satisfont ces propriétés et sont représentatifs des jeux que nous considérons ici. La notion de stratégie est au centre de l'étude de ces jeux. En termes simples, une stratégie est une façon de jouer qui permet de s'assurer un certain résultat. La question centrale, à la fois quand on joue à un jeu et quand on l'étudie, est le problème de trouver la 'meilleure' stratégie, qui assure la victoire du joueur qui l'applique. Dans cette thèse, nous considérons à la fois des jeux à un joueurs, appelés puzzles combinatoires, et des jeux à deux joueurs. Le Rubik's cube, Rush-Hour, et le taquin sont des exemples biens connus de puzzles combinatoires. Récemment, un certain nombre de jeux -- des jeux à un joueur notamment -- ont connu un regain d'intérêt en tant qu'objets d'étude dans un domaine plus grand appelé reconfiguration. Les puzzles que l'on vient de mentionner peuvent tous être décrit de la façon suivante: il y a un ensemble de configurations, qui représente tous les états possibles du jeu; et le joueur est autorisé à transformer une configuration en une autre à via un certain nombre de règles. Le but est d'atteindre une certaine configuration cible à partir d'une configuration initiale. Le domaine de la reconfiguration étend cette définition à des problèmes de recherche: l'ensemble des configurations devient l'ensemble des solutions à une instance d'un problème donné, et l'on se demande si l'on peut transformer une solution donnée en une autre en utilisant uniquement un ensemble de règles de transformation précises. La recherche sur ce type de problèmes a été guidée par des motivations algorithmiques: ce processus peut être vu comme un moyen d'adapter une solution déjà en place en une nouvelle solution à l'aide de petits changements locaux; et des connections avec d'autres problèmes comme la génération aléatoire, ainsi que des problèmes de physique statistique. Les jeux à deux joueurs, qui sont aussi appelés jeux combinatoires, ont été étudiés depuis le début du XXème siècle avec les travaux de Bouton, continués par Berlekamp, Conway et Guy avec le développement d'une théorie unifiant un certain nombre de jeux classiques. Ce travail se focalise sur des joueurs parfaits, c'est à dire qui choisissent toujours le coup optimal. Notre but est de caractériser lequel des deux joueurs possède une stratégie qui lui assure la victoire, quelque soient les coups de son adversaire. Cette approche est au coeur de ce qui est appelé la Théorie des Jeux Combinatoires. Une grande parties des recherche est focalisée sur des 'jeux mathématiques', qui sont des jeux inventés par des mathématiciens, souvent avec des règles très simples, et rarement connus en dehors de la recherche. La motivation principale pour étudier ces jeux est la présence de liens parfois surprenant entre ces jeux et d'autres domaines des mathématiques comme entre autre la théorie des nombres, les automates ou les systèmes dynamiques. Dans cette thèse, nous étudions ainsi des jeux à un et deux joueurs. Nous nous intéressons tout particulièrement à la complexité de ces jeux, c'est à dire évaluer à quel point il est difficile (d'un point de vue algorithmique) de calculer une stratégie gagnante. Nous nous intéressons aussi à leur structure et à certaines propriétés qu'ils peuve satisfaire. Finalement, un des outils principaux dans cette étude est la notion de graphe, et nous utilisons notamment des méthodes et des techniques provenant de théorie des graphes pour résoudre ces problèmes / This thesis explores problems related to games. The games that we consider in this study are games for which there is no hidden information: all the players have access to all the information related to the game; there is also no randomness and everything is deterministic. A few well-known board games (such as chess or go) fall in this category and are representative of the kinds of games that we consider here. Central to the study of these games is the notion of strategy, which roughly speaking, is a way of playing which ensures a certain objective. The main question of interest, when both playing and studying a game, is the problem of finding the 'best' strategy, which secures the victory for the player following it. In this thesis, we consider both one-player games, also called combinatorial puzzles, and two-player games. Examples of combinatorial puzzles include Rubik's cube, Rush-Hour, Sokoban, the 15 puzzle, or peg solitaire. Recently, some types of one-player games in particular have received a strong regain of interest as part of the larger area of reconfiguration problems. The puzzles we described above can all be described in the following way: there is a set of configurations, which represents all the possible states of the game; and the player is allowed to transform a configuration using a prescribed set of moves. Starting from an initial configuration, the goal is to reach a target configuration by a succession of valid moves. Reconfiguration extends this definition to any search problem: the set of configuration becomes the set of solutions to an instance of a given problem, and we ask whether we can transform one given solution to another using only a prescribed set of moves. Hence, in addition to the combinatorial puzzles, reconfiguration problems also include many `games' which are not played by humans anymore but are instead mathematical problems sharing a lot of similarities with combinatorial puzzles. The study of reconfiguration problems has been driven by many different motivations. It has algorithmic applications: it can be seen as a way to adapt a current solution already in place to reach a new one by only making small local changes. It is also connected to other problems such as random sampling, approximate counting or problems coming from statistical physics. It can also be used as a tool for understanding the performance of some heuristic algorithms based on local modifications of solutions such as local search. Two-player games, which are also called combinatorial games, have been studied since the beginning of the twentieth century, with the works of Bouton which were continued with the development of a nice theory by Berlekamp, Conway, and Guy, unifying a certain number of classical games. We focus in this study on perfect strategies (i.e., players always choosing the best possible move), and try to characterize who wins under perfect play for various games. This approach is at the heart of what is called Combinatorial Game Theory. Most of the research in this area is focused on `math games' which are games invented by mathematicians, often with simple rules and almost never played by humans. The main motivation for studying these games comes from the nice, and sometimes unexpected connections these games have with other areas of mathematics, such as for example number theory, automatons, or dynamical systems. In this thesis, we study one- and two-player games. The questions we consider are often related to complexity. Complexity theory consists in trying to classify problems depending on their hardness. By hardness we mean to quantify how much time it would take for a computer to solve the problem. An other aspect of this research consists in investigating structural properties that these games can satisfy. Finally, one of our main tools is the notion of graph, and we use in particular methods and techniques from graph theory to answer the different questions we just mentioned

Avec l’avènement du numérique, il est désormais possible aux chercheurs d’amasser des grandes quantités de données et les plateformes de réseaux sociaux en ligne ne font pas exception à cela. Les sociologues, comme d’autres, se sont emparés de ces nouvelles ressources afin de poursuivre leurs enquêtes sur les modalités de l’interaction entre individus et leur impact sur la structuration de la sociabilité. Suivant cette voie, ce travail de thèse vise à l’analyse d’un grand nombre de comptes Facebook, aussi bien au travers des outils classiques de l’analyse de données que de la théorie des graphes, à laquelle des contributions méthodologiques sont apportées. Deux facteurs principaux encouragent l’étude de l’activité et de la sociabilité en ligne. D’une part, le temps important dédié à cette plateforme par de nombreux internautes justifie l’intérêt porté par les sociologues aux échanges qui s’y construisent. Par ailleurs, et contrairement à ce que l’on peut observer sur d’autre sites de réseaux sociaux en ligne, les liens entre individus sur Facebook sont proches de ceux hors-lignes. Dans un premier temps, la thèse s’évertue à démêler les multiples facettes de ce à quoi ”être sur Facebook” correspond. Distribués autour de pratiques normatives fabulées, les usages de nos enquêtés fluctuent au gré de leur appropriation ou non des composantes de l’importante variété de moyens de communication proposés par la plateforme. Ces usages, comme on le verra, sont ainsi différemment adoptés selon les catégories socioprofessionnelles et influent par ailleurs sur les modalités d’échanges et d’interactions des enquêtés avec leurs amis en ligne. Ces modalités sont également explorées dans ce travail, tout comme le rôle du conjoint et sa place dans la structure relationnelle. La seconde partie de la thèse se propose de construire une typologie de ces structures relationnelles dites égocentrées, c’est-à-dire depuis le point de vue de l’enquêté. Cette typologie des réseaux de sociabilité en ligne se base sur l’énumération de leurs sous-graphes induits, les graphlets, initialement développée par des chercheurs en bioinformatique. Cette approche offre une vision méso (entre micro et macro) des réseaux, propice à souligner des phénomènes inédits de sociologie des réseaux. A fort potentiel pluri-disciplinaire, la méthodologie graphlets elle même est également discutée et explorée. / With the digital advent, it is now possible for researchers to collect important amounts of data and online social network platforms are surely part of it. Sociologists, among others, seized those new resources to investigate over interaction modalities between individuals as well as their impact on the structure of sociability. Following this lead, this thesis work aims at analyzing a large number of Facebook accounts, through data analysis and graph theory classical tools, and to bring methodological contributions. Two main factors encourage to study Facebook social activities. On one hand, the importance of time spent on this platform by many Internet users justifies by itself the sociologists interest. On the other, and contrarily to what we observe on other social network websites, ties between individuals are similar to the ones that appear offline. First, the thesis proposes to detangle the multiple meanings that are behind the fact of ”being on Facebook”. The uses of our surveyed are not compacted in fantasized normative practices but vary depending on how they appropriate the different composers of the platform tools. These uses, as we will see it, do not concern all the socioprofessional categories in the same way and they also influence how the respondents interact with their online friends. The manuscript also explores these interactions, as well as the lover role into the relational structure. Second part of the thesis builds a typology of these relational structures. They are said as egocentred, which means that they are taken from the perspective of the respondent. This typology of social networks is based on their graphlet counts, that are the number of times each type of subnetwork appear in them. This approach offers a meso perspective (between micro and macro), that is propitious to underline some new social phenomena. With a high pluri-disciplinary potential, the graphlet methodology is also discussed and explored itself.

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.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

L'objectif de réduction de la consommation en kérosène des avions passant par une plus grande efficacité des systèmes, la distribution électrique devient un moyen privilégié pour satisfaire les besoins. Dans ce cadre, la notion d'avion « plus électrique » implique de revoir les systèmes de distribution et d'étudier, notamment, le passage en haute tension continue(HVDC). Une description générale des systèmes embarqués sur les avions civils est donnée dans ce manuscrit ainsi qu'une description des avantages et inconvénients des différents vecteurs énergétiques permettant de mieux situer les gains envisageables lors du passage à l'électrification des systèmes. Cependant, la mise en place de la distribution HVDC peut entraîner de nouveaux problèmes, notamment de qualité et/ou d'instabilité. Afin de palier ces problèmes, une architecture est proposée dans laquelle les équipements sont reliés entre eux par des coeurs de distribution eux-mêmes liés par des organes de transferts de puissances pouvant maîtriser ces transferts: on parle alors de réseau maillé. Pour pouvoir réaliser ces transferts, deux types d'équipements électroniques de puissance sont proposés : le DCPFC (Direct Current Power Flow Controler) et le MAPFC (Mixed function for Actuation and Power Flow Control). Ces équipements imposent une gestion énergétique spécifique: il faut déterminer les modes de fonctionnement des équipements ainsi que les références des puissances à transférer. Pour cela, une modélisation du réseau sous forme de graphe est effectuée, ceci se traduisant par un algorithme générique permettant de déterminer les équations structurelles du réseau ainsi que deux algorithmes servant à contrôler des grandeurs distinctes: Les grandeurs discrètes sont contrôlées par un système expert détenant un ensemble de règles de fonctionnement ; Les grandeurs continues sont gérées par un algorithme de recherche de flot dans un graphe. Après la mise en place en simulation de l'ensemble du réseau maillé, un banc d'essai expérimental valide les principes décrits théoriquement et permet l'étude de différentes gestions énergétiques (tout autant qu'il permet de tester un équipement seul ou le réseau dans une configuration non-maillée). Finalement, une exploitation des concepts sur un réseau répondant aux normes aéronautiques est développée. Ceci posant notamment des problèmes aux niveaux de la conception des équipements mais également sur l'architecture actuelle des réseaux électriques (connexion du neutre des générateurs, protection des personnes, compatibilité électromagnétique, etc.).

Le co-clustering est une technique de classification consistant à réaliser une partition simultanée des lignes et des colonnes d'une matrice de données. Parmi les approches existantes, MODL permet de traiter des données volumineuses et de réaliser une partition de plusieurs variables, continues ou nominales. Nous utilisons cette approche comme référence dans l'ensemble des travaux de la thèse et montrons la diversité des problèmes de data mining pouvant être traités, comme le partitionnement de graphes, de graphes temporels ou encore le clustering de courbes. L'approche MODL permet d'obtenir des résultats fins sur des données volumineuses, ce qui les rend difficilement interprétables. Des outils d'analyse exploratoire sont alors nécessaires pour les exploiter. Afin de guider l'utilisateur dans l'interprétation de tels résultats, nous définissons plusieurs outils consistant à simplifier des résultats fins afin d'en avoir une interprétation globale, à détecter les clusters remarquables, à déterminer les valeurs représentatives de leurs clusters et enfin à visualiser les résultats. Les comportements asymptotiques de ces outils d'analyse exploratoire sont étudiés afin de faire le lien avec les approches existantes. Enfin une application sur des comptes-rendus d'appels de l'opérateur Orange, collectés en Côte d'Ivoire, montre l'intérêt de l'approche et des outils d'analyse exploratoire dans un contexte industriel.

Soit G = (V, E) un graphe simple fini. Soit (a, b) un couple d’entiers positifs. On note par τ(G) le nombre de sommets d’un chemin d’ordre maximum dans G. Une partition (A,B) de V(G) est une (a,b)−partition si τ(⟨A⟩) ≤ a et τ(⟨B⟩) ≤ b. Si G possède une (a, b)−partition pour tout couple d’entiers positifs satisfaisant τ(G) = a+b, on dit que G est τ−partitionnable. La conjecture de partitionnement des chemins, connue sous le nom anglais de Path Partition Conjecture, cherche à établir que tout graphe est τ−partitionnable. Elle a été énoncée par Lovász et Mihók en 1981 et depuis, de nombreux chercheurs ont tenté de démontrer cette conjecture et plusieurs y sont parvenus pour certaines classes de graphes. Le présent mémoire rend compte du statut de la conjecture, en ce qui concerne les graphes non-orientés et ceux orientés. / Let G = (V,E) be a finite simple graph. We denote the number of vertices in a longest path in G by τ(G). A partition (A,B) of V is called an (a,b)−partition if τ(⟨A⟩) ≤ a and τ(⟨B⟩) ≤ b. If G can be (a,b)−partitioned for every pair of positive integers (a, b) satisfying a + b = τ (G), we say that G is τ −partitionable. The following conjecture, called The Path Partition Conjecture, has been stated by Lovász and Mihók in 1981 : every graph is τ−partitionable. Since that, many researchers prove that this conjecture is true for several classes of graphs and digraphs. This study summarizes the different results about the Path Partition conjecture.

Nous détaillons dans cette thèse des algorithmes modérément exponentiels pour l'approximation du problème MAX SAT. Nous discutons d'une méthode générique pour la conception d'algorithmes exponentiels réalisant des schémas d'approximation dans un cadre plus général. Enfin, nous présentons des résultats paramétrés pour des problèmes de coupe à cardinalité contrainte. / We give in this thesis some moderately exponential algorithms for the MAX SAT problem. We discuss a very general method to conceive efficient exponential algorithms that give approximation scheme. In the end, we present some parameterized results for CUT problem with constrained cardinality.

Une nouvelle borne supérieure sur le cardinal des codes de sous-espaces d'un espace vectoriel fini est établie grâce à la méthode de la programmation semidéfinie positive. Ces codes sont d'intérêt dans le cadre du codage de réseau (network coding). Ensuite, par la même méthode, l'on démontre une borne sur le cardinal des ensembles qui évitent une distance donnée dans l'espace de Johnson et qui est obtenue par une variante d'un programme de Schrijver. Les résultats numériques permettent d'améliorer les bornes existantes sur le nombre chromatique mesurable de l'espace Euclidien. Une hiérarchie de programmes semidéfinis positifs est construite à partir de certaines matrices issues des complexes simpliciaux. Ces programmes permettent d'obtenir une borne supérieure sur le nombre d'indépendance d'un graphe. Aussi, cette hiérarchie partage certaines propriétés importantes avec d'autres hiérarchies classiques. A titre d'exemple, le problème de déterminer le nombre d'indépendance des graphes de Paley est analysé. / We apply the semidefinite programming method to obtain a new upper bound on the cardinality of codes made of subspaces of a linear vector space over a finite field. Such codes are of interest in network coding.Next, with the same method, we prove an upper bound on the cardinality of sets avoiding one distance in the Johnson space, which is essentially Schrijver semidefinite program. This bound is used to improve existing results on the measurable chromatic number of the Euclidean space.We build a new hierarchy of semidefinite programs whose optimal values give upper bounds on the independence number of a graph. This hierarchy is based on matrices arising from simplicial complexes. We show some properties that our hierarchy shares with other classical ones. As an example, we show its application to the problem of determining the independence number of Paley graphs.

Les réseaux sont présents dans plusieurs domaines scientifiques et d’ingénierie tels que la biologie, la physique, la sociologie ainsi que la robotique ou la théorie de la communication. L’étude de ces réseaux montre qu’ils sont souvent structurés en sous-groupes. Entre eux il n’y a pas ou il y a très peu d’interaction. Par conséquent, un accord local au sein de chaque groupe est naturellement atteint alors que le consensus associé à un tel réseau doit être imposé par une loi de commande spécifique. Nous proposons donc un contrôleur discret quasi-périodique pour échanger des informations entre les groupes. Un agent de chaque groupe est choisi le « leader » et, à certains moments, ces leaders communiquent entre eux à travers un nouveau réseau. Ceci permet d’obtenir le consensus dans tout le réseau mais engendre des réinitialisation/sauts dans l’état de leaders. La première contribution de la thèse est la caractérisation de la valeur de consensus dans le cadre des systèmes linéaires impulsifs. Il est remarquable que la valeur de consensus dépende seulement des conditions initiales et des topologies des réseaux impliqués. Elle n’est donc pas sensible aux instants de réinitialisation des états de leaders. Afin d’étudier la stabilité de la valeur de consensus obtenue, nous proposons une méthode fondée sur la vérification d’une condition LMI. Cela peut être adaptée pour la conception du réseau d’interaction entre les leaders permettant d’atteindre une valeur de consensus a priori choisie. Il est aussi possible d’utiliser la condition LMI afin de garantir une vitesse de convergence désirée vers le consensus. Pour ces derniers objectifs, la topologie du réseau continue à être considérée comme fixe et connue pour chaque groupe. L’ensemble des valeurs de consensus qui peuvent être atteintes est contenu dans l’intervalle défini par le minimum et le maximum des accords locaux initiaux. Ensuite nous présentons l’étude d’un problème pratique. Des robots mobiles non-holonome, séparés dans des groupes, doivent atteindre une formation donnée. L’algorithme de consensus à pour mission de définir les trajectoires de référence pour ces robots en prenant en compte juste les informations locale. Le robot poursuit la trajectoire de référence en utilisant une commande classique pour cela. / Networks appear in several areas of science and engineering such as biology, physics, sociology as well as robotics and communication theory. Studying these networks it is possible to see cluster-like structures, which are disconnected or very weakly connected one to another. The presence of these clusters hampers consensus throughout the overall network. Instead, local agreement is reached within each cluster. To enforce consensus we have to design an appropriate decentralized controller that imposes interactions between clusters. While the interactions inside each cluster are continuous, we propose a quasi-periodic discrete controller to exchange information between clusters. A single agent from each cluster is chosen to be the leader, and at certain moments, the leaders communicate with each other through a new network. This allows consensus in the entire network but generates resets/jumps on the leaders’ state. The first contribution of this manuscript is related to the characterization of the consensus value in the linear impulsive dynamics framework. It is noteworthy that the consensus value depends only on the initial conditions and the topologies of the involved networks. Therefore, the consensus value does not depend on the reset sequence used for the leaders’ states. To study the stability of the consensus value a LMI based condition is proposed. The main advantage of this approach is its flexibility. Indeed with some modifications to the LMI condition it is possible to analyse the convergence speed of the network or to design the leaders’ network. The purpose of leaders’ network design is to reach an a priori specified consensus value with a specified convergence speed. Whatever is the objective, throughout the manuscript we consider that the network topology is fixed and known for each cluster. The set of consensus values that can be reached is restricted to the interval defined by the minimum and maximum initial local agreements. A last contribution is related to the application of the proposed methodology to a practical situation. We consider a fleet of non-holonomic mobile robots separated in clusters. The communication inside each cluster are secured and cheap while between clusters it is expensive and not securely to communicate. Nevertheless the robots have to reach a given formation. In this case our consensus algorithm is in charge of providing reference trajectories to each robot by using only the available local information. The robot follows the reference by using a classical trajectory tracking control.