.

.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Développer des analyseurs statiques nécessite une manipulation intensive de structures d'arbres et de graphes représentant le programme. La finalité de cette thèse est de proposer des constructions de langage dédiées au prototypage d'outils d'analyse et de transformation de programmes et inspirées de la réécriture de termes et de termes-graphes. L'originalité de notre approche est d'embarquer ces nouvelles constructions dans les langages généralistes sous la forme d'un langage dédié embarqué. Les travaux de cette thèse se fondent sur le langage Tom qui propose d'embarquer des constructions de réécriture dans des langages généralistes comme Java. La première contribution de cette thèse a été de formaliser les langages embarqués sous le concept de langage îlot. Ce formalisme a ainsi permis de certifier la compilation du langage Tom. Nos travaux sur l'analyse de Bytecode nous ont ensuite conduit à réfléchir à la représentation et la manipulation de graphes de flot de programmes et nous avons alors proposé des constructions de langage inspirées de la réécriture de termes-graphes. Une autre contribution de cette thèse est la conception d'un langage de stratégies adapté à l'expression de propriétés sur un programme. Associé au filtrage, ce langage permet d'exprimer de manière déclarative des analyses et des transformations sur des arbres ou des graphes. Enfin, l'ensemble des propositions de cette thèse a été intégré au langage Tom sous la forme de nouvelles constructions syntaxiques ou d'améliorations de constructions existantes et a ainsi pu être appliqué à l'analyse du langage Java. / Developing static analyzers requires an intensive handling of tree and graph structures representing the program. Even if generalist languages such as Java or C++ have libraries dedicated to the manipulation of such structures, the absence of specialized statements makes the code complex and difficult to maintain. The purpose of this thesis is to provide dedicated language constructs to prototype tools for analysis and program transformation inspired by the term and term-graph rewriting. The originality of our approach is to embed these new statements in generalist languages. This is motivated by the development of the Tom language that offers rewriting constructs for generalist languages like Java. The first contribution of this thesis is to formalize embedded languages in the concept of island languages. This formalism enables the certification of the Tom compiler. Our work on Bytecode analysis leads us to propose a dedicated language for the representation and manipulation of program flow graphs. Thus we propose language constructs based on the term-graph rewriting. A further contribution of this thesis is to design a strategy language adapted to the expression of properties on a program. Associated with matching capabilities, this language allows to express in a declarative way analysis and transformations on trees or graphs. Finally, all the proposals of this thesis have been integrated into the Tom language in the form of new statements or improvements of existing ones. This language proposal has been applied to the analysis of Java programs.

Dans cette thèse, nous présentons une approche algorithmique permettant la génération de guides de construction de cages moléculaires organiques. Il s'agit d'architectures semi-moléculaires possédant un espace interne défini capable de piéger une molécule cible appelée substrat. De nombreuses œuvres proposent de générer des cages organiques moléculaires obtenues à partir de structures symétriques, qui ont une bonne complexité, mais elles ne sont pas spécifiques car elles ne prennent pas en compte des cibles précises. L'approche proposée permet de générer des guides de construction de cages moléculaires organiques spécifiques à un substrat donné. Afin de garantir la spécificité de la cage moléculaire pour le substrat cible, une structure intermédiaire, qui est une expansion de l'enveloppe du substrat cible, est utilisée. Cette structure définie la forme de l'espace dans lequel est piégé le substrat. Des petits ensembles d'atomes, appelés motifs moléculaires liants, sont ensuite intégrés à cette structure intermédiaire. Ces motifs moléculaires sont les ensembles d'atomes nécessaires aux cages moléculaires pour leur permettre d’interagir avec le substrat afin de le capturer. / In this thesis, we present an algorithmic approach allowing the generation of construction guides of organic molecular cages. These semi-molecular architectures have a defined internal space capable of trapping a target molecule called substrate. Many works propose to generate molecular organic cages obtained from symmetrical structures, which have a good complexity, but they are not specific because they do not take into account precise targets. The proposed approach makes it possible to generate guides for the construction of organic molecular cages specific to a given substrate. In order to ensure the specificity of the molecular cage for the target substrate, an intermediate structure, which is an expansion of the envelope of the target substrate, is used. This structure defines the shape of the space in which the substrate is trapped. Small sets of atoms, called molecular binding patterns, are then integrated into this intermediate structure. These molecular patterns are the sets of atoms needed by molecular cages to allow them to interact with the substrate to capture it.

Les Graphes sont des structures mathématiques puissantes constituant un outil de modélisation universel utilisé dans différents domaines de l'informatique, notamment dans le domaine de la reconnaissance de formes. L'appariement de graphes est l'opération principale dans le processus de la reconnaissance de formes à base de graphes. Dans ce contexte, trouver des solutions d'appariement de graphes, garantissant l'optimalité en termes de précision et de temps de calcul est un problème de recherche difficile et d'actualité. Dans cette thèse, nous nous intéressons à la résolution de ce problème dans deux domaines : la reconnaissance de formes 2D et 3D. Premièrement, nous considérons le problème d'appariement de graphes géométriques et ses applications sur la reconnaissance de formes 2D. Dance cette première partie, la reconnaissance des Kites (structures archéologiques) est l'application principale considérée. Nous proposons un "framework" complet basé sur les graphes pour la reconnaissance des Kites dans des images satellites. Dans ce contexte, nous proposons deux contributions. La première est la proposition d'un processus automatique d'extraction et de transformation de Kites a partir d'images réelles en graphes et un processus de génération aléatoire de graphes de Kites synthétiques. En utilisant ces deux processus, nous avons généré un benchmark de graphes de Kites (réels et synthétiques) structuré en 3 niveaux de bruit. La deuxième contribution de cette première partie, est la proposition d'un nouvel algorithme d'appariement pour les graphes géométriques et par conséquent pour les Kites. L'approche proposée combine les invariants de graphes au calcul de l'édition de distance géométrique. Deuxièmement, nous considérons le problème de reconnaissance des formes 3D ou nous nous intéressons à la reconnaissance d'objets déformables représentés par des graphes c.à.d. des tessellations de triangles. Nous proposons une décomposition des tessellations de triangles en un ensemble de sous structures que nous appelons triangle-étoiles. En se basant sur cette décomposition, nous proposons un nouvel algorithme d'appariement de graphes pour mesurer la distance entre les tessellations de triangles. L'algorithme proposé assure un nombre minimum de structures disjointes, offre une meilleure mesure de similarité en couvrant un voisinage plus large et utilise un ensemble de descripteurs qui sont invariants ou au moins tolérants aux déformations les plus courantes. Finalement, nous proposons une approche plus générale de l'appariement de graphes. Cette approche est fondée sur une nouvelle formalisation basée sur le problème de mariage stable. L'approche proposée est optimale en terme de temps d'exécution, c.à.d. la complexité est quadratique O(n2), et flexible en terme d'applicabilité (2D et 3D). Cette approche se base sur une décomposition en sous structures suivie par un appariement de ces structures en utilisant l'algorithme de mariage stable. L'analyse de la complexité des algorithmes proposés et l'ensemble des expérimentations menées sur les bases de graphes des Kites (réelle et synthétique) et d'autres bases de données standards (2D et 3D) attestent l'efficacité, la haute performance et la précision des approches proposées et montrent qu'elles sont extensibles et générales / Graphs are powerful mathematical modeling tools used in various fields of computer science, in particular, in Pattern Recognition. Graph matching is the main operation in Pattern Recognition using graph-based approach. Finding solutions to the problem of graph matching that ensure optimality in terms of accuracy and time complexity is a difficult research challenge and a topical issue. In this thesis, we investigate the resolution of this problem in two fields: 2D and 3D Pattern Recognition. Firstly, we address the problem of geometric graphs matching and its applications on 2D Pattern Recognition. Kite (archaeological structures) recognition in satellite images is the main application considered in this first part. We present a complete graph based framework for Kite recognition on satellite images. We propose mainly two contributions. The first one is an automatic process transforming Kites from real images into graphs and a process of generating randomly synthetic Kite graphs. This allowing to construct a benchmark of Kite graphs (real and synthetic) structured in different level of deformations. The second contribution in this part, is the proposition of a new graph similarity measure adapted to geometric graphs and consequently for Kite graphs. The proposed approach combines graph invariants with a geometric graph edit distance computation. Secondly, we address the problem of deformable 3D objects recognition, represented by graphs, i.e., triangular tessellations. We propose a new decomposition of triangular tessellations into a set of substructures that we call triangle-stars. Based on this new decomposition, we propose a new algorithm of graph matching to measure the distance between triangular tessellations. The proposed algorithm offers a better measure by assuring a minimum number of triangle-stars covering a larger neighbourhood, and uses a set of descriptors which are invariant or at least oblivious under most common deformations. Finally, we propose a more general graph matching approach founded on a new formalization based on the stable marriage problem. The proposed approach is optimal in term of execution time, i.e. the time complexity is quadratic O(n2) and flexible in term of applicability (2D and 3D). The analyze of the time complexity of the proposed algorithms and the extensive experiments conducted on Kite graph data sets (real and synthetic) and standard data sets (2D and 3D) attest the effectiveness, the high performance and accuracy of the proposed approaches and show that the proposed approaches are extensible and quite general

Dans cette thèse nous explorons différentes facettes des modèles de tenseurs aléatoires. Les modèles de tenseurs aléatoires ont été introduits en physique dans le cadre de l'étude de la gravité quantique. En effet les modèles de matrices aléatoires, qui sont un cas particuliers de modèles de tenseurs, en sont une des origines. Ces modèles de matrices sont connus pour leur riche combinatoire et l'incroyable diversité de leurs propriétés qui les font toucher tous les domaines de l'analyse, la géométrie et des probabilités. De plus leur étude par les physiciens ont prouvé leur efficacité en ce qui concerne l'étude de la gravité quantique à deux dimensions. Les modèles de tenseurs aléatoires incarnent une généralisation possible des modèles de matrices. Comme leurs cousins, les modèles de matrices, ils posent questions dans les domaines de la combinatoire (comment traiter les cartes combinatoires d dimensionnelles ?), de la géométrie (comment contrôler la géométrie des triangulations générées ?) et de la physique (quel type d'espace-temps produisent-ils ? Quels sont leurs différentes phases ?). Cette thèse espère établir des pistes ainsi que des techniques d'études de ces modèles. Dans une première partie nous donnons une vue d'ensemble des modèles de matrices. Puis, nous discutons la combinatoire des triangulations en dimensions supérieures ou égales à trois en nous concentrant sur le cas tridimensionnelle (lequel est plus simple à visualiser). Nous définissons ces modèles et étudions certaines de leurs propriétés à l'aide de techniques combinatoires permettant de traiter les cartes d dimensionnelles. Enfin nous nous concentrons sur la généralisation de techniques issues des modèles de matrices dans le cas d'une famille particulières de modèles de tenseurs aléatoires. Ceci culmine avec le dernier chapitre de la thèse donnant des résultats partiels concernant la généralisation de la récurrence topologique de Eynard et Orantin à cette famille de modèles de tenseurs. / In this thesis manuscript we explore different facets of random tensor models. These models have been introduced to mimic the incredible successes of random matrix models in physics, mathematics and combinatorics. After giving a very short introduction to few aspects of random matrix models and recalling a physical motivation called Group Field Theory, we start exploring the world of random tensor models and its relation to geometry, quantum gravity and combinatorics. We first define these models in a natural way and discuss their geometry and combinatorics. After these first explorations we start generalizing random matrix methods to random tensors in order to describes the mathematical and physical properties of random tensor models, at least in some specific cases.

Cette thèse porte sur l'historisation des données dans les bases de données graphes. La problématique des données en graphes existe depuis longtemps mais leur exploitation par des moteurs de système de gestion de bases de données, principalement dans les moteurs NoSQL, est récente. Cette apparition est notamment liée à l'émergence des thématiques Big Data dont les propriétés intrinsèques, souvent décrites à l'aide des propriétés 3V (variété, volume, vélocité), ont révélé les limites des bases de données relationnelles classiques. L'historisation quant à elle, est un enjeu majeur des SI qui a été longtemps abordé seulement pour des raisons techniques de sauvegarde, de maintenance ou plus récemment pour des raisons décisionnelles (suites applicatives de Business Intelligence). Cependant, cet aspect s'avère maintenant prendre une place prédominante dans les applications de gestion. Dans ce contexte, les bases de données graphes qui sont de plus en plus utilisées n'ont que très peu bénéficié des apports récents de l'historisation. La première contribution consiste à étudier le nouveau poids des données historisées dans les SI de gestion. Cette analyse repose sur l'hypothèse selon laquelle les applications de gestion intègrent de plus en plus en leur sein les enjeux d'historisation. Nous discutons ce positionnement au regard de l'analyse de l'évolution des SI par rapport à cette problématique. La deuxième contribution vise, au-delà de l'étude de l'évolution des sytèmes d'information, à proposer un modèle innovant de gestion de l'historisation dans les bases de données NoSQL en graphes. Cette proposition consiste d'une part en l'élaboration d'un système unique et générique de représentation de l'historique au sein des BD NoSQL en graphes et d'autre part à proposer des modes d'interrogation (requêtes). Nous montrons qu'il est possible d'utiliser ce système aussi bien pour des requêtes simples (c'est-à-dire correspondant à ce que l'on attend en première intention d'un système d'historisation~: récupérer les précédentes versions d'une donnée) mais aussi de requêtes plus complexes qui permettent de tirer parti aussi bien de la notion d'historisation que des possibilités offertes par les bases de données graphes (par exemple, la reconnaissance de motifs dans le temps). / This thesis deals with data historization in the context of graphs. Graph data have been dealt with for many years but their exploitation in information systems, especially in NoSQL engines, is recent. The emerging Big Data and 3V contexts (Variety, Volume, Velocity) have revealed the limits of classical relational databases. Historization, on its side, has been considered for a long time as only linked with technical and backups issues, and more recently with decisional reasons (Business Intelligence). However, historization is now taking more and more importance in management applications.In this framework, graph databases that are often used have received little attention regarding historization. Our first contribution consists in studying the impact of historized data in management information systems. This analysis relies on the hypothesis that historization is taking more and more importance. Our second contribution aims at proposing an original model for managing historization in NoSQL graph databases.This proposition consists on the one hand in elaborating a unique and generic system for representing the history and on the other hand in proposing query features.We show that the system can support both simple and complex queries.Our contributions have been implemented and tested over synthetic and real databases.

Cette thèse s'inscrit dans le cadre de la théorie des graphes, et porte plus particulièrement sur des problèmes de coloration de graphes. Dans cette thèse, nous nous intéressons à l'utilisation et au développement de la méthode de déchargement, un argument de comptage qui exploite fortement la structure du graphe. Cette méthode est décisive dans la preuve du Théorème des Quatre Couleurs. Nous donnons d'abord une vue d'ensemble des outils de déchargement que nous utilisons dans ce travail, entre les méthodes élégantes mises en application, et les astuces développées. Dans le cadre de la coloration d'arêtes par liste, nous résolvons la Conjecture de Coloration par Liste faible dans le cas des graphes planaires de degré maximum 8, en prouvant qu'on peut colorier par liste les arêtes de ces derniers avec 9 couleurs seulement. Ceci améliore un résultat de Borodin de 1990. Enfin, nous présentons nos résultats dans le cadre de la coloration de carrés, où il s'agit de colorier les sommets sans qu'il y ait deux sommets adjacents ou avec un voisin commun qui soient de la même couleur. On s'intéresse en particulier à des conditions suffisantes sur la densité du graphe (c-à-d le degré moyen maximum d'un sous-graphe) pour qu'on puisse colorier son carré avec peu de couleurs. / This thesis falls within graph theory, and deals more precisely with graph coloring problems. In this thesis, we use and develop the discharging method, a counting argument that makes strong advantage of the graph structure. This method is decisive in the proof of the Four Color Theorem. We first give an illustrated overview of the discharging tools that are used for this work: nice methods that we apply, and handy tricks that we develop. In the realm of list edge coloring, we most notably prove that the weak List Coloring Conjecture is true for planar graphs of maximum degree 8 (i.e. that they are edge 9-choosable), thus improving over a result of Borodin from 1990. We finally present our results about square coloring, where the goal is to color the vertices in such a way that two vertices that are adjacent or have a common neighbor receive different colors. We look in particular into sufficient conditions on the density of a graph (i.e. the maximum average degree of a subgraph) for its square to be colorable with few colo

Le problème de l'exploration de graphes trouve ses motivations en informatique fondamentale, notamment en logique et en théorie de la complexité. Il possède également de nombreuses applications en robotique. Quel que soit le cadre, la quantité de mémoire utilisée par l'entité mobile (robot, automate fini, etc.) effectuant l'exploration est un des paramètres importants à considérer. Dans cette thèse, nous étudions en détail la complexité en espace de l'exploration de graphes, à travers différents modèles. Nous distinguons principalement deux cadres d'études.<br /><br />Dans la première partie de la thèse, nous nous attachons à l'étude de l'exploration ``sans assistance'', c'est-à-dire lorsque l'entité mobile ne possède aucune information sur le graphe à explorer. Dans ce contexte, nous prouvons plusieurs bornes inférieures et supérieures sur la quantité de mémoire nécessaire et suffisante à l'entité pour explorer tous les graphes. En particulier, nous montrons que l'algorithme très simple de parcours en profondeur d'abord est optimal en mémoire lorsque la complexité est exprimée en fonction du degré et du diamètre.<br /><br />Dans la seconde partie de la thèse, nous nous attachons à l'étude de l'exploration ``avec assistance''. Nous considérons un modèle supposant l'existence d'un oracle ayant une connaissance exhaustive du graphe exploré, et capable d'aider l'entité mobile en lui fournissant de l'information. Nous nous intéressons ainsi à la quantité minimale d'information (mesurée en nombre de bits) que l'oracle doit fournir à l'entité pour permettre l'exploration. Cette information peut être soit donnée directement à l'entité, soit codée sur les sommets du graphes.