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.

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.