Attitude determination involves the estimation of the orientation of a body (usually aircraft or satellite) with respect to a known frame of reference. It has important applicationsin areas spanning navigation and communication. There exist two main approaches for determining attitude using the Global Positioning System (GPS): (1) algorithms which determine attitude via baseline estimates in two frames, and (2) algorithms which solve for attitude by incorporating the attitude parameters directly into the state. For each approach, we propose an algorithm which aims to determine attitude in an efficient and numerically reliable fashion. We present numerical simulations demonstrating the performance of our algorithms and provide a comparison evaluating which approach is better - a result which is not presently clearly documented in the literature. / La détermination de l'attitude est l'estimation de l'orientation dans l'espace d'un véhicule ou d'un satellite par rapport à un repère de référence. Ils existent des applications importantes qui exigent la connaissance de l'attitude, particulièrement dans les domaines de navigation et de communication. La détermination de l'attitude à l'aide de GPS peut être obtenue a partir de deux approches: (1) en déterminant la rotation en utilisant des estimées de lignes de base de deux repères, ou (2) en utilisant des mesures de GPS pour déterminer les paramètres d'attitude directement. Pour chaque approche, on propose un algorithme à but de déterminer l'attitude de manière efficace et numériquement fiable. On présente des simulations démontrant la performance de nos algorithmes. On présente aussi une comparaison évaluant quelle serait la meilleure approche - un résultat qui n'est pas actuellement clairement documenté dans la littérature.

This thesis is concerned with integer least squares problems, also referred to as closest vector problems. One often used approach to solving these problems is the discrete search method, which typically involves two stages, the reduction and the search. The main purpose of the reduction is to make the search faster. Reduction strategies for box-constrained integer least squares problems involve column reordering of the input matrix. There are currently two algorithms for column reordering that are most effective for the search stage, referred to here as SW and CH. Although both use all available information in the problem, the SW and CH algorithms look different and were derived respectively from geometric and algebraic points of view. In this thesis we modify the SW algorithm to make it more computationally efficient and easier to comprehend. We then prove that the SW and CH algorithms actually give the same column reordering in theory. Finally, we propose a new mathematically equivalent algorithm, which is more computationally efficient and is still easy to understand. This thesis also extends the column permutation idea to ordinary integer least squares problems. A new reduction algorithm which combines the well-known Lenstra–Lenstra–Lovász (LLL) reduction and the new column reordering strategy is proposed. The new reduction can be much more effective than the LLL reduction in some cases. The thesis also reviews some common search algorithms. A new one is proposed, which is based on two previous algorithms, the depth-first search and the best-first search. This hybrid algorithm makes use of the advantages of both originals, is more efficient than either and is easier to implement than other previous hybrid algorithms. / Cette thèse s'intéresse aux problèmes de moindres carrés entiers (ILS), ou les problèmes du vecteur le plus proche. Une approche souvent utilisée pour résoudre ces problèmes est la méthode de recherche discrète, qui implique deux étapes: la réduction et la recherche. Le but principal de la réduction est de rendre l'étape de recherche plus rapide. Les stratégies de réduction des problèmes ILS sous contrainte de boîte impliquent la réorganisation de colonnes de la matrice de données. Il existe actuellement deux algorithmes pour la réorganisation des colonnes, appelés ici les algorithmes SW et CH, qui sont les plus efficaces pour la phase de recherche. Bien que les deux utilisent toutes les informations disponibles dans le problème, les algorithmes SW et CH sont différents en apparence, et ont été obtenus respectivement à partir d'une point de vue géométrique et algébrique de vue. Dans cette thèse, nous modifions l'algorithme SW pour rendre son calcul plus efficace et plus facile à comprendre. Nous démontrons ensuite qu'en théorie, les algorithmes SW et CH donne effectivement la même réorganisation de colonnes. Enfin, nous proposons un nouveau algorithme mathématiquement équivalent qui est plus efficace, tout en demeurant facile à comprendre. Cette thèse étend également l'idée de permutation de colonnes aux problèmes ordinaires de moindres carrés entiers. Un nouveau algorithme de réduction qui combine le célèbre agorithme Lenstra-Lenstra-Lovász (LLL) avec la nouvelle stratégie de réorganisation de colonnes est proposé. La nouvelle réduction peut être plus efficace que la réduction LLL dans certains cas.Cette thèse examine également certains algorithmes de recherche d'usage courant. Un nouveau est proposé qui est basé sur deux algorithmes précédents: l'algorithme de parcours en profondeur et celui de la recherche au meilleur d'abord. Notre algorithme hybride détient les avantages des deux originaux, tout en étant plus efficace et plus facile à utiliser que d'autres algorithmes hybrides déjà existants.

Social aspects of multiplayer games are well known as contributors to game success, with online friendships and socialization expected to expand and strengthen a player-base. Understanding the nature of social behavior and determining the impact of cooperation on gameplay is thus important to game design. In this work, we make use of data exposed through in-game and web-based API's of two contemporary multiplayer games, World of Warcraft and Halo: Reach. We use this data to investigate the extent of cooperation among players and the effect on individual player behavior. We moreover show how the quantitative assessment of cooperative behavior can be used to isolate potential problem areas in games which may require additional balancing. We first monitor group health and position to measure the pacing of a cooperative scenario in World of Warcraft. We measure a scenario's pacing as the temporal progression of its difficulty, which directly reflects the required level of cohesion and coordination among the players in a group. Our results verify the informal perception that statically designed content becomes increasingly trivial as players obtain stronger stats, thus reducing the need for cohesion. Direct quantification of this behavior, as enabled by designs such as ours, allows for online, adaptive pacing that should better foster player community by consistently emphasizing the need for communication.The benefits of actual group behavior also has a reverse impact on game design. In our experiment involving Halo: Reach, our results demonstrate that players who enter as a group into the multiplayer matchmaking system have, on average, a significantly higher win-to-loss ratio than players who enter the matchmaking system alone. This gives them an advantage over less social players, and thus attests to the potential for refinement in group matchmaking techniques. In addition, our exploratory principal component analysis of individual player performances reveals a set of novel player types adapted to the multiplayer context and quite distinct from player types found in other game genres.From a general standpoint, the data collection techniques outlined in this thesis reveal the use of publically-accessible game APIs as a relatively unexplored yet promising source of insight into real-world gameplay behavior. Our results serve as evidence for two widely-assumed notions of multiplayer game design; the first, that static game content adversely affects a game's replayability and ultimately lessens the need for communication and cohesion among players. The second, that coordination among players provides a significant advantage over those who choose to play independently in a team-based setting. / Les interactions sociales entre les utilisateurs de jeux vidéo multijoueurs contemporains contribuent largement à la propagation et à la longévité de ces derniers. La compréhension des facteurs qui se lient à la promotion d'interactions sociales au sein de ces environnements est donc importante à leur développement. Dans cette thèse, nous recueillons des données à partir d'interfaces de programmation de deux jeux multijoueurs contemporains: World of Warcraft et Halo: Reach. Nous analysons ces données afin d'évaluer l'effet global du comportement coopératif, ainsi que son effet sur le comportement d'individus. De plus, nous démontrons que la mesure quantitative de comportements coopératifs peut aider à l'identification de fautes systémiques d'un jeux.En premier lieu, nous mesurons les points de vie et la position des membres d'un groupe de joueurs pour évaluer le débit d'un scénario coopératif de World of Warcraft. Nous définissons ce débit en fonction de la difficulté du scénario par rapport au temps. L'achèvement d'un scénario à débit intense impose ainsi un niveau de communication plus élevé entre les membres du groupe. Nos résultats appuient d'ailleurs la perception informelle que les jeux conçus avec des environnements et des ennemis non-adaptifs perdent l'intérêt des joueurs lorsque ceux-ci deviennent trop puissants. De plus, cet accroissement en puissance réduit le nombre d'interactions sociales en diminuant l'exigence de la communication entre les joueurs. En deuxième lieu, nous observons les conséquences de la coopération entre les joueurs de Halo: Reach. Les données recueillies dans ce contexte suggèrent que les joueurs qui entrent en groupe d'amis dans le système d'établissement de parties ont de plus fortes chances d'obtenir une victoire que ceux qui s'y introduisent individuellement. Nous découvrons ainsi une faute potentielle de ce système d'établissement de parties qui favorise les joueurs plus sociaux au détriment des joueurs plus solitaires. De plus, nous appliquons une analyse des composantes principales (PCA) sur les résultats moyens de chaque joueur, ce qui révèle un ensemble de descripteurs adaptés au contexte multijoueur, très distinct des descripteurs attribués aux joueurs d'autres types de jeux.D'un point de vue global, quoique les interfaces de programmation de jeux soient relativement inexplorées, notre méthodologie démontre que celles-ci offrent une panoplie d'informations liées aux comportement de joueurs. Nos résultats supportent d'autant plus deux notions informelles enracinées dans le design de jeux multijoueurs -- la première dicte que les environnements statiques agissent contre la rejouabilité d'un jeu, et que ceux-ci réduisent ultimement les besoins de communication et de cohésion entre joueurs. Dans un contexte d'affrontements d'équipes, la deuxième notion soutenue par nos données suggère que les joueurs coordonnés en groupe ont un avantage inné par rapport aux joueurs plutôt indépendants.

The complexity of software systems has been steadily increasing over the past few decades. As a result, numerous means of shielding developers from unnecessarily low-level details, or accidental complexity, have been adopted. Today, Model-Driven Engineering (MDE) is considered to be the state-of-the-art of such means. Models describe complex systems from various viewpoints and at various levels of abstraction. To reduce accidental complexity, Multi-Paradigm Modelling (MPM) promotes modelling every part of a system, at the most appropriate level(s) of abstraction, using the most appropriate formalism(s). At the intersection of MDE and MPM principles is Domain-Specific Modelling (DSM),which promotes modelling using constructs familiar to domain-experts. Documented industrial applications of DSM have demonstrated increases in productivity of up to an order of magnitude, as well as an elevation in the level of abstraction of first class development artifacts. Due to a number of obstacles, DSM has yet to be widely embraced and recognized as a worthwhile and competitive discipline. On the one hand, means to perform essential tasks such as Domain-Specific model (DSm) differencing (e.g., for version control) and de-bugging are still lacking or incomplete. On the other hand, an enormous strain is placed on DSM experts to develop tools, formalisms and compilers that elegantly hide and encapsulate the complexities of whole families of systems. As such, these experts are often faced with problems and challenges that are several "meta-levels" more complex than the increasingly complex systems whose creation they facilitate. This thesis contributes to the removal of both the aforementioned obstacles with a strong focus on the last. First, the long-standing Separation of Concerns principles, that have guided much of the improvements in computer-assisted development, are explored in the light of MPM to produce a new and more structured approach to artifact (e.g., executable code, configuration files) synthesis from DSms. Whereas traditional artifact synthesis techniques favour brute force and transform entire models to artifacts via a single and often complex generator, we propose the modular isolation, compilation and later re-combination of each concern within DSms. Second, a side-effect of this layered approach is a much increased ease of examining and manipulating intermediate data and concept representations between DSms and artifacts. This leads to the introduction of a set of guidelines, caveats and examples, that together form a blueprint for future DSM debuggers. Third, the proposed approach to artifact synthesis from DSms is re-examined in the context of Domain-Specific Modelling Language (DSML) engineering, while remaining mindful of DSM and MPM principles. The result is the extraction of a collection of concepts that form the domain of DSML design and specification, and the introduction of a technique for composing these concepts to create new DSMLs while dramatically reducing the complexity of this notoriously difficult task. Finally, AToMPM, a new tool for MPM, is presented. In addition to several noteworthy technical innovations and improvements, its main scientific interest lies in its theoretically sound approach towards the specification of modelling language syntax and semantics and of model transformation rule pattern languages, and in its implementation and integration of recent research work by ourselves and others. / Au cours des dernières décennies, la complexité des systèmes logiciels n'a cessé de croître. En conséquence, de nombreuses techniques visant à isoler les développeurs de détail de bas niveau, aussi appellé complexité accidentelle, ont été adoptées. La palme de celles-ci est l'Ingénierie à Base de Modèles (IBM), qui préconise la description de systèmes complexes au moyen de modèles de cible et de niveau d'abstraction variés. Afin de réduire la complexité accidentelle, la Modélisation à Paradigmes Multiples (MPM) prône la modélisation de chaque partie d'un système au niveau d'abstraction le plus approprié, usant des langages les plus appropriés. La Modélisation Spécifique au Domaine (MSD) se situe au croisement des principes de l'IBM et de la MPM. Elle promeut l'usage de notions familières aux experts des domaines concernés. Des études en milieu industriel ont révélé que la DSM pouvait mener à une augmentation de la productivité allant jusqu'à un ordre de magnitude, tout en élevant le niveau d'abstraction des artefacts de développement. En raison d'un certain nombre d'obstacles, la MSD ne jouit toujours que d'une adoption et d'une renommée limitées. D'une part, les moyens et outils requis pour effectuer des tâches essentielles telles que la comparaison de modèles Spécifiques au Domaine (mSD) (e.g., pour le contrôle de version) et leur débogage demeurent absents ou incomplets. D'autre part, un fardeau énorme est placé sur les épaules d'experts en MSD, à qui incombent les tâches de créer des outils, des langages et des compilateurs qui masquent élégamment la complexité de familles de systèmes entières. Ces experts font souvent face à des épreuves et des problèmes qui se situent à plusieurs "meta-niveaux" de complexité et difficulté au-dessus de ceux des systèmes, eux-mêmes de plus en plus complexes, dont ils facilitent la création.Cette thèse aborde les deux obstacles mentionnés ci-haut tout en insistant sur le second. Tout d'abord, les principes aguerris de la Séparation des Préoccupations, qui ont guidé bon nombre des améliorations passées dans le développement informatique, sont explorés dans le contexte de la MPM pour produire une nouvelle approche, plus structurée, à la synthèse d'artefacts (e.g., code exécutable, fichiers de configurations) à partir de mSD. Cette approche se distingue des méthodes traditionelles, qui privilégient la synthèse d'artefacts via un unique et souvent très complexe compilateur, en optant plutôt pour une synthèse par phase, qui isole, compile et recombine chacune des préoccupations présentes dans un mSD. Un des effets secondaires de cette approche par phase est qu'il devient largement plus aisé d'examiner, de manipuler et de représenter les données et notions se situant conceptuellement entre les mSD et les artefacts. Exploitant cet avantage, nous proposons une série de recommendations, d'avertissements et d'exemples qui forment une marche à suivre pour le développement de débogeurs pour la MSD. Ensuite, nous réexaminons notre approche de synthèse d'artefacts dans le contexte de la conception de Langages de Modélisation Spécifiques au Domaine (LMSD), en demeurant toujours fidèles aux principes fondateurs de la MSD et de la MPM. Les résultats sont l'identification d'un ensemble de concepts qui forment le domaine de la spécification et du design de LMSD, et l'introduction d'une technique qui permet la création de nouveaux LMSD au moyen de l'agencement de ces concepts. Notre technique réduit drastiquement la difficulté associée à la création de LMSD, une tâche dont la complexité est notoire.En dernier lieu, AToMPM, un nouvel outil de MPM, est présenté. En plus d'un nombre important d'innovations et d'améliorations techniques, ses attraits principaux, d'un point de vue purement scientifique, sont son approche élégante à la spécification de la syntaxe et de la sémantique de langages de modélisation et de langages de motifs, et son intégration de techniques récentes d'auteurs variés, dont nous-mêmes.

Uncertainty relations express the fundamental incompatibility of certain observables in quantum mechanics. Far from just being puzzling constraints on our ability to know the state of a quantum system, uncertainty relations are at the heart of why some classically impossible cryptographic primitives become possible when quantum communication is allowed. This thesis is concerned with strong notions of uncertainty relations and their applications in quantum information theory.One operational manifestation of such uncertainty relations is a purely quantum effect referred to as information locking. A locking scheme can be viewed as a cryptographic protocol in which a uniformly random n-bit message is encoded in a quantum system using a classical key of size much smaller than n. Without the key, no measurement of this quantum state can extract more than a negligible amount of information about the message, in which case the message is said to be "locked". Furthermore, knowing the key, it is possible to recover, that is "unlock", the message. We give new efficient constructions of bases satisfying strong uncertainty relations leading to the first explicit construction of an informationlocking scheme. We also give several other applications of our uncertainty relations both to cryptographic and communication tasks.In addition, we define objects called QC-extractors, that can be seen as strong uncertainty relations that hold against quantum adversaries. We provide several constructions of QC-extractors, and use them to prove the security of cryptographic protocols for two-party computations based on the sole assumption that the parties' storage device is limited in transmitting quantum information. In doing so, we resolve a central question in the so-called noisy-storage model by relating security to the quantum capacity of storage devices. / Les relations d'incertitude expriment l'incompatibilité de certaines observables en mécanique quantique. Les relations d'incertitude sont utiles pour comprendre pourquoi certaines primitives cryptographiques impossibles dans le monde classique deviennent possibles avec de la communication quantique. Cette thèseétudie des notions fortes de relations d'incertitude et leurs applications à la théorie de l'information quantique.Une manifestation opérationnelle de telles relations d'incertitude est un effet purement quantique appelé verrouillage d'information. Un système de verrouillage peut être considéré comme un protocole cryptographique dans lequel un message aléatoire composé de n bits est encodé dans un système quantique en utilisant une clé classique de taille beaucoup plus petite que n. Sans la clé, aucune mesure sur cet état quantique ne peut extraire plus qu'une quantité négligeable d'information sur le message, auquel cas le message est "verrouillé". Par ailleurs, connaissant la clé, il est possible de récupérer ou "déverrouiller" le message. Nous proposons de nouvelles constructions efficaces de bases vérifiant de fortes relations d'incertitude conduisant à la première construction explicite d'un système de verrouillage. Nous exposons également plusieurs autres applications de nos relations d'incertitude à des tâches cryptographiques et des tâches de communication.Nous définissons également des objets appelés QC-extracteurs, qui peuventêtre considérés comme de fortes relations d'incertitude qui tiennent contre des adversaires quantiques. Nous fournissons plusieurs constructions deQC-extracteurs, que nous utilisons pour prouver la sécurité de protocoles cryptographiques pour le calcul sécurisé à deux joueurs en supposant uniquement que la mémoire des joueurs soit limitée en ce qui concerne la transmission d'information quantique. Ce faisant, nous résolvons une question centrale dans le modèle de mémoire bruitée en mettant en relation la sécurité et la capacité quantique de la mémoire.

In the era of big data, data sets have been growing very large, and interest for algorithms and computation framework that handle such large scales is increasing. The number of computing cores per chip has also increased. Instead of developing ingenious ways of speeding up convergences and obtaining better approximations for a smaller subclass of the problems, it is interesting to simply "throw more cores" at exact algorithms and get a speed-up which scales accordingly. This allows practitioners who are not specialists to use the algorithms more efficiently. The MapReduce framework is one of the most widely used paradigms for parallel computation, and we show how to cast the exact deterministic algorithms for our customized spatial model in this framework. Higher-order Markov random fields, i.e., Markov random fields with higher-order interactions, have been shown to be able to represent large-scale properties of typical spatial scenes via MCMC simulation. We present a Markov random field parametrization such that the specification of clique configurations that include higher-order interactions is included in a methodical fashion. This ought to be useful for a practitioner with respect to specifying the type of images desired. The general Markov random field model commonly requires approximation techniques due to its intractable normalization constant, and inference and simulation techniques for models with high dependence via MCMC tend to be time-consuming and may involve algorithms with sensitive convergence criteria. These algorithms are not suitable for practitioners or spatial modellers who are not well-versed in MCMC, and it is therefore more desirable for them to work with models that are able to reproduce spatial structures, while still being easier to wield. We construct variants of the Markov random field that seek to achieve the same goal, but whose inference and simulation is tractable without MCMC, and cast the latter in the MapReduce framework. We also consider the MapReduce formulation of MCMC simulation algorithms for Markov random fields in order to leverage the power of parallel computing. / Dans cette époque du "big data", les fichiers de données atteignent des tailles très importantes, et il y a un intérêt grandissant pour les algorithmes et les infrastructures de calcul adaptés à de telles quantités de données. Le nombre d'unités de calcul par puce électronique va lui aussi en grandissant. Au lieu de développer des méthodes ingénieuses pour accélérer la convergence et obtenir de meilleures approximations pour des classes de problèmes plus restreintes, il est intéressant de combiner l'utilisation d'algorithmes exacts avec une simple augmentation du nombre de coeurs ("cores") de microprocesseurs dédiés aux caluls et d'obtenir ainsi une accélération proportionelle. Ceci permet à des utilisateurs qui ne sont pas des spécialistes d'utiliser les algorithmes avec plus d'efficacité. Le "framework" MapReduce est un des paradigmes les plus utilisés pour le calcul parallèle. Nous montrons comment formuler les algorithmes de notre modèle spatial spécialisé dans cette infrastructure. On sait que les champs aléatoires de Markov avec des intéractions d'ordre élevé peuvent être utilisés pour représenter les propriétés à grande échelle de motifs spatiaux typiques par la simulation MCMC (Markov Chain Monte Carlo). Nous présentons une paramétrisation des champs aléatoires markoviens telle que la spécification des configurations de cliques qui comprennent des intéractions d'ordre supérieur à deux est prise en compte méthodiquement. Ceci sera utile à l'utilisateur qui voudra spécifier le type d'images qu'il désire produire. L'utilisation d'un champ aléatoire de Markov général requiert des approximations à cause de la constante de normalisation difficilement calculable en pratique, et les techniques d'inférence et de simulation pour les modèles avec dépendances d'ordre élevé par MCMC ont tendance à demander des temps de calculs prohibitifs, et sont parfois basées sur des algorithmes dont les critères de convergence sont sensibles aux données. Ces algorithmes ne sont pas adaptés aux besoins des utilisateurs et modélisateurs sans connaissances approfondies du MCMC. Il est donc préférable pour eux de travailler avec des modèles qui peuvent reproduire les structures spatiales, tout en étant plus faciles d'utilisation. Nous construisons des variantes du champ de Markov aléatoire avec les mêmes objectifs, mais pour lesquelles l'inférence et la simulation peuvent être accomplies sans recours au MCMC, et nous adaptons ces dernières au framework MapReduce. Nous nous intéressons également à la formulation dans MapReduce des algorithmes de simulation MCMC pour les champs aléatoires de Markov pour pouvoir faire usage de la puissance du calcul parallèle.

The prediction of RNA three-dimensional structures from its sequence only is a milestone to RNA function analysis and prediction. In recent years, many methods addressed this challenge, ranging from cycle decomposition and fragment assembly to molecular dynamics simulations. However, their predictions remain fragile and limited to small RNAs. In this work, we introduce RNA-MoIP, a new framework incorporating the novel local motif information available in databases for the prediction of RNA structures. We show that our approach (i) improves the accuracy of canonical base pair predictions, (ii) identifies the best secondary structures in a pool of sub-optimal structures, and (iii) predicts accurate 3D structures of large RNA molecules. / Un objectif principal de l'analyse fonctionnelle et prédictive de l'ARN est d'obtenir sa structure tridimensionnel à partir de sa séquence. Pour résoudre ce problème, plusieurs méthodes ont été développées durant les dernières années, telles la décomposition cyclique, l'assemblage de fragments et la simulation de dynamiques moléculaire. Cependant, leurs capacacités prédictives restent limitées. Nous avons mis au point un nouvel outil, RNA-MoIP, permettant d'incorporer l'information des motifs locaux nouvellement accessibles dans des bases de données pour la prédiction de structures d'ARN. Nous montrons que notre approche (i) améliore la prédiction des paire de bases canoniques (ii) identifie la meilleure structure secondaire dans un ensemble de sous-optimaux et (iii) prédit des structures 3D précises pour de large molécules d'ARN.

The Lenstra, Lenstra and Lov\'sz (LLL) reduction is the most popular lattice reduction and is a powerful tool for solving many complex problems in mathematics and computer science. The blocking technique casts matrix algorithms in terms of matrix-matrix operations to permit efficient reuse of data in the algorithms. In this thesis, we use the blocking technique to develop two floating point block LLL reduction algorithms, the left-to-right block LLL (LRBLLL) reduction algorithm and the alternating partition block LLL (APBLLL) reduction algorithm, and give the complexity analysis of these two algorithms. We compare these two block LLL reduction algorithms with the original LLL reduction algorithm (in floating point arithmetic) and the partial LLL (PLLL) reduction algorithm in the literature in terms of CPU run time, flops and relative backward errors. The simulation results show that the overall CPU run time of the two block LLL reduction algorithms are faster than the partial LLL reduction algorithm and much faster than the original LLL, even though the two block algorithms cost more flops than the partial LLL reduction algorithm in some cases. The shortcoming of the two block algorithms is that sometimes they may not be as numerically stable as the original and partial LLL reduction algorithms. The parallelization of APBLLL is discussed. / Le Lenstra, Lenstra et réduction Lovasz (LLL) est la réduction de réseaux plus populaire et il est un outil puissant pour résoudre de nombreux problèmes complexes en mathématiques et en informatique. La technique bloc LLL bloquante reformule les algorithmes en termes de matrice-matrice opérations de permettre la réutilisation efficace des données dans les algorithmes bloc LLL. Dans cette thèse, nous utilisons la technique de blocage de développer les deux algorithmes de réduction bloc LLL en points flottants, l'algorithme de réduction bloc LLL de la gauche vers la droite (LRBLLL) et l'algorithme de réduction bloc LLL en partition alternative (APBLLL), et donner a l'analyse de la complexité des ces deux algorithmes. Nous comparons ces deux algorithmes de réduction bloc LLL avec l'algorithme de réduction LLL original (en arithmétique au point flottant) et l'algorithme de réduction LLL partielle (PLLL) dans la littérature en termes de temps d'exécution CPU, flops et les erreurs de l'arrière par rapport. Les résultats des simulations montrent que les temps d'exécution CPU pour les deux algorithmes de réduction blocs LLL sont plus rapides que l'algorithme de réduction LLL partielle et beaucoup plus rapide que la réduction LLL originale, même si les deux algorithmes par bloc coûtent plus de flops que l'algorithme de réduction LLL partielle dans certains cas. L'inconvénient de ces deux algorithmes par blocs, c'est que parfois, ils peuvent n'être pas aussi stable numériquement que les algorithmes originaux et les algorithmes de réduction LLL partielle. Le parallélisation de APBLLL est discutée.

Radio Frequency Identification (RFID) technology is widely used for variousapplications from access control to object tracking systems. Automation and fasterservices provided by this technology have striking effects on our daily life. However,there are several security and privacy concerns about RFID systems that remainunsolved. During the past years, several attacks have been designed against MifareClassic and HID iClass, two of the most widely used RFID systems on the market.The aim of this study was to improve the security and privacy mechanisms of RFIDsystems through the development of tools and the methodology of system analysis, inthe hope to find the possible flaws before the adversaries do. As an example, effortswere made to partially analyze OPUS cards (the RFID-enabled public transportationpasses in Montreal) and several security and privacy violating specifications of thesecards were highlighted. It was revealed that the static identification number of thecard is transfered in the anticollision process which can be used to track the cardholder without his consent. In addition, the information about the last three usages ofthe card (the time, the date and the metro/bus station) are transferred unencryptedand before the authentication process. Only a linear conversion is applied to theinformation which can be reversed by a simple application such as the one developedand provided in this study.Furthermore, design modifications to improve the security and privacy level of RFIDsystems were provided. These modifications are categorized based on the cost andthe disruption of service that the application of these modifications imposes to themanufacturing company.Key Words: RFID Systems, Privacy, Security, OPUS Cards / Les technologies de radio identification (RFID) sont fortement utilisées dans diverses applications qui vont du contrôle d'accès aux systèmes de traçabilité d'objets. L'automatisation et la rapidité accrue des services que ces technologies rendent possibles ont des effets marqués sur notre vie quotidienne. Cependant, les systèmes RFID comportent de nombreux problèmes de sécurité et de protection de la vie privée qui ne sont toujours pas résolus. Au cours des dernières années, de nombreuses attaques ont été conues contre la puce Classic de MIFARE ainsi que la puce iClass d'HID, deux des systèmes RFID les plus répandus sur le marché. Le but de cette étude est d'améliorer les mécanismes de sécurité et de protection de la vie privée des systèmes RFID par le développement d'outils et la méthodologie d'analyse des systèmes, dans l'espoir de découvrir les failles de sécurité potentielles avant que des adversaires ne le fassent. Par exemple, nous avons procédé à une analyse partielle des cartes OPUS (les cartes qui contiennent les titres de transport en commun utilisés à Montréal, qui font usage de la technologie RFID), et mis en évidence de nombreux éléments des spécifications de ces cartes qui représentent une faille de sécurité ou de protection de la vie privée. Nous avons découvert que le numéro d'identification statique de la carte est transmis durant le processus anticollision, ce qui peut être utilisé pour suivre la trace du détenteur de la carte sans son consentement. De plus, des informations concernant les trois dernières utilisations d'une carte (l'heure, la date, et la station de métro ou d'autobus) sont transmis sans être chiffrés, et avant le processus d'authentification n'ait lieu. Seule une conversion linéaire est appliquée sur l'information, et cette conversion peut être inversée par une simple application telle que celle que nous avons développé au cours de cette étude. De plus, nous présentons des modifications visant à améliorer le niveau de sécurité et de protection de la vie privée des systèmes RFID. Nous classons ces modifications sur la base de leur coût et de la gravité des interruptions de service que l'application de ces modifications ferait subir au manufacturier.Mots clés: Systèmes RFID, protection de la vie privée, sécurité, cartes OPUS

Recent years have seen a huge growth in the demand for online virtual worlds. The type of these online systems can range from virtual meeting setups, to a more video game like competitive environment. An equally large number of virtual worlds have been developed to meet this demand, and the competition between these system is very strong. Developers of such systems can benefit from any edge they can get in terms of technical quality of the system or the enjoy ability of the online experience.We propose that a monitoring system designed especially for virtual worlds will be able to provide that `èdge" to the developers. As such, we present, in this Thesis, a flexible real-time monitoring architecture which caters to the specific challenges and requirements of virtual worlds. Handling huge amount of data present in the worlds is dealt by distributing the data gathering process between multiple node. The proposed system modifies the gathered data, into a form more suitable for users to observe in real-time, by filtering it before displaying the final result. We use Mammoth, a massively multiplayer research framework, as the test-bed for a sample implementation of the proposed architecture. We use the results of experiments conducted on this implementation to validate that the system is indeed suitable for real-time monitoring of virtual worlds. / De nos jours, la demande des mondes virtuels est en plein essor. Ceux-ci vont des sites de rencontre jusqu'aux environnements compétitifs comme par exemple les jeux vidéo en ligne. Afin de satisfaire la demande de mondes virtuels, de nombreux sites ont été mis en place. Du fait de la très grande concurrence présente, les développeurs des services virtuels essayent de bénéficier de tout avantage possible en termes d'avantages techniques ou de la qualité des expériences vécues en ligne.Nous considérons qu'un système de surveillance des mondes virtuels est en mesure de fournir cet "avantage" aux développeurs. Ainsi, nous présentons dans notre thèse un système de surveillance en temps réel fait sur mesure afin de faire face aux défis et aux besoins particuliers de chaque monde virtuel. Afin de manipuler toute l'information obtenue des mondes virtuels, le processus d'obtention des données est distribué entre plusieurs nœuds. Le système que nous proposons modifie les données obtenues pour les rendre plus faciles à observer en temps réel. Ceci se fait en filtrant les données avant de déployer les résultats. Nous utilisons Mammoth, une infrastructure massif de recherche multi-joueurs comme le banc d'essai pour implémenter un échantillon de l'architecture proposée. Nous utilisons les résultats obtenus des expériences réalisées dans cette implémentation pour confirmer que le système est approprié pour surveiller les mondes virtuels en temps réel.