Génération automatique d'algorithmes linéairesDécomposition de graphes, logique, stratégies de capture
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
In both parts of this thesis, we use automata to solve in a decentralised manner some graphs problems, i. E. The automata do not have a global vision of the graph in which they move, and each automaton makes local decisions using the information available on the node on which it stands. We study the impact of this information on the number of automata or the memory (state, whiteboard) that are necessary for the resolution of the problem. In the first part, we consider some methods of generation of linear algorithms that have been proposed in the literature to solve the problems expressed in monadic second order logic on graphs of bounded treewidth or of bounded cliquewidth. Although the generated algorithms are linear, the multiplicative constant of these algorithms can be very large, making them difficult to use. We have nevertheless implemented a method of generation based on the automata, and we have proved that, for a certain number of properties, the algorithms obtained are usable in practice. In the second part, we consider the problem of distributed graph searching. In a given graph, the goal is that a team, using a minimum number of searchers who calculate their own strategy, capture a fugitive arbitrarily fast and invisible. We study the compromise between the number of searchers and the quantity of information to provide on the environment to capture the fugitive.
Abstract FR:
Dans les deux parties qui composent cette thèse, nous utilisons des automates pour résoudre de manière décentralisée certains problèmes de graphes, i. E. Les automates n'ont pas une vision globale du graphe qu'ils parcourent, et chaque automate prend des décisions locales en utilisant l'information présente sur le nœud qu'il occupe. Nous étudions l'impact de cette information sur le nombre d'automates ou la mémoire (états, tableau blanc) nécessaires pour la résolution du problème. Dans la première partie, nous considérons des méthodes de génération d'algorithmes linéaires qui ont été proposées dans la littérature pour résoudre les problèmes exprimés en logique du second ordre monadique sur les graphes de largeur arborescente ou de largeur de clique bornée. Bien que linéaire, les constantes multiplicatives de ces algorithmes générés peuvent cependant être très grandes, rendant ainsi difficile leur utilisation. Nous avons néanmoins implémenté une méthode de génération basée sur les automates, et montré que les algorithmes obtenus pour un certain nombre de propriétés sont utilisables en pratique. Dans la deuxième partie, nous considérons le problème de la capture répartie. Dans un graphe donné, le but est qu'une équipe, utilisant un nombre minimum de chercheurs qui calculent eux-mêmes leur stratégie, capture un fugitif arbitrairement rapide et invisible. Nous étudions notamment le compromis entre le nombre de chercheurs et la quantité d'informations à leur fournir sur l'environnement pour capturer le fugitif.