De nos jours, les systèmes automatisés sont omniprésent : processus industriels, avionique, énergie atomique... La présence de tels systèmes dans des applications critiques, couplée à leur complexité rend indispensable leur vérification de façon automatique afin de garantir la sûreté de leur fonctionnement. En plus, les contraintes économiques imposent un temps de développement court, ce qui rend accru le besoin de méthodes de vérification efficaces et à coût réduit. Les algorithmes de Model-Checking sont conçus pour la vérification totale des systèmes en parcourant leurs graphes d'états. Cependant, les graphes d'états des systèmes logiciels réels ont de très grandes tailles (explosion combinatoire de la taille de l'espace d'états). Ce phénomène constitue l'obstacle principal de la vérification automatique par model checking. Alternativement, on a recours à l'exploration partiel via des algorithmes randomises. Au lieu d'abandonner l'exploration par manque de ressources et ne retourner aucune réponse quant à la validité du système, le résultat de la vérification est donné approximativement avec une probabilité d'erreur que l'on peut contrôler. La majorité des méthodes randomisées de vérification utilisent la marche aléatoire comme schéma d'exploration. Les méthodes que nous proposons opèrent sur le schéma de l'exploration même ainsi que sur le remplacement en mémoire pour apporter des performances importantes. Ces algorithmes présentent un jeu assez complet de stratégies d'exploration: en profondeur, en largeur, ou alternativement selon un paramètre de mixage prédéfini. Le choix de ce paramètre est guidé par un facteur de densité DF caractéristique du graphe considéré.

Ce travail de thèse présente un modèle de construction du sens d'un genre nouveau, défini dans le cadre des mathématiques du continu. Le langage y est vu comme un système morphodynamique, obéissant aux principes de base de la Gestalttheorie. Les unités linguistiques découpent leur sens dans un espace sémantique possédant une structure de variété différentiable. Nous avons implémenté ce modèle et l'avons testé sur le lexique adjectival français. Une méthode de construction automatique des espaces sémantiques, reposant sur l'analyse d'un graphe de synonymie, permet d'explorer le lexique adjectival dans son ensemble, ou de construire des espaces locaux. Les espaces sémantiques locaux servent de base à une méthode dynamique de calcul du sens, permettant de prendre en compte les différents facteurs de polysémie adjectivale. L'utilisation des espaces sémantiques globaux ouvre de belles perspectives, tant dans le domaine du calcul du sens que celui de l'exploration de graphes petit monde.

Notre travail porte sur l'extraction de connaissances sur des langages graphiques dont les symboles sont a priori inconnus. Nous formons l'hypothèse que l'observation d'une grande quantité de documents doit permettre de découvrir les symboles composant l'alphabet du langage considéré. La difficulté du problème réside dans la nature bidimensionnelle et manuscrite des langages graphiques étudiés. Nous nous plaçons dans le cadre de tracés en-ligne produit par des interfaces de saisie de type écrans tactiles, tableaux interactifs ou stylos électroniques. Le signal disponible est alors une trajectoire échantillonnée produisant une séquence de traits, eux-mêmes composés d'une séquence de points. Un symbole, élément de base de l'alphabet du langage, est donc composé d'un ensemble de traits possédant des propriétés structurelles et relationnelles spécifiques. L'extraction des symboles est réalisée par la découverte de sous-graphes répétitifs dans un graphe global modélisant les traits (noeuds) et leur relations spatiales (arcs) de l'ensemble des documents. Le principe de description de longueur minimum (MDL : Minimum Description Length) est mis en oeuvre pour choisir les meilleurs représentants du lexique des symboles. Ces travaux ont été validés sur deux bases expérimentales. La première est une base d'expressions mathématiques simples, la seconde représente des graphiques de type organigramme. Sur ces bases, nous pouvons évaluer la qualité des symboles extraits et comparer à la vérité terrain. Enfin, nous nous sommes intéressés à la réduction de la tâche d'annotation d'une base en considérant à la fois les problématiques de segmentation et d'étiquetage des différents traits.

Nous étudions dans cette thèse le problème de l’exploration parallèle d’un graphe à l’aide des multiples, synchronisés et mobiles agents. Chaque agent est une entité individuelle qui peut, indépendamment des autres agents, visiter les sommets du graphe ou parcourir ses arêtes. Le but de ensemble des agents est de visiter tous les sommets de graphe.Nous étudions d’abord l’exploration du graphe dans un modèle où chaque agent est équipé de mémoire interne, mais les noeuds n’ont pas de mémoire. Dans ce modèle les agents sont autorisés à communiquer entre eux en échangeant des messages. Nous présentons des algorithmes qui s’exécutent dans un minimum de temps possible pour polynomiale nombre d’agents (polynomiale en nombre de sommets du graphe). Nous étudions aussi quelle est l’impact de différentes méthodes des communications. Nous étudions des algorithmes où les agents peuvent se communiquer à distance arbitraire,mais aussi où communication est possible seulement entre les agents situés dans le même sommet. Dans les deux cas nous présentons des algorithmes efficaces. Nous avons aussi obtenu des limites inférieures qui correspondent bien à la performance des algorithmes.Nous considérons également l’exploration de graphe en supposant que les mouvements des agents sont déterminés par le soi-disant rotor-router mécanisme. Du point de vue d’un sommet fixé, le rotor- router envoie des agents qui visitent les sommet voisins dans un mode round-robin. Nous étudions l’accélération défini comme la proportion entre le pire des cas de l’exploration d’un agent unique et des plusieurs agents. Pour générales graphes, nous montrerons que le gain de vitesse en cas de multi-agent rotor-router est toujours entre fonction logarithmique et linéaire du nombre d’agents. Nous présentons également des résultats optimaux sur l’accélération de multi-agent rotor-router pour cycles, expanseurs, graphes aléatoires, cliques, tores de dimension fixé et une analyse presque optimale pour hypercubes.Finalement nous considérons l’exploration sans collision, où chaque agent doit explorer le graphe de manière indépendante avec la contrainte supplémentaire que deux agents ne peuvent pas occuper le même sommet. Dans le cas où les agents sont donnés le plan de graphe, on présente un algorithme optimal pour les arbres et un algorithme asymptotiquement optimal pour générales graphes. Nous présentons aussi des algorithmes dans le cas de l’exploration sans collision des arbres et des générales graphes dans la situation où les agents ne connaissent pas le graphe. Nous fermons la thèse par des observations finales et une discussion de problèmes ouverts liés dans le domaine de l’exploration des graphes. / In this thesis we study the problem of parallel graph exploration using multiple synchronized mobile agents. Each mobile agent is an entity that can, independently of other agents, visit vertices of the graph and traverse its edges. The goal of the agents is to visit all vertices of the graph. We first study graph exploration in the model where agents are equipped with internal memory but no memory is available at the nodes. Agents in this model are also allowed to communicate between each other by exchanging messages. We present algorithms working in a minimal possible time for a team of polynomial size (in the number of vertices of the graph). We also study the impact of the available range of communication by analysing algorithms for agents which can communicate at arbitrary distance, or only with other agents located at the same node. We present efficient algorithms and lower bounds that almost match our positive results in both communication models. We also consider graph exploration when movements of agents are determined according to the so-called rotor-router mechanism. From the perspective of a fixed node, the rotor-router sends out agents which visit the node along its outgoing edges, ina round-robin fashion. We study the speedup which is the ratio between the worst-case exploration of a single agent and of multiple agents. We first show that the speed up for general graphs for the multi-agent rotor-router is always between logarithmic and linear in the number of agents. We also present a tight analysis of the speedup for the multi-agent rotor-router for cycles, expanders, random graphs, cliques, constant dimensional tori and an almost-tight analysis for hypercubes. Finally we consider collision-free exploration, where each agent has to explore the graph independently with the additional constraint that no two agents can occupy the same node at the same time. In the case when agents are given the map of the graph, we show an optimal algorithm for trees and an asymptotically optimal algorithm for general graphs. We also present algorithms for collision-free exploration of trees and general graphs in the case when agents have no initial knowledge about the graph. We close the thesis with concluding remarks and a discussion of related open problems in the area of graph exploration.

Nous étudions dans cette thèse le problème de l'exploration parallèle d'un graphe à l'aide des multiples, synchronisés et mobiles agents. Chaque agent est une entité individuelle qui peut, indépendamment des autres agents, visitez les sommets du graphe ou parcourir ses arêtes. Le but de ensemble des agents est de visiter tous les sommets de graphe. Nous étudions d'abord l'exploration du graphe dans un modèle où chaque agent est équipé de mémoire interne, mais les nœuds n'ont pas de mémoire. Dans ce modèle les agents sont autorisés à communiquer entre eux en échangeant des messages. Nous présentons des algorithmes qui s'exécutent dans un minimum de temps possible pour polynomiale nombre d'agents (polynomiale en nombre de sommets du graphe). Nous étudions aussi quelle est l'impacte de différent méthodes des communications. Nous étudions des algorithmes où les agents peuvent se communiquer à distance arbitraire, mais aussi où communication est possible seulement entre les agents situés dans le même sommet. Dans les deux cas nous présentons des algorithmes efficaces. Nous avons aussi obtenu des limites inférieures qui correspondent bien à la performance des algorithmes. Nous considérons également l'exploration de graphe en supposant que les mouvements des agents sont déterminés par le soi-disant rotor-router mécanisme. Du point de vue d'un sommet fixé, le rotor- router envoie des agents qui visitent les sommet voisins dans un mode round-robin. Nous étudions l'accélération défini comme la proportion entre le pire des cas de l'exploration d'un agent unique et des plusieurs agents. Pour générales graphes, nous montrerons que le gain de vitesse en cas de multi-agent rotor-router est toujours entre fonction logarithmique et linéaire du nombre d'agents. Nous présentons également des résultats optimaux sur l'accélération de multi-agent rotor-router pour cycles, expanseurs, graphes aléatoires, cliques, tores de dimension fixé et une analyse presque optimale pour hypercubes. Finalement nous considérons l'exploration sans collision, où chaque agent doit explorer le graphe de manière indépendante avec la contrainte supplémentaire que deux agents ne peuvent pas occuper le même sommet. Dans le cas où les agents sont donnés le plan de graphe, on présente un algorithme optimal pour les arbres et un algorithme asymptotiquement optimal pour générales graphes. Nous présentons aussi des algorithmes dans le cas de l'exploration sans collision des arbres et des générales graphes dans la situation où les agents ne connaissent pas le graphe. Nous fermons la thèse par des observations finales et une discussion de problèmes ouverts liés dans le domaine de l'exploration des graphes.