As the level of realism required by modern video games and movies increases, so does the need for natural-looking simulations. Reproducing the physical behaviour of humans has been one of the pillars of modern research in the field of computer animation. This is a challenging problem because it is difficult to describe what constitutes a natural pose or motion. This problem can be addressed through optimizations that build on assumptions and approximations about properties such as energy, head orientation, or centre of mass position. Alternatively, instead of attempting to create realistic models for humans, motion capture can be used to record (and replay) the pose and motion of human subjects. Most existing approaches rely on some form of combination of physics-based optimization and motion capture. Additionally, some approaches augment and/or attempt to replace motion capture data with contact force measurements. The contributions of this thesis impact many of the above. First, we introduce a setup and a calibration technique for synchronously recording the pose as well as the contact forces in the special case of climbing. Our setup consists of an instrumented bouldering wall that records contact forces and an array of motion capture cameras that record posture. Our calibration technique uses an iterative and alternating least-squares optimization to reconcile force measurements and captured poses in a single space and time frame. Second, we study the relationship between captured motion and forces in an effort to fully describe poses from contact forces. Eliminating the need for motion capture is especially desirable in the context of climbing because of occlusions. To estimate static poses from forces, we use a physics-based optimization. The optimal solution for our objective function is the pose with the highest physical plausibility given the forces and additional constraints such as climber anatomy and hold positions. To eliminate local minima and speed up our optimization, a simpler "hint objective" is used to guide our solver toward a promising region. Comparison between poses reconstructed from forces and the corresponding poses obtained via motion capture shows that our objective function is a good model for human posture. / Le réalisme toujours plus accru des films et des jeux vidéo modernes nécessite des simulations paraissant de plus en plus naturelles. La reproduction des comportements physiques d'êtres humains est l'un des piliers de la recherche moderne dans le domaine de l'animation. C'est un problème complexe parce qu'il est difficile de décrire en quoi consiste une pose ou un mouvement naturel. Pour adresser ce problème, il est possible d'utiliser des optimisations portant sur des hypothèses et approximations de propriétés telles que l'énergie du système, l'orientation de la tête, ou la position du centre de masse. Plutôt que de tenter de modéliser des êtres humains de manière réaliste, la capture de mouvement peut être utilisée pour enregistrer (et rejouer) la pose ou le mouvement de sujets capturés. La plupart des approches existantes proposent une certaine combinaison d'optimisation basée sur la physique et de capture de mouvement. Certaines approches complémentent et/ou tentent de remplacer la capture de mouvement via des mesures de force de contact. Les contributions de cette thèse sont pertinentes pour bon nombre de ces approches. En premier lieu, nous introduisons un système et une technique de calibration pour mesurer de manière synchrone des poses et des forces de contact dans le cas particulier de l'escalade. Notre système est constitué d'un mur d'escalade équipé de capteurs qui mesurent les forces de contact, ainsi que d'un ensemble de caméras qui enregistrent la pose du grimpeur via capture de mouvement. Pour notre technique de calibration, nous utilisons une optimisation des moindres carrés qui agit de manière itérative et alternante pour exprimer les forces et les poses capturées dans un même repère spatio-temporel. En second lieu, nous étudions la relation entre le mouvement et les forces capturées dans le but d'exprimer des poses exclusivement en terme des forces de contact mesurées par les capteurs. Éliminer ainsi la capture de mouvement est particulièrement avantageux dans le contexte de l'escalade en raison des occlusions. Nous utilisons une optimisation basée sur la physique afin d'estimer des poses statiques à partir de forces de contact. La solution optimale pour notre fonction objectif est la pose la plus plausible pour les forces de contact et autres contraintes physiques prises en compte, telles que l'anatomie du grimpeur et l'emplacement des prises. Pour éliminer les minima locaux et pour accélérer l'optimisation, nous utilisons une fonction objectif simple qui guide notre résolveur vers une région prometteuse. En comparant des poses reconstruites à partir des forces de contact avec des poses mesurées via capture de mouvement, nous montrons que notre fonction objectif permet de modéliser de manière adéquate le choix de posture d'êtres humains.

Programs written for machine execution will always be susceptible to information theft. This information can include trademarked algorithms, data embedded in the program, or even data the program accesses. As technology advances computer scientists are building more and more powerful tools for reverse-engineering such as decompilers.The Java programming language is particularly open to reverse-engineering attacks because of its well-defined, open, and portable binary format. We examine one area of better-securing the intellectual property of a Java program; obfuscation. Obfuscation of a program involves transforming the code of the program into a more complex, but semantically equivalent representation. This can include the addition of confusing control flow, the removal of certain information embedded in the program which is not explicitly required for execution, or the cloaking of data.Obfuscation is one of the only techniques available other than cryptological options. While many approaches to obfuscation are ultimately reversible, it nevertheless seriously hinders those attempting to steal information by increasing the computing time and power required by software to reverse-engineer the program and also severely increases the complexity of any source code that is recovered by the reverse-engineering.In this thesis we present a number of obfuscating transformations implemented within a new automatic tool we name the Java Bytecode Obfuscator (JBCO). We present empirical measures of the performance costs of these transformations in terms of execution speed and program size. Complexity measurements that gauge the effectiveness of the obfuscations are also given. Finally, we review the feasibility of each transformation by looking at source code generated from obfuscated bytecode by various decompilers. / Les programmes écrits pour l'exécution d'ordinateur seront toujours susceptibles au vol d'information. Cette information peut inclure des algorithmes de marque de commerce, des données incluses dans le programme, ou même des données concernant les accès de programme. Suivant les avancées technologiques, les informaticiens construisent des outils de plus en plus puissants pour l'ingénierie inverse telle que le décompilateur. Le langage de programmation de Java est particulièrement ouvert aux attaques de l'ingénierie inverse en raison de son format binaire bien défini, ouvert, et portatif. Nous recherches portent sur un domaine permettant de mieux sécuriser fixer la propriété intellectuelle des programmes en Java; obscurcissement. L'obscurcissement d'un programme implique de transformer le code du programme en une représentation plus complexe mais sémantiquement équivalente. Ceci peut inclure l'addition de l'écoulement embrouillant de commande, de la supression de certaines informations incluses dans les programmes dont l'exécution n'est pas spécifiquement exigée, ou de la dissimulation des données. Excepté les techniques cryptologique s, l'obscurcissement est l'une des seules techniques disponibles. Même si beaucoup de stratégies de l'obscurissment sont finalement réversibles, il gêne sérieusement ceux qui essayent de voler l'information en augmentant la durée de calcul et la puissance exigées par les logicels d'ingénierie inverse et augmente considérablement la complexité de n'importe quel code source récupere par cette technique. Dans cette thèse nous présentons un certain nombre de transformations d'obscurcissement mises en application dans un outil automatique que nous appelons le Java Bytecode Obfuscator (JBCO). Nous présentons des mesures empiriques des coûts d'exécution de ces transformations en termes de vitesse d'exécution et taille de programme. Des mesures de complexité qui mesurent l'efficacité des obscurc

Markov models have been a keystone in Artificial Intelligence for many decades. However, they remain unsatisfactory when the environment modeled is partially observable. There are pathological examples where no history of fixed length is sufficient for accurate deci- sion making. On the other hand, working with a hidden state (such as in POMDPs) has a high computational cost. In order to circumvent this problem, I suggest the use of a context- based model. My approach replaces strict transition probabilities by a linear approximation of probability distributions. The method proposed provides a trade-off between a fully and partially observable model. I also discuss improving the approximation by constructing history-based features. Simple examples are given in order to show that the linear approx- imation can behave like certain Markov models. Empirical results on feature construction are also given to illustrate the power of the approach. / Depuis plusieurs déecennies, les modèeles de Markov forment l'une des bases de l'Intelligence Artificielle. Lorsque l'environnement modélisé n'est que partiellement observable, cepen- dant, ceux-ci demeurent insatisfaisants. Il est connu que la prise de décision optimale dans certains problèmes exige un historique infini. D'un autre côté, faire appel au con- cept d'état caché (tel qu'à travers l'utilisation de POMDPs) implique un coût computa- tionnel plus élevé. Afin de pallier à ce problème, je propose un modèle se servant une représentation concise de l'historique. Plutôt que de stocker un modèle parfait des prob- abilitités de transition, mon approche emploie d'une approximation linéaire des distribu- tions de probabilités. La méthode proposée est un compromis entre les modèles partielle- ment et complètement observables. Je traite aussi de la construction d'éléments en lien avec l'historique afin d'améliorer l'approximation linéaire. Des exemples restreints sont présentés afin de montrer qu'une approximation linéaire de certains modèles de Markov peut être atteinte. Des résultats empiriques au niveau de la construction d'éléments sont aussi présentés afin d'illustrer les bénéfices de mon approche.

Stock option trading has been very active since options were invented. Option analysis is very useful in helping investors decide investing strategies and predict the trend of the future stock movements. In this thesis, basic theory about stock option trading and some important approaches of option analysis such as option volume, open interest, put/call ratios and breakeven stock prices are discussed. A system called Stock Option Analyzer that can perform the option analysis based on these approaches is described in detail. The Stock Option Analyzer is able to automatically retrieve option quotes on any specified stock from the website Yahoo!Finance and present analysis results in the user's web browser. This analysis information is very useful for us to understand investors' opinions about the underlying stocks. The system is developed using JSP technology, utilizing JavaBeans, Java applets, and the help of the web server to generate web page contents dynamically.

Discrete-event modelling and simulation has become an established approach to the description and study of complex dynamic systems. In recent years there has been an increased interest in modelling complex dynamic-structure systems, i.e., systems whose structure changes over time. Such systems are generally more difficult to understand and analyze than systems with a static structure. These challenges can be met by the development of appropriate modelling formalisms based on a solid foundation and with suitable supporting tools. In this thesis we explore an approach to modelling and simulation of dynamic-structure discrete-event systems based on process algebra. The thesis consists of two parts. We begin by exploring, in the first part, a formalism for static-structure discrete-event modelling and simulation called the Discrete-EVent System Specification formalism (DEVS [Zeigler 76, 2000].) We develop an alternative theoretical foundation for DEVS based on Structural Operational Semantics, focusing on determinism and compositionality properties. In the second part we develop a modelling language for dynamic-structure discrete-event systems named kiltera, based on process algebras and incorporating elements from discrete-event modelling. This language, based on the \pi-calculus [Milner 89], allows us to describe and reason about timed, mobile and distributed discrete-event systems in a single framework. We develop a theoretical foundation based on Structural Operational Semantics and establish fundamental properties concerning time-determinism, continuity, compositionality and legitimacy. We build a simulator for the language which supports both sequential and distributed execution of models, based on a variant of the Time Warp algorithm [Jefferson 85]. Finally we apply this language to the modelling and simulation of traffic. / La modélisation et la simulation à événements discrets constituent une approche bien établie pour la description et l'étude des systèmes dynamiques complexes. Ces dernières années, il y a eu un regain d'intérêt pour la modélisation des systèmes complexes à structure dynamique. Ces systèmes sont généralement plus difficiles à comprendre et à analyser que les systèmes ayant une structure statique. Cette analyse et cette compréhension peuvent être développées à l'aide de formalismes de modélisation fondés sur une base solide et des outils appropriés. Dans cette thèse, nous explorons une approche de modélisation et de simulation des systèmes à événements discrets fondée sur l'algèbre de processus. Ce document se compose de deux parties. Dans la première partie, nous étudions ce que l'on appelle le formalisme Discrete-EVent System Specifications (DEVS.) Nous développons un autre fondement théorique pour DEVS fondée sur la sémantique opérationnelle structurelle, en mettant l'accent sur les propriétés de déterminisme et de compositionalité. Dans la deuxième partie, nous développons un langage de modélisation pour systèmes à structure dynamique nommé kiltera, en nous fondant sur les algèbres de processus et en incorporant des éléments de modélisation à événements discrets. Ce langage, en se fondant sur le \pi-calcul, nous permet de décrire et de raisonner sur les systèmes mobiles, distribués et au temps-réel, à événements discrets, dans un cadre conceptuel unique. Nous développons une base théorique fondée sur la sémantique opérationnelle structurelle et nous établissons des propriétés fondamentales concernant le déterminisme-temps, la continuité, la compositionalité et la légitimité. Nous construisons un simulateur pour le langage qui supporte à la fois l'exécution séquentielle et distribuée de modèles, en utilisant une variante de l'algorithme Time Warp. Enfin, nous appliquons ce la

Description logics (DLs) are a family of knowledge representation languages to describe concepts in a given domain. While we can define the semantics of description logics using, for example, a translation into first-order logic, so far the proof-theoretic nature of DL has not been well investigated. In this thesis, we develop a proof theory for a constructive version of Description Logic, specifically Attributive Language with Complement (ALC), in two steps: First, we define a natural deduction system for ALC and develop a sequent calculus formulation, for which we prove cut-admissibility. We build on prior work on constructive description logic by de Paiva [2006] and modal logic by Simpson [1994], which ensures the consistency of the proposed systems for ALC. In addition, we prove soundness and completeness of this system with respect to known Kripke semantics. The study of these properties provides further evidence that it is appropriate to consider description languages as logics. Second, we adapt recent work by Andreoli [1992] on focusing systems for a variety of non-classical logics to the setting of constructive description logics. Exploiting the invertibility of certain inference rules, we design a focusing calculus suitable for backwards search, and prove its correctness via cut-admissibility. This proof-theoretic study lays the foundation for the development of a practical proof search strategy for constructive description logics. / Les logiques descriptives (DLs) sont une famille de langues de representation de connaissance pour décrire les concepts dans un domaine donné. Pendant que nous pouvons définir la sémantique de logiques descriptives en utilisant, par exemple, une traduction dans la logique du premier ordre, pour l'instant la nature théorique de preuve de DL n'a pas été bien enquêtée. Dans cette thèse, nous développons une théorie de preuve pour une version constructive de la logique descriptive, en "Attributive Language with Complement" (ALC ), en deux étapes: Premièrement, nous définissons un système de déduction naturel pour ALC et développons une formulation de calcul de séquent, pour laquelle nous prouvons l'admissibilité de coupure. Nous tirons parti du travail préalable sur la logique descriptive constructive par de Paiva [2006] et la logique modale par Simpson [1994], qui garantit la cohérence des systèmes proposés pour ALC. En plus, nous prouvons la solidité et complétude de ce système par rapport aux sémantiques Kripke connues. L'étude de ces propri étés fournissent plus d'indices que c'est approprié à considérer les langues descriptives comme des logiques propres. Deuxièmement, nous adaptons le travail récent par Andreoli [1992] sur les systèmes concentrés pour une variété de logiques non-classiques au cadre de logiques descriptives constructives. Le fait d'exploiter l'invertibility de certaines règles d'inférences, nous concevons un calcul concentré convenable à recherche reculons et prouvez son exactitude par l'admissibilité de coupure. Cette étude sur une théorie de preuve pose la fondation pour le développement d'une stratégie de recherche de preuves pratiques.

Application frameworks provide a general design that connects together the different parts of a program and that free developers from low-value activities. In the course of a framework's evolution, changes ranging from a simple function renaming to major modifications of the design can break client programs that depend on the framework. Finding suitable replacements for framework elements that were accessed by a client program and deleted as part of the framework's evolution can be a challenging task. We present a recommendation system, SemDiff, that suggests adaptations to client programs by analyzing how a framework was adapted to its own changes. In a study of the evolution of a large open-source framework and three client programs, our approach recommended relevant adaptive changes with a high level of precision, and detected non-trivial changes typically undiscovered by current changes detection techniques. / Les cadres d'applications fournissent un design général qui relie les différentes parties d'un programme et qui libère les développeurs des tâches à faible valeur ajoutée. Durant l'évolution d'un cadre d'applications, des changements allant d'un simple renommage d'une fonction à des modifications majeures du design peuvent briser les programmes clients qui dépendent du cadre d'applications. Trouver un remplacement adéquat pour les éléments du cadre d'applications qui étaient accédés par le programme client et qui ont été supprimés durant l'évolution du cadre d'applications peut s'avérer être une tâche difficile. Nous présentons un système de recommandations, SemDiff, qui suggère des adaptations aux programmes clients en analysant comment un cadre d'applications a été adapté à ses propres modifications. Dans une étude sur l'évolution d'un grand cadre d'applications en code source libre et de trois programmes clients, notre système a recommandé des adaptations pertinentes avec un haut degré de précision. Notre système a aussi détecté des changements non triviaux qui sont typiquement ignorés par les techniques de détection de changements courantes.

We offer an alternative method for type checking expressions in an extension of Hindley and Milner’s lambda calculus with generalized algebraic data types. The approach foregoes all mention of type equalities and unifiers and only applies type conversions at case statements in a deterministic fashion. What we introduce is a method for finding out the appropriate types of pattern bound variables within a type derivation and how to convert them back so that they are valid types in the context of the enclosing expression. Everything is done locally so scoping is no longer an issue. The system is proven sound and complete. An implementation of the system is discussed. / Ce document propose une methode alternative de verification du type dans une extension du systeme de typage de Hindley et Milner avec des types de donnees algebriques generalises. Cette methode n’utilise pas d’unificateur et d’egalite de type. De plus, elle ne convertit les types qu’a l’expression de case, et ce de maniere deterministique. Tout est fait localement dans ce systeme. Le systeme est prouve complet et correcte et une implementation est decrite.

With the launch of World of Warcraft in 2004, Massively Multiplayer Online Games (MMOGs) really came into their own as millions of people started playing worldwide. Providing scalability to such a large audience while maintaining a consistent gameplay experience is a diffcult task which many companies face in an industry where only few succeed. This thesis focuses on the issues of how a MMOG can be scaled to support more concurrent players and how consistency can be maintained in a Distributed Multi-Server Environment (DMSE). As a basis for investigation the notion of "Subgames" (i.e. games within games) was introduced. As smaller, more flexible game units, subgames reduce scalability problems but raise consistency concerns by requiring modular game actions in a distributed environment to function. This is addressed through a new transactional protocol and action framework which abstracts and solves consistency issues while creating an infrastructure which allows for scalability. A complete solution is illustrated using these techniques through the design of general game mechanics and subgames. The approach here further enables scalability of MMOGs in a DMSE and provides a general framework for the further investigation of MMOG consistency and scalability through subgame instances. / La popularité des jeux massivement multi-joueurs en ligne ( MMOGs ) a grandement augmenté avec l'arrivée du jeu World of Warcraft, qui est joué par des millions de personnes à travers le monde. Cependant, ce type d'application nécessite des infrastructures extensibles pour accommoder des milliers de joueurs, tout en offrant une expérience de jeu consistante. Ceci représente un grand obstacle que plusieurs compagnies doivent affronter, mais qui est surmonté par peu. Cette thèse aborde les problèmes reliés à la croissance du nombre de joueurs simultanés, tout en discutant comment maintenir un environnement distribué multi- serveurs ( DMSE ) consistant. La notion de sous-jeux ( un jeu qui se déroule l'intérieur d'un autre jeu ) a été utilisée pour mieux étudier le problème. En tant qu'unités de jeu plus petits et flexibles, les sous-jeux facilitent la croissance, mais augmentent les problèmes de concurrence puisque leur bon fonctionnement nécessite des actions modulaires dans un environnement distribué. Ces défis sont adressés par un nouveau protocole transactionnel et un cadre d'applications d'actions qui font abstraction et règlent les problèmes de consistance, tout en offrant une infrastructure qui permet une certaine croissance. Une solution, où les mécanismes de jeux et de sous-jeux sont adaptés en conséquence, illustre les techniques proposées dans cette thèse. Ces techniques permettent une plus grande croissance pour les jeux MMOGs dans un DMSE, tout en fournissant des outils de sous-jeux qui permettent l'étude des défis de consistance et de croissance.

Modal logics were formalized in the early to mid-20th century to pin down the notion of truth qualified by modalities such as "necessity", "possibility", and "belief", which arise in philosophy and natural languages. They have since outgrown their philosophical trappings and have found applications in type systems and as description languages in many domains of computer science and artificial intelligence. Although they frequently exhibit redundancies in their proof spaces, analytic tableau systems in the style of Smullyan have emerged as popular proof formalisms for modal logics. Inspired by previous work on matrix characterizations by Bibel, Andrews, and Wallen, we propose a new characterization of validity for a family of multimodal logics with interacting accessibility relations which avoids the redundancies common in tableau systems. Our goal is not to produce a high-performance theorem prover for multimodal logics, but to present a fresh way of understanding and establishing multimodal logical validity. / Les logiques modales ont été formalisées vers le milieu du 20ième siècle avec le but de comprendre la notion de vérité qualifiée par des modes tels que "la nécessité", "la possibilité", et "la croyance", qui proviennent de la philosophie et des langages naturels. Ces modes, depuis évolués au-delà de leurs origines philosophiques, trouvent plusieurs applications dans la sémantique statique des langages de programmation et chez les logiques de description de plusieurs domaines de l'informatique et de l'intelligence artificielle. Bien que leurs espaces démonstrationnels présentent des redondances, les systèmes de tableaux analytiques sont un formalisme de démonstration populaire. Nous proposons une nouvelle caractérisation de validité pour une famille de logiques multimodales définies avec des relations d'accessibilité interagissantes qui évite les redondances présentes chez les systèmes de tableaux. Nos innovations sont inspirées par les caractérisations matricielles présentées auparavant par Bibel, Andrews, et Wallen. Notre but n'est pas de produire un démonstrateur automatique de théorèmes de haute performance, mais de présenter une façon originale de comprendre et concevoir la validité logique multimodale.