Many geometric problems are intrinsically linked to the issue of splitting or classifying points. We investigate two such families of problems in two separate branches of research. Guarding problems are motivated by the issue of guarding a region with security cameras or illuminating it with lights. Such problems have been studied for decades, but there are two significant guarding problems whose complexity is not completely understood. First, we investigate the problem of guarding simple polygons; this problem is known to be NP-complete but its approximability is not known. Second, we investigate the complexity of guarding monotone chains, also known as 1.5-dimensional terrains. Understanding the interaction of 'visibility polygons' and how they separate point sets is crucial for the investigation of such problems. We resolve a significant open problem by proving strong NP-completeness for terrain guarding. We also present an approximation algorithm for guarding simple polygons with perimeter guards; this new algorithm improves the state of the art.A geometric split tree is a data structure for storing point sets that recursively splits the space, and in turn the data, in some random way. Understanding the distribution of such a tree's structure is a matter of understanding the distribution of the splits. We investigate the distributions associated with several natural splitting methods. We make new connections between an important problem in discrete geometry and natural probability distributions. With the goal of analyzing geometric split trees based on their splits, we introduce a random tree model that is general while still allowing powerful comparisons with random trees from more restricted models. / Beaucoup de problèmes géométriques sont intrinsèquement liés à la question de la division ou classification des points. Nous étudions deux familles de problèmes dans deux branches distinctes de recherche. Les problèmes de surveillance sont motivés par la question de la surveillance d'une région avec des caméras de sécurité ou d'éclairage avec des feux. Ces problèmes ont été étudiés depuis des décennies, mais il y a deux problèmes importants dont la complexité n'est pas complètement élucidée. Tout d'abord, nous étudions le problème de surveiller des polygones simples. Ce problème est connu pour être NP-complet, mais son approximabilité n'est pas connue. Deuxièmement, nous étudions la complexité de surveiller des chaînes monotones, aussi connues comme terrains en dimension 1,5. Comprendre l'interaction des polygones de visibilité et la façon dont ils divisent les ensembles de points est crucial pour l'étude de ces problèmes. Nous résoudrons un problème important ouvert en prouvant que surveiller les terrains est fortement NP-complet. Nous présentons également un algorithme d'approximation pour la surveillance des polygones simples avec des gardes sur le périmètre. Ce nouvel algorithme améliore l'état de l'art.Un arbre de division géométrique est une structure de données pour stocker des ensembles de points qui divise de manière récursive l'espace, et aussi les données, d'une certaine manière aléatoire. Le compréhension de la répartition de la structure d'un tel arbre est une question de compréhension des répartitions des divisions. Nous étudions les répartitions associées à plusieurs méthodes de division naturelles. Nous faisons de nouvelles connexions entre un problème important en géométrie discrète et des distributions de probabilité naturelles. Dans le but d'analyser les arbres de division géométriques en fonction de leurs divisions, nous introduisons un modèle d'arbre aléatoire qui est général tout en permettant des comparaisons puissants avec les arbres aléatoires dans des modèles plus restreints.

Model Driven Engineering (MDE) research has achieved major progress in the past fewyears. Though MDE research and adoption are moving forward at an increasing pace,there are still few major challenges left to be addressed. Model Transformations (MT)represent an essential part of MDE that is gradually reaching maturity level. Testing MThas been shown to be a challenging task due to a new set of problems. In this thesis weattempt to complement the work done so far by the research community to address MTtesting challenges.We use findings from the research in classical testing to create a prospective view on MTtesting challenges and opportunities. More specifically, we focus on two challenges : ModelComparison and automating testing execution through a Testing Framework. First,we introduce a model comparison approach (based an existing graph comparison algorithm)that is customizable, and fine tuned to performs best in testing situations. Theperformance of our algorithm is throughly investigated against different types of models.Second, we introduce TUnit : a modelled framework for testing Model transformations.We demonstrate the benefit of using TUnit in supporting the process of testing transformationsin regression testing and enabling semantic equivalence through extending ourcase study to perform a comparison of coverability graphs of Petri Nets. / La recherche sur le Model Driven Engineering (MDE) a accomplit de grands progrèsau cours des dernières années. Bien que la recherche et l'adoption avancent à grandspas, il reste encore plusieurs défis majeurs à adresser. La Transformation de Modèle(TM) représente un élément essentiel du MDE qui atteint graduellement le niveau dematurité. Le test sur les TM s'est démontré être une tˆache difficile en raison des nouveauxproblèmes survenus. Dans cette thèse, nous essayons de complémenter le travail complétépar la communauté de recherche pour adresser les défis restants des tests sur les TM.Nous utilisons les résultats de la recherche en tests classiques pour créer une visionprospective sur les défis et opportunités des tests sur les TM. Nous nous concentrons plusprécisement sur les deux défis suivants : la comparaison des modèles et l'automation destests exécutés à travers un cadre de tests . Tout d'adord, nous présentons une approcheen comparaison de modèles qui peut être personnalisée et atteint de meilleurs résultatsdans des situations de tests. La performance de notre algorithme est rigoureusementétudiée contre différents types de modèles. Deuxièmement, nous introduisons Tunit : uncadre de tests en transformation de modèles qui est aussi un modèle. Nous démontronsles avantages d'utiliser TUnit pour donner un support au processus de tests sur lestransformations en tests de regression et permettre l'équivalance sémantique.

Solving an integer least squares (ILS) problem usually consists of two stages: reduction and search. This thesis is concerned with the reduction process for the ordinary ILS problem and the ellipsoid-constrained ILS problem. For the ordinary ILS problem, we dispel common misconceptions on the reduction stage in the literature and show what is crucial to the efficiency of the search process. The new understanding allows us to design a new reduction algorithm which is more efficient than the well-known LLL reduction algorithm. Numerical stability is taken into account in designing the new reduction algorithm. For the ellipsoid-constrained ILS problem, we propose a new reduction algorithm which, unlike existing algorithms, uses all the available information. Simulation results indicate that new algorithm can greatly reduce the computational cost of the search process when the measurement noise is large. / La résolution de problèmes de moindres carrés en nombres entiers (ILS) comprend habituellement deux stages: la réduction et la recherche.Cette thèse s'intéresse à la réduction pour le problème ILS ordinaire et le problème ILS sous contrainte d'ellipse. Pour le problème ILS ordinaire, nous dissipons des erreurs communes de compréhension à propos de la réduction dans la littérature et nous montrons ce qui est réellement crucial pour l'efficacité de la recherche. Ce résultat nous permet de développer un nouvel algorithme de réduction plus efficace que le célèbre algorithme LLL. La stabilité numérique est prise en compte dans le développement du nouvel algorithme.Pour le problème ILS sous contrainte d'ellipse, nous proposons un nouvel algorithme de réduction qui, contrairement aux algorithmes existants, utilise toute l'information disponible. Les résultats de simulations indiquent que le nouvel algorithme réduit considérablement les coûts de calcul de la recherche lorsque la variance du bruit est large dans le modèle linéaire.

This dissertation investigates spatial sound production and reproduction technology as a mediator between music creator and listener. Listening experiments investigate the perception of spatialized music as a function of the listening position in surround-sound loud- speaker setups.Over the last 50 years, many spatial sound rendering applications have been developed and proposed to artists. Unfortunately, the literature suggests that artists hardly exploit the possibilities offered by novel spatial sound technologies. Another typical drawback of many sound rendering techniques in the context of larger audiences is that most listeners perceive a degraded sound image: spatial sound reproduction is best at a particular listening position, also known as the sweet spot.Structured in three parts, this dissertation systematically investigates both problems with the objective of making spatial audio technology more applicable for artistic purposes and proposing technical solutions for spatial sound reproductions for larger audiences.The first part investigates the relationship between composers and spatial audio technology through a survey on the compositional use of spatialization, seeking to understand how composers use spatialization, what spatial aspects are essential and what functionalities spatial audio systems should strive to include.The second part describes the development process of spatializaton tools for musical applications and presents a technical concept. The Virtual Microphone Control (ViMiC) system is an auditory virtual environment that recreates a recording situation through virtual sound sources, virtual room properties and virtual microphones. A technical concept is presented to facilitate artistic work with spatial audio systems and to allow the combination of different spatialization tools.The third part investigates the perception of spatialized sounds as a function of the listening positions in multichannel sound systems. Perceptual experiments were designed to understand the multidimensional nature of an off-center sound degradation and to propose concepts to improve the listening conditions for larger audiences.This research extends our understanding of spatial audio perception and has potential value to all those interested in spatial audio quality, including designers, creators and specialists in the fields of acoustics, music, technology and auditory perception. / Cette thèse a pour objet l'étude des dispositifs de production et de reproduction des sons spatialisés. Plus particulièrement, ce travail comporte plusieurs expériences évaluant l'influence de la position d'un auditeur au sein d'un dispositif de haut-parleur de type "surround" sur la perception d'oeuvres musicales. Au cours des 50 dernières années, de nombreuses applications destinées à la mise en espace de sources sonores ont vu le jour. Cependant, deux problèmes principaux persistent. D'une part, il semble que les artistes n'exploitent que très superficiellement le potentiel de ces nouveaux outils de création. D'autre part, dans la majeure partie des cas, lorsque les dispositifs de reproduction de sons spatialité sont utilisés pour un grand nombre de spectateurs, seulement une fraction du public peut vraiment percevoir les nuances et subtilités de la spatialisation; ces privilégiés se situent dans une zone d'écoute plus connue sous le nom de "sweet spot", caractéristique des systèmes de reproduction du son dans l'espace. La recherche systématique de solutions à ces deux problèmes constituent le cœur de ce travail. Cette thèse est divisée en trois parties. Dans la première, grâce à un sondage effectué auprès de compositeurs, nous avons essayé de mieux cerner comment la spatialisation s'intègre dans leur processus de composition, et aussi quels sont leurs exigences vis-a-vis des systèmes de spatialisation afin de faire l'inventaire des fonctionnalités essentielles d'un tel système. Dans la seconde partie de cette thèse, le développement d'un nouvel outil pour la mise en espace de sources sonores est présenté: le système Virtual Microphone Control (ViMiC). Cette application est un environnement auditif virtuel (EAV) qui permet de recréer des conditions d'enregistrement particulières grâce à la modélisation de salles, de microphones et de sources sonores. Une approche technique permettant l'utilisation facile de plusieurs outils de spatialisation à des fins artistiques est aussi présentée. Enfin, dans la troisième partie de cet ouvrage, les résultats de différentes études perceptives sont détaillés pour identifier l'influence de la position des auditeurs lors de performances en son "surround". Ces études ont été mises en place afin de caractériser de manière approfondie la dégradation de la perception sonore en fonction de la position d'un auditeur. Des solutions pratiques permettant de minimiser ces effets négatifs sont aussi proposés. Ce travail de recherche permet d'étendre notre compréhension de la perception des sons spatialisés. D'autre part, cette étude est certainement précieuse pour ceux et celles travaillant à l'amélioration de la qualité des sons spatialisé, qu'ils soient techniciens, compositeurs, spécialistes en acoustique, en musique ou encore en perception auditive.

Digital media has become the preferred approach for producing, selling, and consuming information goods such as books, software, movies, and songs. Information objects produced in digital form can be easily modified, copied, and can be effortlessly distributed using the Internet. Today, online social networking systems have become one of the most popular ways for sharing and distributing content. Despite their growing popularity, many unsolved problems exist with regard to digital object distribution in online social networks. A key problem related to sharing of information goods is usage control of the shared good. Another problem related to usage control is digital rights management, where the usage conditions set by the content creator need to be enforced.In this thesis, we propose new solutions that leverage social factors in order to address the sharing control and rights management problems. In information sharing problem, the owner of a data object wants to share the object with another party in the social network and enforce usage conditions on the shared object. To address this problem, we propose a Social Sharing Control (SSC) scheme for information sharing in large-scale collaborative systems based on the risk involved in the sharing activity. The SSC utilizes game theoretic models for the sharing activities along with other factors in order to assess the sharing risk. Using simulation studies, we analyze the effects of the social network structure and evolution on the SSC scheme.In digital rights management, the content distributor wants to maintain control over the access and usage of the content. To deal with this problem, we propose Social Distribution Network (SDN) a novel distribution system that uses economic and social factors to incentivize the users to conform to copyright restrictions. SDN leverages ideas from group lending to encourage users to segregate into groups. The groups receive economic incentives in the form of discounts based on their purchase and piracy histories. We use utility based analysis to establish certain conditions that are necessary for proper functioning of the SDN. Also, using simulations, we examine the evolution of incentives with time under dynamic network conditions. / Les médias numériques sont devenus le moyen le plus pratique et efficace de produire, distribuer et consommer des contenus tels les livres, les logiciels, les films et la musique. Les objets numériques peuvent être modifiés, copiés et redistribués très facilement à l'aide d'Internet. Le partage des fichiers numériques se fait de plus en plus par l'entremise des réseaux sociaux en ligne et ce, malgré plusieurs problèmes à cet égard. Parmi ces problèmes se trouvent le contrôle du contenu partagé et la gestion des droits numériques visant l'application de règles établies par le créateur du contenu en question.Cette thèse propose de nouvelles solutions utilisant des facteurs sociaux pour traiter les problèmes de contrôle de distribution et de gestion des droits numériques. Le problème du contrôle de la distribution des objets numériques survient lorsque le propriétaire d'un objet numérique veut partager cet objet avec un ou plusieurs tiers tout en gardant le contrôle sur l'utilisation de l'objet en question. À cet effet, nous proposons un système de contrôle du partage (dit "Social Sharing Control" ou SSC) permettant le partage des objets numériques basé sur les risques associés au partage. Le SSC calcule le niveau de risque associé au partage par la théorie des jeux, entre autre. À l'aide de simulations, nous analyserons les effets qu'ont la structure des réseaux sociaux et son évolution sur le SSC.Le problème de la gestion des droits numériques se pose lorsqu'un distributeur de contenu numérique cherche à contrôler l'accès et l'utilisation de ce contenu une fois distribué sur le réseau. Nous abordons le problème en proposant un réseau de distribution social (dit "Social Distribution Network" ou SDN) utilisant des facteurs économiques et sociaux pour inciter les utilisateurs à se conformer aux règles du droit d'auteur. Le SDN met à profit des idées provenant de la théorie des prêts de groupe pour encourager la formation de regroupements socio-économiques d'utilisateurs. Ces groupes ont droits à des rabais incitatifs basés sur les achats antérieurs et le taux de piratage parmi les membres du groupe. Nous utilisons l'analyse de fonction d'utilité pour établir des conditions nécessaires au bon fonctionnementdu SDN. À l'aide de simulations, nous examinons également l'évolution avec le temps des mesures d'incitation dans des réseaux dynamiques.

Recent advances in embedded technologies have enabled cell phones tobecome powerful multihomed computing devices and hosts to a wide rangeof applications. However, communication between the device and the outsideworld is still a complicated task because the device is mobile, the connectionis intermittent, the signal strength varies greatly and the communicationoptions are heterogeneous. Previous work has suggested that communicationwith these devices is simplied and enhanced with the use of message orientedmiddleware (MOM).MOMs generally allow the exchange of small messages on an IP networkusing communication patterns such as notication, request/reply and pub-lish/subscribe. However, mobile devices also support non-IP networks suchas the short message service (SMS). SMS can be seen as a MOM that isadministered by a Mobile Network Provider (MNO). The advantage is itsubiquity and privileged access to the status of the device. Additionally, mo-bile devices can be reached simultaneously on multiple networks, but MOMsdo not support this functionality.In this work, we introduce a mobility middleware that will improve currentMOM. Our mobility middleware uses a utility-based scheme for automati-cally choosing one of three network types: MNO, WiFi and the SMS. Theselection scheme makes a decision using context information from the net-work, the user preferences, the application preferences and the infrastructure.Additionally, delay-tolerant application can use our mobility middleware todelay messages in order to improve the utility. We also guarantee FIFOordering and at-most-once delivery, at-least-once delivery or at-least-onceprocessing as required. Finally, we implement our solution with a Java MEclient and a Java middleware and evaluate the performance impact of addingour mobility middleware to a MOM. / Des avancements technologiques récents sur les systèmes embarqués ont permis aux cellulaires de devenir des puissants appareils et hôtes d'une panoplie d'applications. Cependant, la communication entre l'appareil et l'extérieur est encore une tâche compliquée parce que l'appareil est mobile, la connexion est intermittente, le signal varie et les options de communications sont hétérogènes. Des travaux passés ont suggéré que la communication avec ces appareils est simplifié et augmenté par l'utilisation d'un intergiciel par envoie de messages (MOM).Les MOMs permettent l'échange de petits messages sur un réseau IP tout en utilisant plusieurs modèles de communication tels que la notification, la transmission sur demande et la publication-souscription. Toutefois, les cellulaires supportent aussi les réseaux non IP tel que le service de minimessages (SMS). Le SMS peut être considéré comme un MOM qui est administré par un fournisseur de service sans-fil. L'avantage du SMS est sont ubiquité et sont accès privilégié au statu du cellulaire. De plus, les téléphones mobiles peuvent communiquer sur plusieurs réseaux simultanément, mais les MOMs ne supportent pas cette fonctionnalité.Dans ce travail, nous introduisons un intergiciel pour la mobilité permettant l'amélioration des MOMs suivant le protocole AMQP pour utilisant avec les téléphones intelligents. Notre intergiciel pour la mobilité utilise un modèle d'utilité pour choisir un canal de communication approprié entre les fournisseurs de service sans-fil, Wifi et le SMS. Le modèle d'utilité fait une décision à partir de l'information du contexte courant du réseau, des préférences de l'usager, des préférences de l'application ainsi que de l'infrastructure. De plus, les applications qui supportent un délai peuvent utiliser notre intergiciel pour la mobilité pour introduire un délai pour introduire un délai et améliorer l'utilité. Nous garantissons l'ordre premier entré et premier sortis des messages ainsi que la livraison au plus une fois, au moins une fois ou le traitement au moins une fois tel que requis. Finalement, nous implémentons un client Java ME ainsi qu'un intergiciel Java et nous évaluons l'impact sur la performance de l'introduction de notre intergiciel pour la mobilité à un MOM.

To keep pace with the increasing user base and resulting processing requirements, enterprise and e-commerce applications need constant innovation in their application design and system architecture. Scalability and availability are the basic principles that must be adhered to by the businesses if they want to retain and expand their customer base. The most popular design which provides for both availability and scalability is when the application tier is replicated. In it, all the application servers share a single database, and to prevent the database from becoming the bottleneck in a high volume scenario, caching layers are deployed in each application server. By serving requests from the local cache instead of going to the database, response times are reduced and the load at the database is kept low. Thus, caching is a critical component of such architectures. In this thesis, we focus on object caches at the application tier, which cache Java EE entities. Our target applications are e-commerce applications which are database driven and are resource intensive. In this thesis we design a cache aware load balancing solution which makes effective usage of the caching layer. This results in a more scalable application tier of a multi-tier architecture. Most of the load balancing solutions present in literature are cache agnostic when making the dispatching decision. Example solutions like round-robin cause duplication of the same cache content across all the application servers. In contrast, we present a cache aware load balancing algorithm, which make best possible effort to prevent the duplication of cached entries across the different caches in the cluster, enabling us to make a more efficient usage of cache space available to us. This in turn, results in less cache evictions. We also extend our cache aware load balancing algorithm to take into account the dynamic nature of the application server cluster where the nodes can come up and shutdown as the system is running. The evaluation of our implementation shows improvements in response time and throughput of a well known e-commerce benchmark compared to existing strategies. / Afin de suivre le rythme croissant d'utilisateurs ainsi que les demandes de traitements résultants, les applications entreprise et de commerce électronique ont besoin d'innovations régulières dans leur conception et architecture. L'extensibilité ainsi que la disponibilité sont primordiales pour tout type d'affaires ayant intérêt à garder, voir même étendre, leur clientèle. L'architecture la plus populaire qui fournit en même temps l'extensibilité et la disponibilité est celle pour laquelle le serveur d'applications est répliqué. Une architecture au niveau de laquelle les serveurs d'applications partagent une seule base de données et chacun d'entre eux utilise des couches de cache afin de réduire la charge sur la base de données. En servant les requêtes à partir du cache local, au lieu de les servir à partir de la base données, les temps de réponses sont réduits et la charge de traitement de la base de données est maintenue à un bas niveau. Ainsi, la mise en cache est une composante critique pour ce type d'architectures. Dans cette thèse, on se concentre sur la mise en case d'objets au niveau du serveur d'applications, qui met en cache des entités Java EE. On vise principalement les applications de commerce électroniques qui sont basées sur les bases de données et qui demandent assez de ressources. Dans cette thèse, nous concevons une solution de balancement de la charge qui tient en compte la mise en cache, ce qui rend l'utilisation de la couche du cache assez effective. Ceci résulte en un serveur d'applications assez extensible pour les architectures multi-tier. La plupart des solutions de balancement de la charge ne tiennent pas en compte la mise en cache lors de la distribution de leur requêtes. Par exemple des solutions comme le round-robin entraînent la duplication du même contenu du cache à travers tous les serveurs d'applications. En revanche, nous présentons un algorithme de balancement de la charge qui tient en compte la mise en cache et qui fait de son mieux pour éviter la duplication des entrées mises en cache à travers tous les caches distribués. Ceci nous permet d'utiliser d'une façon efficace l'espace de cache disponible et de réduire le nombre d'expulsions d'entités à partir du cache. Au niveau de notre algorithme de distribution de la charge, et qui tient en compte la mise en cache, nous prenons en considération le nombre dynamique des applications serveurs. En fait, lors de l'exécution d'un système réel, les noeuds de serveurs peuvent joindre ou quitter le système à n'importe quel moment. L'évaluation de notre implémentation montre des améliorations en terme de temps de réponse et de débit de requêtes pour un benchmark bien connu, comparativement à des stratégies existantes.

Decision-making under uncertainty has become critical as autonomous and semi-autonomous agents become more ubiquitious in our society. These agents must deal with uncertainty and ambiguity from the environment and still perform desired tasks robustly. Partially observable Markov decision processes (POMDPs) provide a principled mathematical framework for modelling agents operating in such an environment. These models are able to capture the uncertainty from noisy sensors, inaccurate actuators, and perform decision-making in light of the agent's incomplete knowledge of the world. POMDPs have been applied successfully in domains ranging from robotics to dialogue management to medical systems. Extensive research has been conducted on methods for optimizing policies for POMDPs. However, these methods typically assume a model of the environment is known. This thesis presents a Bayesian reinforcement learning framework for learning POMDP parameters during execution. This framework takes advantage of agents which work alongside an operator who can provide optimal policy information to help direct the learning. By using Bayesian reinforcement learning, the agent can perform learning concurrently with execution, incorporate incoming data immediately, and take advantage of prior knowledge of the world. By using such a framework, an agent is able to adapt its policy to that of the operator. This framework is validated on data collected from the interaction manager of an autonomous wheelchair. The interaction manager acts as an intelligent interface between the user and the robot, allowing the user to issue high-level commands through natural interface such as speech. This interaction manager is controlled using a POMDP and acts as a rich scenario for learning in which the agent must adjust to the needs of the user over time. / Comme le nombre d'agents autonomes et semi-autonomes dansnotre société ne cesse de croître, les prises de décisions sous incertitude constituent désormais un problème critique. Malgré l'incertitude et l'ambiguité inhérentes à leurs environnements, ces agents doivent demeurer robustes dans l'exécution de leurs tâches. Les processus de décision markoviens partiellement observables (POMDP) offrent un cadre mathématique permettant la modélisation des agents et de leurs environnements. Ces modèles sont capables de capturer l'incertitude due aux perturbations dans les capteurs ainsi qu'aux actionneurs imprécis. Ils permettent conséquemment une prise de décision tenant compte des connaissances imparfaites des agents. À ce jour, les POMDP ont été utilisés avec succès dans un éventail de domaines, allant de la robotique à la gestion de dialogue, en passant par la médecine. Plusieurs travaux de recherche se sont penchés sur des méthodes visant à optimiser les POMDP. Cependant, ces méthodes requièrent habituellement un modèle environnemental préalablement connu. Dans ce mémoire, une méthode bayésienne d'apprentissage par renforcement est présentée, avec laquelle il est possible d'apprendre les paramètres du modèle POMDP pendant l'éxécution. Cette méthode tire avantage d'une coopération avec un opérateur capable de guider l'apprentissage en divulguant certaines données optimales. Avec l'aide du renforcement bayésien, l'agent peut apprendre pendant l'éxécution, incorporer immédiatement les données nouvelles et profiter des connaissances précédentes, pour finalement pouvoir adapter sa politique de décision à celle de l'opérateur. La méthodologie décrite est validée à l'aide de données produites par le gestionnaire d'interactions d'une chaise roulante autonome. Ce gestionnaire prend la forme d'une interface intelligente entre le robot et l'usager, permettant à celui-ci de stipuler des commandes de haut niveau de façon naturelle, par exemple en parlant à voix haute. Les fonctions du gestionnaire sont accomplies à l'aide d'un POMDP et constituent un scénario d'apprentissage idéal, dans lequel l'agent doit s'ajuster progressivement aux besoins de l'usager.

Pooled drug design is an important approach in modern, high-throughput pharmacology, in which a large library of compounds is scanned using automated means, in order to find drug combinations that are active against a given target. In order to minimize costs, it is important to decide on the pool size, i.e., the number of compounds which will be tested together. In this paper, we analyze the expected number of trials necessary to determine a winning combination, under the assumption that the compound library may also contain blockers, which will obscure the effect of a drug combination if present in the same pool. We establish formulas for the optimal pool size and show that, surprisingly, it is not affected by the amount of measurement noise. Finally, we present a Bayesian approach that can be used when the number of blockers is unknown. An important result is that using pool sizes greater than the number of desired targets is beneficial, for a large range of possible numbers of blockers. / Nous addressons le problème de la determination des groupes de substances chimiques pour obtenir des nouveaux traitements. Le but est d'automatiser l'analyse des librairies des larges librairies chimiques et pharmacologiques. L'hypothese de base est qu'il y a un groupe de substances qui ont un effect positif sur une certaine maladie, mais on doit l'identifier par l'analyse d'un très large groupe de substances. Dans ce groupe, il y a aussi des substances qui peuvent masquer l'effet désirable. Nous proposons une formule pour calculer le nombre optimal de substances qu'on devrait tester à la meme fois. La conclusion surprenante est que ce nombre ne depend pas des erreures qu'on fait dans les mesurements. Nous etablissons aussi le nombre de combinaisons qu'on devrait tester pour identifier le groupe desiré. Nouspresentons aussi une approche Bayesienne qu'on peut utiliser quand le nombre des substances bloquant l'effect desiré n'est pas connu.

As a consequence of Moore's law, the size of integrated circuits has grown extensively, resulting in simulation becoming the major bottleneck in the circuit design process. Consequently, parallel simulation has emerged as an approach which can be both fast and cost effective. In this thesis, we examine the performance of a parallel Verilog simulator, VXTW, on four large, real designs using an optimistic synchronization scheme named Time Warp. As previous work has made use of either relatively small benchmarks or synthetic circuits, the use of these circuits is far more realistic. Because of the low computational granularity of a gate level simulation and because the computational and communication loads vary throughout the course of the simulation, the performance of Time Warp can be severely degraded or can even be unstable. Dynamic load balancing algorithms for balancing the computational and communication loads during the simulation are described in this thesis. Like all load balancing algorithms, the proposed algorithms have some tuning parameters which must be optimized. In addition, in order to avoid the simulation from being too optimistic, we make use of a time window. In the thesis, we make use of learning techniques from artificial intelligence (N-armed Bandit, Multi-state Q-learning) and heuristic searches (Genetic Algorithm, Simulated Annealing) to tune the parameters of the dynamic load balancing algorithms and to determine the size of the time window. we evaluated the performance of these algorithms on open source Sparc and Leon processor designs and on two Viterbi decoder designs and observed up to a 70% improvement in simulation time using these approaches. / Une des conséquences de la loi de Moore est la croissance significative de lataille des circuits intégrés; il en résulte que la simulation est devenue le goulot d'étranglement majeur dans le processus de conception de tels circuits. Conséquemment, la simulation parallèle se veut une approche qui a le potentiel d'être à la fois rapide etrentable. Dans cette thèse, nous examinerons la performance d'un simulateur Verilog parallèle appelé VXTW sur quatre conceptions de processeurs réelles de grande taille, en utilisant un algorithme de synchronisation optimiste appelé Time Warp. Puisque les travaux précédents ont utilisé des circuits synthétiques ou des tests de performance de taille relativement petite, l'utilisation de ces circuits est beaucoup plus réaliste. Puisque les simulations au niveau des portes logiques impliquent une granularité calculatoire peu élevée, et puisque les charges calculatoires et de communication varient au cours de la simulation, la performance de Time Warp peut se dégrader sévèrement ou devenir instable. Dans cette thèse, nous décrivons des algorithmes dynamiques d'équilibrage de charge visant à équilibrer les charges calculatoires et de communicationdurant la simulation. Comme tous les algorithmes d'équilibrage de charge, les algorithmes proposés comportent des paramètres de réglage qui doivent être optimisés. De plus, nous utilisons une fenêtre de temps pour éviter que la simulation ne soit trop optimiste. Dans cette thèse, nous utilisons des techniques d'apprentissage provenant du domaine de l'intelligence artificielle (machine à sous à leviers multiples, Q-learning avec plusieurs agents) et des recherches heuristiques (algorithmes génétiques, méthode du circuit simulé) pour régler les paramètres des algorithmes dynamiques d'équilibrage des charges, ainsi que pour déterminer la taille de la fenêtre de temps. Nous évaluons la performance de ces algorithmes sur des conceptions de processeurs Sparc et Leon libres de droits, ainsi que sur deux décodeurs Viterbi, et nous avons pu observer une amélioration du temps de simulation de 70% en utilisant ces approches.