Cette thèse d'informatique s'inscrit dans le domaine de la recherche d'information (RI). Elle a pour objet la création d'un modèle de recherche utilisant les graphes pour en exploiter la structure pour la détection de similarités entre les documents textuels d'une collection donnée et une requête utilisateur en vue d'améliorer le processus de recherche d'information. Ces similarités sont dites « structurelles » et nous montrons qu'elles apportent un gain d'information bénéfique par rapport aux seules similarités directes. Le rapport de thèse est structuré en cinq chapitres. Le premier chapitre présente un état de l'art sur la comparaison et les notions connexes que sont la distance et la similarité. Le deuxième chapitre présente les concepts clés de la RI, notamment l'indexation des documents, leur comparaison, et l'évaluation des classements retournés. Le troisième chapitre est consacré à la théorie des graphes et introduit les notations et notions liées à la représentation par graphe. Le quatrième chapitre présente pas à pas la construction de notre modèle pour la RI, puis, le cinquième chapitre décrit son application dans différents cas de figure, ainsi que son évaluation sur différentes collections et sa comparaison à d'autres approches.

Dans ce travail de thèse, nous nous intéressons à plusieurs problèmes de théorie des graphes. Dans un premier temps, nous étudions différents problèmes de coupes et de multicoupes puis, dans un second temps, nous nous focalisons sur des problèmes de recherche de sous-graphes induits. Néanmoins, ces deux parties suivent la même ligne directrice : donner une vue d'ensemble de la complexité des problèmes en établissant leur NP-complétude ou en déterminant un algorithme polynomial de moindre complexité. Dans la première partie de la thèse, nous abordons les problèmes de coupes et de multicoupes. Tout d'abord, nous étudions la conséquence de l'ajout d'une contrainte de cardinalité à ces deux types de problèmes et démontrons leur NP- complétude dans le cas général. Puis, nous déterminons leur complexité dans plusieurs classes de graphes particuliers telles que les étoiles orientées et les chaînes en élaborant, pour les cas polynomiaux, différents algorithmes reposant principalement sur la programmation dynamique et l'utilisation de relaxations lagrangiennes. Nous généralisons ensuite cette approche en considérant les versions multicritères des problèmes de coupes et de multicoupes. Nous prouvons que ces derniers sont NP-complets même dans des topologies très simples comme les chaînes ou les cycles. Dans la seconde partie de ce mémoire, nous abordons des problèmes de recherche de sous-graphes induits. Nous nous intéressons principalement à la recherche d'arbres, de chaînes et de cycles induits couvrant un ensemble T de sommets donnés. Après avoir prouvé la NP-complétude des cas généraux, nous nous focalisons davantage sur les cas où la cardinalité de T est fixée. Nous donnons également plusieurs résultats structurels pour les graphes de maille suffisamment large.

En génie logiciel, les méthodes modernes de développement (ex. le MDA) s'appuient de manière cruciale sur les notions de modélisation et de transformation. Ces méthodes peuvent s'interpréter à l'aide de la théorie des graphes. La difficulté théorique réside aujourd'hui dans l'ajout sur ces graphes de données supplémentaires sur lesquelles il est nécessaire de pouvoir effectuer des calculs. Notre travail s'est focalisé sur le développement d'un cadre mathématique sûr afin d'appliquer ces transformations. Les théories des catégories (à travers le double pushout) et des types inductifs (fonctions de calcul très expressives) nous ont permis de donner une solution unifiée à ce problème dans laquelle une seule opération permet de travailler sur la structure et de calculer avec les attributs en définissant des fonctions entre graphes possédant une partie contravariante pour le travail sur les attributs. De plus, les propriétés usuelles des systèmes de récriture sont vérifiées.

L'objectif de cette thèse est le développement d'algorithmes et de modèles permettant l'optimisation d'itinéraires dans les réseaux routiers. Dans un premier temps, ce travail de recherche étudie le problème de l'interception d'un mobile dans un graphe. Dans ce contexte, l'objectif est de calculer un itinéraire optimal permettant de rejoindre une cible mobile dont la trajectoire est connue. Cette problématique est traitée pour plusieurs situations (un poursuivant/un objectif et plusieurs poursuivants/plusieurs objectifs) et pour plusieurs types de graphes (graphes statiques et graphes FIFO). Pour chaque cas, un algorithme de résolution est proposé et l'optimalité du résultat qu'il retourne est démontrée. De plus, un ensemble de simulations est réalisé afin de vérifier l'efficacité des algorithmes en termes de temps de calcul. Dans un deuxième temps, une nouvelle classe de graphes dynamiques est définie : les graphes dynamiques avec intervalles. La particularité de ces graphes est que le poids de chaque arc dépende du temps et qu'il est représenté par un intervalle. Pour ce nouveau type de graphes, le problème du plus court chemin est étudié. Ce problème peut être vu soit en tant que problème d'optimisation monocritère soit en tant que problème d'optimisation multicritère. Pour chaque cas, le problème est formulé et des approches pour la résolution sont proposées.

Cette thèse s'intéresse au probleme de la reconnaissance d'objets en présence d'une vaste base de modèles. L'indexation de modèles peut être décrite comme suit: étant donne un groupe d'indices image, extraire rapidement de la base de modèles, les modèles contenant le groupe d'indices. La combinatoire du paradigme classique d'appariement indices-modèles étant prohibitive dans ce cas, nous proposons une methode d'indexation par une technique de hachage de graphes. Nous décrivons d'abord les principes: codage d'image et des modelés sous une forme de graphes, gestion d'une base de modèles par tables hash-codees, comparaison de graphes sur la base de leur caractérisation polynomiale, accès a la base de modèles. Ensuite, nous décrivons le système mis en œuvre selon ces principes, et nous présentons quelques résultats d'expérimentation

Le travail de thèse présenté dans ce document traite de l'analyse de différentes propriétés liées à l'observabilité des systèmes à entrée inconnue par approche graphique. La simplicité de mise en œuvre de l'approche graphique permet de se défaire des difficultés numériques inhérentes aux approches géométrique et algébrique. Ce constat a conduit ces dernières décennies, à une série d'études structurelles basées sur l'approche graphique. <br />Parmi les propriétés encore non abordées graphiquement, l'observabilité forte traduit l'observabilité des variables d'état d'un système pour toute valeur d'entrée ainsi que l'observabilité conjointe de l'état et de l'entrée. Ces propriétés plus fortes que l'observabilité simple et le diagnostic nous ont paru utiles et pertinentes à étudier. En effet, les outils d'analyse développés peuvent s'avérer importants dans le cadre de la synthèse d'observateurs ou d'estimateurs d'entrées utile à la synthèse de lois de commandes tolérantes aux défauts ou robustes aux perturbations, ou encore quand il s'agit de vérifier si la propriété d'observabilité d'un système n'est pas altérée lorsqu'il est soumis à des perturbations, voire à des défauts d'amplitude trop importante pour être négligés. <br />Le manuscrit est structuré en trois parties. Dans la première, nous avons abordé l'analyse de différentes propriétés d'observabilité. Plus précisément, nous avons tout d'abord donné des conditions nécessaires et suffisantes d'observabilité de l'entrée et de l'état d'un système. Des conditions nécessaires et suffisantes pour l'observabilité forte d'une partie donnée des composantes de l'entrée et de l'état ont ensuite été établies. Le dernier résultat de cette partie concerne l'observabilité forte de tout l'état d'un système à entrée inconnue. Des conditions nécessaires et suffisantes ont été démontrées. <br />La seconde partie de cette thèse a consisté à étudier le problème du placement des capteurs afin de recouvrer des propriétés d'observabilité forte lorsque les conditions de la première partie ne sont pas vérifiées. Deux cas ont été traités. Le premier concerne la propriété d'observabilité forte d'une partie donnée de l'état. La stratégie de placement de capteurs consiste alors en une condition nécessaire permettant d'imposer qu'au moins une sortie du système soit sensible à chacune des composantes de l'état devant être fortement observables, puis en un système de relations graphiques, utilisé comme condition suffisante à ce qu'une configuration de capteurs assure l'observabilité forte des composantes de l'état choisies. Le second problème de placement de capteurs a pour objectif de rendre observables toutes les composantes de l'état. Le problème a été traité en trois étapes. Pour chacune d'elles, des conditions nécessaires et suffisantes sur le placement de capteurs ont été trouvées. Le nombre minimal de capteurs nécessaire et suffisant a aussi été déterminé. Les conditions trouvées sont fondées essentiellement sur des algorithmes classiques de la théorie des graphes.<br />La troisième partie traite de l'implémentation des résultats établis dans une boîte à outils dédiée à l'analyse structurelle (lisa) des systèmes linéaires et bilinéaires structurés. En premier lieu, les motivations qui ont conduit à la conception de cette boîte à outils sont exposées. La structure de lisa est ensuite présentée. Elle repose entièrement sur des algorithmes de base tels que la détermination des ensembles de successeurs et de prédécesseurs, le calcul des tailles de lien et de couplages maximaux entre deux ensembles de sommets et la caractérisation des ensembles de sommets essentiels dans des liens de taille maximale ou encore des séparateurs d'entrée et de sortie. Tous ces algorithmes ont des ordres de complexité polynomiaux. Nous avons montré comment en associant certains algorithmes de base, nous sommes arrivés à analyser l'observabilité de l'état et de l'entrée et à établir des conditions de détection et de localisation de défauts. Enfin, il est présenté des fonctions pouvant être rajoutées à lisa concernant différentes propriétés structurelles pour en faire un outil d'analyse plus complet.

On étudie divers problèmes concernant le n-cube. On décrit les exemples connus de (0,2) graphes (bipartis de diamètre 2 ou 3). On présente des constructions de (0,2) graphes. On étudie les (0,2) graphes avec des triangles. On montre comment construire certains des (0,2) graphes comme graphes de Cayley de groupes. On étudie les invariants immédiats du n-cube.

Il s'agit d'utiliser par la production de logiciels effectivement opérationnels, les techniques graphiques interactives dans le domaine de l'analyse structurale de système. On s'est orienté plus précisément vers une catégorie précise de représentation des systèmes: les graphes.

Diverses techniques de modélisation sont utilisées en synthèse d'images et en CAO (conception assistée par ordinateur) pour produire des images réalistes et analyser les propriétés géométriques des objets solides modélisés. Cependant, malgré les progrès récents, la conception de formes géométriques reste une tâche complexe. Les objets géométriques que veut modéliser l'utilisateur doivent vérifier certaines propriétés, traditionnellement appelées contraintes. Pour pallier ces inconvénients certains systèmes de modélisation fournissent des outils de spécification des formes par des contraintes géométriques. Nous proposons dans cette thèse deux méthodes de résolution du système de contraintes. La première méthode étudie les graphes bipartis sous-jacents aux systèmes d'équations. Nous montrons qu'il est possible de décomposer polynomialement ces systèmes en sous-systèmes sur-contraints (plus d'équations que d'inconnues), sous-contraints (plus d'inconnues que d'équations) et bien-contraints (autant d'équations que d'inconnues) a partir du graphe biparti. La deuxième méthode proposée étudie les différentes configurations induites par des contraintes de distances, d'angles et de tangences entre points, droites et cercles. Les entités géométriques sont déterminées par un algorithme de réduction de graphes et un système à base de règles.

Cette thèse s'inscrit dans la théorie des matrices aléatoires, à l'intersection avec la théorie des probabilités libres et des algèbres d'opérateurs. Elle s'insère dans une démarche générale qui a fait ses preuves ces dernières décennies : importer les techniques et les concepts de la théorie des probabilités non commutatives pour l'étude du spectre de grandes matrices aléatoires. On s'intéresse ici à des généralisations du théorème de liberté asymptotique de Voiculescu. Dans les Chapitres 1 et 2, nous montrons des résultats de liberté asymptotique forte pour des matrices gaussiennes, unitaires aléatoires et déterministes. Dans les Chapitres 3 et 4, nous introduisons la notion de fausse liberté asymptotique pour des matrices déterministes et certaines matrices hermitiennes à entrées sous diagonales indépendantes, interpolant les modèles de matrices de Wigner et de Lévy.