This thesis presents a vision-based interface for human-robot interaction and control for autonomous robots in arbitrary environments. Vision has the advantage of being a low-power, unobtrusive sensing modality. The advent of robust algorithms and a significant increase in computational power are the two most significant reasons for such widespread integration. The research presented in this dissertation looks at visual sensing as an intuitive and uncomplicated method for a human operator to communicate in close-range with a mobile robot. The array of communication paradigms we investigate includes, but are not limited to, visual tracking and servoing, programming of robot behaviors with visual cues, visual feature recognition, mapping and identification of individuals through gait characteristics using spatio-temporal visual patterns and quantifying the performance of these human-robot interaction approaches. The proposed framework enables a human operator to control and program a robot without the need for any complicated input interface, and also enables the robot to learn about its environment and the operator using the visual interface. We investigate the applicability of machine learning methods – supervised learning in particular – to train the vision system using stored training data. A key aspect of our work is a system for human-robot dialog for safe and efficient task execution under uncertainty. We present extensive validation through a set of human-interface trials, and also demonstrate the applicability of this research in the field on the Aqua amphibious robot platform in the under water domain. While ourframework is not specific to robots operating in the under water domain, vision under water is affected by a number of issues, such as lighting variations and color degradation, among others. Evaluating the approach in such difficult operating conditions provides a definitive validation of our approach. / Cette thèse présentera une interface basée sur la vision qui permet l'intéraction entre humains et robots et aussi le control de robots autonomes parcourant des environments indéfinis. La vision à l'avantage d'être une modalité sensorielle discrète et à faible puissance. La probabilité d'algorithmes complexes et une hausse significative de puissance computationelle sont deux des raisons les plus importantes d'en faire une intégration si répandue. La recherche présentée dans cette dissertation évalue la détection visuelle comme méthode simple et intuitive pour un opérateur humain de communiquer à courte portée avec un robot mobil. L'ensemble des modèles communicationnels étudiés inclus, sans tous les nommés, la localisation et l'inspection visuelle, l'utilisation de signaux visuels pour la programmation comportemental de robots, la reconnaissance visuelle, la reconnaissance d'individus par leurs mouvements corporels caractéristiques utilisant des motifs visuels spatio-temporels tout en quantifiant la performance de cette approche à l'intéraction entre humains et robots. La structure proposée permet à l'opérateur humain de programmer et contôler un robot sans la nécessité d'une interface à entrée de données complexe. Cette structure permet aussi au robot de reconnaître des caractéristiques clés de son environment et de son opérateur humain par l'ulisation d'une interface visuelle. L'étude de l'appplication possible des méthodes d'apprentissage ulitilisées par certaines machines, toujours sous supervision, permet d'entraîner le système visuel à utiliser ses bases de données. Un aspect important de cette recherche est l'élaboration d'un système de dialogues entre humains et robots permettant l'exécution sécuritaire et efficace de tâches aux délimitations incertaines. On présente une ample validation à travers de nombreux essais utilisant notre interface avec l'aide de cobayes humains. On démontre aussi les applications possibles de cette recherche au sein des utilisations aquatiques du Aqua, robot amphibien à plateforme. Alors que notre structure de recherche ne se spécialise pas dans la robotique aquatique, la vision sous l'eau est toujours affectée par de nombreux facteurs, notamment la lumunosité variante et la dégradation de couleur. L'évaluation de l'approche nécessaire dans de telles conditions opérationnelles difficiles crée une validation définitive de notre recherche.

Application Programming Interfaces (APIs) allow software developers to reuse code libraries, frameworks, or services without the need of having to implement relevant functionalities from scratch. The benefits of reusing source code or services through APIs have encouraged the adoption of APIs as the building blocks of modern-day software systems. However, leveraging the benefits of APIs require a developer to frequently learn how to use unfamiliar APIs --- a process made difficult by the increasing size of APIs, and the increase in the number of APIs with which a developer has to work. In this dissertation, we investigated some of the challenges developers encounter when working with unfamiliar APIs, and we designed and implemented new programming tools to assist developers in learning how to use new APIs. To investigate the difficulties developers encounter when learning to use APIs, we conducted a programming study in which twenty participants completed two programming tasks using real-world APIs. Through a systematic analysis of the screen captured videos and the verbalizations of the participants, we isolated twenty different types of questions the programmers asked when learning to use APIs, and identified five of the twenty questions as the most difficult for the programmers to answer in the context of our study. Drawing from varied sources of evidence, such as the verbalizations and the navigation paths of the participants, we explain why the participants found certain questions hard to answer, and provide new insights to the cause of the difficulties. To facilitate the API learning process, we designed and evaluated two novel programming tools: API Explorer and Introspector. The API Explorer tool addresses the difficulty a developer faces when the API types or methods necessary to implement a task are not accessible from the type the developer is working with. API Explorer leverages the structural relationships between API elements to recommend relevant methods on other objects, and to identify API types relevant to the use of a method or class. The Introspector tool addresses the difficulty of formulating effective queries when searching for code examples relevant to implementing a task. Introspector combines the structural relationships between API types to recommend types that should be used together with a seed to search for code examples for a given task. Using the types recommended by Introspector as search query, a developer can search for code examples across two code repositories, and in return, will get a list of code examples ranked based on their relevance to the search query. We evaluated API Explorer through a programming study, and evaluated Introspector quantitatively using ten tasks from six different APIs. The results of the evaluations suggest that these programming tools provide effective support to programmers learning how to use APIs. / Les interfaces de programmation (API) permettent aux développeurs de réutiliser du code, des bibliothèques, des cadres d'application ou des services sans avoir à réimplémenter des fonctionnalités importantes à partir de zéro. Les avantages de la réutilisation de code source ou de services par des APIs ont encouragé l'adoption des APIs comme composant essentiel des logiciels modernes. Cependant, pour tirer parti des avantages des APIs, les développeurs doivent fréquemment apprendre à utiliser des APIs inconnus, un processus rendu difficile par la taille grandissante des APIs et par l'augmentation du nombre d'APIs avec lesquels les développeurs doivent travailler. Dans cette dissertation, nous avons étudié les défis que les développeurs rencontrent quand ils travaillent avec des APIs inconnus et nous avons conçu et implémenté de nouveaux outils de programmation pour aider les développeurs à apprendre comment utiliser ces APIs. Pour étudier les difficultés que les développeurs rencontrent lorsqu'ils apprennent à utiliser les APIs, nous avons conduit une étude dans laquelle 20 participants ont complété deux exercices de programmation enutilisant des APIs populaires. Par une analyse détaillée des bandes vidéo enregistrées lors des exercices et des commentaires émis par les participants, nous avons isolé vingt différent types de questions que les programmeurs ont posées lorsqu'ils apprenaient à utiliser les APIs. Nous avons aussi identifié cinq questions sur les 20 comme étant les plus difficiles à répondre par les programmeurs dans le contexte denotre étude. Notre analyse fournit des éléments probants qui expliquent la cause des difficultés observées.Pour faciliter l'apprentissage des APIs, nous avons conçu et évalué deux outils de programmation: API Explorer et Introspector. API Explorer est un outil qui a pour but de diminuer la difficulté que les développeursrencontrent quand les types ou les méthodes nécessaire à l'accomplissement d'une tâche dans une API ne sont pas accessibles à partir du type avec lequel le développeur travaille. API Explorer tire parti des relations structurelles entre les éléments d'une API pour recommander des méthodes pertinentes sur d'autres objets et pour identifier les types d'une API pertinents pour l'utilisation d'une méthode ou d'une classe. Introspector est un outil qui a pour but de réduire la difficulté à formuler des requêtes efficaces lorsque les développeurs cherchent des exemples de code reliés à l'accomplissement d'une tâche de programmation. Introspector combine les relations structurelles entre les types d'une API pour recommander les types qui devraient être utilisés ensemble avec un germe pour chercher des exemples de code pour une tâche particulière. Un développeur peut ainsi chercher des exemples de code dans deux référentiels en utilisant les types recommandés par Introspector. En retour, l'utilisateur recevra une liste d'exemples de code triée en fonction de leur pertinence avec leur tâche courante. Nous avons évalué API Explorer grâce à une étude avec des utilisateurs et nous avons évalué quantitativement Introspector en analysant les résultats de dix tâches effectuées avec six APIs différents. Les résultats de notre évaluation suggèrent que les outils de programmation que nous proposons offrent un support efficace pour les programmeurs désirant apprendre à utiliser une API.

In computational complexity theory, a reduction is an approach to solving one problemby transforming it into another reference problem in which a solution already exists,thus providing the solution to the original problem in an efficient manner especiallywhen compared with solving the problem directly, which can be costly or even infeasible.The concept of reduction is not only limited to theory; in practice, humansuse past experience to solve problems by \emph{conforming} them, based on analogical reasoning, to known ones that are contained in references or memories.However, because the information retained in references is not always accurate and sometimes filled with redundancies or missing details, the conformation must somehow be robust enough to tolerate these uncertainties.In this thesis, we construct a framework for problem solving by reduction, and we present it in the robotics domain where contexts of problems can be represented using graphical spaces. The process has to match an input problem space to another one in a reference in order to retrieve a solution; we call this process spatial conformation. The content of this thesis can be divided into two parts.First, we develop a general approach and mathematical framework for a range of problem solving challenges to be addressed by reduction. Then we shift our attention to a class of constraint satisfaction problems formulated within the spatial conformation framework. An implementation for each part in robotics applications has been demonstrated to serve as empirical evaluation. / Selon la théorie de la complexité des algorithmes, une réduction est une approche pour résoudre unproblème en le transformant en un autre problème de référence qui a déjà été résolu. Ceci permet de trouver une solution à ce problème initial d'une manière efficace, comparemment à essayer de le résoudre directement, ce qui pourrait être coûteux ou même infaisable. Le concept de réduction n'est pas seulement constrainte à la théorie, en pratique,les humains utilisent leurs expériences pour résoudre de nouveaux problèmes en se basant surleurs raisonnements analogiques et en les conformant aux problémes qui se trouvent dans leurs références ou leurs souvenirs. Cependant, parce que les informations conservées dans les références ne sont pas toujours exactes etparfois manquent des détails, la conformation doit en quelque sorte être suffisamment robuste pour tolérer ces incertitudes. Dans cette thèse, nous construisons un systéme de résolution de problèmes basé sur la méthode de réduction, et nous le présentons dans le domaine de la robotique dans lequel les contextes des problèmes peuvent être représentés dans une espace geométrique. Nous définissons la conformation spatiale par le processus de correspondence entre un probléme d'origine et un autre probléme de référence. Tout d'abord, nous développons une approche générale pour résoudre une série de problèmes devant être traités par réduction. Par la suite, nous mettons l'accent sur une catégorie de problèmes de satisfaction de constraintesformulé dans le système de conformation spatiale. Une implémentation de chaque partie dans les applications de la robotique a été démontrée pour servir d'évaluation empirique.

This thesis proposes a novel probabilistic method for measuring anatomical connectivity in the brain based on measurements obtained from diffusion magnetic resonance imaging. We approach the problem of fibre tractography from the viewpoint that a computational theory should relate to the underlying quantity that is being measured--the anisotropic diffusion of water molecules in fibrous tissues. To achieve this goal, the prior probability of completion between two particular regions of interest is modelled by a 3D directional random walk, which is representative of the ensemble anisotropic displacement to which diffusion-MRI measurements have been sensitized. The 3D directional random walk is controlled by a set of stochastic differential equations whose solution provides the probability of passing through every state in space given initial source and sink regions. Under such a model, particles tend to travel in a straight line, with a slight perturbation in their 3D orientation at each step governed by two consecutive Brownian motions in the spherical components of the orientation. The probability density functions describing the likelihood of passing through a particular position and orientation in 3D, given an initial source region and a final sink region, are respectively called a stochastic source field and a stochastic sink field. The final stochastic completion field is estimated by the product of these two densities and it represents the probability of passing through a particular state in space, while bridging the gap between the two regions. We show that the maximum likelihood curves obtained under the 3D directional random walk are curves of least energy which minimize a weighted sum of curvature squared, torsion squared and length. The 3D directional random walk and the associated completion fields are an extension of Williams and Jacobs' 2D completion model for curve completion in the plane. We then develop an efficient, local and parallelizable computational method to obtain the stochastic completion fields by exploiting the Fokker-Planck equation of the 3D directional random walk. This partial differential equation describes the evolution of the probability distribution of particles following such a random process. Additionally, a rotation invariant solution is proposed using a spherical harmonics basis to capture directions on the 2-sphere. In analogy with the 2D model of completion, we introduce additional diffusion terms to make spatial advection errors isotropic. The 3D stochastic completion field is further adapted to those problems where dense orientation data is present, as is the case for diffusion MRI measurements. The insertion of angular drift terms into the overall stochastic process provides a principled way to compute completions, while exploiting the local orientation information available at each voxel in the volume. Our algorithm provides a novel index of connectivity between two regions of interest, which is based on the overall probability for the computed completion curves between the two. We then discuss an alternative model of the directional random walk, where the 3D orientation change is drawn from a single distribution, i.e., a 3D Brownian distribution.The performance of the stochastic completion field algorithm is validated qualitatively and quantitatively on diffusion-MRI data from biological phantoms and on synthetic data. In vivo human data from 12 subjects is then used to investigate the algorithm's performance qualitatively by comparing the output of our method with published results based on another tractography method. Finally, we conclude by discussing the advantages and limitations of the method developed in this thesis and suggest directions for future work. / Cette thèse propose un nouveau cadre probabiliste pour la reconstruction de la connectivité anatomique dans le cerveau basée sur les données obtenues avec l'imagerie de diffusion par résonance magnétique. Nous abordons le problème de la tractographie par le point de vue qu'une théorie basée sur des calculs numériques doit se rapporter à la quantité sous jacente qui est mesurée-la diffusion anisotropique des molécules d'eau. Pour atteindre cet objectif, la probabilité de complétion à priori entre deux régions d'intérêt est modélisée par une marche aléatoire tridimensionnelle (3D), représentative du déplacement anisotropique local capturé par l'IRM de diffusion. La marche aléatoire 3D varie selon un ensemble d'équations différentielles stochastiques dont la solution fournit la probabilité de passage entre tous les états dans l'espace, étant donné une source initiale et des régions d'intérêts. Dans un tel modèle, les particules ont tendance à se diriger en ligne droite à chaque passage, avec une légère perturbation dans leur orientation tridimensionnelle provenant de mouvement Brownien dans chaque composante de l'orientation. Étant données initialement une région source et une région finale, les fonctions de densité de probabilité décrivant la vraisemblance de passage par une position et orientation tridimensionnelle sont respectivement nommées champ stochastique source et champ stochastique d'intérêt. Le champ stochastique final est estimé par le produit de ces deux densités et représente la probabilité de passage par un état particulier dans l'espace. Nous montrons que les courbes de maximum de vraisemblance obtenues par le procédé de marche aléatoire directionnelle 3D est la courbe de moindre énergie qui minimise la somme pondérée de la courbature au carrée, de la torsion au carrée et de la longueur. La marche aléatoire directionnelle 3D et ses champ de complétion sont une extension du modèle de complétion de Williams et Jacobs pour la complétion 2D.Nous développons ensuite un modèle de calcul efficace, local et parallellisable pour calculer les champs de complétion stochastiques en exploitant l'équation Fokker-Planck de la marche aléatoire directionnelle 3D. Cette équation différentielle partielle décrit l'évolution de la distribution de probabilité pour les particules de suivre un tel processus aléatoire. De plus, une solution invariante par rotation est proposée en utilisant la base des fonctions harmoniques sphériques afin de capturer la direction sur la sphere. En analogie avec le modèle de complétion 2D, nous introduisions des termes de diffusion additionnels pour rendre les erreurs d'advection spatiales isotropiques. Le champ de complétion stochastique 3D est également adapté plus avant lorsque les données d'orientation sont dense, comme c'est le cas pour l'IRM de diffusion. L'insertion de termes de dérive angulaire dans le processus stochastique global fournit un moyen de calculer les complétions tout en exploitant les informations locales d'orientation accessibles dans chaque voxel. Notre algorithme fournit ainsi une nouvelle mesure de la connectivité entre deux régions d'intérêt en se basant sur la probabilité globale des courbes de complétions entre elles. Nous discutions ensuite d'un modèle alternatif de marche directionnelle aléatoire directionnelle, où la perturbation angulaire provient d'une seule distribution, i.e., une distribution 3D brownienne.Les performances de l'algorithme de champ de complétion sont validées qualitativement et quantitativement sur des données d'IRM de diffusion provenant de fantômes synthétiques et biologiques. Les données humaines acquises in vivo sur 12 patients sont utilisées pour comparer les performances de l'algorithme que nous proposons avec d'autres méthodes de tractographie de l'état de l'art. Nous concluons finalement par une discussion sur les avantages et les limitations de la méthode développée dans cette thèse et suggérons des orientations pour les travaux futurs.

Reinforcement Learning has emerged as a useful framework for learning to perform a task optimally from experience in unknown systems. A major problem for such learning algorithms is how to balance optimally the exploration of the system, to gather knowledge, and the exploitation of current knowledge, to complete the task. Model-based Bayesian Reinforcement Learning (BRL) methods provide an optimal solution to this problem by formulating it as a planning problem under uncertainty. However, the complexity of these methods has so far limited their applicability to small and simple domains. To improve the applicability of model-based BRL, this thesis presents several extensions to more complex and realistic systems, such as partially observable and continuous domains. To improve learning efficiency in large systems, this thesis includes another extension to automatically learn and exploit the structure of the system. Approximate algorithms are proposed to efficiently solve the resulting inference and planning problems. / L'apprentissage par renforcement a émergé comme une technique utile pour apprendre à accomplir une tâche de façon optimale à partir d'expérience dans les systèmes inconnus. L'un des problèmes majeurs de ces algorithmes d'apprentissage est comment balancer de façon optimale l'exploration du système, pour acquérir des connaissances, et l'exploitation des connaissances actuelles, pour compléter la tâche. L'apprentissage par renforcement bayésien avec modèle permet de résoudre ce problème de façon optimale en le formulant comme un problème de planification dans l'incertain. La complexité de telles méthodes a toutefois limité leur applicabilité à de petits domaines simples. Afin d'améliorer l'applicabilité de l'apprentissage par renforcement bayésian avec modèle, cette thèse presente plusieurs extensions de ces méthodes à des systèmes beaucoup plus complexes et réalistes, où le domaine est partiellement observable et/ou continu. Afin d'améliorer l'efficacité de l'apprentissage dans les gros systèmes, cette thèse inclue une autre extension qui permet d'apprendre automatiquement et d'exploiter la structure du système. Des algorithmes approximatifs sont proposés pour résoudre efficacement les problèmes d'inference et de planification résultants.

With the advancement in technology, software systems are more and more in control of devices that we use in our daily lives. Complex computer systems are increasingly built for highly critical tasks. Failures of such systems may have severe consequences ranging from loss of business opportunities, physical damage, to loss of human lives. Systems with such responsibilities should be highly dependable. Discovering and documenting potential abnormal situations and irregular user behavior that can interrupt normal system interaction is of tremendous importance in the context of dependable systems development. Exceptions that are identified during requirements elicitation have to be systematically carried over to a subsequent analysis phase, and included in the system specification in order to ensure that the implementation of the system later on can deal with all relevant exceptional situations. This thesis advocates a more methodical approach to exception handling by extending the requirements elicitation and analysis phases of the Fondue development process to address exceptions. Exceptions are discovered at the requirements stage of software development using a use-case based approach, and then mapped to the Fondue specification models: the environment model, in which exceptional messages that signal exceptional situations to the system, the concept model, in which exceptional state is specified that keeps track of the failures of secondary actors, and the operation model, in which recovery functionality is specified. The proposed ideas are illustrated by a comprehensive case study, the 407 ETR Electronic Toll Collection system. / Avec les avancements d'aujourd'hui, les appareils que nous utilisons dans notre vie quotidienne sont de plus en plus dans contrôles des systèmes informatiques. Les systèmes informatiques complexes prennent une nouvelle importance dans la réalisation des tâches hautement critiques. Un échec dans un tel système peut causer des pertes d'occasions d'affaires, des dommages physiques ou, dans le pire des cas, la perte de vies humaines. Les systèmes avec de telles responsabilités doivent être très fiables. La découverte et la documentation des situations potentiellement anormales, sans oublier le comportement irrégulier d'utilisateur qui peut interrompre les interactions régulières du système, sont d'une grande importance dans le contexte de développement de systèmes fiables. Les exceptions qui sont identifiées pendant la phase de collecte des spécifications doivent être systématiquement utilisées a la phase d'analyse, et doivent être également intégrées dans les spécifications systèmes pour assurer que l'implémentation du système peut réagir a toutes les situations exceptionnelles relatives. Cette thèse propose une approche plus méthodique pour la gestion des exceptions en prolongeant les phases de collection de spécifications et d'analyse du processus de développement Fondue pour y ajouter la gestion d'exceptions. Les exceptions sont découvertes dans la phase de spécification du cycle de développement en utilisant une approche cas d'utilisation "use case", pour ensuite les associer aux modèles de spécification Fondue : le modèle d'environnement ou se trouve les messages exceptionnels qui sont envoyés au système dans le cas d'une situation exceptionnelle, le modèle conceptuel, ou les états exceptionnels sont spécifiés un suivi des échecs des acteurs secondaires est effectué; et finalement le modèles opérationnel, ou les fonctionnalités sont spécifiées. Les idées proposées sont illustrées par une étude de cas é

This thesis addresses the problem of creating linguistic taggers for resource-poor languages using existing taggers in resource rich languages. Linguistic taggers are classifiers that map individual words or phrases from a sentence to a set of tags. Part of speech tagging and named entity extraction are two examples of linguistic tagging. Linguistic taggers are usually trained using supervised learning algorithms. This requires the existence of labeled training data, which is not available for many languages. We describe an approach for assigning linguistic tags to sentences in a target (resource-poor) language by exploiting a linguistic tagger that has been configured in a source (resource-rich) language. The approach does not require that the input sentence be translated into the source language. Instead, projection of linguistic tags is accomplished through the use of a parallel corpus, which is a collection of texts that are available in a source language and a target language. The correspondence between words of the source and target language allows us to project tags from source to target language words. The projected tags are further processed to compute the final tags of the target language words. A system for part of speech (POS) tagging of French language sentences using an English language POS tagger and an English/French parallel corpus has been implemented and evaluated using this approach. A parallel corpus of the source and target languages might not be readily available for many language pairs. To deal with this problem, we describe a system for automatic acquisition of aligned, bilingual corpora from pre-specified domains on the World Wide Web. The system involves automatic indexing of a given domain using a web crawler, identifying pairs of pages that are translations of one another, and aligning bilingual texts at the sentence level. Using this approach we create a 40,000,000 word English-French parallel corpus from the Government of Canada d / Le sujet de cette thèse est la création de marqueurs linguistiques pour les langues qui sont pauvres en ressources en utilisant les marqueurs des langues riches en ressources. Les marqueurs linguistiques sont des classificateurs qui conjuguent des mots ou des collections des mots d'une phrase à un ensemble d'étiquettes. La description de nature grammatical et l'extraction des entités nommées sont deux exemples de marquage linguistique. L'apprentissage supervisé est l'outil principal utilisé pour créer des marqueurs linguistiques. Cela exige l'existence de données de formation marqués qui n'est pas disponible dans plusieurs langues. Nous décrivons une approche pour étiquer les phrases d'une langue cible qui est pauvre en ressources en utilisant un marqueur linguistique qui a été configuré dans une langue d'origine qui est riche en ressources. Cette approche n'exige pas que la phrase entrée doit être traduite dans la langue d'origine. Au lieu de cela, les étiquettes linguistiques sont projetées grâce à l'utilisation d'un corpus parallèle (une collection de textes qui sont disponibles dans plus d'une langues) entre la langue cible et la langue d'origine. La correspondence entre les mots de la langue cible et la langue d'origine nous permet de projeter les étiquettes entre les phrases de ces deux langues. Les étiquettes projetées sont traitées pour calculer l'étiquage finale de la phrase de la langue cible. Pour tester cette approche, un descripteur de nature grammaticale de langue française a été mis en oeuvre et évalué en utilisant un descripteur de nature grammaticale de langue anglaise et un corpus parallèle Anglais/Français. Un corpus parallèle entre la langue d'origine et la langue cible n'est pas toujours disponible pour plusieurs langues. Pour résoudre ce problème, nous décrivons un système d'acquisition automatique d'un corpus parallèle à partir du Web. Le corpus est extrait d'un domaine spécifique et automatiquem

Integer least squares (ILS) problems arise from many applications, such as communications, lattice design, and global navigation satellite systems. However, an ILS problem is NP-hard. The objective of this thesis is to design efficient algorithms for solving box-constrained overdetermined integer least squares (BOILS) problems and box-constrained underdetermined integer least squares (BUILS) problems. A typical method to solve ILS problems consists of two stages: reduction and search. For solving the BOILS problems, we propose a new reduction algorithm and a modified search algorithm. Unlike the usual reduction algorithms which only reorder the columns of the lattice generator matrix, the new reduction algorithm also employs the integer Gauss transformations during the reordering process. Simulation results show that our new method makes the search process perform more efficiently than existing algorithms. For solving the BUILS problems, we present three algorithms: recursive generalized sphere decoding (GSD) algorithm, partial regularization algorithm, and tree search decoder. The main part of the recursive GSD algorithm recursively partitions the candidate set for the unknown integer vector into disjoint ordered subsets. The main idea of the partial regularization algorithm is to transform a BUILS problem to an equivalent BOILS problem by using part of the unknown integer vector to do the regularization. Some strategies are proposed to enhance the efficiency of this algorithm. The tree search decoder uses a depth-first tree search process to solve a BUILS problem. For each of these algorithms, various reduction strategies are proposed, which can significantly reduce the computational cost of the corresponding search process. Simulation results indicate that the recursive GSD algorithm is usually faster than other GSD algorithms in the literature, the partial regularization algorithm is the most efficient one among the existing algorithms for moderately underde / Les problèmes de moindres carrés en nombres entiers apparaissent dans plusieurs domaines, dont les télécommunications, la conception de grilles, et la navigation par système de positionnement mondial. Malheureusement, ces problèmes sont de difficulté NP. Le but de cette thèse est de concevoir des algorithmes efficaces pour la résolution de problèmes de moindres carrés en nombres entiers, soit hyperdéterminés ou hypodéterminés, avec contraintes de boîtes. Les méthodes typiques pour résoudre ces problèmes contiennent deux stages: la réduction et la recherche. Pour les problèmes hyperdéterminés, nous proposons un nouvel algorithme de réduction et un algorithme de recherche modifié. Contrairement aux algorithmes existants, qui ne font que trier les colonnes de la matrice génératrice de grille, notre nouvel algorithme de réduction utilise aussi la transformation de Gauss durant le tri. Nos simulations démontrent que notre nouvelle méthode rend le processus de recherche plus rapide. Pour les problèmes hypodéterminés, nous proposons trois nouveaux algorithmes: un algorithme récursif généralisé de décodage par sphère (GDS), un algorithme de régularization partielle (RP), et un algorithme de recherche arborescente (RA). L'algorithme GDS partitionne les solutions réalisables récursvivement en plusieurs ensembles ordonnés et disjoints. L'algorithme RP transforme le problème hypodéterminé en un problème hyperdéterminé équivalent. Nous proposons des stratégies pour rendre cet algorithme plus efficace. L'algorithme RA utilise un processus de recherche en profondeur. Pour chacun de ces trois algorithmes, nous proposons plusieurs stratégies de réduction. Celles-ci peuvent réduire la complexité de l'algorithme de recherche correspondant. Nos simulations démontrent que l'algorithme GDS est habituellement plus rapide que les algorithmes existants, que l'algorithme RP est le plus rapide pour les problèmes peu hypodétermin

Compiler toolkits make it possible to rapidly develop compilers and translators for new programming languages. Recently, toolkit writers have focused on supporting extensible languages and systems that mix the syntaxes of multiple programming languages. However, this work has not been extended down to the lexical analysis level. As a result, users of these toolkits have to rely on ad-hoc solutions when they extend or mix syntaxes. This thesis presents MetaLexer, a new lexical specification language that remedies this deficiency. MetaLexer has three key features: it abstracts lexical state transitions out of semantic actions, makes modules extensible by introducing multiple inheritance, and provides cross-platform support for a variety of programming languages and compiler front-end toolchains. In addition to designing this new language, we have constructed a number of practical tools. The most important are a pair of translators that map MetaLexer to the popular JFlex lexical specification language and vice versa. We have exercised MetaLexer by using it to create lexers for three real programming languages: AspectJ (and two extensions), a large subset of Matlab, and MetaLexer itself. The new specifications are easier to read and require much less action code than the originals. / Les outils de compilation moderne permettent de développer rapidement des compilateurs pour de nouveaux langages de programmation. Récemment, les auteurs de ces outils ont travaillé à supporter des langages et systèmes extensibles qui mélangent la syntaxe de plusieurs langages de programmation. Cependant, ce travail n'a pas été étendu au niveau de l'analyse lexicale. Le résultat est que les utilisateurs de ces outils doivent se fier à des solutions improvisées quand ils augmentent ou mélangent la syntaxe de leurs langages. Cette thèse présente MetaLexer, un nouveau langage de spécification lexical qui remédie à ce manque.MetaLexer a trois aspects principaux: il sépare les transitions d'états lexicaux des actions sémantiques, il rend les modules extensibles en introduisant un système d'héritage multiple, et il offre un support multi-plateforme pour une variété de langages de programmation et d'outils de compilation.En plus de la conception de ce nouveau langage, nous avons implémenté un nombre d'outils pratiques. Le plus important étant une pair de programmes de traduction qui traduisent de MetaLexer au populaire JFlex et vice-versa.Nous avons testé MetaLexer en l'utilisant pour créer des spécifications lexicales pour trois languages de programmations: AspectJ (et deux extensions), un large sous-ensemble du langage Matlab, et MetaLexer lui-même. Les nouvelles spécifications sont plus lisibles et demandent beaucoup moins de code d'action que les originales.

In recent years, there has been an increase in the popularity of dynamic languages such as Python, Ruby, PHP, JavaScript and MATLAB. Programmers appreciate the productivity gains and ease of use associated with such languages. However, most of them still run in virtual machines which provide no Just-In-Time (JIT) compilation support, and thus perform relatively poorly when compared to their statically compiled counterparts. While the reference MATLAB implementation does include a built-in compiler, this implementation is not open sourced and little is known abouts its internal workings. TheMcVMproject has focused on the design and implementation of an optimizing virtual machine for a subset of the MATLAB programming language. / Virtual machines and JIT compilers can benefit from advantages that static compilers do not have. It is possible for virtual machines to make use of more dynamic information than static compilers have access to, and thus, to implement optimization strategies that are more adapted to dynamic languages. Through theMcVMproject, some possible avenues to significantly improve the performance of dynamic languages have been explored. Namely, a just-in-time type-based program specialization scheme has been implemented in order to take advantage of dynamically available type information. / One of the main contributions of this project is to provide an alternative implementation of the MATLAB programming language. There is already an open source MATLAB interpreter (GNU Octave), but our implementation also includes an optimizing JIT compiler and will be open sourced under the BSD license. McVM aims to become a viable implementation for end-users, but could also see use in the compiler research community as a testbed for dynamic language optimizations. In addition to the contribution of the McVM framework itself, we also contribute the design and implementation of a novel just-in-time type-based program specialization system aimed at dynamic languages. / The novel specialization system implemented in McVM shows much promise in terms of potential speed improvements, yielding performance gains up to 3 orders of magnitude faster than competing implementations such as GNU Octave. It is also easily adaptable to other dynamic programming languages such as Python, Ruby and JavaScript. The investigation of performance issues we make in this thesis also suggests future research directions for the design of dynamic language compilers of the future. / Ces dernières années, il y a eu une augmentation de la popularité des langages dynamiques tels que Python, Ruby, PHP, JavaScript et MATLAB. Les programmeurs apprécient les gains de productivité et la facilité d'utilisation associée à ces langues. Cependant, la plupart de ces langages s'exécutent encore dans des machines virtuelles qui ne fournissent aucun support pour la compilation à la volée, et ont donc une performance inférieure si on les compare à leurs homologues compilés statiquement. Bien que l'implémentation de référence de MATLAB comprenne un compilateur intégré, cette application n'est pas open source et son fonctionnement interne demeure un secret industriel. Le projet McVM a mis l'accent sur la conception et l'implémentation d'une machine virtuelle optimisée pour un sous-ensemble du langage de programmation MATLAB. / Les machines virtuelles et les compilateurs à la volée peuvent bénéficier d'avantages que les compilateurs statiques n'ont pas. Il est possible pour les machines virtuelles de faire usage d'informations dynamique à laquelle les compilateurs statiques n'ont pas accès, et donc, de mettre en oeuvre des stratégies d'optimisation qui sont plus adaptées aux langages dynamiques. à travers le projet McVM, plusieurs avenues possibles pour améliorer considérablement la performance des langages dynamiques ont été explorées. Entre autre, un système de spécialisation de programmes à la volée permettant de profiter d'informations sur les types disponible dynamiquement a été implémenté. / L'une des principales contributions de ce projet est de fournir une implémentation alternative du langage de programmation MATLAB. Il existe déjà un interpréteur MATLAB open source (GNU Octave), mais notre application comprend également un compilateur à la volée optimisé et sera distribuée sous la licence open source BSD. McVM vise à devenir une implémentation viable pour les utilisateurs finaux, mais pourrait aussi être utilisée dans le milieu de la recherche sur les compilateurs comme outil d'expérimentation. En plus de la contribution du logiciel intégré McVM lui-même, nous avons également contribué à la conception et la réalisation d'un système de spécialisation de programme à la volée visant à l'optimisation des langages dynamiques. / Le système de spécialisation mis en oeuvre dans McVM se montre très prometteur en termes de potentiel d'améliorations de la vitesse d'exécution, permettant des gains de performance allant jusqu'à trois ordres de grandeur comparés aux implémentations concurrentes telles que GNU Octave. Il est également facilement adaptable à d'autres langages de programmation dynamique tels que Python, Ruby et JavaScript. L'examen des problèmes de performance que nous faisons dans cette thèse suggère aussi des pistes de recherche pour la conception des compilateurs de langages de programmation dynamiques de l'avenir.