L'objectif de notre travail est de déterminer des algorithmes qui facilitent la résolution de jeux combinatoires par des calculs informatiques. En premier lieu, nous expliquons comment l'implémentation du nimber permet d'accélérer le calcul de jeux impartiaux en version normale. Puis, nous proposons des raffinements ou des généralisations d'algorithmes de parcours des arbres de jeu, en particulier le PN-search, tout en discutant de l'intérêt de l'intervention humaine lors de l'exécution de ces algorithmes. Enfin, nous présentons des algorithmes de vérification, dont le but initial était de s'assurer de la validité de nos calculs, mais qui permettent également d'obtenir des arbres solutions de taille réduite. Ces techniques sont appliquées à l'étude de deux jeux : le Sprouts, où les joueurs relient des points par des lignes, et le Dots-and-boxes, dont le but est de compléter le maximum de boîtes en plaçant des arêtes. Le Sprouts est un jeu combinatoire impartial, dont la nature topologique rend difficile la représentation informatique. Nous explicitons une telle représentation, avant d'étudier une généralisation où le jeu se déroule sur des surfaces compactes. Le Dots-and-boxes est un jeu partisan, et nous détaillons diverses simplifications théoriques qui nous ont permis d'obtenir informatiquement des résultats nouveaux sur ce jeu. / The aim of this thesis is to determine algorithms that help to solve combinatorial games by computation. First, we explain how the implementation of the nimber speeds up the computation of impartial games in normal version. Then, we propose refinements or generalizations of tree-traversal algorithms, especially the PN-search, while discussing the benefit of human intervention during the execution of these algorithms. Finally, we present verification algorithms, whose initial goal was to ensure the validity of our computation, but also allowed us to obtain small solution trees. We have applied these methods to the game of Sprouts, where players connect dots with lines, and Dots-and-boxes, where players complete boxes by drawing edges. Sprouts is an impartial combinatorial game, whose topological nature makes it difficult to represent for a computer. We explain such a representation, before studying a generalization where the game is played on compact surfaces. Dots-and-boxes is a partizan game, and we detail various theoretical simplifications that allowed us to compute new results for this game.

Nous cherchons dans cette thèse à calculer les stratégies gagnantes de jeux combinatoires avec un programme informatique. Nous montrons comment les découpages qui apparaissent au sein de certains jeux impartiaux peuvent être utilisés pour accélérer les calculs. Nous détaillons en particulier l'utilisation du concept d'arbre canonique réduit dans les calculs en version misère. Ces méthodes ont été appliquées avec succès au calcul de deux jeux impartiaux en apparence très différents : le Sprouts, où les joueurs relient des points par des lignes, et le Cram, qui consiste à remplir un plateau avec des dominos. Nous exposons ensuite une méthode originale de suivi des calculs de jeux, avec des interactions en temps réel par l'opérateur humain. Enfin, nous décrivons l'architecture du programme modulaire qui nous a permis de réaliser de nombreux calculs différents au sein d'un cadre commun, et qui pourrait être étendu à l'avenir à d'autres jeux ou algorithmes. / The goal of this thesis is to compute the winning strategies of combinatorial games. We show how to accelerate the computation of impartial games when some positions can be splitted into sums of independent components. We detail in particular the concept of reduced canonical tree in misere computations. We have applied these algorithms successfully to the game of Sprouts, where two players draw lines between spots, and the game of Cram, where the players fill a grid with dominoes. Then, we present an innovative method for monitoring the computation and allowing the human operator to interact in real-time. We also describe the architecture of the modular program that allowed us to compute a lot of different results in a single framework.

Cette thèse se place dans le cadre de l'inférence de programmes d'extraction d'information à partir du Web. Elle soutiens les deux idées suivantes: - l'ultilisation de la structure arborescente des documents du Web permet de définir des programmes d'extraction expressifs et efficaces; - les techniques d'inférences grammaticale sur les arbres sont bien adaptées pour l'inférences de programmes d'extraction d'information.

Cette thèse se place dans le cadre de l'inférence de programmes d'extraction d'information à partir du Web. Elle soutiens les deux idées suivantes: - l'ultilisation de la structure arborescente des documents du Web permet de définir des programmes d'extraction expressifs et efficaces; - les techniques d'inférences grammaticale sur les arbres sont bien adaptées pour l'inférences de programmes d'extraction d'information.

Dans cette thèse, nous nous intéressons aux critères d'existence et à la construction effective de fractions rationnelles à dynamique prescrite. Nous commençons par étudier le même problème pour certains revêtements ramifiés post-critiquement finis et nous donnons une méthode de construction à partir de dynamiques d'arbres. Puis nous présentons un théorème de Thurston qui fournit une caractérisation combinatoire pour passer du cadre topologique au cadre analytique. En particulier, nous généralisons aux applications non post-critiquement finies un résultat de Levy qui simplifie le critère de Thurston dans le cas polynomial. Nous illustrons cette généralisation par une condition suffisante d'existence de polynômes ayant un disque de Siegel fixe de type borné. Ensuite nous détaillons la construction par chirurgie quasiconforme d'un exemple de fraction rationnelle non post-critiquement finie dont la dynamique est décrite par un arbre. Plus généralement, nous montrons qu'un résultat de Cui Guizhen et Tan Lei permet de construire une famille de fractions rationnelles à ensemble de Julia disconnexe à partir de certains arbres de Hubbard pondérés.

Pour augmenter la rentabilité d'un grand alternateur, les exploitants cherchent à réduire les coûts de maintenance. Pour ce faire, ils ont besoin d'outils de surveillance de plus en plus précis. D'autre part, depuis que les machines électriques tournantes existent, les opérateurs ont remarqué que des courants parfois importants pouvaient endommager les machines. Des études ont montré que ces courants d'arbre provenaient généralement de défauts de symétrie. Notre étude part de ces constatations pour créer un nouvel outil de diagnostic utilisant la tension d'arbre, mais aussi les courants des voies d'enroulement, la tension des neutres et le flux dans l'entrefer. Des simulations ont été réalisées pour déterminer les signatures de chaque défaut dans ces grandeurs. Pour les valider, nous avons fait construire une maquette pouvant, fonctionner avec des défauts tels que les courts-circuits et l'excentricité statique. La comparaison des mesures et des simulations a démontré que l'outil est fiable, mais encore perfectible. Compte-tenu de la facilité de mise en oeuvre, son application dans les sites de production est envisageable et une méthodologie de simulation pourra être donnée aux centres de recherche de EDF, tandis que nous pourrons continuer nos recherches afin de perfectionner cet outil de diagnostic.

Cette thèse propose un cadre d'évaluation pour des requêtes XQuery dans un<br />contexte de médiation de données XML. Un médiateur doit fédérer des sources de données<br />distribuées et hétérogènes. A cette fin, un modèle de représentation des requêtes est néces-<br />saire. Ce modèle doit intégrer les problèmes de médiation et permettre de définir un cadre<br />d'optimisation pour améliorer les performances. Le modèle des motifs d'arbre est souvent<br />utilisé pour représenter les requêtes XQuery, mais il ne reconnaît pas toutes les spécifica-<br />tions du langage. La complexité du langage XQuery fait qu'aucun modèle de représentation<br />complet n'a été proposé pour reconna^³tre toutes les spécifications. Ainsi, nous proposons un<br />nouveau modèle de représentation pour toutes les requêtes XQuery non typées que nous appe-<br />lons TGV. Avant de modéliser une requête, une étape de canonisation permet de produire une<br />forme canonique pour ces requêtes, facilitant l'étape de traduction vers le modèle TGV. Ce<br />modèle prend en compte le contexte de médiation et facilite l'étape d'optimisation. Les TGV<br />définis sous forme de Types Abstraits de Données facilitent l'intégration du modèle dans tout<br />système en fonction du modèle de données. De plus, une algèbre d'évaluation est définie pour<br />les TGV. Grâce µa l'intégration d'annotations et d'un cadre pour règles de transformation, un<br />optimiseur extensible manipule les TGV. Celui-ci repose sur des règles transformations, un<br />modèle de coût générique et une stratégie de recherche. Les TGV et l'optimiseur extensible<br />sont intégrés dans le médiateur XLive, développé au laboratoire PRiSM.

L’Hémisphère Sud, et plus précisément le sud de l’Amérique du Sud, sont très sous-représentés dans les reconstitutions climatiques globales du fait d’un manque de données paléoclimatiques robustes. Mes travaux de thèse ont donc porté sur l’évaluation de l’archive naturelle cernes d’arbre, abondante le long de la Cordillère des Andes, comme traceur paléoclimatique. Je me suis ainsi appliquée à étudier la réponse régionale de deux espèces d’arbre (Fitzroya cupressoides et Nothofagus pumilio) natives du nord de la Patagonie (41°S, Argentine) aux forçages climatiques externes en analysant leurs différents paramètres physiques. Pour cela, j’ai commencé par déterminer l’influence du climat local et de grande échelle sur leur croissance en étudiant les variations temporelles de leurs largeurs de cerne, puis j’ai essayé d’extraire le signal climatique enregistré dans la composition isotopique de l’oxygène et du carbone de la cellulose de ces cernes. Deux résultats majeurs de ma thèse ont émergé: j’ai mis en évidence (1) des réponses non-linéaires de la croissance au cours du temps liées aux changements de régimes climatiques et, (2) le fort potentiel du delta18O et delta13C de la cellulose pour enregistrer les variations de température d’été-automne sur une large région aux latitudes moyennes de l’Amérique du Sud (35°-55°S). Du fait des relations fortes qui les lient aux températures, les outils isotopiques peuvent être utilisés pour reconstituer des chronologies de température mais aussi des modes climatiques tels que l’Oscillation Antarctique. / The Southern Hemisphere, and particularly southern South America, are very under-represented in global climate reconstructions due to a lack of robust paleoclimatic data. My thesis was therefore focused on the evaluation of the tree-ring archive, which is widespread along the Andes, as a paleoclimatic tracer. I studied the regional response to external climate forcing of two native species (Fitzroya cupressoides and Nothofagus pumilio) in northern Patagonia (41°S, Argentina), by analysing their different physical tree-ring parameters. In this perspective, I analysed the temporal variations of the width and of the oxygen and carbon isotopic compositions of the cellulose of their rings and related them to local and large-scale climate variations. Two major results of my thesis have emerged: I highlighted (1) non-linear growth responses over time related to shifts in climate regimes and, (2) the potential of cellulose delta18O and delta13C to record summer-autumn temperature variations over a large area in the mid latitudes of South America (35°-55°S). As their variations are strongly linked to temperature the isotopic tools can be used to reconstruct chronologies of temperature but also of climate modes such as the Southern Annular Mode.

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

Dans le travail présenté dans cette thèse, nous proposons d'élargir les idées des opérateurs connexes à base d'arbres. Nous introduisons la notion d'espaces de formes à base d'arbres, construit à partir des représentations d'image à base d'arbres. De nombreuses méthodes de l'état de l'art, s'appuyant sur ces représentations d'images à base d'arbres, consistent à analyser cet espace de forme. Une première conséquence de ce changement de point de vue est notre proposition d'un détecteur de caractéristiques locales, appelé les « tree-based Morse regions » (TBMR). Cette approche peut être considérée comme une variante de la méthode des MSER. La sélection des TBMRs est basée sur des informations topologiques, et donc extrait les régions indépendamment du contraste, ce qui la rend vraiment invariante aux changements de contraste; de plus, la méthode peut être considérée sans paramètres. La précision et la robustesse de l'approche TBMR sont démontrées par le test de reproductibilité et par des applications au recalage d'image et à la reconstruction 3D, en comparaison des méthodes de l'état de l'art. L'idée de base de la proposition principale dans cette thèse est d'appliquer les opérateurs connexes à l'espace des formes. Un tel traitement est appelé la morphologie basée sur la forme. Ce cadre polyvalent traite des représentations d'images à base de région. Il a trois conséquences principales. 1) Dans un but de filtrage, il s'agit d'une généralisation des opérateurs connexes à base d'arbres. En effet, le cadre englobe les opérateurs connexes classiques par attributs. En outre, il permet également de proposer deux nouvelles classes d'opérateurs connexes: nivellements inférieurs/supérieurs à base de forme et shapings. 2) Ce cadre peut être utilisé pour la détection/segmentation d'objets en sélectionnant les points pertinents dans l'espace des formes. 3) Nous pouvons également utiliser ce cadre pour transformer les hiérarchies en utilisant les valeurs d'extinction, obtenant ainsi une simplification/segmentation hiérarchique. Afin de montrer l'utilité de l'approche proposée, plusieurs applications sont développées. Les applications à l'analyse d'images rétinenne de filtrage basé sur la forme montrent qu'une simple étape de filtrage, comparée à des traitements plus évolués, réalise des résultats au niveau de l'état de l'art. Une application de shaping pour la simplification d'image est proposée, fondée sur une minimisation de la fonctionnelle de Mumford-Shah subordonnée à l'arbre de formes. Pour la détection/segmentation d'objets, nous proposons un estimateur de l'énergie basée sur le contexte. Cet estimateur est approprié pour caractériser la signification d'objet. Enfin, nous étendons le cadre de la connectivité contrainte en utilisant l'aspect de transformation de hiérarchie / In a large number of applications, the processing relies on objects or area of interests, and the pixel-based image representation is notwell adapted. These applications would benefit from a region-based processing. Early examples of region-based processing can be found in the area of image segmentation, such as the quad tree. Recently, in mathematical morphology, the connected operators have received much attention. They are region-based filtering tools that act by merging flat zones. They have good contour preservation properties in the sense that they do not create any new boundaries, neither do they shift the existing ones. One popular implementation for connected operators relies on tree-based image representations, notably threshold decomposition representations and hierarchical representations. Those tree-based image representations are widely used in many image processing and computer vision applications. Tree-based connected operators consist in constructing a set of nested or disjoint connected components, followed by a filtering of these connected components based on an attribute function characterizing each connected component. Finally, the filtered image is reconstructed from the simplified tree composed of the remaining connected components. In the work presented in this thesis, we propose to expand the ideas of tree-based connected operators. We introduce the notion of tree-based shape spaces, built from tree-based image representations. Many state-of-the-art methods relying on tree-based image representations consist of analyzing this shape space. A first consequence of this change of point of view is our proposition of a local feature detector, called the tree-based Morse regions (TBMR). It can be seen as a variant of the MSER method. The selection of TBMRs is based on topological information, and hence it extracts the regions independently of the contrast, which makes it truly contrast invariant and quasi parameters free. The accuracy and robustness of the TBMR approach are demonstrated by the repeatability test and by applications to image registration and 3D reconstruction, as compared to some state-of-the-art methods. The basic idea of the main proposition in this thesis is to apply connected filters on the shape space. Such a processing is called the framework of shape-based morphology. It is a versatile framework that deals with region-based image representations. It has three main consequences. 1) For filtering purpose, it is a generalization of the existing tree-based connected operators. Indeed, the framework encompasses classical existing connected operators by attributes. Besides, It also allows us to propose two classes of novel connected operators: shape-based lower/upper levelings and shapings. 2) This framework can be used to object detection/segmentation by selecting relevant points in the shape space. 3) We can also use this framework to transform the hierarchies using the extinction values, so that a hierarchical simplification or segmentation is obtained. Some applications are developed using the framework of shape-based morphology to demonstrate its usefulness. The applications of the shape-based filtering to retinal image analysis show that a mere filtering step that we compare to more evolved processings, achieves state-of-the-art results. An efficient shaping used for image simplification is proposed by minimizing Mumford-Shah functional subordinated to the topographic map. For object detection/segmentation, we proposed a context-based energy estimator that is suitable to characterize object meaningfulness. Last, we extend the hierarchy of constrained connectivity using the aspect of hierarchy transformation of constrained connectivity using the aspect ofhierarchy transformation.