<p>A major current challenge consists in extending formal methods in order to handle infinite-state systems. Infiniteness stems from the fact that the system operates on unbounded data structure such as stacks, queues, clocks, integers; as well as parameterization.</p><p>Systems with unbounded data structure are natural models for reasoning about communication protocols, concurrent programs, real-time systems, etc. While parameterized systems are more suitable if the system consists of an arbitrary number of identical processes which is the case for cache coherence protocols, distributed algorithms and so forth. </p><p>In this thesis, we consider model checking problems for certain fundamental classes of probabilistic infinite-state systems, as well as the verification of safety properties in parameterized systems. First, we consider probabilistic systems with unbounded data structures. In particular, we study probabilistic extensions of Lossy Channel Systems (PLCS), Vector addition Systems with States (PVASS) and Noisy Turing Machine (PNTM). We show how we can describe the semantics of such models by infinite-state Markov chains; and then define certain abstract properties, which allow model checking several qualitative and quantitative problems.</p><p>Then, we consider parameterized systems and provide a method which allows checking safety for several classes that differ in the topologies (linear or tree) and the semantics (atomic or non-atomic). The method is based on deriving an over-approximation which allows the use of a symbolic backward reachability scheme. For each class, the over-approximation we define guarantees monotonicity of the induced approximate transition system with respect to an appropriate order. This property is convenient in the sense that it preserves upward closedness when computing sets of predecessors.</p>

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.

O crescimento de cursos a distância oferecidos através da Web tem promovido uma grande reflexão sobre como acompanhar a evolução do aluno através deste curso. Em um curso presencial o docente possui meios mais seguros e concretos de observar e gerenciar o processo de aprendizagem já que os participantes estão em contato físico constante. Além disto, normalmente em um curso a distância, o aluno faz seu horário de estudo o que resulta num esforço ainda maior por parte do docente para acompanhar os alunos, pois terá que analisar momentos diferentes do curso ao mesmo tempo. A escolha de métodos para acompanhar a evolução do estudante em um curso on-line é sempre muito difícil de ser realizada e deve ser adequada as necessidades específicas do contexto estudado. Este trabalho apresenta além de conceitos pedagógicos relacionados a avaliação da aprendizagem presencial ambientes de gerenciamento de cursos a distância através da Web, sendo estes os alicerces das propostas realizadas nesta dissertação. As alternativas apresentadas, dentro de um ambiente interativo e através de testes objetivos, para realização de uma avaliação formativa tem como principal objetivo acompanhar o desenvolvimento do aluno no processo de aprendizagem. Como resultado da aplicação da metodologia para a construção de testes objetivos obteve-se uma ferramenta denominada AvaliaOnline, cuja finalidade é criar e aplicar questões do tipo múltipla-escolha em problemas que possuem valores numéricos e fórmulas ou algoritmos relacionados a sua resolução. A ferramenta permite que os valores numéricos que constituem o enunciado de uma questão sejam modificados toda vez que a mesma é apresentada, através do sorteio aleatório destes valores que serão utilizados para resolução do problema. Ou seja, a resposta correta da questão é gerada no momento da exibição da mesma. Além disto, é possível realizar uma dependência entre as questões que constituem o teste, construíndo uma árvore de questões onde o docente verifica o “caminho" percorrido pelo aluno durante o teste, dando subsídios para um acompanhamento mais detalhado sobre a resolução do estudante. Finalizando este trabalho, são apresentados exemplos práticos da utilização das ferramentas interativas para acompanhamento do aluno e da criação e aplicação de um teste desenvolvido através da ferramenta AvaliaOnline. / The increase in the number of distance courses in the Web has caused much reflection on how to track the student’s evolution through this course. In a live course it is possible for the teacher to observe and manage the learning process through safer and more concrete ways, once the participants are in constant physical contact. In addition, in a distance course the student usually determines how many hours he must study as well as when he will be studying. This will demand a bigger effort on the part of the teacher to track students once he may have to analyse different moments of the course at the same time. The choice of methods to track the stucent’s evolution in an on-line course is always very difficult to be made and it must be suitable to the specific needs of the studied context. This work presents pedagogical concepts related to tradicional learning evaluation as well as distance course managing environments through the Web, having these as the foundations of the proposals made in this dissertation. The alternatives presented, in an interactive environment and through objective tests, in order to have a formative evaluation, have as their main goal to track the development of the student in the learning process. As a result of the application of methodology for the construction of objective tests, a tool named AvaliaOnline was obtained, whose aim is to create and apply multiple-choice type questions to problems that have numerical values and formulas or algorithms related to their resolution. The tool allows the numerical values in the description of a question to be modified every time it is presented, through random sorting out of these values, which will be used for the resolution of the problem, that is, the correct answer of the question is produced at the moment of its exhibition. Besides, it is possible to establish dependence among the test questions, building a tree of questions where the teacher verifies the “path" followed by the student during the test, providing support for more detailed tracking on the resolution of the student. At the end of this work, practical examples are presented on the use of interactive tools to track the student and on the creation and application of a test developed through the tool AvaliaOnline. The experiments made show the potencial of such alternatives once they are used in a suitable context and under teacher tracking with.

Dans cette thèse, nous abordons des problèmes NP-difficiles à l'aide de techniques combinatoires, en se focalisant sur le domaine de la complexité paramétrée. Les principaux problèmes que nous considérons sont les problèmes de Multicoupe et d'Arbre Orienté Couvrant avec Beaucoup de Feuilles. La Multicoupe est une généralisation naturelle du très classique problème de coupe, et consiste à séparer un ensemble donné de paires de sommets en supprimant le moins d'arêtes possible dans un graphe. Le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles consiste à trouver un arbre couvrant avec le plus de feuilles possible dans un graphe dirigé. Les résultats principaux de cette thèse sont les suivants. Nous montrons que le problème de Multicoupe paramétré par la taille de la solution est FPT (soluble à paramètre fixé), c'est-à-dire que l'existence d'une multicoupe de taille $k$ dans un graphe à $n$ sommets peut être décidée en temps $f(k)*poly(n)$. Nous montrons que Multicoupe dans les arbres admet un noyau polynomial, c'est-à-dire est réductible aux instances de taille polynomiale en $k$. Nous donnons un algorithme en temps $O^*(3.72^k)$ pour le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles et le premier algorithme exponentiel exact non trivial (c'est-à-dire meilleur que $2^n$). Nous fournissons aussi un noyau quadratique et une approximation à facteur constant. Ces résultats algorithmiques sont basés sur des résultats combinatoires et des propriétés structurelles qui concernent, entre autres, les décompositions arborescentes, les mineurs, des règles de réduction et les $s-t$ numberings. Nous présentons des résultats combinatoires hors du domaine de la complexité paramétrée: une caractérisation des graphes de cercle Helly comme les graphes de cercle sans diamant induit, et une caractérisation partielle des classes de graphes 2-bel-ordonnées. / This thesis tackles NP-hard problems with combinatorial techniques, focusing on the framework of Fixed-Parameter Tractability. The main problems considered here are Multicut and Maximum Leaf Out-branching. Multicut is a natural generalisation of the cut problem, and consists in simultaneously separating prescribed pairs of vertices by removing as few edges as possible in a graph. Maximum Leaf Out-branching consists in finding a spanning directed tree with as many leaves as possible in a directed graph. The main results of this thesis are the following. We show that Multicut is FPT when parameterized by the solution size, i.e. deciding the existence of a multicut of size $k$ in a graph with $n$ vertices can be done in time $f(k)*poly(n)$. We show that Multicut In Trees admits a polynomial kernel, i.e. can be reduced to instances of size polynomial in $k$. We give an $O^*(3.72^k)$ algorithm for Maximum Leaf Out-branching and the first non-trivial (better than $2^n$) exact algorithm. We also provide a quadratic kernel and a constant factor approximation algorithm. These algorithmic results are based on combinatorial results and structural properties, involving tree decompositions, minors, reduction rules and $s-t$ numberings, among others. We present results obtained with combinatorial techniques outside the scope of parameterized complexity: a characterization of Helly circle graphs as the diamond-free circle graphs, and a partial characterisation of 2-well-quasi-ordered classes of graphs.

O crescimento de cursos a distância oferecidos através da Web tem promovido uma grande reflexão sobre como acompanhar a evolução do aluno através deste curso. Em um curso presencial o docente possui meios mais seguros e concretos de observar e gerenciar o processo de aprendizagem já que os participantes estão em contato físico constante. Além disto, normalmente em um curso a distância, o aluno faz seu horário de estudo o que resulta num esforço ainda maior por parte do docente para acompanhar os alunos, pois terá que analisar momentos diferentes do curso ao mesmo tempo. A escolha de métodos para acompanhar a evolução do estudante em um curso on-line é sempre muito difícil de ser realizada e deve ser adequada as necessidades específicas do contexto estudado. Este trabalho apresenta além de conceitos pedagógicos relacionados a avaliação da aprendizagem presencial ambientes de gerenciamento de cursos a distância através da Web, sendo estes os alicerces das propostas realizadas nesta dissertação. As alternativas apresentadas, dentro de um ambiente interativo e através de testes objetivos, para realização de uma avaliação formativa tem como principal objetivo acompanhar o desenvolvimento do aluno no processo de aprendizagem. Como resultado da aplicação da metodologia para a construção de testes objetivos obteve-se uma ferramenta denominada AvaliaOnline, cuja finalidade é criar e aplicar questões do tipo múltipla-escolha em problemas que possuem valores numéricos e fórmulas ou algoritmos relacionados a sua resolução. A ferramenta permite que os valores numéricos que constituem o enunciado de uma questão sejam modificados toda vez que a mesma é apresentada, através do sorteio aleatório destes valores que serão utilizados para resolução do problema. Ou seja, a resposta correta da questão é gerada no momento da exibição da mesma. Além disto, é possível realizar uma dependência entre as questões que constituem o teste, construíndo uma árvore de questões onde o docente verifica o “caminho” percorrido pelo aluno durante o teste, dando subsídios para um acompanhamento mais detalhado sobre a resolução do estudante. Finalizando este trabalho, são apresentados exemplos práticos da utilização das ferramentas interativas para acompanhamento do aluno e da criação e aplicação de um teste desenvolvido através da ferramenta AvaliaOnline. / The increase in the number of distance courses in the Web has caused much reflection on how to track the student’s evolution through this course. In a live course it is possible for the teacher to observe and manage the learning process through safer and more concrete ways, once the participants are in constant physical contact. In addition, in a distance course the student usually determines how many hours he must study as well as when he will be studying. This will demand a bigger effort on the part of the teacher to track students once he may have to analyse different moments of the course at the same time. The choice of methods to track the stucent’s evolution in an on-line course is always very difficult to be made and it must be suitable to the specific needs of the studied context. This work presents pedagogical concepts related to tradicional learning evaluation as well as distance course managing environments through the Web, having these as the foundations of the proposals made in this dissertation. The alternatives presented, in an interactive environment and through objective tests, in order to have a formative evaluation, have as their main goal to track the development of the student in the learning process. As a result of the application of methodology for the construction of objective tests, a tool named AvaliaOnline was obtained, whose aim is to create and apply multiple-choice type questions to problems that have numerical values and formulas or algorithms related to their resolution. The tool allows the numerical values in the description of a question to be modified every time it is presented, through random sorting out of these values, which will be used for the resolution of the problem, that is, the correct answer of the question is produced at the moment of its exhibition. Besides, it is possible to establish dependence among the test questions, building a tree of questions where the teacher verifies the “path” followed by the student during the test, providing support for more detailed tracking on the resolution of the student. At the end of this work, practical examples are presented on the use of interactive tools to track the student and on the creation and application of a test developed through the tool AvaliaOnline. The experiments made show the potencial of such alternatives once they are used in a suitable context and under teacher tracking with.

La première partie de cette thèse s'intéresse au groupage de trafic dans les réseaux de télécommunications. La notion de groupage de trafic correspond à l'agrégation de flux de faible débit dans des conduits de plus gros débit. Cependant, à chaque insertion ou extraction de trafic sur une longueur d'onde il faut placer dans le noeud du réseau un multiplexeur à insertion/extraction (ADM). De plus il faut un ADM pour chaque longueur d'onde utilisée dans le noeud, ce qui représente un coût d'équipements important. Les objectifs du groupage de trafic sont d'une part le partage efficace de la bande passante et d'autre part la réduction du coût des équipements de routage. Nous présentons des résultats d'inapproximabilité, des algorithmes d'approximation, un nouveau modèle qui permet au réseau de pouvoir router n'importe quel graphe de requêtes de degré borné, ainsi que des solutions optimales pour deux scénarios avec trafic all-to-all: l'anneau bidirectionnel et l'anneau unidirectionnel avec un facteur de groupage qui change de manière dynamique. La deuxième partie de la thèse s'intéresse aux problèmes consistant à trouver des sous-graphes avec contraintes sur le degré. Cette classe de problèmes est plus générale que le groupage de trafic, qui est un cas particulier. Il s'agit de trouver des sous-graphes d'un graphe donné avec contraintes sur le degré, tout en optimisant un paramètre du graphe (très souvent, le nombre de sommets ou d'arêtes). Nous présentons des algorithmes d'approximation, des résultats d'inapproximabilité, des études sur la complexité paramétrique, des algorithmes exacts pour les graphes planaires, ainsi qu'une méthodologie générale qui permet de résoudre efficacement cette classe de problèmes (et de manière plus générale, la classe de problèmes tels qu'une solution peut être codé avec une partition d'un sous-ensemble des sommets) pour les graphes plongés dans une surface. Finalement, plusieurs annexes présentent des résultats sur des problèmes connexes.

The broad aim of this research is to contribute knowledge that enables improvements in how designers model decision alternatives at the systems level—i.e., how they model different system configurations and concepts. There are three principal complications: (1) design concepts and systems configurations are partially-defined solutions to a problem that correspond to a large set of possible design implementations, (2) each concept or configuration may operate on different physical principles, and (3) decisions typically involve tradeoffs between multiple competing objectives that can include "non-engineering" considerations such as production costs and profits. This research is an investigation of a data-driven approach to modeling partially-defined system alternatives that addresses these issues. The approach is based on compositional strategy in which designers model a system alternative using abstract models of its components. The component models are representations of the rational tradeoffs available to designers when implementing the components. Using these models, designers can predict key properties of the final implementation of each system alternative. A new construct, called a parameterized efficient set, is introduced as the decision-theoretic basis for generating the component-level tradeoff models. Appropriate efficiency criteria are defined for the cases of deterministic and uncertain data. It is shown that the model composition procedure is mathematically sound under reasonable assumptions for the case of deterministic data. This research also introduces an approach for describing the valid domain of a data-driven model based on the use of support-vector machines. Engineering examples include performing requirements allocation for a hydraulic log splitter and architecture selection for a hybrid vehicle.

Cette thèse porte sur des aspects structuraux et algorithmiques des graphes. Elle est divisée en deux parties, qui comportent deux études différentes : une partie sur des algorithmes centralisés-séquentiels, et une autre sur des algorithmes distribués. Dans la première partie, on étudie des aspects algorithmiques de deux structures de graphes appelés séparateurs minimaux et cliques maximales potentielles. Ces deux objets sont au coeur d'un méta-théorème dû à Fomin, Todinca and Villanger (SIAM J. Comput. 2015), qui affirme qu'une grande famille des problèmes d'optimisation peut être résolue en temps polynomial, si le graphe d'entrée contient un nombre polynomial de séparateurs minimaux. La contribution de cette partie consiste à prolonger le méta-théorème de Fomin et al. de deux manières : d'un côté, on l'adapte pour qu'il soit valide pour une plus grande famille des problèmes ; de l'autre, on étend ces résultats à des version paramétrées, pour certains paramètres des graphes. La deuxième partie de la thèse correspond à une étude du modèle appelé « Diffusion dans une Clique Congestionnée ». Dans ce modèle, les sommets d'un graphe communiquent entre eux dans des rondes synchrones, en diffusant un message de petite taille, visible par tout autre sommet. L'objectif ici est d'élaborer des protocoles qui reconnaissent des classes de graphes, en minimisant la taille des messages et le nombre de rondes. La contribution de cette partie est l'étude du rôle du hasard dans ce modèle, et la conception de protocoles pour la reconnaissance et la reconstruction des certaines classes des graphes. / This thesis is about structural and algorithmic aspects of graphs. It is divided in two parts, which are about two different studies: one part is about centralized-sequential algorithms, and the other part is about distributed algorithms. In the first part of the thesis we study algorithmic applications of two graph structures called minimal separators and potential maximal cliques. These two objects are in the core of a meta-theorem due to Fomin, Todinca and Villanger (SIAM J. Comput. 2015), which states that a large family of graph optimization problems can be solved in polynomial time, when the input is restricted to the family of graphs with polynomially many minimal separators. The contribution of this part of the thesis is to extend the meta-theorem of Fomin et al. in two ways. On one hand, we adapt it to be valid into a larger family of problems. On the other hand, we extend it into a parameterized version, for several graph parameters. In the second part of this thesis we study the broadcast congested clique model. In this model, the nodes of a graph communicate in synchronous rounds, broadcasting a message of small size visible to every other node. The goal is to design protocols that recognize graph classes minimizing the number of rounds and the message sizes. The contribution of this part is to explore the role of randomness on this model, and provide protocols for the recognition and reconstruction of some graph classes.

Nespornou vyhodou počítačem podporované výroby (CAM) je výrazná časová úspora při přípravě obráběcího programu. Asociativita je jedním z řešení, její místo v rámci přípravy výrobku se nachází mezi hlavní konstrukcí a technologií podniku. Pro studium asociativity byl použity CAD/CAM modely kompresoru, který díky své komplexní geomtrii posloužil jaky dobrý příklad. Tato práce se podtrhuje omezené možnosti asociativity, především pokud jde o realizaci obráběcího programu pro součást tvořenou více prvky. Dále v této studii budou prezentovány jisté možnosti zlepšení procesu. Studie asociativity v této práci je zaměřena především na obrábění, tedy její aplikace jsou využívány zejména ve oborech jako je automobilový průmysl, letectví, kosmický průmysl či stavebnictví. Kompresor studovaný v této práci je vyroben ze slitiny titanu Ti-6Al-4V a jedná se o součást využívanou v kosmickém průmyslu. Jelikož se jsou jeho rozměry velmi malé, jsou pro jeho obrábění nezbytné velmi přesné nástroje a vysoké řezné rychlosti. Tato práce představuje odlišné strategie obrábění navrhnuté pro výrobu kompresoru, společně s analýzou výsledků. Po počáteční přípravě výroby následují dvě hlavní etpy : editace programu v CATII V5 a jeho ověření v NCSimul8.

Le problème de satisfaction de contraintes (CSP) est un problème NP-complet classique en intelligence artificielle qui a suscité un engouement important de la communauté scientifique grâce à la richesse de ses aspects pratiques et théoriques. Cependant, au fil des années un gouffre s'est creusé entre les praticiens, qui développent des méthodes exponentielles mais efficaces pour résoudre des instances industrielles, et les théoriciens qui conçoivent des algorithmes sophistiqués pour résoudre en temps polynomial certaines restrictions de CSP dont l'intérêt pratique n'est pas avéré. Dans cette thèse nous tentons de réconcilier les deux communautés en fournissant des méthodes polynomiales pour tester automatiquement l'appartenance d'une instance de CSP à une sélection de classes traitables majeures. Anticipant la possibilité que les instances réelles ne tombent que rarement dans ces classes traitables, nous analysons également de manière systématique la possibilité de décomposer efficacement une instance en sous-problèmes traitables en utilisant des méthodes de complexité paramétrée. Finalement, nous introduisons un cadre général pour exploiter dans les CSP les idées développées pour la kernelization, un concept fondamental de complexité paramétrée jusqu'ici peu utilisé en pratique. Ce dernier point est appuyé par des expérimentations prometteuses. / The Constraint Satisfaction Problem (CSP) is a fundamental NP-complete problem with many applications in artificial intelligence. This problem has enjoyed considerable scientific attention in the past decades due to its practical usefulness and the deep theoretical questions it relates to. However, there is a wide gap between practitioners, who develop solving techniques that are efficient for industrial instances but exponential in the worst case, and theorists who design sophisticated polynomial-time algorithms for restrictions of CSP defined by certain algebraic properties. In this thesis we attempt to bridge this gap by providing polynomial-time algorithms to test for membership in a selection of major tractable classes. Even if the instance does not belong to one of these classes, we investigate the possibility of decomposing efficiently a CSP instance into tractable subproblems through the lens of parameterized complexity. Finally, we propose a general framework to adapt the concept of kernelization, central to parameterized complexity but hitherto rarely used in practice, to the context of constraint reasoning. Preliminary experiments on this last contribution show promising results.