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.

En cas de sinistre, les infrastructures de communication peuvent être partiellement ou totalement détruites, ou inefficaces en raison du trafic élevé. Néanmoins, il est nécessaire d'assurer la connectivité entre les équipes de secours et le centre de commandement. Par conséquent, les solutions de communication temporaires sont essentielles jusqu'à ce que l'infrastructure soit rétablie. Dans cette thèse, nous nous concentrons sur le déploiement d’une solution de communication appelée réseaux de substitution. Ainsi, nous proposons un algorithme d'auto - déploiement pour permettre aux routeurs mobiles et répartis composant un réseau de substitution de couvrir la zone cible. Notre algorithme surveille les conditions du réseau pour décider si le routeur doit ou non se déplacer, ajustant la position de ce dernier en fonction des informations à un saut au moyen de la mesure active, c'est à dire, les paquets sondes. Ces paquets sondes permettent à l'algorithme de surveiller le canal et ses éventuels changements au fil du temps. Si le taux de transmission des paquets est suffisamment élevé, les connaissances obtenues seront exactes, cependant, le coût augmentera proportionnellement en consommant plus de ressources réseau. Par conséquent, nous proposons d'utiliser des données de substitution obtenus au moyen d'un estimateur autorégressif pour réduire la surcharge sans impacter notre algorithme de déploiement. Nous montrons par simulation l'efficacité des deux algorithmes et leurs performances en termes de temps de déploiement, de délai, de gigue et de débit. / In case of a disaster, the communication infrastructure may be partially or totally destroyed, or insufficient due to the high data traffic. Despite this, it is necessary to provide connectivity between the rescue teams and the command center. Therefore, temporary communication solutions are crucial until the infrastructure is restored. In this thesis, we focus on the deployment of communication solution called substitution networks. Thus, we propose a self-deployment algorithm to allow mobile routers that compose a substitution network spread out to cover the target area. Our algorithm monitors the network conditions to decide whether the router should move or not, adjusting its position based on one-hop information by means of active measurement, i.e., probe packets. Such probe packets allows the algorithm to monitor the channel and its eventual changes over time. If the probe transmission rate is enough high, the insights obtained will be accurate, however, the overhead will increase proportionally consuming network resources. Hence, we propose to use surrogate data obtained by means of an autoregressive estimator to reduce the overhead without impacting our deployment algorithm. We show by simulation the efficiency of both algorithms and their performance in terms of deployment time, delay, jitter, and throughput.

Dans cette thèse, nous nous intéressons à la problématique de transport usager dans un contexte multimodal, multi-objectif et dépendant du temps. Notre première contribution porte sur la définition du graphe de transfert, un modèle de représentation des réseaux multimodaux. Sur base de ce modèle, cette thèse propose plusieurs algorithmes de calculs d’itinéraires multimodaux et dépendants du temps mais simplement mono-objectifs. Toujours dans le souci de faire face aux exigences des usagers, nous nous intéressons dans une deuxième partie de cette au problème multi-objectif. Nous avons expérimenté dans un premier temps, la version dépendante du temps de l’algorithme exact de Martins, ensuite proposé une solution basée sur les algorithmes génétiques. Ces deux approches restent limitées faute de temps ou d’espace. L’algorithme hybride combinant la rapidité des méta-heuristiques et la complétude des méthodes exactes a donné de meilleurs résultats / The focus of this thesis is about multi-modal, multi-objective and time-dependent in passengers transport networks. We propose itineraries processing solutions that satisfy the user needs, as much as possible. The first part of our contributions begins with the definition of the transfer-graph model that is consistent with the distributed nature of multi-modal transport networks. Based on this model, we propose several itineraries processing algorithms. We have been interested, in a second part of this thesis, in developing multi-objective solutions to satisfy more constraints at the same time. We first experimented the time-dependent version of an exact algorithm based on Martins. We then proposed a solution based on a genetic algorithm. Both of these approaches are limited because of either excessive time response or memory space limit. The hybrid algorithm which combines the speed of meta-heuristics and completeness of exact methods, provide better results

L'hypothèse qu'un grand nombre de problèmes n'admettent pas d'algorithme (exact et déterministe) polynomial date de l'avènement de la théorie de la NP-complétude dans les années 70. Depuis, de nombreuses théories et techniques algorithmiques se sont développées pour résoudre ces problèmes difficiles le plus efficacement possible. Dans cette thèse, nous nous intéressons aux algorithmes exacts faiblement exponentiels. L'objectif est d'obtenir des algorithmes de complexité 0* (c^n) où n est la taille de la donnée et c une Constante la plus faible possible / The assumption that many problems do not admit algorithm (exact and deterministic) polynomial ate of the advent of the theory of NP-completeness in the 70s. Since many theories and algorithmic techniques have been developed to solve these problems difficult as efficiently as possible. In this thesis, we focus on exact algorithms weakly exponential. The objective is to obtain algorithms complexity 0 * (c ^ n) where n is the size of the data and one constant c as small as possible

L'estimation de canal est une tâche cruciale du récepteur dans les systèmes de communication sans fil, en particulier en cas de mobilité où les paramètres du canal varient avec le temps. Dans cette thèse, un nouvel estimateur de boucle de poursuite d'ordre 3 ( RW3-CATL), qui a une structure semblable à la PLL avec une faible complexité a été tout d'abord proposé pour estimer l'amplitude complexe du canal dans le cas mono-trajet mono-porteuse. Le lien entre un filtre de Kalman en régime asymptotique basé sur un modèle d'approximation de marche aléatoire (RW3-KF) et l'estimateur proposé est établi. Les expressions des paramètres sous-optimaux et d'EQM correspondante sont données sous forme analytiques en fonction des gains de boucle. Ensuite, les performances asymptotiques du RW3-KF ont été analysées en résolvant les équations de Riccati. L'expression analytique de la variance optimale du bruit d'état qui minimise l'EQM asymptotique a été également déduite. / Channel Estimation is a crucial task of the receiver in wireless communication systems, especially in case of mobility where the channel parameters vary with time. In this thesis, a novel PLL-structured third-order tracking loop estimator (RW3-CATL) with a low complexity is firstly proposed to estimate the complex amplitude of the channel in the mono-path single-carrier scenario. The connection between a steady-state Kalman filter based on a random walk approximation model (RW3-KF) and the proposed estimator has been established. The sub-optimal parameters and the corresponding MSE of the RW3-CATL are given in closed-form expressions in function of the tracking loop parameters. Then, the asymptotic performance of the RW3-KF has been analysed by solving the Riccati equations. The closed-form expression of the optimal state noise variance which minimizes the asymptotic MSE is also derived.

Reproduction de : Thèse de 3e cycle : mathématiques appliquées : Grenoble, INPG : 1986. / Titre provenant de l'écran-titre. Bibliogr. p. 75-77.

Les grilles de calcul et les grille de PC sur Internet offrent des alternatives intéressantes pour le calcul scientifique à grande échelle, qui demande des ressources de calcul importantes. Toutefois, l’adaptation des applications pour ces systèmes est difficile à cause des facteurs nombreux tels que l'interface complexe de programmation. L'objectif de cette thèse est de trouver une solution pour faciliter le calcul scientifique à grande échelle. Pour ce faire, j’ai travaillé sur l’algorithme de Gauss Jordan et une nouvelle version d’un schéma de parallélisme. Ce schéma peut exploiter le maximum de parallélisme entre des opérations. Comme un exemple excellent, l'algorithme de Gauss Jordan est également utilisé pour évaluer des environnements expérimentaux et des outils différents. Les expérimentations avec YML, OmniRPC et XtremWeb sur les grilles et les grilles de PC montrent que YML peut être une bonne solution pour que les utilisateurs fassent du calcul scientifique à grande échelle, à cause des bonnes caractéristiques comme « l’interface d'abstraction de haut niveau», « les composants réutilisables » et «le surcoût acceptable». Pour obtenir les meilleures performances de cette plate-forme, les questions concernées, telles que la granularité des tâches, la persistance des données et le mécanisme d’ordonnancement, sont également abordés dans cette thèse. Selon les analyses faites ci-dessus et les caractéristiques communes des nuages informatiques ciblés, YML-PC, une architecture de référence basée sur les workflows pour les constructions de nuages informatiques privés scientifique est proposée. YML-PC hérite les bonnes caractéristiques présentées ci-dessus et des autres technologies clefs telles que « la persistance des données », « La prévision du temps disponible »  et « l'évaluation sur des nœuds de calcul hétérogènes » pour YML-PC, qui sont également abordées dans cette thèse. Les évaluations sur l'algorithme de Gauss Jordan sont réalisées sur les grilles, les grilles de PC et les nuages informatiques privés qui sont implantés sur la plate-forme Grid5000, la plateforme de calcul de Polytech Lille en France et la plateforme de calcul de Hohai, en Chine. / Grid computing and Desktop Grid computing provide interesting alternatives for large scale scientific computing which needs very large scale computing resources. However gridification is hard to develop because of series of factors such as complex programming interface. The aim of this dissertation is to find a solution to make large scientific computing in an easy way. To do that, research on Gauss Jordan algorithm is made and a new parallel programming version is presented. The parallel version can achieve maximum degree parallelism between operations. Also the Gauss Jordan algorithm as an excellent example is used to evaluate different experimental environments and tools. Experiments with YML, OmniRPC and XtremWeb on Grid and Desktop Grid environments testify YML can be a good solution for end users to make large scale scientific computing for its series of good features such as higher level interface, component reuse and acceptable overhead. To get better performance of platform, related issues such as task granularity, data persistence and schedule mechanism are also discussed in this dissertation. According to analysis made above and the common features of Clouds possessed, YML-PC a reference architecture based on workflow for building scientific Private Clouds is proposed. YML-PC inherits those good features presented above and some other key technologies such as “data persistence”, “available time prediction” and “evaluation on heterogeneous computing nodes” for YML-PC are also discussed in this dissertation. Evaluations are made based on Gauss Jordan algorithm on Grids, Desktop Grids and Private Clouds which build on Grid5000, Polytech Lille platform, France and Hohai platform, China.

Les villes actuelles sont de plus en plus connectées. Les compteurs sont relevés sans-fil et à distance. Les luminaires des villes communiquent pour économiser l’énergie tandis que les engins de ramassage communiquent avec les poubelles pour planifier les tournées. Ces réseaux sont sans infrastructure et les nœuds capteurs puisent leur énergie dans une batterie limitée.Dans cette thèse j'analyse les problématiques des réseaux sans-fil muti-sauts dans les villes intelligentes. J’étudie dans un premier temps l’importance et l’impact de la topologie sur les performances réseau. Plus précisément, au travers de simulations et d’études expérimentales, je démontre que le placement des nœuds impacte les performances des algorithmes de routage géographique. Je propose ensuite une famille d’algorithmes de clustering pour réseaux de capteurs sans-fil reposant sur l’hypothèse qu’un chef de cluster consomme plus d’énergie que les autres nœuds. L’idée principale de ces algorithmes est que le rôle de cluster-head doit être attribué en fonction du niveau d’énergie des nœuds et de leur voisinage. Ces algorithmes ont été testés grâce à des simulations sur des topologies de villes réalistes avec des paramètres de simulation tirés du monde réel. Enfin, je propose un algorithme de routage pour les villes intelligentes ayant pour base deux techniques de routage. Il repose sur l'hypothèse que seulement une partie des nœuds dispose de l'information de sa position. Je montre qu’il est possible d’obtenir des performances proches des algorithmes de routage géographique, même sous cette hypothèse. / In recent years, cities have become more and more connected. Readings of the electricity usage are being performed wirelessly. In order to reduce the energy consumption, lampposts became intelligent, while the garbage trucks communicate with dust bins in order to plan the garbage collection tours. These networks often lack the infrastructure and sensor nodes rely on a battery with a limited capacity. In this thesis, I analyze the issues of multi-hop wireless networks in smart cities. First, I study the significance and impact of network topologies on network performance. More precisely, through simulations and an experimental study, I show that the placement of nodes impacts the performance of geographic routing algorithms. Then, I propose a set of clustering algorithms for wireless sensor networks that optimize the lifetime of the network. The key hypothesis is that a cluster-head is consuming more energy than a regular node. This set of algorithms, named BLAC, creates multi-hop clusters in which each cluster-head is the root of a tree. The main idea is that the role of each cluster-head should be assigned regarding the remaining energy of nodes and their neighborhood. These algorithms have been tested through simulations based on realistic city topologies with simulation parameters resembling the real world.In the end, I propose a routing algorithm for large scale smart cities that combines two geographic routing techniques. It relies on the hypothesis that only a fraction of nodes in the network are aware of their positions. I show that it is possible to achieve the performance close to classical routing algorithms, even under this hypothesis.

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