Line-of-sight networks were introduced by Frieze et al. to model wireless communications in an urban setting. Their model is based on a two-dimensional grid of points in the shape of a torus. Two grid points are said to be mutually visible if they lie in the same row or column of the torus and if the distance between them is within a certain predetermined range. Distance is measured using the L1 norm. A random graph is obtained by placing a node at each grid point independently with the same placement probability and connecting all mutually visible pairs of nodes. Among the results proven by Frieze et al. is a threshold for the connectivity of the graph.In this thesis we extend the model of Frieze et al. to higher dimensions and the general Lp norm. Specifically we consider an underlying d-dimensional grid in the shape of a torus and we define two points to be mutually visible if they differ in at most k coordinates, and the distance between them is within a certain range. We then prove corresponding asymptotically tight connectivity thresholds for this generalized model. / Les réseaux de lignes de visée ont été introduits par Frieze et al. pour modéliser les communications sans fil en milieu urbain. Leur modèle est basé sur une grille bidimensionnelle de points en forme de tore. Deux points de la grille sont dits mutuellement visibles si ils sont situés sur la même ligne ou la même colonne du tore et si la distance entre eux est dans un certain intervalle prédéterminé. La distance est mesurée en utilisant le norme L1. Un graphe aléatoire est obtenu en plaçant un noeud à chaque point de la grille indépendamment avec la même probabilité de placement et en reliant toutes les paires de noeuds qui sont mutuellement visible. En particulier, Frieze et. al déterminent le seuil de connectivité du graphe.Dans cette thèse, nous généralisons le modèle de Frieze et al. à dimensions supérieures. Plus précisément, nous considérons comme un réseau sous-jacent une grille à d dimensions et nous disons que deux points sont mutuellement visibles si ils ont un maximum de k coordonnées différentes, et si la distance entre eux est dans un certain intervalle. Ensuite, nous prouvons un seuil pour la connectivité de ce modèle généralisé.

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.

Greenhouse gas emissions from world energy generation in 2010 were the highest in history, according to the latest estimates from the International Energy Agency, released on May 30th, 2011. In addition, the demand for food, feed, fiber and fuel increases to meet the needs of a growing global population, making soil fertility management increasingly important. In this context Biochar has proved itself to be a potential and practical solution in combating these issues. In this present study, influence of various process parameters on the pyrolysis of the five different types of ligno cellulosic biomasses into biochar was investigated. The operational parameters for pyrolysis were optimized using response surface methodology individually based on the temperature of operation and the time of residence. The independent process parameters for pyrolysis such as operational time and residence time were evaluated using a central composite design to access their effects and their interactions on the yield of biochar from lignocellulosic biomass. Optimal temperatures for a desirability function of 0.5 for maple, balsa, bamboo, pine and ebony are 345°C, 334°C, 326.7°C, 325.8°C and 340.8°C respectively with the corresponding residence times of 22, 43.75, 28, 24.8 and 21.75 minutes respectively. All the biomass data fitted the proposed model very well. The least fit was observed in balsa wood biomass. Temperature was the major influential factor compared to time. Density analysis was done to compare the changes in density before and after pyrolysis. It was observed that the density of biochar was 0.8 times the density of the wood from which it was originally made. Proximate analysis was performed to compare the fuel and optimal biochar properties. Characterization of biochar revealed important details: Hyperspectral imaging analysis which measured the mean reflectances of the biochar disclosed that porosity which is inversely proportional to the porosity decreased as the temperature increased. Thus higher temperature indicated greater porosity compared to average and low temperatures. Pycnometry analysis suggested that the severity of the pyrolysis hiked the degree of porosity as well. This result was further substantiated with the scanning electron microscope images which showed larger sized pores at greater temperatures. / Émissions de gaz à effet de serre de la production d'énergie mondiale en 2010 étaient les plus élevés dans l'histoire, selon les dernières estimations de l'Agence internationale de l'énergie, publié le 30 mai 2011. En outre, la demande augmente aliments, la nourriture, fibres et combustible pour répondre aux besoins d'une population mondiale croissante, ce qui rend la fertilité des sols en plus important. Dans ce contexte biochar s'est avéré être une solution potentielle et pratique dans la lutte contre ces problèmes. Dans la présente étude, l'influence des paramètres du processus différents sur la pyrolyse des cinq différents types de biomasses ligno cellulosique en biochar a été étudiée. Les paramètres opérationnels pour la pyrolyse ont été optimisés en utilisant la méthodologie de surface de réponse individuelle basée sur la température de fonctionnement et le temps de résidence. Les paramètres de processus indépendant pour la pyrolyse comme le temps de fonctionnement et le temps de séjour ont été évalués en utilisant un plan composite central pour accéder à leurs effets et leurs interactions sur le rendement de biochar à partir de biomasse lignocellulosique. Les températures optimales pour une fonction de désirabilité de 0,5 pour l'érable, balsa, le bambou, le pin et l'ébène sont 345 ° C, 334 ° C, 326,7 ° C, 325,8 ° C et 340,8 ° C, respectivement avec le temps de séjour correspondant de 22, 43,75, 28 , 24,8 et 21,75 minutes respectivement. Toutes les données sur la biomasse équipé le modèle proposé très bien. Le moins bon a été observée dans la biomasse bois de balsa. La température était le principal facteur d'influence par rapport au temps. Analyse de la densité a été faite pour comparer les changements dans la densité avant et après pyrolyse. Il a été observé que la densité de biochar a été 0,8 fois la densité du bois à partir de laquelle il a été initialement faite. L'analyse immédiate a été effectuée pour comparer les propriétés du carburant et optimale du biochar. Caractérisation de biochar a révélé des détails importants: l'analyse d'imagerie hyperspectrale qui a mesuré la réflectance moyenne de la biochar a révélé que la porosité qui est inversement proportionnelle à la porosité diminué lorsque la température augmente. Ainsi plus la température indiquée plus grande porosité par rapport aux températures moyennes et basses. Analyse Pycnométrie suggéré que la sévérité de la pyrolyse a haussé le degré de porosité ainsi. Ce résultat a été étayé par les images microscope électronique à balayage montrant des pores plus grands de taille à des températures plus élevées.

Video surveillance has become of a major research topic recently due to the increasing number of potential applications in public spaces. In particular, there is a demand for automated surveillance applications that detect different types of activities related to public safety, such as in metro stations. Automated video surveillance is intended to be used as an aid to human operators by bringing to their attention certain designated events of interest.This thesis presents a real-time video surveillance system that detects a range of activities in a scene viewed by a single color-video camera. Our contribution in this work is mainly exploiting the properties of the CIELab color space to improve the performance at the low level processing, proposing a multi-level blob matching algorithm to solve the object tracking problem, and using a hierarchy of semantics for detecting events that are of interest to public spaces surveillance.A complete framework of a surveillance system is presented. Objects in an observed scene are modeled by blobs that are detected by means of the adaptive background modeling codebook implementation based on the work of Kim et al. [2]. The implementation uses a dynamically updated codebook in which blobs in the video are characterized in color space, while also dealing with shadows. Collections of blobs, which represent potential objects of interest, are tracked and classified in real-time. For tracking, we employ a simple correlation process based on an elaborate blob matching algorithm. The essence of this algorithm is to find the best blob collection based on matching all potential color histograms from previous frames to those obtained in the current frame. Rules are used to resolve complex cases such as ghosts, occlusion, and lost tracks. Objects are then classified as either being animate persons or inanimate objects. This is essential for providing an accurate description of the scene and drawing the correct inferences about object interaction and events. Given this description of the video, a hierarchical semantic approach is used for event detection. The proposed framework investigates a generalized approach to detecting a spectrum of behaviours based on object interactions and trajectories. These behaviours range from simple single agent events such as loitering, to more complex interactive ones, such as people walking together. Experimental results are presented for standard available videos in order to verify the performance of the system and are compared to existing results in the literature. These results show a significant improvement both in terms of quality and speed, making a step towards a more reliable fully automated surveillance system. / La surveillance vidéo est devenue un sujet de recherche majeur récemment en raison du nombre croissant d'usages potentiels dans les espaces publics. En particulier, il y a une demande pour des applications de surveillance automatisées qui détectent différents types d'activités liées à la sécurité publique, comme dans les stations de métro. La surveillance vidéo automatisée est destinée à être utilisé comme une aide aux opérateurs humains en attirant leur attention à certains événements désignés d'intérêt. Cette thèse présente un système de surveillance vidéo en temps réel qui détecte une gamme d'activités dans une scène captée par une caméra vidéo couleur. Nos contributions sont principalement l'exploitation des propriétés de l'espace couleur CIELab pour améliorer la performance du traitement de bas niveau, la proposition d'un algorithme multi-niveau recherchant les équivalences de 'blob' pour résoudre le problème de suivi d'objets, et l'utilisation d'une hiérarchie de sémantique pour détecter les événements d'intérêt dans la surveillance des espaces publics. Un cadre complet d'un système de surveillance est présenté. Les objets dans une scène observée sont modélisés par des 'blob's qui sont détectés par la mise en œuvre du dictionnaire de modélisation d'arrière-plan adaptative basée sur les travaux de Kim et al. [1]. La mise en œuvre utilise un dictionnaire mis à jour dynamiquement dans lequel les blobs dans la vidéo sont caractérisées dans l'espace couleur, tout en traitant avec les ombres. Les collections de blobs, qui représentent des objets d'intérêt potentiel, sont suivies et classées en temps réel. Pour le suivi, nous employons un processus de corrélation simple basé sur un algorithme complexe de recherche d'équivalences de blob. L'essence de cet algorithme est de trouver la meilleure collection de blob basée sur la correspondance des tous les histogrammes potentiels de couleurs des cadres précédents à ceux obtenus dans le cadre actuel. Des lois sont utilisées pour résoudre les cas complexes comme les 'fantômes', l'occlusion, et les pistes perdues. Les objets sont alors classés comme étant des personnes animées ou des objets inanimés. Cela est essentiel pour fournir une description précise de la scène et pour faire les bonnes déductions par rapport aux événements et aux interactions d'objets. Une approche sémantique hiérarchique est utilisée pour la détection des événements, en partant de cette description. Le cadre proposé étudie une approche généralisée pour détecter une gamme de comportements fondés sur les interactions et les trajectoires d'objets. Ces comportements varient d'événements simples avec un seul agent, comme le flânage, aux événements plus complexes et interactifs, par exemple des personnes qui marchent ensemble. Les résultats expérimentaux sont présentés pour des vidéos standards et disponibles, puis sont comparés aux résultats existants dans la littérature afin de vérifier les performances du système. Ces résultats montrent une amélioration importante en termes de qualité et de vitesse, un pas vers un système plus fiable de surveillance entièrement automatisé.

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.