Les jeux des gendarmes et du voleur dans les graphes traitent de la<br />capture d'un voleur qui se déplace dans un réseau par une équipe de<br />gendarmes. Ces jeux trouvent leurs motivations en informatique<br />fondamentale, notamment dans le cadre de la théorie de la complexité<br />et dans celui de la théorie des mineurs de graphes. Ces jeux ont<br />également des applications en intelligence artificielle et en<br />robotique. Quel que soit le contexte, le nombre de gendarmes utilisés<br />a un coût et doit être minimisé. Dans cette thèse, nous étudions<br />diverses contraintes auxquelles les stratégies de capture sont<br />soumises, ainsi que le coût de ces contraintes en terme de nombre de<br />gendarmes. Nous distinguons principalement trois cadres d'étude.<br /><br />Dans la première partie de cette thèse, nous définissons une variante<br />de stratégie de capture qui établit un pont entre la largeur<br />arborescente et la largeur linéaire des graphes. En particulier, nous<br />prouvons la monotonie de cette variante générale et donnons un<br />algorithme exponentiel exact pour calculer de telles stratégies.<br /><br />Dans la seconde partie de cette thèse, nous nous intéressons aux<br />stratégies dites connexes qui doivent assurer que la partie propre du<br />réseau est constamment connexe. Nous prouvons plusieurs bornes<br />supérieures et inférieures du coût de cette contrainte en terme de<br />nombre de gendarmes. Nous étudions également la propriété de monotonie<br />des stratégies de capture connexe.<br /><br />Dans la troisième partie de cette thèse, nous étudions les stratégies<br />de capture dans un contexte décentralisé. Nous proposons plusieurs<br />algorithmes décentralisés qui permettent aux gendarmes de calculer<br />eux-mêmes la stratégie qu'ils doivent réaliser.

Dans cette thèse, nous étudions les décompositions arborescentes qui satisfont certaines contraintes supplémentaires et nous proposons des algorithmes pour les calculer dans certaines classes de graphes. Finalement, nous résolvons des problèmes liés au routage en utilisant ces décompositions ainsi que des propriétés structurelles des graphes. Cette thèse est divisée en deux parties. Dans la première partie, nous étudions les décompositions arborescentes satisfaisant des propriétés spécifiques. Dans le Chapitre 2, nous étudions les décompositions de taille minimum, c’est-À-Dire avec un nombre minimum de sacs. Etant donné une entier k 4 fixé, nous prouvons que le problème de calculer une décomposition arborescente de largeur au plus k et de taille minimum est NP-Complet dans les graphes de largeur arborescente au plus 4. Nous décrivons ensuite des algorithmes qui calculent des décompositions de taille minimum dans certaines classes de graphes de largeur arborescente au plus 3. Ces résultats ont été présentés au workshop international ICGT 2014. Dans le Chapitre 3, nous étudions la cordalité des graphes et nous introduisons la notion de k-Good décomposition arborescente. Nous étudions tout d’abord les jeux de Gendarmes et Voleur dans les graphes sans long cycle induit. Notre résultat principal est un algorithme polynomial qui, étant donné un graphe G, soit trouve un cycle induit de longueur au moins k+1, ou calcule une k-Good décomposition de G. Ces résultats ont été publiés à la conférence internationale ICALP’12 et dans la revue internationale Algorithmica. Dans la seconde partie de la thèse, nous nous concentrons sur des problèmes de routage. / A tree decomposition of a graph is a way to represent it as a tree by preserving some connectivity properties of the initial graph. Tree decompositions have been widely studied for their algorithmic applications, in particular using dynamic programming approach. In this thesis, we study tree decompositions satisfying various constraints and design algorithms to compute them in some graph classes. We then use tree decompositions or specific graph properties to solve several problems related to routing. The thesis is divided into two parts. In the first part, we study tree decompositions satisfying some properties. In Chapter 2, we investigate minimum size tree decompositions, i.e., with minimum number of bags. Given a fixed k 4, we prove it is NP-Hard to compute a minimum size decomposition with width at most k in the class of graphs with treewidth at least 4. We design polynomial time algorithms to compute minimum size tree decompositions in some classes of graphs with treewidth at most 3 (including trees). Part of these results will be presented in ICGT 2014. In Chapter 3, we study the chordality (longest induced cycle) of graphs and introduce the notion of good tree decomposition (where each bag must satisfy some particular structure). Precisely, we study the Cops and Robber games in graphs with no long induced cycles. Our main result is the design of a polynomial-Time algorithm that either returns an induced cycle of length at least k+1 of a graph G or compute a k-Good tree decomposition of G. These results have been published in ICALP 2012 and Algorithmica. In the second part of the thesis, we focus on routing problems.

Dans cette thèse, nous nous intéressons à diagnostiquer des systèmes intrinsèquement distribués (comme les systèmes pairs-à-pairs) où chaque pair n'a accès qu'à une sous partie de la description d'un système global. De plus, en raison d'une politique d'accès trop restrictive, il sera pourra qu'aucun pair ne puisse expliquer le comportement du système global. Dans ce contexte, le challenge du diagnostic distribué est le suivant: expliquer le comportement global d'un système distribué par un ensemble de pairs ayant chacun une vision limitée, tout comme l'aurait fait un unique pair diagnostiqueur ayant, lui, une vision globale du système.D'un point de vue théorique, nous montrons que tout nouveau système, logiquement équivalent au système pair-à-pairs initialement observé, garantit que tout diagnostic local d'un pair pourra être prolongé par un diagnostic global (dans ce cas, le nouveau système est dit correct pour le diagnostic distribué).Nous montrons aussi que si ce nouveau système est structuré (c-à-d: il contient un arbre couvrant pour lequel tous les pairs contenant une même variable forme un graphe connecté) alors il garantit que tout diagnostic global pourra être retrouvé à travers un ensemble de diagnostics locaux des pairs (dans ce cas le nouveau système est dit complet pour le diagnostic distribué).Dans un souci de représentation succincte et afin de respecter la politique de confidentialité du vocabulaire de chacun des pairs, nous présentons un nouvel algorithme Token Elimination (TE), qui décompose le système de pairs initial vers un système structuré.Nous montrons expérimentalement que TE produit des décompositions de meilleurs qualité (c-à-d: de plus petites largeurs arborescentes) que les méthodes envisagées dans un contexte distribué. À partir du système structuré construit par TE, nous transformons chaque description locale en une Forme Normale Disjonctive (FND) globalement cohérente.Nous montrons que ce dernier système garantit effectivement un diagnostic distribué correct et complet. En plus, nous exhibons un algorithme capable de vérifier efficacement que tout diagnostic local fait partie d'un diagnostic minimal global, faisant du système structuré de FNDs un système compilé pour le diagnostic distribué.

L'alignement de macromolécules biologiques comme les protéines, l'ADN ou encore l'ARN est une problématique biologique et bio-informatique qui a pour but de révéler une partie des mystères du fonctionnement des cellules, constituants des êtres vivants. Les ARN non-codant sont des macromolécules intervenant dans le métabolisme de tout être vivant et les deux problématiques majeurs les concernant sont: la prédiction de leur structure pour mieux comprendre leur fonctionnement et leur détection dans des bases de données ou des génomes. L'une des approches: l'alignement structure-séquence d'ARN, répond à ces deux problématiques. Le problème d'alignement structure-séquence consiste à aligner une structure connue d'un premier ARN avec la séquence d'un deuxième ARN.La structure est représentée sous la forme d'un graphe ou de façon équivalente sous la forme d'une séquence arc-annotées et la séquence représente la suite des nucléotides de l'ARN.Pour résoudre ce problème, nous cherchons à optimiser l'alignement selon une fonction de coût. C'est donc un problème d'optimisation, qui malheureusement se révèle NP-Difficile.En conséquence différents travaux définissent des classes d'instances réduites pour lesquelles ils proposent des algorithmes spécifiques mais à complexités polynomiales.Les travaux de ma thèse unifient et la généralisent les approches précédentes par la construction d'un algorithme à complexité paramétrée non spécifique à une classe d'instances. En utilisant cet algorithme, il est possible de résoudre le problème d'alignement structure-séquence pour toutes les instances possibles, et aussi efficacement que les précédentes approches sur leur domaine de résolution respectif. Cet algorithme utilise une technique empruntée à la théorie des graphes: la décomposition arborescente, c'est-à-dire qu'il transforme la structure donnée en une décomposition arborescente et c'est ensuite cette décomposition qui est alignée avec la séquence donnée. L'alignement entre une décomposition arborescente et une séquence se fait par programmation dynamique.Sa mise en place a nécessité une reformulation du problème ainsi qu'une modification importante de l'utilisation classique de la programmation dynamique pour les décompositions arborescentes. Au final, cela conduit à un algorithme paramétré dont le paramètre est entièrement lié à la décomposition arborescente. La construction des décompositions arborescentes pour lesquelles l'alignement s'effectuera plus le efficacement possible est malheureusement un problème lui aussi NP-Difficile. Néanmoins, nous avons créé une heuristique de construction de décompositions adaptée aux structures d'ARN.Nous avons alors défini des nouvelles classes de structures pour lesquelles notre algorithme (décomposition et alignement) possède une faible complexité. Ces classes incluent notamment toutes les autres classes précédemment définies et la complexité de notre algorithme est au moins aussi faible que celles des algorithmes spécifiques sur leurs classes de structures respectives. Ces classes de structures représentent la majorité des structures connues et contiennent de nombreux éléments importants jusqu'alors non pris en compte (tel que les motifs tertiaires d'ARN). Le problème de l'alignement structure-séquence tente de répondre aux problématiques de prédictions de structures et de recherche d'ARN. Néanmoins, la qualité des résultats obtenus par sa résolution dépendent de la fonction de coût utilisée. Durant ma thèse j'ai commencé la mise place de la construction par apprentissage d'une nouvelle fonction de coût, adaptée aux nouvelles classes de structures que nous avons défini. Enfin de par la nature de l'algorithme, le travail réalisé permet des améliorations non négligeables, en terme de qualité des résultats et de rapidité de calcul comme la recherche de solution sous-optimales ou l'utilisation de l'algorithme au sein d'heuristiques dérivées d'heuristiques classiques.

Dans cette thèse, nous nous intéressons à diagnostiquer des systèmes intrinsèquement distribués (comme les systèmes pairs-à-pairs) où chaque pair n'a accès qu'à une sous partie de la description d'un système global. De plus, en raison d'une politique d'accès trop restrictive, il sera pourra qu'aucun pair ne puisse expliquer le comportement du système global. Dans ce contexte, le challenge du diagnostic distribué est le suivant: expliquer le comportement global d'un système distribué par un ensemble de pairs ayant chacun une vision limitée, tout comme l'aurait fait un unique pair diagnostiqueur ayant, lui, une vision globale du système.D'un point de vue théorique, nous montrons que tout nouveau système, logiquement équivalent au système pair-à-pairs initialement observé, garantit que tout diagnostic local d'un pair pourra être prolongé par un diagnostic global (dans ce cas, le nouveau système est dit correct pour le diagnostic distribué).Nous montrons aussi que si ce nouveau système est structuré (c-à-d: il contient un arbre couvrant pour lequel tous les pairs contenant une même variable forme un graphe connecté) alors il garantit que tout diagnostic global pourra être retrouvé à travers un ensemble de diagnostics locaux des pairs (dans ce cas le nouveau système est dit complet pour le diagnostic distribué).Dans un souci de représentation succincte et afin de respecter la politique de confidentialité du vocabulaire de chacun des pairs, nous présentons un nouvel algorithme Token Elimination (TE), qui décompose le système de pairs initial vers un système structuré.Nous montrons expérimentalement que TE produit des décompositions de meilleurs qualité (c-à-d: de plus petites largeurs arborescentes) que les méthodes envisagées dans un contexte distribué. À partir du système structuré construit par TE, nous transformons chaque description locale en une Forme Normale Disjonctive (FND) globalement cohérente.Nous montrons que ce dernier système garantit effectivement un diagnostic distribué correct et complet. En plus, nous exhibons un algorithme capable de vérifier efficacement que tout diagnostic local fait partie d'un diagnostic minimal global, faisant du système structuré de FNDs un système compilé pour le diagnostic distribué. / In this thesis, we focus on diagnosing inherently distributed systems such as peer-to-peer, where each peer has access to only a sub-part of the description of an overall system.In addition, due to a too restrictive access control policy, it can be possible that neither peer nor supervisor is able to explain the behaviour of the overall system.The goal of distributed diagnosis is to explain the behaviour of a distributed system by a set of peers (each having a limited local view) as a single diagnosis engine having a global view of the overall system.First, we show that any new system logically equivalent to the initially observed peer-to-peer setting ensures that all diagnosis of a peer may be extended to a global diagnosis (in this case the new system ensures correctness of the distributed diagnosis).Moreover, we prove that if the new system is structured (i.e.it contains a spanning tree for which all peers containing the same variable form a connected graph) then it ensures that any global diagnosis can be found through a set of local diagnoses (in this case the new system ensures the completeness of the distributed diagnoses).For a succinct representation and in order to comply with the privacy policy of the vocabulary of each peer, we present a new algorithm Token Elimination (TE), which decomposes the original peer system to a structured one.We experimentally show that TE produces better quality decompositions (i.e. smaller tree widths) than proposed methods in a distributed context.From the structured system built by TE, we transform each local description into globally consistent DNF.We demonstrate that the latter system is correct and complete for the distributed diagnosis.Finally, we present an algorithm that can effectively check that any local diagnosis is part of a global minimal diagnosis, turning the structured system of DNFs into a compiled system for distributed diagnosis.

L'alignement de macromolécules biologiques comme les protéines, l'ADN ou encore l'ARN est une problématique biologique et bio-informatique qui a pour but de révéler une partie des mystères du fonctionnement des cellules, constituants des êtres vivants. Les ARN non-codant sont des macromolécules intervenant dans le métabolisme de tout être vivant et les deux problématiques majeurs les concernant sont: la prédiction de leur structure pour mieux comprendre leur fonctionnement et leur détection dans des bases de données ou des génomes. L'une des approches: l'alignement structure-séquence d'ARN, répond à ces deux problématiques. Le problème d'alignement structure-séquence consiste à aligner une structure connue d'un premier ARN avec la séquence d'un deuxième ARN.La structure est représentée sous la forme d'un graphe ou de façon équivalente sous la forme d'une séquence arc-annotées et la séquence représente la suite des nucléotides de l'ARN.Pour résoudre ce problème, nous cherchons à optimiser l'alignement selon une fonction de coût. C'est donc un problème d'optimisation, qui malheureusement se révèle NP-Difficile.En conséquence différents travaux définissent des classes d'instances réduites pour lesquelles ils proposent des algorithmes spécifiques mais à complexités polynomiales.Les travaux de ma thèse unifient et la généralisent les approches précédentes par la construction d'un algorithme à complexité paramétrée non spécifique à une classe d'instances. En utilisant cet algorithme, il est possible de résoudre le problème d'alignement structure-séquence pour toutes les instances possibles, et aussi efficacement que les précédentes approches sur leur domaine de résolution respectif. Cet algorithme utilise une technique empruntée à la théorie des graphes: la décomposition arborescente, c'est-à-dire qu'il transforme la structure donnée en une décomposition arborescente et c'est ensuite cette décomposition qui est alignée avec la séquence donnée. L'alignement entre une décomposition arborescente et une séquence se fait par programmation dynamique.Sa mise en place a nécessité une reformulation du problème ainsi qu'une modification importante de l'utilisation classique de la programmation dynamique pour les décompositions arborescentes. Au final, cela conduit à un algorithme paramétré dont le paramètre est entièrement lié à la décomposition arborescente. La construction des décompositions arborescentes pour lesquelles l'alignement s'effectuera plus le efficacement possible est malheureusement un problème lui aussi NP-Difficile. Néanmoins, nous avons créé une heuristique de construction de décompositions adaptée aux structures d'ARN.Nous avons alors défini des nouvelles classes de structures pour lesquelles notre algorithme (décomposition et alignement) possède une faible complexité. Ces classes incluent notamment toutes les autres classes précédemment définies et la complexité de notre algorithme est au moins aussi faible que celles des algorithmes spécifiques sur leurs classes de structures respectives. Ces classes de structures représentent la majorité des structures connues et contiennent de nombreux éléments importants jusqu'alors non pris en compte (tel que les motifs tertiaires d'ARN). Le problème de l'alignement structure-séquence tente de répondre aux problématiques de prédictions de structures et de recherche d'ARN. Néanmoins, la qualité des résultats obtenus par sa résolution dépendent de la fonction de coût utilisée. Durant ma thèse j'ai commencé la mise place de la construction par apprentissage d'une nouvelle fonction de coût, adaptée aux nouvelles classes de structures que nous avons défini. Enfin de par la nature de l'algorithme, le travail réalisé permet des améliorations non négligeables, en terme de qualité des résultats et de rapidité de calcul comme la recherche de solution sous-optimales ou l'utilisation de l'algorithme au sein d'heuristiques dérivées d'heuristiques classiques. / The alignment of biological macromolecules such as proteins, DNA or RNA is a biological and bio-informatics problematic which aims to reveal some of the mysteries of how cells works. The non-coding RNA are involved in the metabolism of all living beings. The two major issues concerning them are: the prediction of their structure to better understand their function and their detection in databases or genomes. One approach, the structure-sequence alignment of RNA, addresses these two issues. The work done during my thesis provides some constructive elements on this problem and led me to call the graph algorithmic for its resolution. The alignment problem is to align a structure of a first RNA with the sequence of a second RNA. The structure on the first RNA is represented as a graph or equivalently as an arc-annotated sequence and the sequence represents the nucleotide sequence of the second RNA.To solve this problem, we aim to compute a minimal cost alignment, according to a given cost function. So, this is an optimization problem, which turns out to be NP-hard.Accordingly, different works define several reduced structure classes for which they propose specific algorithms but with polynomial complexity. The work of my thesis unifies and generalizes previous approaches by the construction of a unique (not class specific) parameterized algorithm. Using this algorithm, it is possible to solve the problem of structure-sequence alignment for all possible instances, and as effectively as previous approaches in their respective field of resolution.This algorithm uses a technique from graph theory: the tree decomposition, that is to say, it transforms the given structure into a tree-decomposition and the decomposition is then aligned with the sequence. The alignment between a tree-decomposition and a sequence is done by dynamic programming. Its implementation requires a reformulation of the problem as well as a substantial modifications to the conventional use of dynamic programming for tree decompositions. This leads to an algorithm whose parameter is entirely related to the tree-decomposition.The construction of tree decompositions for which the alignment is the most effective is unfortunately a NP-Hard problem. Nevertheless, we have developed a heuristic construction of decompositions adapted to RNA structures. We then defined new structure classes which extend existing ones without degrading the complexity of the alignment but which can represent the majority of known structures containing many important elements that had not be taken into account previously (such as RNA tertiary motifs).The sequence-structure alignment problem attempts to answer the problem of prediction of structures and RNA research. However, the quality of the results obtained by its resolution depends on the cost function. During my PhD I started to define new cost functions adapted to the new structure classes by a machine learning approach. Finally, the work allows significant improvements in terms of quality of results and computation. For example the approach directly allows the search for sub-optimal solutions or its use within heuristics derived from traditional heuristic methods.

L’importance des problèmes CSP, WCSP et #CSP est reflétée par la part considérable des travaux, théoriques et pratiques, dont ils font l’objet en intelligence artificielle et bien au-delà. Leur difficulté est telle qu’ils appartiennent respectivement aux classes NP-complet, NP-difficile et #P-complet. Aussi, les méthodes qui permettent de résoudre efficacement leurs instances ont une complexité en temps exponentielle. Les travaux de recherche de cette thèse se focalisent sur les méthodes de résolution exploitant la notion de décomposition arborescente. Ces méthodes ont suscité un vif intérêt de la part de la communauté scientifique du fait qu’elles soient capables de résoudre en temps polynomial certaines classes d’instances. Cependant, en pratique, elles n’ont pas encore montré toute leur efficacité vu la qualité de la décomposition employée ne prenant en compte qu’un critère purement structurel, sa largeur. Premièrement, nous proposons un nouveau cadre général de calcul de décompositions qui a la vertu de calculer des décompositions qui capturent des paramètres plus pertinents à l’égard de la résolution que la seule largeur de la décomposition. Ensuite, nous proposons une exploitation dynamique de la décomposition pendant la résolution pour les problèmes (W)CSP. Le changement de la décomposition pendant la résolution vise à adapter la décomposition selon la nature de l’instance. Finalement, nous proposons un nouvel algorithme de comptage qui exploite la décomposition d’une façon différente de celle des méthodes standards afin d’éviter des calculs inutiles.L’ensemble des contributions ont été évaluées et validées expérimentalement. / The importance of CSP, WCSP and #CSP problems is reflected by the considerableamount of theoretical and practical work of which they are subject in artificial intelligenceand far beyond. Their difficulty is such that they belong respectively to the NP-complete,NP-hard and #P-complete classes. Hence, the methods that are able to solve efficientlytheir instances have a complexity in exponential time. The research works of this thesisfocus on the solving methods exploiting the notion of tree-decomposition. These methodshave aroused a keen interest from the scientific community because they are able to solvesome classes of instances in polynomial time. Nevertheless, in practice, they have notshown yet their full efficiency given the quality of the used decomposition that takes onlyinto account a purely structural criterion, its width. First, we propose a new generic framework for computing decompositions which has the virtue of computing decompositionsthat capture more relevant parameters in the context of solving than the width. Then,we propose a dynamic exploitation of the decomposition during the solving for (W)CSPproblems. The modification of the decomposition during the solving aims to adapt the decomposition to the nature of the instance. Finally, we propose a new counting algorithmthat exploits the decomposition in a different way than standard methods in order toavoid unnecessary computations. All the contributions have been evaluated and validatedexperimentally.

Savoir comment transmettre une information est fondamental dans un réseau. Il est essentiel que chaque entité du réseau soit capable de décider localement, avec sa vue du réseau, du chemin par lequel l'information doit passer. Ainsi, il est souvent utile d'étudier la topologie du réseau, modélisée par un graphe, pour répondre à ces exigences. Nous nous intéressons dans un premier temps, à la décomposition arborescente des graphes planaires. En effet, comme dans beaucoup de problèmes de graphes, l'étude de la topologie des graphes nous conduit à procéder à une décomposition du graphe afin d'exploiter les propriétés structurelles qui en découlent. En suite, nous nous sommes aussi intéressés à la structure des graphes qui excluent un mineur H, en particulier le graphe K_{2,r}. Ces travaux nous ont permis d'améliorer les bornes actuelles connues sur la largeur arborescente de ces graphes. Dans la dernière partie, nous abordons le problème du routage compact. Nous nous sommes intéressés aux schémas de routage de plus courts chemins utilisant des adresses, des tables de routage de tailles optimales de O(log n) bits, où n est le nombre de sommets du graphe. Nous proposons un tel schéma de routage pour une famille de graphes valués contenant les arbres et les graphes planaire-extérieurs. / In a network, it is crucial to know how to construct an efficent routing scheme. It is fundamental for each entity with its local knowledge of the network, to be able to decide on which link to forward messages. Thus, it is important to sutdy the underlying network topology in order to design routing schemes. In the first part of this thesis, we construct a new tree-decomposition for planar graphs. In fact, as in many graph problems, the study of the graph structure leads to do a tree-decomposition for exploiting structural propertys of the graphs. In second part, we studied the structure of H-minor free graphs, in particular whenever H = K_{2,r}. Our results improve upon previous known bounds about the tree-width of K_{2,r}-minor free graphs. At last, we treat the problème of compact routing scheme. More precisely, we are interested in shortest-path routing schemes that use O(\log n) bits for addresses, headers and routing tables, where n is the number of vertices in the graph. We propose such a routing scheme for a large family of weighted graphs including outerplanar graphs.

Nous étudions dans cette thèse des problèmes d’optimisation avec applications dans les réseaux optiques. Les problèmes étudiés sont liés à la tolérance aux pannes et à l’utilisation efficace des ressources. Les résultats obtenus portent principalement sur la complexité de calcul de ces problèmes. La première partie de cette thèse est consacrée aux problèmes de trouver des chemins et des chemins disjoints. La recherche d’un chemin est essentielle dans tout type de réseaux afin d’y établir des connexions et la recherche de chemins disjoints est souvent utilisée pour garantir un certain niveau de protection contre les pannes dans les réseaux. Nous étudions ces problèmes dans des contextes différents. Nous traitons d’abord les problèmes de trouver un chemin et des chemins lien ou nœud- disjoints dans des réseaux avec nœuds asymétriques, c’est-à-dire des nœuds avec restrictions sur leur connectivité interne. Ensuite, nous considérons les réseaux avec des groupes de liens partageant un risque (SRLG) en étoile : ensembles de liens qui peuvent tomber en panne en même temps suite à un événement local. Dans ce type de réseaux, nous examinons le problème de recherche des chemins SRLG-disjoints. La deuxième partie de cette thèse est consacrée au problème de routage et d’allocation de spectre (RSA) dans les réseaux optiques élastiques (EONs). Les EONs sont proposés comme la nouvelle génération des réseaux optiques et ils visent une utilisation plus efficace et flexible des ressources optiques. Le problème RSA est central dans les EONs. Il concerne l’allocation de ressources aux requêtes sous plusieurs contraintes. / We study in this thesis optimization problems with application in optical networks. The problems we consider are related to fault-tolerance and efficient resource allocation and the results we obtain are mainly related to the computational complexity of these problems. The first part of this thesis is devoted to finding paths and disjoint paths. Finding a path is crucial in all types of networks in order to set up connections and finding disjoint paths is a common approach used to provide some degree of protection against failures in networks. We study these problems under different settings. We first focus on finding paths and node or link-disjoint paths in networks with asymmetric nodes, which are nodes with restrictions on their internal connectivity. Afterwards, we consider networks with star Shared Risk Link Groups (SRLGs) which are groups of links that might fail simultaneously due to a localized event. In these networks, we investigate the problem of finding SRLG-disjoint paths. The second part of this thesis focuses on the problem of Routing and Spectrum Assignment (RSA) in Elastic Optical Networks (EONs). EONs are proposed as the new generation of optical networks and they aim at an efficient and flexible use of the optical resources. RSA is the key problem in EONs and it deals with allocating resources to requests under multiple constraints. We first study the static version of RSA in tree networks. Afterwards, we examine a dynamic version of RSA in which a non-disruptive spectrum defragmentation technique is used. Finally, we present in the appendix another problem that has been studied during this thesis.

Les problèmes d’optimisation combinatoire sont devenus la cible de nombreuses recherches scientifiques pour leur importance dans la résolution de problèmes académiques et de problèmes réels rencontrés dans le domaine de l’ingénierie et dans l’industrie. La résolution de ces problèmes par des méthodes exactes ne peut être envisagée à cause des délais de traitement souvent exorbitants que nécessiteraient ces méthodes pour atteindre la (les) solution(s) optimale(s). Dans cette thèse, nous nous sommes intéressés au contexte algorithmique de résolution des problèmes combinatoires, et au contexte de modélisation de ces problèmes. Au niveau algorithmique, nous avons appréhendé les méthodes hybrides qui excellent par leur capacité à faire coopérer les méthodes exactes et les méthodes approchées afin de produire rapidement des solutions. Au niveau modélisation, nous avons travaillé sur la spécification et la résolution exacte des problématiques complexes de fouille des ensembles de motifs en étudiant tout particulièrement le passage à l’échelle sur des bases de données de grande taille. D'une part, nous avons proposé une première parallélisation de l'algorithme DGVNS, appelée CPDGVNS, qui explore en parallèle les différents clusters fournis par la décomposition arborescente en partageant la meilleure solution trouvée sur un modèle maître-travailleur. Deux autres stratégies, appelées RADGVNS et RSDGVNS, ont été proposées qui améliorent la fréquence d'échange des solutions intermédiaires entre les différents processus. Les expérimentations effectuées sur des problèmes combinatoires difficiles montrent l'adéquation et l'efficacité de nos méthodes parallèles. D'autre part, nous avons proposé une approche hybride combinant à la fois les techniques de programmation linéaire en nombres entiers (PLNE) et la fouille de motifs. Notre approche est complète et tire profit du cadre général de la PLNE (en procurant un haut niveau de flexibilité et d’expressivité) et des heuristiques spécialisées pour l’exploration et l’extraction de données (pour améliorer les temps de calcul). Outre le cadre général de l’extraction des ensembles de motifs, nous avons étudié plus particulièrement deux problèmes : le clustering conceptuel et le problème de tuilage (tiling). Les expérimentations menées ont montré l’apport de notre proposition par rapport aux approches à base de contraintes et aux heuristiques spécialisées. / Combinatorial optimization problems have become the target of many scientific researches for their importance in solving academic problems and real problems encountered in the field of engineering and industry. Solving these problems by exact methods is often intractable because of the exorbitant time processing that these methods would require to reach the optimal solution(s). In this thesis, we were interested in the algorithmic context of solving combinatorial problems, and the modeling context of these problems. At the algorithmic level, we have explored the hybrid methods which excel in their ability to cooperate exact methods and approximate methods in order to produce rapidly solutions of best quality. At the modeling level, we worked on the specification and the exact resolution of complex problems in pattern set mining, in particular, by studying scaling issues in large databases. On the one hand, we proposed a first parallelization of the DGVNS algorithm, called CPDGVNS, which explores in parallel the different clusters of the tree decomposition by sharing the best overall solution on a master-worker model. Two other strategies, called RADGVNS and RSDGVNS, have been proposed which improve the frequency of exchanging intermediate solutions between the different processes. Experiments carried out on difficult combinatorial problems show the effectiveness of our parallel methods. On the other hand, we proposed a hybrid approach combining techniques of both Integer Linear Programming (ILP) and pattern mining. Our approach is comprehensive and takes advantage of the general ILP framework (by providing a high level of flexibility and expressiveness) and specialized heuristics for data mining (to improve computing time). In addition to the general framework for the pattern set mining, two problems were studied: conceptual clustering and the tiling problem. The experiments carried out showed the contribution of our proposition in relation to constraint-based approaches and specialized heuristics.