Repeated changes to a software system can introduce small weaknesses such as unplanned dependencies between different parts of the system. While such problems usually go undetected, their cumulative effect can result in a noticeable decrease in the quality of a system. We present an approach to warn developers about increased coupling between the (potentially scattered) implementation of different features. Our automated approach can detect sections of the source code contributing to the increased coupling as soon as software changes are tested. Developers can then inspect the results to assess whether the quality of their changes is adequate. We have implemented our approach for C++ and integrated it with the development process of proprietary 3D graphics software. Our field study showed that, for files in the target system, causing increases in feature coupling is a significant predictor of future modifications due to bug fixes. / Chaque modification appliquée à un système logiciel peut y introduire de nouvelles failles telles que des dépendances structurelles entre ses éléments unitaires. Il peut être difficile de percevoir ce processus de dégradation de la qualité puisque qu’il n’implique pas nécessairement une dégradation fonctionnelle. Nous présentons ici une nouvelle technique permettant à l’ingénieur logiciel de comprendre l’impact de ses modifications sur les dépendances structurelles dans le contexte des fonctionnalités du système. Notre approche automatisée identifie les éléments logiciels ainsi potentiellement dégradés dès que le logiciel est soumis à sa procédure de vérification habituelle. L’ingénieur peut alors inspecter les résultats de notre analyse pour déterminer si la qualité de la modification appliquée est adéquate. Nous avons déployés notre système dans un environnement logiciel graphique 3D privé sous C++. Notre étude démontre que, pour ce système, l’addition de dépendances structurelles est un précurseur de modifications rectificatrices dans le futur.

During the past two decades, thermal microfluidic chips have significantly been investigated. Due to their high capacity of heat transport, an increasing number of studies on different aspects of thermal microfluidic chips have been conducted. However, a comprehensive investigation on the geometry of microfluidic chips using state of the art finite element software is absent from the literature. In this thesis, geometric parameters of thermal microfluidic chips have been optimized, using finite element software. Consequently, micro and macro phenomena were investigated in different models. The micro modelling approach investigated single microchannels and optimized the microchannel cross-section. Furthermore, two-phase flows in the microchannel were modelled, using finite element software ANSYS CFX. Liquid accumulation in the sharp corners of the microchannel was captured in the model and the phase change phenomenon was observed. The results of the finite element analysis were compared to the literature and a good correlation was observed. The configuration of microchannels in a microfluidic chip was studied through the macro modelling approach. Dimensionless design charts were presented in this section to be employed for all kinds of thermal microfluidic chips with different boundary conditions. Based on the validity of the finite element software, two-phase flows in the optimized three-dimensional network of microchannels were modelled. The results showed the circulation of the two phases in the microchannels and demonstrated the proper operation of the thermal microfluidic chip. / Au cours des deux dernières décades, les puces thermiques micro-fluidiques ont été considérablement examinées. Du fait de leur haute capacité pour le transport de chaleur, de nombreuses études ont été réalisées sur différents aspects de leurs propriétés. Cependant, une étude de la géométrie des puces micro-fluidiques utilisant un logiciel d'analyse par éléments finis est absente de la littérature. Dans cette thèse, des paramètres géométriques des puces thermiques micro-fluidiques ont été optimisés en utilisant un logiciel d'analyse par éléments finis. Ainsi, les phénomènes micro et macro ont été étudiés dans différents modèles. L'approche micro a consisté à étudier les micro-canaux seuls, et à optimiser la géométrie de leur section transverse. De plus, deux phases d'écoulement ont été modélisées en utilisant le logiciel d'élément fini ANSYS CFX. L'accumulation de liquide dans les coins saillants a été saisie par le modèle et le phénomène de changement de phase a pu être également observé. Les résultats de l'analyse par élément finis ont été comparés à ceux trouvés dans la littérature, et une bonne corrélation a été observée. La configuration des micro-canaux dans la puce micro-fluidique a été étudiée par l'approche macro. Des graphes adimensionnels ont été présentés dans cette section afin d'être employés pour toutes sortes de puces ayant différentes conditions aux frontières. En se basant sur la validité du modèle micro, élaboré par élément finis, l'écoulement des deux phases dans un réseau tridimensionnel de micro-canaux avec une géométrie optimisée a été modélisé. Les résultats montrent une circulation des deux phases dans les micro-canaux et démontrent le bon fonctionnement des puces thermiques micro fluidiques.

Graph drawing studies the problem of producing layouts of relational structures that can be represented by combinatorial graphs. An orthogonal drawing is one whose edges are drawn as polygonal lines, with constituent segments drawn parallel to the coordinate axes. Orthogonal drawings arise in applications in diverse fields such as information visualization and VLSI circuit layout. One of the most successful methodologies for generating 2D orthogonal layouts of graphs is the so-called Topology-Shape-Metrics approach, where the task of defining the combinatorial shape of the drawing is separated from the task of determining the geometric coordinates of the vertices in the final drawing. In contrast to its 2Dcounterpart, however, the aforementioned Topology-Shape-Metrics approach has not been exploited in 3D. The first step toward achieving this goal is due to Di Battista et al. [10, 11], who give combinatorial characterizations of paths and cycles with given shape such that they admit simple (i.e. nonself- intersecting) orthogonal 3D drawings. In particular, [10] studies the following problem: given a cycle with an axis-parallel direction label on each edge, can we compute a simple orthogonal drawing of the cycle? However, the necessity part of the proof for the characterization in [10] was later discovered by its authors to be incomplete. The aim of this thesis, therefore, is to complete the proof of the characterization given by Di Battista et al., and to discuss further results that arise as consequences of this now complete characterization. / Le dessin de graphe étudie le problème de produire des plans de structures relationnelles pouvant être représentées par des graphes combinatoires. Un dessin orthogonal est un graphe dont les arêtes sont des lignes polygonales parallèles aux axes de coordonnées. Les dessins orthogonaux sont utiles dans plusieurs applications de divers champs comme la visualisation d'information et la fabrication de plan pour l'intégration de circuits à très grande échelle (very large scale integration - VLSI). Une des meilleures méthodes pour générer des plans orthogonaux bidimensionnels de graphes est l'approche dite de «Topology-Shape-Metrics» [Topologie-Forme-Métrique], où la tâche de définir les formes combinatoires du dessin est séparée de celle de déterminer les coordonnées géométriques des sommets dans le dessin final. Par opposition à son équivalent bidimensionnel, la méthode de «Topology-Shape-Metric» mentionnée précédemment n'a pas encore été exploitée en trois dimensions. La première étape afin d'atteindre ce but est énoncée par Di Battista et autres [10, 11] lorsqu'il donne les caractéristiques combinatoires des chemins et cycles d'une forme donnée tels qu'ils admettent des dessins 3D simples, (c'est-à-dire: sans intersections). En particulier, [10] étudie le problème suivant: étant donné un cycle avec une étiquette associant chaque arête à son axe parallèle, peut-on obtenir un dessin orthogonal simple du cycle? La preuve de la condition nécessaire pour la caractérisation dans [10] s'est néanmoins révélée comme étant incomplète par les auteurs. Le but de ce mémoire est donc de compléter la preuve de la caractérisation donnée par Di Battista et autres et aussi de discuter les résultats futurs résultant des conséquences de la complétion de la caractérisation.

Markov Decision Processes are a mathematical framework widely used for stochastic optimization and control problems. Reinforcement Learning is a branch of Artificial Intelligence that deals with stochastic environments where the dynamics of the system are unknown. A major issue for learning algorithms is the need to balance the amount of exploration of new experiences with the exploitation of existing knowledge. We present three methods for dealing with this exploration-exploitation tradeoff for Markov Decision Processes. The approach taken is Bayesian, in that we use and maintain a model estimate. The existence of an optimal policy for Bayesian exploration has been shown, but its computation is infeasible. We present three approximations to the optimal policy by the use of statistical sampling.\\ The first approach uses a combination of Linear Programming and Q-learning. We present empirical results demonstrating its performance. The second approach is an extension of this idea, and we prove theoretical guarantees along with empirical evidence of its performance. Finally, we present an algorithm that adapts itself efficiently to the amount of time granted for computation. This idea is presented as an approximation to an infinite dimensional linear program and we guarantee convergence as well as prove strong duality. / Les processus de décision Markoviens sont des modèles mathématiques fréquemment utilisés pour résoudre des problèmes d'optimisation stochastique et de contrôle. L'apprentissage par renforcement est une branche de l'intelligence artificielle qui s'intéresse aux environnements stochastiques où la dynamique du système est inconnue. Un problème majeur des algorithmes d'apprentissage est de bien balancer l'exploration de l'environnement, pour acquérir de nouvelles connaissances, et l'exploitation des connaissances acquises. Nous présentons trois méthodes pour obtenir de bons compromis exploration-exploitation dans les processus de décision Markoviens. L'approche adoptée est Bayésienne, en ce sens où nous utilisons et maintenons une estimation du modèle. L'existence d'une politique optimale pour l'exploration Bayésienne a été démontrée, mais elle est impossible à calculer efficacement. Nous présentons trois approximations de la politique optimale qui utilise l'échantillonnage statistique. \\ La première approche utilise une combinaison de programmation linéaire et de l'algorithme "Q-Learning". Nous présentons des résultats empiriques qui démontrent sa performance. La deuxième approche est une extension de cette idée, et nous démontrons des garanties théoriques de son efficacité, confirmées par des résultats empiriques. Finalement, nous présentons un algorithme qui s'adapte efficacement au temps alloué pour le calcul de la politique. Cette idée est présentée comme une approximation d'un programme linéaire à dimension infini; nous garantissons sa convergence et démontrons une dualité forte.

The pure methods in a program are those that exhibit functional or side effect free behaviour, a useful property of methods or code in the context of program optimization as well as program understanding. However, gathering purity data is not a trivial task, and existing purity investigations present primarily static results based on a compile-time analysis of program code. We perform a detailed examination of dynamic method purity in Java programs using a Java Virtual Machine (JVM) based analysis. We evaluate multiple purity definitions that range from strong to weak, consider purity forms specific to dynamic execution, and accommodate constraints imposed by an example consumer application of purity data, memoization. We show that while dynamic method purity is actually fairly consistent between programs, examining pure invocation counts and the percentage of the bytecode instruction stream contained within some pure method reveals great variation. We also show that while weakening purity definitions exposes considerable dynamic purity, consumer requirements can limit the actual utility of this information. A good understanding of which methods are "pure" and in what sense is an important contribution to understanding when, how, and what optimizations or properties a program may exhibit. / Les fonctions purs dans un programme sont ceux qui démontre un comportement sans fonctionnalité ou effet secondaire. Ceci s'avère une propriété utile pour une fonction ou du code dans le contexte d'optimisation et de compréhension du programme. Cependant, récolter de l'information de pureté n'est pas une tâche facile, et les techniques existantes pour les analyses de pureté ne fournissent que des résultats statiques basés sur une analyses de la compilation du programme. Nous avons exécuter une analyse détaillée de la pureté dynamique des fonctions dans des applications Java en utilisant une approche basés sur un Java Virtual Machine (JVM). Nous avons évalué multiples définitions de pureté, forte et faible, et considéré les formats de pureté spécifiques à l'exécution, tout en considérant les contraintes qui nous sont imposées par un application "consommateur" d'information de pureté et de mémorisation. Nous démontrons que malgré la consistance de la pureté dynamique des fonctions parmi certains applications, l'examen du nombre d'invocation pure et le pourcentage de chaîne d'instruction "bytecode" trouvé dans les fonctions purs nous dévoile l'existante de grande variation. Nous montrons aussi que malgré l'affaiblissement de la définition de la pureté expose considérablement la pureté dynamique, les pré-requis des consommateurs peuvent actuellement limiter l'utilité de cet information. Une bonne compréhension de ce qu'est une fonction "pure" et dans quel sens, est une important contribution à comprendre quand, où, et quelles optimisations ou propriétés une application peut dévoilée.

We address the problem of automatically constructing basis functions for linear approximation of the value function of a Markov decision process (MDP). Our work builds on results by Bertsekas and Casta˜non (1989) who proposed a method for automatically aggregating states to speed up value iteration. We propose to use neighbourhood component analysis , a dimensionality reduction technique created for supervised learning, in order to map a high-dimensional state space to a low-dimensional space, based on the Bellman error, or on the temporal difference (TD) error. We then place basis functions in the lower-dimensional space. These are added as new features for the linear function approximator. This approach is applied to a high-dimensional inventory control problem, and to a number of benchmark reinforcement learning problems. / Nous adressons la construction automatique de fonctions base pour l'approximation linéaire de la fonction valeur d'un processus de décision Markov. Cette thèse se base sur les résultats de Bertsekas et Castañon (1989), qui ont proposé une méthode pour automatiquement grouper des états dans le but d'accélérer la programmation dynamique. Nous proposons d'utiliser une technique récente de réduction de dimension afin de projeter des états en haute dimension dans un espace à basse dimension. Nous plaçons alors des fonctions base radiales dans ce nouvel espace. Cette technique est appliquée à plusieurs problèmes de référence standards pour les algorithmes d'apprentissage par renforcement, ainsi qu'à un problème de contrôle d'inventaire en haute dimension.

The popularity of massively multiplayer games has increased in recent years and game providers are facing scalability problems to accomodate growing populations of users. Broadcasting all state changes to every player is not a viable solution to maintain a consistent game state in a massively multiplayer game. To successfully overcome the challenge of scale, massively multiplayer games have to employ sophisticated interest management techniques that only send relevant state changes to each player. In this thesis we develop a space partitioning technique based on triangulation that adapts to the world’s obstacles. We introduce obstacle-aware interest management algorithms that use the triangular partitioning to determine the relevance of objects based on the occlusion created by obstacles. We compare the performance of both obstacle-aware and state-of-the-art interest management algorithms based on measurements obtained in a real massively multiplayer game using human and computer-generated player actions. We show that obstacle-aware interest management algorithms can reduce the number of update messages between players and that algorithms based on our triangle-based partitioning can scale to a larger number of objects. The experiments also show that measurements obtained with computer-controlled players performing random actions can approximate measurements of games played by real humans, provided that the traces of the random players are designed adequately. As the size of the world and the number of players of massively multiplayer games increases, adaptive interest management techniques such as the ones studied in this thesis will become increasingly important. / La popularité des jeux massivement multijoueurs a augmenté de façon phénoménale au cours des dernières années. Les fournisseurs de jeux rencontrent de plus en plus de problèmes d’extensibilité pour supporter des populations croissantes de joueurs. La diffusion à tous les joueurs des changements réalisés dans le monde virtuel n’est pas une solution viable pour maintenir une vision cohérente du monde dans un jeu massivement multijoueurs. Pour surmonter ce défi d’extensibilité, les jeux massivement multijoueurs doivent utiliser des techniques de gestion d’intérêt sophistiquées qui relaient seulement l’information pertinente vers chaque joueur. Dans cette thèse nous développons une technique de partition de l’espace qui s’adapte aux obstacles du monde virtuel en utilisant une triangulation. Nous présentons des algorithmes sensible-aux-obstacles de gestion d’intérêt qui emploient les partitions triangulaires pour déterminer la pertinence des objets pour chaque joueur, selon l’occlusion créée par les obstacles. Nous comparons l’efficacité des algorithmes sensible-aux-obstacles et d’autres algorithmes modernes de gestion d’intérêt à l’aide de données obtenues d’un vrai jeu massivement multijoueurs. À cet effet, nous utilisons à la fois des actions de vrais joueurs et des actions de joueurs générées par ordinateur. Nous démontrons que les algorithmes sensible-aux-obstacles de gestion d’intérêt peuvent réduirent le nombre de messages relayés entre les joueurs. Nous démontrons également que les algorithmes utilisant notre partition triangulaire peuvent s’adapter à un plus grand nombre d’objets tout en conservant de bonnes performances. Nos expériences suggèrent également que les résultats obtenus à partir de joueurs contrôlés par ordinateur se déplaçant aléatoirement ce rapprochent des résultats obtenus avec de vrais joueurs, dans la mesure où les actions aléatoires des joueurs son

Moore's Law states that computational power will roughly double every 18 months. To the semiconductor designer, this means the never-ending challenge of bringing increasingly larger and more complex ICs (Integrated Circuits) to market. It is well known that the principle bottleneck in circuit design is simulation. Uniprocessor simulators may not be able to keep up with increased demands on them for both speed and memory. This thesis has three main contributions. The first contribution is a distributed Verilog simulation environment which can be executed on a cluster of workstations using a message-passing library such as MPI (Message Passing Interface). It employs OOCTW as the synchronization backend and takes advantage of the open source code of Icarus Verilog simulator. It is designed to be flexible for future extension and optimization. To our knowledge, DVS is the first distributed Verilog simulator. The second contribution is event reconstruction, a technique which reduces the overhead caused by event saving. As the name implies, event reconstruction reconstructs input events and anti-events from the differences between adjacent states, and does not save input events in the event queue. Memory consumption and execution time of event reconstruction are compared to the results obtained by dynamic checkpointing revealing that event reconstruction yields a significant reduction in memory utilization and leads to a faster simulation. The third contribution is a multiway design-driven iterative partitioning algorithm for Verilog based on module instances. We do this in order to take advantage of the design hierarchy information contained in the modules and their instances. A Verilog instance is represented by one vertex in a circuit hypergraph. The vertex can be flattened into multiple vertices in the event that an adequate load balance is not achieved by instance based partitioning. In this case the algorithm flattens the largest instance and moves gates betw / La Loi de Moore stipule que la puissance des processeurs double approximativement tous les 18 mois. Pour le constructeur de semi-conducteurs, cela ´equivaut `a un constant probl`eme d'apporter des CI (Circuits Integr´es) de plus en plus larges et complexes sur le march´e. Il est bien connu que le goulet d'´etranglement dans la conception de circuits r´eside dans la simulation. Les simulateurs `a simple processeur peuvent ne pas suivre les demandes croissantes pour plus de vitesse et de m´emoire. Cette th`ese pr´esente un environnement de simulation Verilog avec plusieurs techniques d'optimization. Verilog est une langue de conception digitale couramment utilis´ee. Une simulation distribu´ee Verilog peut ˆetre ex´ecut´ee sur un groupe de postes de travail en utilisant une librarie passant des messages telle que IPM (Interface Passant des Messages). Nous d´ecrivons la reconstruction d'´ev´enements, une technique qui r´eduit l'en-tˆete caus´e par une sauvegarde d'´ev´enements, et comparons sa consommation de m´emoire et son temps d'ex´ecution avec les r´esultats obtenus par checkpointing dynamique. Comme son nom l'indique, la reconstruction d'´ev´enements reconstruit la saisie d'´ev´enements et d'anti-´ev´enements `a partir de la difference entre les ´etats adjacents, et ne sauvegarde pas la saisie d'´ev´enements dans la queue des ´ev´enements. Nous proposons un algorythme partionn´e redondant `a plusieurs voies et orient´e vers le design pour Verilog bas´e sur des instances de modules. Nous faisons cela afin de profiter de l'information hi´erarchique de conception contenue dans les modules et leurs instances. Une instance Verilog est repr´esent´ee par un vertex dans un circuit hypergraphique. Ce vertex peut etre ´ecras´e en plusieurs vertexs dans le cas o`u une charge ad´equate n'est pas produite par une instance bas´ee sur des partitions. Dans ce cas l`a l'algorythme ´ecrase la plus grosse instance et d´eplace les port

Modern computer games tend to provide complex narratives, ensuring both extended and interesting game play. Narratives are important not only in traditional adventure games and role playing games, but also in first person shooting games and strategy games. Even so, many narratives contain defects that reduce the quality of games, and so it is important to develop analysis or verification techniques. Unfortunately, formal verification attempts are few, and in practice primarily done by manual inspection and test-playing. Our research is based on a framework, named Programmable Narrative Flow Graph (PNFG) that provides a high-level language to represent narratives. Our approach is to apply high-level, formal analysis to narratives to find out their winning paths, as a first step forward deeper verification. We extend the PNFG framework by developing a generic dataflow analysis module, and implement several analyzers to gather high-level data on narrative behaviors. To improve the performance of our approach, we also designed several optimizations that reduce the size of the search space. Not all individual optimizations are effective on all narratives, but our final, fully-optimized strategy is able to analyze large narratives in relatively little time—an improvement of several orders of magnitude over the state-of-the-art in narrative analysis. This represents a practical and effective design for analyzing narratives that we hope can be the basic of real improvements in game development. / Les jeux modernes pour ordinateurs ont tendance `a apporter les structures narratives complexes, en affirmant un jeu `a la fois entendu et int´eressant. Les structures narratives sont importantes non seulement dans le jeu d'aventure et le jeu de rˆole, mais aussi dans le jeu de tir `a la premi`ere personne et le jeu de strat´egie. Malgr´e tout, beaucoup de structures narratives poss`edent des d´efauts qui r´eduisent la qualit´e des jeux, ainsi c'est important de d´evelopper la technique de analyse ou de v´erification. Malheureusement, des tentatives de v´erification formelle sont limit´ees, et dans la pratique effectu´ee avant tout par l'inspection manuelle et l'essai du jeu. Notre recherche est bas´ee sur une structure applicative nomm´ee Programmable Narrative Flow Graph (PNFG) (Plan de Flux Narratif Programmable) qui offre un langage de haut niveau `a repr´esenter des structures narratives. En tant que premier pas vers la v´erification plue profonde, notre approche est `a appliquer l'analyse formelle de haut niveau sur les structures narratives afin de trouver leurs winning paths (chemins de la victoire). Nous prolongeons la structure applicative PNFG par l'´elaboration d'un module d'analyse de flux de donn´ees g´en´eriques, mais aussi mettons en oeuvre plusieurs analyseurs `a recueillir des donn´ees de haut niveau sur les comportements narratifs. Pour am´eliorer la performance de notre approche, nous avons ´egalement conc¸u plusieurs optimisations qui r´eduisent la taille de l'espace de recherche. Non toutes les diff´erentes optimisations sont efficaces sur les structures narratives, mais notre strat´egie finale et totalement optimis´ee$

Video mosaics are useful for mapping, localization, and asthetics. This thesis demonstrates a fully automated method to take video sequences of a scene from multiple disparate reference points and mosaic them together. The dissertation begins with a new approach to mosiacing still images with dynamic objects. Extending to video, foreground segmentation is achieved using a multi-Gaussian mixture model. This is applied to creating a noise free background image. Backgrounds are then aligned spatially using image features. Videos are aligned temporally using a novel technique based on brightness properties. Finally, new techniques to smoothly mosaic videos together using seam optimization creates the final result. The procedure is validated using synthetic data and an underwater sequence. / Les mosaïques visuelles peuvent être utiles pour la cartographie, la localisation, et les esthétiques. Cette thèse démontre une méthode entièrement automatisée pour prendre les séquences visuelles d'une scène de multiples points de référence disparates et de combiner ces vidéos ensemble en mosaïque. La dissertation commence par une nouvelle approche à créer des mosaïques avec des photos de plateaux contenant des objets dynamiques. Ensuite, avec la vidéo, la segmentation du premier plan est réalisée utilisant un modèle multigaussien mélangé. Ceci est applique a créer un fond d'image sans bruit. Les fonds d'images se sont âpres alignés dans l'espace en utilisant des dispositifs d'images. Les vidéos sont alignées temporellement utilisant une technique originale basée sur des propriétés d'éclat. Les nouvelles techniques de créer les mosaïques en utilisant l'optimisation de couture sont utilisées pour souplement combiner les vidéos ensemble. Le procédé est validé utilisant des données synthétiques et une séquence sous-marine.