Les automates cellulaires ont été introduits il y a une soixantaine d'années par von Neumann et Ulam qui cherchaient à définir les caractéristiques d'un système formel apte au calcul universel et à l'auto-reproduction. Leur utilité a été rapidement reconnue dans des domaines variés comme la physique et la biologie, pour modéliser des phénomènes complexes. En informatique, ils offrent un cadre privilégié pour l'étude du parallélisme massif. Leur description est simple et bien formalisée. Ils ont a la même puissance de calcul que les machines de Turing et de plus la richesse algorithmique propre aux machines parallèles tout en restant un modèle physiquement réaliste. Dans le cadre unificateur de la reconnaissance de langages, je m'intéresse aux questions de complexité sur les automates cellulaires, avec une attention particulière aux petites classes de complexité : calcul en temps réel (i.e. temps minimal) et en temps linéaire; en effet, c'est pour ces classes que l'apport du parallélisme est remarquable par rapport au mode séquentiel. Avec pour objectif de préciser les capacités de ce modèle et de mieux comprendre ce qu'est un calcul parallèle, trois tendances majeures se dégagent de mes travaux : l'étude des limites de ce modèle, la comparaison avec d'autres modèles de calcul et la question de l'influence de certains paramètres comme la dimension ou le voisinage sur ses capacités de reconnaissance.

Attention, ce résumé comporte un peu d'ironie et d'humour. Dans ce mémoire, nous défendons l'idée selon laquelle, pour tout modèle de calcul raisonnable, ce n'est plus tant le modèle qui compte pour caractériser les classes de complexité importantes que la complexité de la structure combinatoire sous-jacente et en définitive d'un graphe sous-jacent. Pour prendre l'exemple des circuits booléens ou algébriques comme modèles, tout ce qui importe est la complexité du graphe orienté sous-jacent au circuit. Par modèle de calcul raisonnable, nous entendons, comme il se doit, un modèle qui étudié sur une classe de graphes standard nous donne la classe de complexité standard attendue afin de satisfaire aux règles élémentaires des tautologies. On pourrait aussi choisir comme modèles raisonnables les modèles Turing-complet (ou une autre notion de complétude plus adaptée selon les objets calculés), formalisables dans une logique simple (afin d'éviter les "tricheries" et les modèles conçus spécialement pour faire échouer la belle idée défendue). Néanmoins, cette seconde option n'étant pas sans risque, nous nous contentons de la proposer. La thèse défendue est une version un peu plus formalisée et précise mathématiquement de cette idée aux contours un peu flous et qui est donc nécessairement un peu fausse telle quelle.

La comparaison de réseaux biologiques est actuellement l'une des approches les plus prometteuses pour aider à la compréhension du fonctionnement des organismes vivants. Elle apparaît comme la suite attendue de la comparaison de séquences biologiques dont l'étude ne représente en réalité que l'aspect génomique des informations manipulées par les biologistes. Dans cette thèse, nous proposons une approche innovante permettant de comparer deux réseaux biologiques modélisés respectivement par un graphe orienté D et un graphe non-orienté G, et dotés d'une fonction f établissant la correspondance entre les sommets des deux graphes. L'approche consiste à extraire automatiquement une structure dans D, biologiquement significative, dont les sommets induisent dans G, par f, une structure qui soit aussi biologiquement significative. Nous réalisons une étude algorithmique du problème issu de notre approche en commençant par sa version dans laquelle D est acyclique (DAG). Nous proposons des algorithmes polynomiaux pour certains cas, et nous montrons que d'autres cas sont algorithmiquement difficiles (NP-complets). Pour résoudre les instances difficiles, nous proposons une bonne heuristique et un algorithme exact basé sur la méthode branch-and-bound. Pour traiter le cas où D est cyclique, nous introduisons une méthode motivée par des hypothèses biologiques et consistant à décomposer D en DAGs tels que les sommets de chaque DAG induisent dans G un sous-graphe connexe. Nous étudions également dans cette thèse, l'inférence des voies de signalisation en combinant les informations sur les causes et sur les effets des événements extra-cellulaires. Nous modélisons ce problème par un problème d'orientation de graphes mixtes et nous effectuons une étude de complexité permettant d'identifier les instances faciles et celles difficiles.

Cette thèse porte sur l'étude de la complexité de l'exploration de graphes dynamiques par agent mobile. Une entité mobile (appelée agent) se déplaçant dans un graphe dynamique doit traverser/visiter au moins une fois chacun de ses sommets. (Le temps de traversée d'une arête est unitaire.) Ce problème fondamental en algorithmique par agents mobiles a été très étudié dans les graphes statiques depuis l'article originel de Claude Shannon. Concernant les graphes dynamiques, seul le cas des graphes dynamiques périodiques a été étudié. Nous étudions ce problème dans deux familles de graphes dynamiques, les graphes dynamiques périodiquement variables (PV-graphes) et les graphes dynamiques T-intervalle-connexes. Les résultats obtenus dans cette thèse améliorent des résultats existants et donnent des bornes optimales sur le problème étudié. Un PV-graphe est défini par un ensemble de transporteurs suivant infiniment leur route respective le long des stations du réseau. En 2013, Flocchini, Mans et Santoro ont étudié le problème de l'exploration des PV-graphes en considérant que l'agent doit toujours rester sur les transporteurs. Cette thèse montre l'impact de la capacité d'attendre sur les stations. Nous prouvons que l'attente sur les stations permet à l'agent d'atteindre de meilleures complexités en pire cas : le nombre de mouvements est réduit d'un facteur multiplicatif d'au moins $\Theta(p)$, et la complexité en temps passe de $\Theta(kp^2)$ à $\Theta(np)$, où $n$ est le nombre de stations, $k$ le nombre de transporteurs, et $p$ la période maximale ($n\leq kp$ dans tout PV-graphe connexe). Par ailleurs, l'algorithme que nous proposons pour prouver les bornes supérieures permet de réaliser la cartographie du PV-graphe, en plus de l'explorer. Dans la deuxième partie de cette thèse, nous considérons le même problème (l'exploration) dans les graphes dynamiques T-intervalle-connexes. Un graphe dynamique est $T$-intervalle-connexe ($T \geq 1$) si pour chaque fenêtre de $T$ unités de temps, il existe un sous-graphe couvrant connexe stable. Nous considérons dans un premier temps les graphes dynamiques T-intervalle-connexes qui ont un anneau de taille $n$ comme graphe sous-jacent et nous montrons que la complexité en temps en pire cas de leurs exploration est de $2n-T-\Theta(1)$ unités de temps si l'agent connaît la dynamique du graphe, et $n+ \frac{n}{\max\{1,T-1\}} (\delta-1) \pm\Theta(\delta)$ unités de temps sinon, où $\delta$ est le temps maximum entre deux apparitions successives d'une arête. Nous généralisons ensuite ces résultats en considérant une autre famille de graphes sous-jacents, les cactus à $n$ sommets. Un cactus est un graphe connexe dans lequel deux cycles ont au plus un sommet en commun. Nous donnons un algorithme qui permet d'explorer ces graphes dynamiques en au plus $2^{O(\sqrt{log n})} n$ unités de temps, et nous montrons que la borne inférieure de notre algorithme est $2^{\Omega(\sqrt{log n})} n$.

Cette recherche en informatique théorique construit de nouveaux ponts entre logique linéaire et théorie de la complexité. Elle propose deux modèles de machines abstraites qui permettent de capturer de nouvelles classes de complexité avec la logique linéaire, les classes des problèmes efficacement parallélisables (NC et AC) et celle des problèmes solutionnables avec peu d'espace, dans ses versions déterministes et non-déterministes (L et NL). La représentation des preuves de la logique linéaire comme réseaux de preuves est employée pour représenter efficacement le calcul parallèle des circuits booléens, y compris à profondeur constante. La seconde étude s'inspire de la géométrie de l'interaction, une délicate reconstruction de la logique linéaire à l'aide d'opérateurs d'une algèbre de von Neumann. Nous détaillons comment l'interaction d'opérateurs représentant des entiers et d'opérateurs représentant des programmes peut être reconnue nilpotente en espace logarithmique. Nous montrons ensuite comment leur itération représente un calcul effectué par des machines à pointeurs que nous définissons et que nous rattachons à d'autres modèles plus classiques. Ces deux études permettent de capturer de façon implicite de nouvelles classes de complexité, en dessous du temps polynomial.

Ce document pr esente les travaux que j'ai r ealis es depuis ma th ese de doctorat. Outre la pr esentation de mes contributions, j'ai essay e de pr esenter des survols des domaines dans lesquels mes travaux s'inscrivent et d'indiquer les principales questions qui s'y posent. Mes travaux visent a r epondre aux nouveaux challenges algorithmiques que posent la croissance des r eseaux de telecommunications actuels ainsi que l'augmentation des donnees et du trafi c qui y circulent. Un moyen de faire face a la taille de ces probl emes est de s'aider de la structure particuliere des r eseaux. Pour cela, je m'attache a d e nir de nouvelles caract erisations des propri et es structurelles des graphes pour les calculer et les utiliser effi cacement a des fins algorithmiques. Autant que possible, je propose des algorithmes distribu es qui ne reposent que sur une connaissance locale/partielle des r eseaux. En particulier, j' etudie les jeux de poursuite - traitant de la capture d'une entit e mobile par une equipe d'autres agents - qui off rent un point de vue int eressant sur de nombreuses propri et es de graphes et, notamment, des d ecompositions de graphes. L'approche de ces jeux d'un point de vue agents mobiles permet aussi l' etude de mod eles de calcul distribu e. Le chapitre 1 est d edi e a l' etude de plusieurs variantes des jeux de gendarmes et voleur. Le chapitre 2 traite des decompositions de graphes et de leur relation avec les problemes d'encerclement dans les graphes. Le chapitre 3 se concentre sur les probl emes d'encerclement dans des contextes a la fois centralis e et distribu e. Finalement, le chapitre 4 traite de probl emes de routage dans diff erents contextes, ainsi que de mod eles de calcul distribu e.

Il existe une multitude de traitements d'images dans la littérature, chacun étant adapté à un ensemble plus ou moins grand de cadres d'application. La généralisation ou la mise en collaboration de ces traitements pour un système plus complet et plus robuste est un problème mal posé. Les traitements d'images sont fondamentalement trop différents les uns par rapport aux autres pour être mis en commun de façon naturelle. De plus, ces derniers sont trop rigides pour pouvoir s'adapter d'eux-mêmes lorsqu'un problème non prévu à l'avance par le concepteur apparaît. Or la vision est un phénomène autoadaptatif, qui sait traiter en temps réel des situations singulières, en y proposant des traitements particuliers et adaptés. Elle est aussi un traitement complexe des informations, tant ces dernières ne peuvent être réduites à des représentations réductionnistes et simplifiantes sans être mutilées. Dans cette thèse, un système de vision est entrepris comme un tout où chaque partie est adaptée à l'autre, mais aussi où chaque partie ne peut s'envisager sans l'autre dans les tensions les plus extrêmes générées par la complexité et l'intrication des informations. Puisque chaque parcelle d'information joue un rôle local dans la vision, tout en étant dirigée par un objectif global peu assimilable à son niveau, nous envisageons la vision comme un système où chaque agent délibère selon une interférence produite par le potentiel décisionnel de chacun de ses voisins. Cette délibération est entreprise comme le résultat produit par l'interférence d'une superposition de solutions. De cette manière, il émerge du système à base d'agents une décision commune qui dirige les actions locales faites par chaque agent ou chaque partie du système. En commençant par décrire les principales méthodes de segmentation ainsi que les descripteurs de formes, puis en introduisant les systèmes multi-agents dans le domaine de l'image, nous discutons d'une telle approche où la vision est envisagée comme un système multi-agent apte à gérer la complexité inhérente de l'information visuelle tant en représentation qu'en dynamisme systémique. Nous ancrons dans ces perspectives deux modèles multi-agents. Le premier modèle traite de la segmentation adaptative d'images sans calibration manuelle par des seuils. Le deuxième modèle traite de la représentation de formes quelconques à travers la recherche de coefficients d'ondelettes pertinents. Ces deux modèles remplissent des critères classiques liés au traitement d'images, et à la reconnaissance de formes, tout en étant des cas d'études à développer pour la recherche d'un système de vision auto-adaptatif tel que nous le décrivons.

Dans un avion, un hélicoptère ou un lanceur actuel, des milliers de capteurs, pour la plupart non critiques sont utilisés pour la mesure de divers paramètres (températures, pressions, positions...) Les résultats sont ensuite acheminés par des fils vers les calculateurs de bord qui les traitent. Ceci implique la mise en place de centaines de kilomètres de câbles (500 km pour un avion de ligne) dont le volume est considérable. Il en résulte une grande complexité de conception et de fabrication, des problèmes de fiabilité, notamment au niveau des connexions, et une masse importante. Par ailleurs l'instrumentation de certaines zones est impossible car leur câblage est difficilement envisageable par manque d'espace. En outre, s'il est souvent intéressant d'installer de nouveaux capteurs pour faire évoluer un aéronef ancien, l'installation des câbles nécessaires implique un démantèlement partiel, problématique et coûteux, de l'appareil. Pour résoudre ces problèmes, une idée innovante a émergé chez les industriels de l'aéronautique : commencer à remplacer les réseaux filaires reliant les capteurs d'un aéronef et leur centre de décision par des réseaux sans fil. Les technologies de communication sans fil sont aujourd'hui largement utilisées dans les marchés de l'électronique de grande consommation. Elles commencent également à être déployées pour des applications industrielles comme l'automobile ou le relevé à distance de compteurs domestiques. Cependant, remplacer des câbles par des ondes représente un défi technologique considérable comme la propagation en milieu confiné, la sécurité, la sureté de fonctionnement, la fiabilité ou la compatibilité électromagnétique. Cette thèse est motivée d'une part par l'avancée non négligeable dans le milieu aérospatial que pourrait être l'établissement d'un réseau sans fil à bord d'aéronefs dans la résolution de problématique classiques comme l'allégement et l'instrumentation. Il en résulterait donc : * Une meilleure connaissance de l'environnement et de la santé de l'aéronef * Un gain sur le poids. * Un gain en flexibilité. * Un gain en malléabilité et en évolutivité. * Un gain sur la complexité. * Un gain sur la fiabilité D'autre part, étant donnée la complexité de la conception de ce réseau de capteur sans fil, il a été nécessaire d'appliquer une méthodologie évolutive et adaptée mais inspirée de l'ingénierie système. Il est envisageable, vu le nombre de sous-systèmes à considérer, que cette méthodologie soit réutilisable pour d'autre cas pratiques. Une étude aussi complète que possible a été réalisée autour de l'existant déjà établi sur le sujet. En effet, on peut en lisant ce mémoire de thèse avoir une idée assez précise de ce qui a été fait. Une liste a été dressée de toutes les technologies sans fil en indiquant leur état de maturité, leurs avantages et leurs inconvénients afin de préciser les choix possibles et les raisons de ces choix. Des projets de capteurs sans fil ont été réalisés, des technologies sans fil performantes et personnalisables ont été développées et arrivent à maturité dans des secteurs variés tels que la domotique, la santé, l'automobile ou même l'aéronautique. Cependant aucun capteur sans fil n'a été véritablement installé en milieu aérospatial car de nombreux verrous technologiques n'ont pas été levés. Fort des expériences passées, et de la maturité qu'ont prise certaines technologies, des conclusions ont été tirées des projets antérieurs afin de tendre vers des solutions plus viables. Une fois identifiés, les verrous technologiques ont été isolés. Une personnalisation de notre solution a été à envisager afin de remédier tant que faire se peut à ces points bloquants avec les moyens mis à disposition. La méthodologie appliquée nous a permis d'identifier un maximum de contraintes, besoins et exigences pour mieux focaliser les efforts d'innovation sur les plus importantes et choisir ainsi les technologies les plus indiquées.