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.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Le $\lambda \mu^{\wedge \vee}$-calcul est une extension du $\lambda$-calcul associée à la déduction naturelle classique où sont considérés tous les connecteurs.<br>Les principaux résultats de cette thèse sont :<br>- La standardisation, la confluence et une extension de la machin de J.-L. Krivine en $\lambda \mu^{\wedge \vee}$-calcul.<br>- Une preuve sémantique de la forte normalisation du théorème d'élimination des coupures.<br>- Une sémantique de réalisabilité pour le $\lambda \mu^{\wedge \vee}$-calcul qui permet de caractériser le comportement calculatoire de certains termes typés et clos.<br>- Un théorème de complétude pour le $\lambda \mu$-calcul simplement typé.<br>- Une introduction à un $\lambda \mu^{\wedge \vee}$-calcul par valeur confluent.

Dans ce travail, nous adaptons la méthode des symétries conditionnelles afin de construire des solutions exprimées en termes des invariants de Riemann. Dans ce contexte, nous considérons des systèmes non elliptiques quasilinéaires homogènes (de type hydrodynamique) du premier ordre d'équations aux dérivées partielles multidimensionnelles. Nous décrivons en détail les conditions nécessaires et suffisantes pour garantir l'existence locale de ce type de solution. Nous étudions les relations entre la structure des éléments intégraux et la possibilité de construire certaines classes de solutions de rang k. Ces classes de solutions incluent les superpositions non linéaires d'ondes de Riemann ainsi que les solutions multisolitoniques. Nous généralisons cette méthode aux systèmes non homogènes quasilinéaires et non elliptiques du premier ordre. Ces méthodes sont appliquées aux équations de la dynamique des fluides en (3+1) dimensions modélisant le flot d'un fluide isentropique. De nouvelles classes de solutions de rang 2 et 3 sont construites et elles incluent des solutions double- et triple-solitoniques. De nouveaux phénomènes non linéaires et linéaires sont établis pour la superposition des ondes de Riemann. Finalement, nous discutons de certains aspects concernant la construction de solutions de rang 2 pour l'équation de Kadomtsev-Petviashvili sans dispersion. / In this work, the conditional symmetry method is adapted in order to construct solutions expressed in terms of Riemann invariants. Nonelliptic quasilinear homogeneous systems of multidimensional partial differential equations of hydrodynamic type are considered. A detailed description of the necessary and sufficient conditions for the local existence of these types of solutions is given. The relationship between the structure of integral elements and the possibility of constructing certain classes of rank-k solutions is discussed. These classes of solutions include nonlinear superpositions of Riemann waves and multisolitonic solutions. This approach is generalized to first-order inhomogeneous hyperbolic quasilinear systems. These methods are applied to the equations describing an isentropic fluid flow in (3+1) dimensions. Several new classes of rank-2 and rank-3 solutions are obtained which contain double and triple solitonic solutions. New nonlinear and linear superpositions of Riemann waves are described. Finally, certain aspects of the construction of rank-2 solutions through an application to the dispersionless Kadomtsev-Petviashvili equation are discussed.

Les réseaux Euclidiens sont un riche objet algébrique qui apparaît dans des contextes variés en mathématiques et en informatique. Cette thèse considère plusieurs aspects algorithmiques des réseaux. Le concept de réduction d'une base d'un réseau est étudié minutieusement : nous couvrons en particulier le spectre complet des compromis qualité-temps des algorithmes de réduction. D'une part, nous présentons et analysons des algorithmes rapides pour trouver une base assez courte (base LLL-réduite) d'un réseau donné arbitraire. D'autre part, nous proposons de nouvelles analyses pour des algorithmes (plus lents) permettant de calculer des bases très courtes (bases HKZ et BKZ-réduites). Cette étude des algorithmes de résolution efficace de problèmes portant sur les réseaux est complétée par une application constructive exploitant leur difficulté apparente. Nous proposons et analysons des schémas cryptographiques, dont la fonction de chiffrement NTRU, et les prouvons au moins aussi difficiles à casser que de résoudre des problèmes pires-cas bien spécifiés portant sur les réseaux.

Dans ce travail, nous adaptons la méthode des symétries conditionnelles afin de construire des solutions exprimées en termes des invariants de Riemann. Dans ce contexte, nous considérons des systèmes non elliptiques quasilinéaires homogènes (de type hydrodynamique) du premier ordre d'équations aux dérivées partielles multidimensionnelles. Nous décrivons en détail les conditions nécessaires et suffisantes pour garantir l'existence locale de ce type de solution. Nous étudions les relations entre la structure des éléments intégraux et la possibilité de construire certaines classes de solutions de rang k. Ces classes de solutions incluent les superpositions non linéaires d'ondes de Riemann ainsi que les solutions multisolitoniques. Nous généralisons cette méthode aux systèmes non homogènes quasilinéaires et non elliptiques du premier ordre. Ces méthodes sont appliquées aux équations de la dynamique des fluides en (3+1) dimensions modélisant le flot d'un fluide isentropique. De nouvelles classes de solutions de rang 2 et 3 sont construites et elles incluent des solutions double- et triple-solitoniques. De nouveaux phénomènes non linéaires et linéaires sont établis pour la superposition des ondes de Riemann. Finalement, nous discutons de certains aspects concernant la construction de solutions de rang 2 pour l'équation de Kadomtsev-Petviashvili sans dispersion. / In this work, the conditional symmetry method is adapted in order to construct solutions expressed in terms of Riemann invariants. Nonelliptic quasilinear homogeneous systems of multidimensional partial differential equations of hydrodynamic type are considered. A detailed description of the necessary and sufficient conditions for the local existence of these types of solutions is given. The relationship between the structure of integral elements and the possibility of constructing certain classes of rank-k solutions is discussed. These classes of solutions include nonlinear superpositions of Riemann waves and multisolitonic solutions. This approach is generalized to first-order inhomogeneous hyperbolic quasilinear systems. These methods are applied to the equations describing an isentropic fluid flow in (3+1) dimensions. Several new classes of rank-2 and rank-3 solutions are obtained which contain double and triple solitonic solutions. New nonlinear and linear superpositions of Riemann waves are described. Finally, certain aspects of the construction of rank-2 solutions through an application to the dispersionless Kadomtsev-Petviashvili equation are discussed.

L'objet de cette thèse est l'extension aux structures complexes de la méthode de Résolution Inverse Fenêtrée Filtrée (RIFF). L'idée principale se base sur le modèle Eléments Finis local et libre d'une partie de la structure étudiée. Tout d'abord, la méthode a été développée dans le cas des poutres. Les mesures de vibrations sont alors injectées dans le modèle Eléments Finis de la partie de poutre analysée. Les rotations sont estimées à l'aide de mesures de déplacements supplémentaires et des fonctions de forme sur le support élémentaire. La méthode étant sensible vis-à-vis des incertitudes de mesures, une régularisation a dû être développée. Celle-ci repose sur une double inversion de l'opérateur où une régularisation de type Tikhonov est appliquée dans la seconde inversion. L'optimisation de cette régularisation est réalisée par le principe de la courbe en L. A cause des effets de lissage induits par la régularisation, les moments ne peuvent être reconstruits mais ils apparaissent comme des "doublets" de forces. Ceci nous a conduit à résoudre le problème en supposant que seules des forces agissent sur la poutre. Enfin, une étude des effets de la troncature du domaine a été menée dans le but de s'affranchir des efforts de couplage apparaissant aux limites de la zone étudiée. Le cas des plaques a été considéré ensuite afin d'augmenter progressivement la complexité des modèles utilisés. L'approche Eléments Finis a permis d'intégrer à la méthode des techniques de condensation dynamique et de réduction par la méthode de Craig-Bampton. Le nombre de degrés de liberté est trop élevé pour permettre une estimation des rotations par mesures de déplacements supplémentaires, la condensation dynamique est employée afin de les supprimer dans le modèle théorique. Par ailleurs, la régularisation induisant une perte de résolution spatiale à cause de son effet de lissage, une procédure de déconvolution spatiale basée sur l'algorithme de Richardson- Lucy a été ajoutée en post traitement. Enfin, une application de la méthode à la détection de défauts a été envisagée de même que l'application de la méthode à l'identification des efforts appliqués par une pompe à huile sur un banc d'essais industriel. Le travail s'est donc appuyé sur des développements numériques et la méthode a été validée expérimentalement en laboratoire et en contexte industriel. Les résultats de la thèse fournissent un outil prédictif des efforts injectés par des sources de vibrations raccordées à une structure en s'appuyant sur un modèle Eléments Finis local et des mesures vibratoires, le tout en régime harmonique.