En développant des outils pour étudier les chaînes de Markov réversibles ainsi qu’une classification des arbres par leur constante de branchement, on pourra traiter du problème du retour à l’origine d’une marche aléatoire sur un arbre. Ces mêmes outils nous permettront d’étudier la percolation sur les arbres. En particulier, il sera possible de relier explicitement la constante de branchement d’un arbre à la valeur critique pour la marche aléatoire biaisée et à la valeur critique de percolation. Par la suite, on détaille comment en arriver à des bornes intéressantes pour deux valeurs critiques du processus de contact sur l’arbre homogène, un résultat de Pemantle. On généralise aussi un résultat de Schinazi qui nous permet de trouver une borne inférieure pour la valeur critique de survie du processus de contact sur le recouvrement universel d’un graphe fini.

Pour une bonne modélisation mathématique de l'occurrence de phénomènes aléatoires, part fondamentale de la discipline actuarielle, il est nécessaire d'employer des distributions multivariées permettant de capturer adéquatement les relations de dépendance présentes entre les phénomènes. Celles qu'offrent les champs aléatoires markoviens, une famille de modèle probabilistes graphiques, répondent à ce besoin, les relations de dépendance qu'elles introduisent se calquant à un arbre ou à un graphe. Les champs aléatoires markoviens misent ainsi sur les riches possibilités de topologies d'arbres et de graphes pour offrir cette même richesse en termes de dépendance. Une nouvelle famille de champs aléatoires markoviens arborescents, c'est-à-dire se basant sur des arbres, est proposée. Les membres de cette famille se distinguent par le fait qu'ils ont des distributions marginales fixes de Poisson, « fixes » dans le sens que la dépendance introduite n'a pas d'impact sur elles. Des distribution marginales fixes sont inhabituelles pour un champ aléatoire markovien, bien que généralement désirables pour fins de modélisation. Cette caractéristique est possible par l'encapsulation, dans les arêtes de l'arbre, de la dynamique de propagation induite par l'opérateur d'amincissement binomial. Cela mène également à une représentation stochastique intuitive des champs aléatoires markoviens de la famille, à des méthodes simples de simulation et à des expressions analytiques pour leur fonction de masses de probabilités conjointe et leur fonction génératrice de probabilités conjointe, notamment. Quantités importantes dans un contexte actuariel, la somme des composantes du champ aléatoire markovien, interprétable comme le nombre total d'événement s'étant produits, et les contributions individuelles de ces composantes sont étudiées en profondeur. Cette analyse passe notamment par l'établissement d'ordres stochastiques. À cet effet, un nouvel ensemble partiellement ordonné est défini pour comparer des arbres aux topologies différentes selon la distribution qu'ils induisent pour la somme, ce qui est, à notre connaissance, novateur dans le contexte de modèles pobabilistes graphiques. Est offerte une comparaison de cet ensemble partiellement ordonné avec quelques autres en lien avec la théorie spectrale des graphes. / For adequate mathematical modeling of random phenomena's occurrences, it is necessary to employ multivariate distributions that appropriately capture the existing dependence relations between those phenomena. The multivariate distributions granted by Markov random fields, a family of probabilistic graphical models, answer to this need, by encrypting the dependence scheme they introduce on a tree or a graph. Markov random fields thus leverage on the rich possibilities of tree shapes and graph shapes to provide these possibilities in terms of dependence schemes. We propose a new family of tree-based Markov random fields, characterized by their Poisson marginal distributions. The marginal distributions are also fixed, meaning they are not affected by the introduced dependence. This fixedness is uncommon for Markov random fields, while being desirable for modeling purposes. It is obtained from the encapsulation, in the edges of the tree, of the propagation dynamic induced by the binomial thinning operator. This leads to an intuitive stochastic representation of Markov random fields from the proposed family, simple methods of simulation, and analytic expressions for their joint probability mass function and their joint probability generating function, notably. Important quantities in an actuarial context are the sum of the components of the Markov random field, interpreted as the total number of occurring phenomena, and the individual contributions of these components. They are thoroughly studied, notably via the use of stochastic order relations. We incidently design a new partially ordered set (poset) of trees, in order to compare trees of different shapes based on the distribution of the sum they respectively convey. To our knowledge, this approach is innovative in the context of probabilistic graphical models. We provide comparisons of the newly defined poset with some other posets of trees fetched from spectral graph theory.

L'objectif de ce travail est de développer deux modules pour créer une simulation Monte Carlo ayant comme objectif futur de calculer les doses de radiation d'un traitement en radiothérapie externe. Le premier module permet de lire, modéliser et réduire le nombre de voxels présent dans une série d'images médicales de type DICOM. La réduction doit se faire tout en gardant les informations essentielles pour une simulation Monte Carlo. Un algorithme a été développé pour appliquer une compression de type octree à la distribution des densités électroniques recueillies dans les images de tomodensitométrie. L'image résultante possède ainsi une certaine anisotropie au niveau de la résolution. Des résultats obtenus, la réduction du nombre total de voxels atteinte est de l'ordre de 75% de la taille initiale. Les simulations Monte Carlo démontrent qu'aucune information dosimétrique n'est perdue après la transformation. L'efficacité de la simulation se trouve améliorée tant au niveau de sa rapidité que de son utilisation de la mémoire. Le second module développé est un modèle d'accélérateur linéaire de type Primus (Siemens). Ce modèle permet d'obtenir des distributions de doses pour deux faisceaux de photons d'énergies différentes (6 et 23 megavolts [MV]). Dans les deux cas, les distributions de doses ont été comparées à des mesures expérimentales prises avec une chambre à ionisation. Les distributions de doses dans l'axe central du faisceau ont atteint un niveau de précision de 2%. Au niveau des distributions de doses hors axe, les déviations maximales sont de l'ordre de 5% et de 2mm dans les pénombres. Pour le faisceau de 23 MV, la géométrie présente une asymétrie qui devra être corrigée en modifiant le filtre égalisateur ou en utilisant une source de radiation asymétrique. Dans tous les cas, l'ouverture des collimateurs secondaires devra être optimisée afin d'éliminer les erreurs au niveau de la pénombre. Une fois ces modifications effectuées, les images DICOM compressées avec l'octree pourront être insérées à l'intérieur du modèle de l'accélérateur. Ce faisant, il suffirait d'ajuster la configuration des faisceaux et du patient pour évaluer un traitement en radiothérapie externe.

L'objet de cette thèse est d'obtenir une description des plongements élémentaires (au sens de la logique du premier ordre) dans un groupe hyperbolique sans torsion. Le résultat principal décrit ces plongements en terme d'une structure définie par Sela dans sa solution au problème de Tarski: la structure de tour hyperbolique. Ainsi, si H est plongé élementairement dans un groupe hyperbolique sans torsion G, on peut obtenir G en amalgamant successivement des groupes de surfaces à bord à un produit libre de H avec des groupes libres et des groupes de surfaces sans bord. Ceci permet en corollaire de montrer qu'un sous-groupe plongé élémentairement dans un groupe libre de type fini est un facteur libre. Les techniques utilisées pour obtenir cette description sont essentiellement géométriques: actions sur des arbres réels ou simpliciaux, existence de décompositions JSJ. On s'appuie également sur des résultats d'existence d'ensembles de factorisation qui affirment que pour certains groupes A de type fini, étant donné un groupe hyperbolique sans torsion G, il existe un ensemble fini de quotients de A tel que tout morphisme non injectif de A vers G se factorise par l'un de ces quotients après précomposition par un automorphisme de A. On expose une preuve de ces résultats, y compris une version complète et détaillée du shortening argument de Rips et Sela. Le shortening argument montre, grâce à l'analyse de Rips des actions sur des arbres réels, que si une suite d'action d'un groupe A sur des espaces hyperboliques converge vers un A-arbre réel d'un certain type, alors une infinité de ces actions peuvent être raccourcies.

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.

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.

Tableau d'honneur de la Faculté des études supérieures et postdoctorales, 2006-2007 / Une solution de plus en plus courante pour appuyer les forces militaires déployées en milieu urbain consiste à utiliser des plates-formes robotisées pour la réalisation des tâches présentant un niveau de risque important. Dans cette optique, les travaux de recherche présentés dans ce mémoire ont permis de développer un système exploitant un capteur volumétrique 3D pour effectuer la modélisation d'environnements urbains et l'exploration efficace de ceux-ci à l'aide d'une plate-forme mobile autonome. Un aspect important de ce projet est que, le modèle 3D de l'environnement étant préservé sous forme d'octree multirésolution tout au long du processus, les modules de cartographie, d'exploration et de navigation qui composent la plate-forme mobile peuvent y avoir accès en tout temps afin d'effectuer leurs tâches respectives. À partir des résultats obtenus pour des tests effectués en simulation et dans un environnement réel, il a été possible de valider que le système développé permet d'explorer un environnement de façon autonome tout en générant de façon simultanée un modèle 3D complet de l'espace parcouru.