L'identification de molécules bio-actives est un problème majeur pour la recherche thérapeutique et la recherche en biologie. La découverte de ces molécules repose largement sur le criblage de très grandes collections de molécules mais qui restent petites devant la taille de l'espace chimique. Dans ce contexte, les scientifiques sont demandeurs d'outils d'analyse automatique de chimiothèques et de molécules.<br />L'objectif de cette thèse est de fournir un outil de comparaison des molécules et plus généralement d'objets structurés. Nous proposons dans ce travail un algorithme générique qui identifie plusieurs sous-structures communes à entre deux objets, représentés par des graphes ou des formules logiques et évalue un degré d'inclusion entre ces objets.<br /><br />Ce degré d'inclusion correspond à un test de subsomption à valeur réelle entre formules logiques qui pourrait compléter le test de theta-subsomption classique dans les algorithmes d'apprentissage relationnel. Dans le domaine de la chimie, une mesure de similarité moléculaire a été définie à partir de deux degrés d'inclusion pour classer des molécules. L'algorithme se révèle être plus performant que les mesures de similarité et fonctions noyau auxquelles il a été comparé. Il pourra être envisagé de l'utiliser dans des problèmes de prédiction de bio-activité.

Soit un réseau comprenant des lignes de communication qui échouent indépendamment, dans lequel tous ou certains sites, appelés terminaux, doivent être capables de communiquer entre eux. Dans le modèle stochastique statique classique le réseau est représenté par un graphe probabiliste dont les arêtes sont présentes selon des probabilités connues. La mesure de fiabilité classique (CLR) est la probabilité que les terminaux appartiennent à la même composante connexe. Dans plusieurs contextes il est utile d'imposer la condition plus forte que la distance entre deux terminaux quelconques soit bornée supérieurement par un paramètre d. La probabilité que ça se produise est connue comme la fiabilité diamètre-bornée (DCR). Il s'agit d'une extension de la CLR. Les deux problèmes appartiennent à la classe NP-difficile de complexité; le calcul exact n'est possible que pour les instances de taille limitée ou topologies spécifiques. Dans cette thèse, nous contribuons des résultats concernant le problème du calcul et l'estimation de la DCR. Nous étudions la complexité de calcul de cas particuliers, paramétré par le nombre de terminaux, nœuds et le paramètre d. Nous passons en revue des méthodes pour le calcul exact et étudions des topologies particulières pour lesquelles le calcul de la DCR a une complexité polynomiale. Nous introduisons des résultats de base sur le comportement asymptotique de la DCR lorsque le réseau se développe comme un graphe aléatoire. Nous discutons sur l'impact de la contrainte de diamètre dans l'utilisation des techniques de Monte Carlo, et adaptons et testons une famille de méthodes basées sur le conditionnement de l'espace d'échantillonnage en utilisant des structures nommées d-pathsets et d-cutsets. Nous définissons une famille de mesures de performabilité qui généralise la DCR, développons une méthode de Monte Carlo pour l'estimer, et présentons des résultats expérimentaux sur la performance de ces techniques Monte Carlo par rapport é l'approche naïve. Finalement, nous proposons une nouvelle technique qui combine la simulation Monte Carlo et l'interpolation polynomiale pour les mesures de fiabilité.

Thèse (M.Sc.)--Université Laval, 2007. / Bibliogr.: f. [110]-113. Publié aussi en version électronique dans la Collection Mémoires et thèses électroniques.

Th. doct.--Morphol. math.--Paris--Ecole nationale supérieure des mines, 1990. / Bibliogr. p. 279-287. Résumé en anglais.

Th. doct.--Informatique--Nancy 1, 1996. / Bibliogr. p. 169-170. Notes bibliogr. Résumé en français et en anglais. 1997 d'après la déclaration de dépôt légal.

En informatique comme dans de multiples autres domaines, les graphes peuvent être trouvés partout. Ils sont utilisés pour représenter des données dans des domaines allant de la chimie à l'architecture, en tant que structures abstraites ou que modèles des données et de leurs évolutions. Dans tous ces domaines, il est prévisible que les graphes évoluent au cours du temps suite à des réactions chimiques, une mise à jour des connaissance ou l'exécution d'un programme. Être capable de traiter ces transformations est une tâche particulièrement importante et difficile. Dans ce travail, notre objectif est d'étudier la vérification de telles transformations de graphes, c'est à dire comment prouver qu'une transformation de graphes est correcte. La correction d'une transformation est plus précisément définie comme la correction d'une spécification pour cette transformation contenant en plus une précondition et une postcondition. Nous avons décidé d'utiliser un calcul à la Hoare générant une plus faible précondition pour une postcondition et une transformation. Si cette plus faible précondition est impliquée par la précondition, la spécification est correcte. Nous avons choisi une approche plus algorithmique pour les transformation de graphes utilisant des actions atomiques. Nous définissons deux moyens de construire des transformations de graphes: en utilisant un langage impératif ou en utilisant des systèmes de règles de réécriture. Le principal ingrédient est la logique qui est choisie pour représenter la précondition, la postcondition et les possibles conditions internes. Pour que la logique puisse interagir avec le calcul, nous demandons que le problème de décision soit décidable, qu'elle soit fermée par substitutions et qu'elle soit capable d'exprimer l'existence ou l'absence d'un sous-graphe affecté par la transformation. Le résultat central de ce travail est l'identification et l'explication de ces conditions. / In computer science as well as multiple other fields, graphs have become ubiquitous. They are used to represent data in domains ranging from chemistry to architecture, as abstract structures or as models of the data or its evolution. In all these domains, graphs are expected to evolve over time due to chemical reactions, update of the knowledge or programs. Being able to deal with such transformations is an extremely important and difficult task. In this work, our aim is to study the verification of such graph transformation, that is how to prove that a graph transformation is correct. Correctness of a graph transformation is more precisely defines as correctness of a specification for the transformation containing additionally a precondition and a postcondition. We decided to use a Hoare-like calculus generating the weakest precondition for a postcondition and a transformation. If this weakest precondition is implied by the actual precondition, the specification is correct. We chose a more algorithmic approach to graph transformation by using atomic actions.We chose to define two ways to build graph transformations: using an imperative programming language and using rule-base rewriting systems. The main ingredient of the verification of graph transformation is the logic that is chosen to represent the precondition, the postcondition and the possible conditions internal to the transformation. So that the logic can interact with the calculus, we require that the decision problem be decidable, that the logic be closed under the substitutions introduced by the Hoare-like calculus and that it has to be able to express the existence and absence of a match for the transformation. The core result of this work is the identification and explanation of these conditions.

Dans cette thèse, nous étudions la complexité paramétrée de problèmes combinatoires dans les graphes. Plus précisément, nous présentons une multitude d’algorithmes de programmation dynamique ainsi que des réductions montrant que certains de ces algorithmes sont optimaux. Nous nous intéressons principalement à la treewidth, un paramètre de graphes pouvant être vu comme une mesure de distance entre la structure d’un graphe et la structure topologique d’un arbre. Certains de nos algorithmes sont aussi paramétrés par la taille de la solution demandée et le degré maximum du graphe donné en entrée. Nous avons obtenu un certain nombre de résultats dont certains d’entre eux sont listés ci-dessous. Nous présentons un encadrement du nombre de graphes étiquetés de treewidth bornée. Nous étendons le domaine d’application de la théorie de la bidimensionalité par contraction au delà des graphes ne contenant pas de graphe apex en tant que mineur. Nous montrons aussi que la technique des structures de Catalan, outil améliorant l’efficacité des algorithmes résolvant des problèmes de connexité lorsque le graphe d’entrée est creux, ne peut être appliquée à la totalité des problèmes de connectivité, même si l’on ne considère, parmi les graphes creux, que les graphes planaires. Nous considérons le problème F-M-Deletion qui, étant donné une collection de graphes F, un graphe G et un entier k, demande s’il est possible de retirer au plus k sommets de G de telle sorte que le graphe restant ne contienne aucun graphe de F en tant que mineur. Nous considérons aussi la version topologique de ce problème, à savoir F-TM-Deletion. Ces deux problèmes généralisent des problèmes de modification de graphes bien connus tels que Vertex Cover, Feedback Vertex Set et Vertex Planarization. En fonction de la collection de graphes F, nous utilisons différentes techniques de programmation dynamique pour résoudre F-M-Deletion et F-TM-Deletion paramétrés par la treewidth. Nous utilisons des techniques standards, la structure des graphes frontières et l’approche basée sur le rang. En dernier lieu, nous appliquons ces techniques algorithmiques à deux problèmes issus du réseau de communications, à savoir une variation du problème classique de domination et un problème consistant à trouver un arbre couvrant possédant certaines propriétés, et un problème issu de la bioinformatique consistant à construire un arbre contenant en tant que mineur (topologique) un ensemble d’arbres donnés correspondant à des relations d’évolution entre ensembles d’espèces. / In this thesis, we study the Parameterized Complexity of combinatorial problems on graphs. More precisely, we present a multitude of dynamic programming algorithms together with reductions showing optimality for some of them. We mostly deal with the graph parameter of treewidth, which can be seen as a measure of how close a graph is to the topological structure of a tree. We also parameterize some of our algorithms by two other parameters, namely the size of a requested solution and the maximum degree of the input graph. We obtain a number of results, some of which are listed in the following. We estimate the number of labeled graphs of bounded treewidth. We extend the horizon of applicability of the theory of contraction Bidimensionality further than apex-minor free graphs, leading to a wider applicability of the design of subexponential dynamic programming algorithms. We show that the Catalan structure technique, that is a tool used to improve algorithm efficiency for connectivity problems where the input graph is restricted to be sparse, cannot be applied to all planar connectivity problems. We consider the F-M-Deletion problem that, given a set of graphs F, a graph G, and an integer k, asks if we can remove at most k vertices from G such that the remaining graph does not contain any graph of F as a minor. We also consider the topological version of this problem, namely F-TM-Deletion. Both problems generalize some well-known vertex deletion problems, namely Vertex Cover, Feedback Vertex Set, and Vertex Planarization. Depending on the set F, we use distinct dynamic programming techniques to solve F-M-Deletion and F-TM-Deletion when parameterized by treewidth. Namely, we use standard techniques, the rank based approach, and the framework of boundaried graphs. Finally, we apply these techniques to two problems originating from Networks, namely a variation of the classical dominating set problem and a problem that consists in finding a spanning tree with specific properties, and to a problem from Bioinformatics, namely that of construcing a tree that contains as a minor (or topological minor) a set of given trees corresponding to the evolutionary relationships between sets of species.

No description available.

No description available.

Les décompositions de graphes, lorsqu’elles sont de petite largeur, sont souvent utilisées pour résoudre plus efficacement des problèmes étant difficiles dans le cas de graphes quelconques. Dans ce travail de thèse, nous nous intéressons aux limites liées à ces décompositions, et à la construction d’obstructions certifiant leur grande largeur. Dans une première partie, nous donnons un algorithme généralisant et unifiant la construction d’obstructions pour différentes largeurs de graphes, en temps XP lorsque paramétré par la largeur considérée. Nous obtenons en particulier le premier algorithme permettant de construire efficacement une obstruction à la largeur arborescente en temps O(ntw+4). La seconde partie de notre travail porte sur l’étude du problème ENSEMBLE [σ, ρ]-DOMINANT, une généralisation des problèmes de domination sur les graphes et caractérisée par deux ensembles d’entiers σ et ρ. Les diverses études de ce problème apparaissant dans la littérature concernent uniquement les cas ou le problème est FPT, lorsque paramétré par la largeur arborescente. Nous montrons que ce problème ne l’est pas toujours, et que pour certains cas d’ensembles σ et ρ, il devient W[1]-difficile lorsque paramétré par la largeur arborescente. Dans la dernière partie, nous étudions la complexité d’un nouveau problème de coloration appelé k-COLORATION ADDITIVE, combinant théorie des graphes et théorie des nombres. Nous montrons que ce nouveau problème est NP-complet pour tout k ≥ 4 fixé, tandis qu’il peut être résolu en temps polynomial sur les arbres pour k quelconque et non fixé. / Graphs decompositions of small width are usually used to solve efficiently problems which are difficult in general. In this thesis, we focus on some limits of these decompositions, and the construction of some obstructions certifying a large width. First, we give a generic algorithm unifying obstructions’ construction for several graph widths, in XP time when parameterized by the considered width. In particular, it gives the first algorithm computing efficiently an obstruction to tree-width in time O(ntw+4). Secondly, we study the parameterized complexity of [σ, ρ]-DOMINATING SET, a generalization of some domination problems characterized by two sets of integers σ and ρ. All known studies focused only on cases where this problem is FPT when parameterized by tree-width. In this work, we show that there are some cases where the problem is no longer FPT, and become W[1]-hard instead. Finally, we study the computational complexity of a new coloration problem, named k-ADDITIVE COLORING, which combines both graph theory and number theory. We show that this new problem is NP-complete for any fixed number k ≥ 4, while it can be solved in polynomial time on trees for any k.