Massively multiplayer online games have gained such momentum throughout the years that their consumer base has exploded. Being mainly built on a client-server architecture, the server becomes the bottleneck, causing scalability problem. To alleviate this, peer-to-peer structures have been exploited in the game context. In this thesis, we have developed a peer-to-peer based Network Engine of the Mammoth game research framework.Based on pSense [ASB08], this network layer is flexible enough such that it can be run on different transport protocols. The idea is that players send their game changes directly to other players that are close to them in the game world without going through a server. As clients move, they detect other players with the help of gossiping. Special sensor nodes suggest them to build connections to new players. Through these message exchanges, each client node creates and updates the list of peers interested in their movements. Since clients constantly move around, this overlay maintenance is highly dynamic. A Suggestion Engine is built to perform this overlay maintenance. Experiments are designed to analyse and compare the performance of the network engine when running on top of two different transport protocols: UDP/IP and TCP/IP. / Les jeux en ligne massivement multijoueur ont gagné une si grande popularité au cours des dernières années que leur nombre de consommateurs a explosé. Généralement conçu pour une architecture client-serveur, celui-ci subi une faiblesse au niveau de leur extensibilité, car un goulot d'étranglement se forme normalement du côté du serveur. Afin de régler ce problème, les architectures poste-à-poste ont été adopté et intégré dans les contextes de jeu. Pour cette thèse, nous avons développé un moteur de réseaux (Network Engine) conçu pour une architecture poste-à-poste pour Mammoth, qui est un logiciel intégré pour la recherche des jeux en ligne massivement multi-joueurs. Basé sur pSense [ASB08], notre couche de réseau est assez flexible afin qu'il puisse supporter différents protocoles de transport. Les noeuds clients se découvrent entre eux part l'intermédiaire d'une troisime entité. Cette dernière émet des messages de suggestions afin d'établir des connections entre les noeuds clients. Grâce aux messages communiqués, les noeuds clients créent et fait un mise à jour de leur liste de noeuds homologues intéressés par leurs mouvements. Vu que les clients bougent constamment dans le jeu, cette structure de réseau doit tre très dynamique. Un moteur de suggestion (Suggestion Engine) est créé pour faire la maintenance de la structure. Une suite d'expériences ont été développées afin d'analyser et de comparer la performance du moteur de réseau lorsqu'il est exécuté avec deux différents protocoles de transport : UDP/IP et TCP/IP.

The triple-negative (TN) and basal-like breast cancers have poor outcomes, and lack both targeted therapies and accurate prognostic markers of outcome. Despite the application of microarray technologies to molecular profiling of breast tumors, most current genomics-derived predictors are incapable of stratifying TN or basal breast cancer patients by outcome. We have collected all publicly available breast cancer gene expression datasets to build a human-Compendium; from this, we selected TN and basal patient cohorts to build a TN-Compendium (TN-C) and basal-Compendium (basal-C). Using a de novo machine learning methodology, we have built 25-gene predictors of recurrence for TN and basal patients. Compared to previously reported predictors, these classifiers exhibit superior performance, and highlight multiple biological processes, including immune response, cytoskeletal regulation, signaling and ligand gated ion channels, as being differentially present between recurrent and non-recurrent patients. The small size of these predictors makes them potential candidates for use in clinical settings. / Le Cancer du sein triple négatif (TN) ou basal-like ont de mauvais résultats, et manque les thérapies ciblées et précises marqueurs pronostiques du résultat. Malgré l'application des technologies des biopuces pour le profilage moléculaire des tumeurs du sein, la plus récente des prédicteurs de génomique provenant sont incapables de stratification TN ou basale cancer du sein par résultat. Nous avons rassemblé tous les ensembles de données accessible au public du cancer du sein par l'expression des gènes pour construire un homme-Compendium; de cela, nous avons sélectionné AMT et à la base des cohortes de patients pour construire un TN-Compendium (TN-C) et basal-Compendium (basal-C). En utilisant une machine de novo méthodologie d'apprentissage, nous avons construit des prédicteurs 25-gène de récidive pour les TN et les patients de la base. Par rapport à des prédicteurs signalés précédemment, la performance exposer ces classificateurs supérieure, et mettre en évidence plusieurs processus biologiques, y compris la réponse immunitaire, la régulation du cytosquelette, signalisation et canaux ioniques ligand, comme étant présents de façon différentielle entre les patients récurrents et non récurrents. La petite taille de ces prédicteurs en fait des candidats potentiels pour une utilisation en milieu clinique.

Probabilistic Relational Models (PRMs) are a type of directed graphical model used in the setting of statistical relational learning. PRMs are an extension to Bayesian networks, a popular model which assumes independence between observations. A PRM aims to exploit the logical structure that is often present between observations. We present two approximate inference methods for PRMs. First, we propose an algorithm based on Gibbs sampling that makes use of the relational structure for fast and scalable inference. We then consider PRMs with reference uncertainty, which are models that contain uncertainty about the relational structure itself. We propose an inference method based on a Metropolis-Hasting algorithm which depends on a sparse data structure that decreases the model complexity. Finally we present a software framework called ProbReM that can be used to model and perform inference on PRMs. / Les modèles probabiliste relationel (MPRs) sont un type de modèle graphique utilisés dans le cadre de l'apprentissage relationnelle. Les MPR sont une extension des réseaux Bayésiens, soit un modèle aprécié qui suppose l'indépendance entre les observations. Un MPR vise à exploiter la structure logique qui est souvent présente entre les observations. Nous présentons deux méthodes d'inférence approximative pour les MPR. Premièrement, nous proposons un algorithme basé sur l'échantillonnage de Gibbs qui fait usage de la structure relationnelle pour l'inférence rapide et évolutif. Nous considerons ensuite les MPR à l'incertitude de référence, qui sont des modèles qui contiennent des incertitudes au sujet de la structure relationnelle elle-même. Nous proposons une méthode d'inférence basée sur un algorithme de Metropolis-Hasting, qui repose sur une structure de données éparses qui diminue la complexité du modèle. Enfin, nous présentons un logiciel appelé ProbReM qui peut être utilisé pour modeler et faire de l'inférence sur les MPR.

Lattice basis reduction is a powerful tool for solving complex problems both in pure mathematics and practical applications. In this thesis, we use lattice basis reduction as a preconditioning technique to accelerate the real relaxation based branch and bound (RRBB) method for solving integer least squares (ILS) problems. We give theoretical arguments and simulation results to show that applying lattice preconditioning to the RRBB method can greatly reduce the size of the RRBB tree for ordinary ILS problems, making the method more efficient. We then propose new reduction strategies, which are more effective than some typical existing reduction strategies for lattice preconditioning. Finally we extend the preconditioning techniques to the RRBB method for box-constrained and more general linear-inequality constrained ILS problems. Numerical test results indicate lattice preconditioning is also very effective to reduce the computation time of the RRBB method for these constrained problems. / Les techniques de réduction de réseaux est un outil puissant pour résoudre des problèmes complexes tant en mathématiques pures et les applications pratiques. Dans cette thèse, nous utilisons reduction de réseaux comme une technique de préconditionnement pour accélérer la branche réelle détente et de base lié (RRBB) méthode pour résoudre les problèmes de moindres carrés en nombres entiers (ILS). Nous donnons des arguments théoriques et des résultats de simulation pour montrerque l'application de treillis de préconditionnement de la méthode RRBB peut réduire considérablement la taille de l'arbre RRBB pour des problèmes ILS ordinaires, cequi rend la méthode plus efficace. Nous proposons ensuite de nouvelles stratégies de réduction, qui sont plus efficaces que certaines stratégies de réduction de type existants pour le préconditionnement treillis. Enfin nous étendons les techniques de préconditionnement de la méthode RRBB pour la contrainte des boîtes et des contraintes linéaires-inégalité plus générales des problémes ILS. Les résultats des simulations numériques indiquent que le préconditionnement treillis est également très efficace pour réduire le temps de calcul de la méthode RRBB pour ces problèmes contraints.

Topological quantum computing is an approach to the problem of implementingquantum gates accurately and robustly. The idea is to exploit topological propertiesof certain quasiparticles called anyons to obtain a proposed implementation of quan-tum computing which is inherently fault-tolerant. The mathematical structure thatdescribes anyons is that of modular tensor categories. These modular tensor cate-gories can be constructed from the representations of certain algebraic objects calledquantum groups. In this thesis we give an explanation of modular tensor categoriesand quantum groups as they relate to topological quantum computing. It is intendedthat it can be read with some basic knowledge of algebra and category theory. Thehope is to give a concrete account accessible to computer scientists of the theory ofmodular tensor categories obtained from quantum groups. The emphasis is on thecategory theoretic and algebraic point of view rather than on the physical point ofview. / Le calcul quantique topologique est une approche au problème d'implementationde circuits quantique d'une façon robuste et precisé. L'idée s'agit d'exploiter certaines propriétés de quasiparticules, dites "anyons", pour obtenir une implémentation du calcul quantique qui est intrinsequement tolerante aux pannes. La structure mathématique qui décrit ces anyons est celle des catégories modulaires. Ces objets peuvent être construites à partir de représentations de certaines algèbres, appelées groupes quantiques. Dans ce mémoire, nous donnerons une exposition des catégories modulaires, des groupes quantiques et du lien qu'ils partagent avec le calcul quantique. Le mémoire ne devrait requérir qu'une connaissance de base en algèbre et en théorie des categories. L'espoir étant de donner un model concret pour les informaticiens de la théorie de catégories obtenus à partir de groupes quantiques. L'emphase sera sur le point de vu algèbrique et catégorique plutôt que celui physique.

MATLAB is a dynamic scientific language used by scientists, engineers and students worldwide. Although MATLAB is very suitable for rapid prototyping and development, MATLAB users often want to convert their final MATLAB programs to a static language such as FORTRAN, to integrate them into already existing programs of that language, to leverage the performance of powerful static compilers, or to ease the distribution of executables. This thesis presents an extensible object-oriented toolkit to help facilitate the generation of static programs from dynamic MATLAB programs. Our open source toolkit, called the MATLAB Tamer, targets a large subset of MATLAB. Given information about the entry point of the program, the MATLAB Tamer builds a complete callgraph, transforms every function into a reduced intermediate representation, and provides typing information to aid the generation of static code. In order to provide this functionality, we need to handle a large number of MATLAB builtin functions. Part of the Tamer framework is the builtin framework, an extensible toolkit which provides a principled approach to handle a large number of builtin functions. To build the callgraph, we provide an interprocedural analysis framework, which can be used to implement full-program analyses. Using this interprocedural framework, we have developed value analysis, an extensible interprocedural analysis to estimate MATLAB types, which helps discover the call edges needed to build the call graph. In order to make the static analyses even possible, we disallow a small number of MATLAB constructs and features, but attempt to support as large a subset of MATLAB as possible. Thus, by both slightly restricting MATLAB, and by providing a framework with powerful analyses and simplifying transformations, we can "Tame MATLAB". / MATLAB est un langage scientifique utilisé par des ingénieurs, scientifiques, et étudiants à travers le monde. Bien que MATLAB soit très approprié pour les prototypages et les développements rapides, les usagers veulent souvent convertir leurs programmes MATLAB finaux vers un langage statique tel FORTRAN, dans le but de les intégrer à des programmes existants dans ce langage, de tirer avantage des performances des compilateurs statiques plus puissants, ou de faciliter la distribution des fichiers exécutables. Cette thèse présente un toolkit extensible orienté objet pour faciliter la production de programmes statiques à partir de programmes MATLAB dynamiques. Notre toolkit à code source libre, appelé MATLAB Tamer («dompteur MATLAB »), vise un large sous-ensemble de MATLAB. À partir d'informations sur le point d'entrée du programme, le MATLAB Tamer construit un graphe d'appels complet, transforme chaque fonction en une représentation réduite intermédiaire et fournit l'information sur le typage pour faciliter la production du code statique. Pour fournir cette fonctionnalité, nous devons manipuler une grand nombre de fonctions MATLAB intégrées. Une partie du cadre du Tamer est le cadre intégré, un toolkit extensible fournissant une approche de principe pour manipuler un grand nombre de fonctions intégrées. Pour construire le graphe d'appels, nous fournissons un cadre d'analyse interprocédural pouvant être utilisé pour implanter des analyses de programmes complets. En utilisant ce cadre inter-procédural, nous avons développé l'analyse des valeurs, une analyse inter-procédurale extensible pour estimer les types MATLAB, pour aider à découvrir les arrêtes d'appels nécessaires pour construire le graphe d'appels. Pour pouvoir rendre faisable une analyse statique, nous interdisons un petit nombre de concepts et caractéristiques de MATLAB, mais nous tentons de supporter un sous-ensemble de MATLAB aussi grand que possible. Conséquemment, en restreignant légèrement MATLAB, en fournissant un puissant cadre d'analyse et en simplifiant les transformations, nous pouvons «dompter MATLAB».

In some applied areas such as the Global Positioning System (GPS) and communications, etc., there is a linear model y = Ax + v, where the unknown parameter vector x is an integer vector and the noise vector v follows a normal distribution N(0, sigma^2 I). The typical methods for estimating x are the integer rounding (IR), the Babai nearest plane (BNP), and the integer least squares (ILS) methods. While IR and BNP are polynomial-time methods, the ILS method solves an NP-hard problem. The most effective approach to validating an integer estimator is to find its success rate, which is the probability of correct integer estimation. It has been found in the literature that the ILS estimator is optimal among all admissible integer estimators, including the IR and BNP estimators, as it maximizes the success rate. In communications applications, the integer parameter vector x is often constrained to a box. In this thesis, we first extend the concept of success rates to box-constrained versions of IR (BIR), BNP (BBNP), and ILS (BILS). We then extend some results for the success rates of the corresponding unconstrained estimators to these box-constrained estimators. In addition, we apply the success rate results to improve the efficiency of the BILS estimation process. If some entries of the integer estimator obtained by BBNP have high success rates, then we can fix these entries and solve a smaller BILS problem. This may reduce the overall computational time. Numerical simulations results are presented to support our findings. / Dans certains domaines appliqués comme la navigation utilisant le système mondial de positionnement (GPS) et comme les communications, il y a un modèle linéaire, y = Ax+v, où x est un vecteur de paramètres entiers à estimer et v est un vecteur contenant le bruit et suivant une loi normale N(0, sigma^2 I). Les méthodes typiques pour estimer x sont l'algorithme d'arrondissement à l'entier le plus proche (IR), l'algorithme de l'hyperplan le plus proche de Babai (BNP) et l'algorithme des moindres carrés en nombres entiers (ILS). Tandis que les algorithmes IR et BNP sont polynomiaux, la méthode ILS résout un problème NP-difficile. L'approche la plus efficace pour valider un estimateur entier est de trouver son taux de réussite, qui est la probabilité de trouver la bonne estimation pour le vecteur de paramètres. Dans la littérature, il s'avère que l'estimateur ILS est optimal parmi les estimateurs admissibles, y compris les estimateurs IR et BNP, car il maximise le taux de réussite. Dans les applications de communication, le vecteur de paramètres est souvent contraint à une boîte. Dans cette thèse, nous développons le concept de taux de réussite pour les méthodes d'estimation avec contraintes de boîtes (les méthodes BIR, BBNP et BILS). Nous présentons aussi quelques résultats pour les taux de réussite de ces estimateurs contraints à boîtes. De plus, nous appliquons ces résultats afin d'améliorer l'efficacité de l'algorithme BILS. Si certaines entrées du vecteur obtenu par BILS ont des taux de réussite élevés, nous pouvons les utiliser et résoudre un problème BILS de dimensions réduites. Cela peut réduire le temps de calcul. Des résultats de simulations sont présentés à l'appui de nos conclusions.

Matlab is a very popular dynamic scripting language for numericalcomputations used by scientists, engineers and students world-wide. Matlabprograms are often developed incrementally using a mixture of Matlab scriptsand functions and frequently build upon existing code which may use outdatedfeatures. This results in programs that could benefit from refactoring,especially if the code will be reused and/or distributed. Despite the needfor refactoring there appear to be no Matlab refactoring tools available.Correct refactoring of Matlab is quite challenging because of itsnon-standard rules for binding identifiers. Even simple refactorings arenon-trivial. Compiler writers and software engineers are generally not familiar with \matlab and how it's used sothe problem has been left untouched so far. This thesis has two main contributions. The first is McBench, a tool that helps compiler writers understand the language better. In order to have a systematic approach to the problem, we developed this tool to give us some insight about how programmers use Matlab.The second contribution is a suite of semantic-preserving refactoring for Matlabfunctions and scripts including: function and script inlining, convertingscripts to functions, extracting new functions, and converting dynamic feval calls to static function calls. These refactorings have been implemented using the McLabcompiler framework, and an evaluation is given on a large set of Matlabprograms which demonstrates the effectiveness of our approach. / matlab est un langage de script dynamique utilisé à des fins de calcul numérique par des scientifiques, ingénieurs et étudiants du monde entier. Les programmes matlab sont souvent développés selon une méthode incrémentale, sur la base d'un mélange de scripts et fonctions Matlab, et sont habituellement conçus à partir d'un code existant dont les fonctionnalités seraient obsolètes. Par conséquent, certains programmes pourraient bénéficier de réusinage, surtout si le code sera réutilisé et/ou distribué. Malgré ce besoin, il n'existe aucun outil matlab de ce genre. Le réusinage de Matlab est assez difficile car les règles pour la liaison des identificateurs ne sont pas standards. Même une opération de maintenance simple revêt une certaine complexité. De plus, les créateurs de compilateurs et les ingénieurs en informatique ne sont généralement pas familiers avec matlab et la façon dont il est utilisé. C'est pourquoi à ce jour le problème n'a jamais été traité. Cette thèse apporte deux contributions principales: d'une part la création de MCBENCH, un outil aidant les créateurs de compilateurs à mieux comprendre le langage. Afin d'avoir une approche systématique du problème, nous avons développé cet outil pour en savoir plus sur la façon dont les programmeurs utilisent Matlab. L'autre contribution est une suite de réusinages préservant la sémantique des fonctions et scripts Matlab: incorporation de fonctions et scripts, conversion de scripts en fonctions, extraction de nouvelles fonctions et conversion d'appels dynamiques feval en appels de fonction statique. Le cadriciel et compilateur McLab a été utilisé pour la mise en œuvre de ces réusinages. De plus, une évaluation est donnée sur un large éventail de programmes Matlab afin de démontrer l'efficacité de notre approche.

Network information theory is the study of communication problems involving multiple senders, multiple receivers and intermediate relay stations. The purpose of this thesis is to extend the main ideas of classical network information theory to the study of classical-quantum channels. We prove coding theorems for the following communication problems: quantum multiple access channels, quantum interference channels, quantum broadcast channels and quantum relay channels. A quantum model for a communication channel describes more accurately the channel's ability to transmit information. By using physically faithful models for the channel outputs and the detection procedure, we obtain better communication rates than would be possible using a classical strategy. In this thesis, we are interested in the transmission of classical information, so we restrict our attention to the study of classical-quantum channels. These are channels with classical inputs and quantum outputs, and so the coding theorems we present will use classical encoding and quantum decoding.We study the asymptotic regime where many copies of the channel are used in parallel, and the uses are assumed to be independent. In this context, we can exploit information-theoretic techniques to calculate the maximum rates for error-free communication for any channel, given the statistics of the noise on that channel. These theoretical bounds can be used as a benchmark to evaluate the rates achieved by practical communication protocols. Most of the results in this thesis consider classical-quantum channels with finite dimensional output systems, which are analogous to classical discrete memoryless channels. In the last chapter, we will show some applications of our results to a practical optical communication scenario, in which the information is encoded in continuous quantum degrees of freedom, which are analogous to classical channels with Gaussian noise. / La théorie de l'information multipartite étudie les problèmes de communication avec plusieurs émetteurs, plusieurs récepteurs et des stations relais. L'objectif de cette thèse est d'étendre les idées centrales de la théorie de l'information classique à l'étude des canaux quantiques. Nous allons nous intéresser aux scénarios de communication suivants: les canaux quantiques à accès multiples, les canaux quantiques à interférence, les canaux quantiques de diffusion et les canaux quantiques à relais. Dans chacun des ces scénarios de communication, nous caractérisons les taux de communication réalisables pour l'envoi d'information classique sur ces canaux quantiques. La modélisation quantique des canaux de communication est importante car elle fournit une représentation plus précise de la capacité du canal à transmettre l'information. En utilisant des modèles physiquement réalistes pour les sorties du canal et la procédure de détection, nous obtenons de meilleurs taux de communication que ceux obtenus dans un modèle classique. En effet, l'utilisation de mesures quantiques collectives sur l'ensemble des systèmes physiques en sortie du canal permet une meilleure extraction d'information que des mesures indépendantes sur chaque sous-système. Nous avons choisi d'étudier les canaux à entrée classique et sortie quantique qui constituent une abstraction utile pour l'étude de canaux quantiques généraux où l'encodage est restreint au domaine classique.Nous étudions le régime asymptotique où de nombreuses copies de du canal sont utilisées en parallèle, et les utilisations sont indépendantes. Dans ce contexte, il est possible de caractériser les limites absolues sur la transmission d'information d'un canal, si on connait les statistiques du bruit sur ce canal. Ces résultats théoriques peuvent être utilisées comme un point de repère pour évaluer la performance des protocoles de communication pratiques. Nous considérons surtout les canaux où les sorties sont des systèmes quantiques de dimension finie, analogues aux canaux classiques discrets. Le dernier chapitre présente des applications pratiques de nos résultats à la communication optique, où systèmes physiques auront des degrés de liberté continus. Ce contexte est analogue aux canaux classiques avec bruit gaussien.

A total colouring is the assignment of a colour to each vertex and edge of a graph such that no adjacent vertices or incident edges receive the same colour and no edge receives the same colour as one of its endpoints. If we formulate the problem of finding the total chromatic number as an integer program, we can consider the fractional relaxation known as fractional total colouring. In this thesis we present an algorithm for computing the fractional total chromatic number of a graph, which runs in polynomial time on average. We also present an algorithm that asymptotically almost surely computes the fractional total chromatic number of $G_{n,p}$ for all values of $p$. / Une coloration totale d’un graphe est le coloration des arêtes et des sommets telle que deux sommets adjacents ont des couleurs différentes, deux arêtes incidentes ont des couleurs différentes, et une arête a une couleur différente de celles des ses extrémités. Si nous formulons le problème de trouver le nombre chromatique total comme un programme linéaire entier, nous pouvons considérer la relaxation connue comme la coloration totale fractionnaire. Dans cette thèse nous présentons un algorithme pour calculer le nombre chromatique total d’un graphe en temps polynomial en moyenne. Nous présentons aussi un algorithme qui calcule asymptotiquement presque sûrement le nombre chromatique total de $G_{n,p}$ pour toute valeur de $p$. fr