L'utilisation des méthodes formelles est de plus en plus courante dans le développement logiciel, et les systèmes de types sont la méthode formelle qui a le plus de succès. L'avancement des méthodes formelles présente de nouveaux défis, ainsi que de nouvelles opportunités. L'un des défis est d'assurer qu'un compilateur préserve la sémantique des programmes, de sorte que les propriétés que l'on garantit à propos de son code source s'appliquent également au code exécutable. Cette thèse présente un compilateur qui traduit un langage fonctionnel d'ordre supérieur avec polymorphisme vers un langage assembleur typé, dont la propriété principale est que la préservation des types est vérifiée de manière automatisée, à l'aide d'annotations de types sur le code du compilateur. Notre compilateur implante les transformations de code essentielles pour un langage fonctionnel d'ordre supérieur, nommément une conversion CPS, une conversion des fermetures et une génération de code. Nous présentons les détails des représentation fortement typées des langages intermédiaires, et les contraintes qu'elles imposent sur l'implantation des transformations de code. Notre objectif est de garantir la préservation des types avec un minimum d'annotations, et sans compromettre les qualités générales de modularité et de lisibilité du code du compilateur. Cet objectif est atteint en grande partie dans le traitement des fonctionnalités de base du langage (les «types simples»), contrairement au traitement du polymorphisme qui demande encore un travail substantiel pour satisfaire la vérification de type. / Formal methods are rapidly improving and gaining ground in software. Type systems are the most successful and popular formal method used to develop software. As the technology of type systems progresses, new needs and new opportunities appear. One of those needs is to ensure the faithfulness of the translation from source code to machine code, so that the properties you prove about the code you write also apply to the code you run. This thesis presents a compiler from a polymorphic higher-order functional language to typed assembly language, whose main property is that type preservation is verified statically, through type annotations on the compiler's code. Our compiler implements the essential code transformations for a higher-order functional language, namely a CPS conversion and closure conversion as well as a code generation. The thesis presents the details of the strongly typed intermediate representations and the constraints they set on the implementation of code transformations. Our goal is to guarantee type preservation with a minimum of type annotations, and without compromising readability and modularity of the code. This goal is already a reality for simple types, and we discuss the problems remaining for polymorphism, which still requires substantial extra work to satisfy the type checker.

Cette thèse est consacrée à la complexité basée sur le paradigme des preuves interactives. Les classes ainsi définies ont toutes en commun qu’un ou plusieurs prouveurs, infiniment puissants, tentent de convaincre un vérificateur, de puissance bornée, de l’appartenance d’un mot à un langage. Nous abordons ici le modèle classique, où les participants sont des machines de Turing, et le modèle quantique, où ceux-ci sont des circuits quantiques. La revue de littérature que comprend cette thèse s’adresse à un lecteur déjà familier avec la complexité et l’informatique quantique. Cette thèse présente comme résultat la caractérisation de la classe NP par une classe de preuves interactives quantiques de taille logarithmique. Les différentes classes sont présentées dans un ordre permettant d’aborder aussi facilement que possible les classes interactives. Le premier chapitre est consacré aux classes de base de la complexité ; celles-ci seront utiles pour situer les classes subséquemment présentées. Les chapitres deux et trois présentent respectivement les classes à un et à plusieurs prouveurs. La présentation du résultat ci-haut mentionné est l’objet du chapitre quatre. / This thesis is devoted to complexity theory based on the interactive proof paradigm. All classes defined in this way involve one or many infinitely powerful provers attempting to convince a verifier of limited power that a string belongs to a certain language. We will consider the classical model, in which the various participants are Turing machines, as well as the quantum model, in which they are quantum circuits. The literature review included in this thesis assume that the reader is familiar with the basics of complexity theory and quantum computing. This thesis presents the original result that the class NP can be characterized by a class of quantum interactive proofs of logarithmic size. The various classes are presented in an order that facilitates the treatment of interactive classes. The first chapter is devoted to the basic complexity classes; these will be useful points of comparison for classes presented subsequently. Chapters two and three respectively present classes with one and many provers. The presentation of the result mentioned above is the object of chapter four.

La recherche en génie logiciel a depuis longtemps tenté de mieux comprendre le processus de développement logiciel, minimalement, pour en reproduire les bonnes pratiques, et idéalement, pour pouvoir le mécaniser. On peut identifier deux approches majeures pour caractériser le processus. La première approche, dite transformationnelle, perçoit le processus comme une séquence de transformations préservant certaines propriétés des données à l’entrée. Cette idée a été récemment reprise par l’architecture dirigée par les modèles de l’OMG. La deuxième approche consiste à répertorier et à codifier des solutions éprouvées à des problèmes récurrents. Les recherches sur les styles architecturaux, les patrons de conception, ou les cadres d’applications s’inscrivent dans cette approche. Notre travail de recherche reconnaît la complémentarité des deux approches, notamment pour l’étape de conception: dans le cadre du développement dirigé par les modèles, nous percevons l’étape de conception comme l’application de patrons de solutions aux modèles reçus en entrée. Il est coutume de définir l’étape de conception en termes de conception architecturale, et conception détaillée. La conception architecturale se préoccupe d’organiser un logiciel en composants répondant à un ensemble d’exigences non-fonctionnelles, alors que la conception détaillée se préoccupe, en quelque sorte, du contenu de ces composants. La conception architecturale s’appuie sur des styles architecturaux qui sont des principes d’organisation permettant d’optimiser certaines qualités, alors que la conception détaillée s’appuie sur des patrons de conception pour attribuer les responsabilités aux classes. Les styles architecturaux et les patrons de conception sont des artefacts qui codifient des solutions éprouvées à des problèmes récurrents de conception. Alors que ces artefacts sont bien documentés, la décision de les appliquer reste essentiellement manuelle. De plus, les outils proposés n’offrent pas un support adéquat pour les appliquer à des modèles existants. Dans cette thèse, nous nous attaquons à la conception détaillée, et plus particulièrement, à la transformation de modèles par application de patrons de conception, en partie parce que les patrons de conception sont moins complexes, et en partie parce que l’implémentation des styles architecturaux passe souvent par les patrons de conception. Ainsi, nous proposons une approche pour représenter et appliquer les patrons de conception. Notre approche se base sur la représentation explicite des problèmes résolus par ces patrons. En effet, la représentation explicite du problème résolu par un patron permet : (1) de mieux comprendre le patron, (2) de reconnaître l’opportunité d’appliquer le patron en détectant une instance de la représentation du problème dans les modèles du système considéré, et (3) d’automatiser l’application du patron en la représentant, de façon déclarative, par une transformation d’une instance du problème en une instance de la solution. Pour vérifier et valider notre approche, nous l’avons utilisée pour représenter et appliquer différents patrons de conception et nous avons effectué des tests pratiques sur des modèles générés à partir de logiciels libres. / Software engineering researchers have long tried to understand the software process development to mechanize it or at least to codify its good practices. We identify two major approaches to characterize the process. The first approach—known as transformational—sees the process as a sequence of property-preserving transformations. This idea was recently adopted by the OMG’s model-driven architecture (MDA). The second approach consists in identifying and codifying proven solutions to recurring problems. Research on architectural styles, frameworks and design patterns are part of this approach. Our research recognizes the complementarity of these two approaches, in particular in the design step. Indeed within the model-driven development context, we view software design as the process of applying codified solution patterns to input models. Software design is typically defined in terms of architectural design and detailed design. Architectural design aims at organizing the software in modules or components that meet a set of non-functional requirements while detailed design is—in some way—concerned by the contents of the identified components. Architectural design relies on architectural styles which are principles of organization to optimize certain quality requirements, whereas detailed design relies on design patterns to assign responsibilities to classes. Both architectural styles and design patterns are design artifacts that encode proven solutions to recurring design problems. While these design artifacts are documented, the decision to apply them remains essentially manual. Besides, once a decision has been made to use a design artifact, there is no adequate support to apply it to existing models. As design patterns present an ‘‘easier’’ problem to solve, and because architectural styles implementation relies on design patterns, our strategy for addressing these issues was to try to solve the problem for design patterns first, and then tackle architectural styles. Hence, in this thesis, we propose an approach for representing and applying design patterns. Our approach is based on an explicit representation of the problems solved by design patterns. Indeed, and explicit representation of the problem solved by a pattern enables to: 1) better understand the pattern, 2) recognize the opportunity of applying the pattern by matching the representation of the problem against the models of the considered system, and 3) specify declaratively the application of the pattern as a transformation of an instance of the problem into an instance of the solution. To verify and validate the proposed approach, we used it to represent and apply several design patterns. We also conducted practical tests on models generated from open source systems.

Dans le développement logiciel en industrie, les documents de spécification jouent un rôle important pour la communication entre les analystes et les développeurs. Cependant, avec le temps, les changements de personel et les échéances toujours plus courtes, ces documents sont souvent obsolètes ou incohérents avec l'état effectif du système, i.e., son code source. Pourtant, il est nécessaire que les composants du système logiciel soient conservés à jour et cohérents avec leurs documents de spécifications pour faciliter leur développement et maintenance et, ainsi, pour en réduire les coûts. Maintenir la cohérence entre spécification et code source nécessite de pouvoir représenter les changements sur les uns et les autres et de pouvoir appliquer ces changements de manière cohérente et automatique. Nous proposons une solution permettant de décrire une représentation d'un logiciel ainsi qu'un formalisme mathématique permettant de décrire et de manipuler l'évolution des composants de ces représentations. Le formalisme est basé sur les triplets de Hoare pour représenter les transformations et sur la théorie des groupes et des homomorphismes de groupes pour manipuler ces transformations et permettrent leur application sur les différentes représentations du système. Nous illustrons notre formalisme sur deux représentations d'un système logiciel : PADL, une représentation architecturale de haut niveau (semblable à UML), et JCT, un arbre de syntaxe abstrait basé sur Java. Nous définissons également des transformations représentant l'évolution de ces représentations et la transposition permettant de reporter les transformations d'une représentation sur l'autre. Enfin, nous avons développé et décrivons brièvement une implémentation de notre illustration, un plugiciel pour l'IDE Eclipse détectant les transformations effectuées sur le code par les développeurs et un générateur de code pour l'intégration de nouvelles représentations dans l'implémentation. / When developing software system in industry, system specifications are heavily used in communication among analysts and developers. However, system evolution, employee turn-over and shorter deadlines lead those documents either not to be up-to-date or not to be consistent with the actual system source code. Yet, having up-to-date documents would greatly help analysts and developers and reduce development and maintenance costs. Therefore, we need to keep those documents up-to-date and consistent. We propose a novel mathematical formalism to describe and manipulate the evolution of these documents. The mathematical formalism is based on Hoare triple to represent the transformations and group theory and groups homomorphisms to manipulate these transformations and apply them on different representations. We illustrate our formalism using two representation of a same system: PADL, that is an abstract design specification (similar to UML), and JCT, that is an Abstract Syntax Tree for Java. We also define transformations describing their evolutions, and transformations transposition from one representation to another. Finally, we provide an implementation of our illustration, a plugin for the Eclipse IDE detecting source code transformations made by a developer and a source code generator for integrating new representations in the implementation.

Les cadriciels et les bibliothèques sont indispensables aux systèmes logiciels d'aujourd'hui. Quand ils évoluent, il est souvent fastidieux et coûteux pour les développeurs de faire la mise à jour de leur code. Par conséquent, des approches ont été proposées pour aider les développeurs à migrer leur code. Généralement, ces approches ne peuvent identifier automatiquement les règles de modification une-remplacée-par-plusieurs méthodes et plusieurs-remplacées-par-une méthode. De plus, elles font souvent un compromis entre rappel et précision dans leur résultats en utilisant un ou plusieurs seuils expérimentaux. Nous présentons AURA (AUtomatic change Rule Assistant), une nouvelle approche hybride qui combine call dependency analysis et text similarity analysis pour surmonter ces limitations. Nous avons implanté AURA en Java et comparé ses résultats sur cinq cadriciels avec trois approches précédentes par Dagenais et Robillard, M. Kim et al., et Schäfer et al. Les résultats de cette comparaison montrent que, en moyenne, le rappel de AURA est 53,07% plus que celui des autre approches avec une précision similaire (0,10% en moins). / Software frameworks and libraries are indispensable to today's software systems. As they evolve, it is often time-consuming for developers to keep their code up-to-date. Approaches have been proposed to facilitate this. Usually, these approaches cannot automatically identify change rules for one-replaced-by-many and many-replaced-by-one methods, and they trade off recall for higher precision using one or more experimentally-evaluated thresholds. We introduce AURA (AUtomatic change Rule Assistant), a novel hybrid approach that combines call dependency and text similarity analyses to overcome these limitations. We implement it in a Java system and compare it on five frameworks with three previous approaches by Dagenais and Robillard, M. Kim et al., and Schäfer et al. The comparison shows that, on average, the recall of AURA is 53.07% higher while its precision is similar (0.10% lower).

Le présent mémoire comprend un survol des principales méthodes de rendu en demi-tons, de l’analog screening à la recherche binaire directe en passant par l’ordered dither, avec une attention particulière pour la diffusion d’erreur. Ces méthodes seront comparées dans la perspective moderne de la sensibilité à la structure. Une nouvelle méthode de rendu en demi-tons par diffusion d’erreur est présentée et soumise à diverses évaluations. La méthode proposée se veut originale, simple, autant à même de préserver le caractère structurel des images que la méthode à l’état de l’art, et plus rapide que cette dernière par deux à trois ordres de magnitude. D’abord, l’image est décomposée en fréquences locales caractéristiques. Puis, le comportement de base de la méthode proposée est donné. Ensuite, un ensemble minutieusement choisi de paramètres permet de modifier ce comportement de façon à épouser les différents caractères fréquentiels locaux. Finalement, une calibration détermine les bons paramètres à associer à chaque fréquence possible. Une fois l’algorithme assemblé, toute image peut être traitée très rapidement : chaque pixel est attaché à une fréquence propre, cette fréquence sert d’indice pour la table de calibration, les paramètres de diffusion appropriés sont récupérés, et la couleur de sortie déterminée pour le pixel contribue en espérance à souligner la structure dont il fait partie. / This work covers some important methods in the domain of halftoning: analog screening, ordered dither, direct binary search, and most particularly error diffusion. The methods will be compared in the modern perspective of sensitivity to structure. A novel halftoning method is also presented and subjected to various evaluations. It produces images of visual quality comparable to that of the state-of-the-art Structure-aware Halftoning method; at the same time, it is two to three orders of magnitude faster. First is described how an image can be decomposed into its local frequency content. Then, the basic behavior of the proposed method is given. Next, a carefully chosen set of parameters is presented that allow modifications to this behavior, so as to maximize the eventual reactivity to frequency content. Finally, a calibration step determines what values the parameters should take for any local frequency information encountered. Once the algorithm is assembled, any image can be treated very efficiently: each pixel is attached to its dominant frequency, the frequency serves as lookup index to the calibration table, proper diffusion parameters are retrieved, and the determined output color contributes in expectation to underline the structure from which the pixel comes.

La méthode de subdivision Catmull-Clark ainsi que la méthode de subdivision Loop sont des normes industrielle de facto. D'autre part, la méthode de subdivision 4-8 est bien adaptée à la subdivision adaptative, parce que cette méthode augmente le nombre de faces ou de sommets par seulement un facteur de 2 à chaque raffinement. Cela promet d'être plus pratique pour atteindre un niveau donné de précision. Dans ce mémoire, nous présenterons une méthode permettant de paramétrer des surfaces de subdivision de la méthode Catmull-Clark et de la méthode 4-8. Par conséquent, de nombreux algorithmes mis au point pour des surfaces paramétriques pourrant être appliqués aux surfaces de subdivision Catmull-Clark et aux surfaces de subdivision 4-8. En particulier, nous pouvons calculer des bornes garanties et réalistes sur les patches, un peu comme les bornes correspondantes données par Wu-Peters pour la méthode de subdivision Loop. / The Catmull-Clark and Loop methods are de facto industry standards. On the other hand, the 4-8 subdivision method is well suited for adaptive subdivision, because this method increases the number of faces or vertices by only a factor of 2 at each step. It is therefore more convenient when trying to achieve a given practical level of precision. In this thesis we will introduce a method to parametrize the subdivision surfaces of Catmull-Clark and 4-8 subdivision. As a consequence, many algorithms developed for parametric surfaces will be able to be applied to Catmull-Clark and 4-8 subdivision surfaces. In particular, we can produce bounds on surface patches which are both guaranteed and realistic, similar to the bounds given by Wu-Peters [24] for the Loop method

Vidéos et images des résultats disponible à : http://www.iro.umontreal.ca/labs/infographie/theses/fatnasss/ / La synthèse d'une flamme animée dans un environnement 3D virtuel, reste à ce jour une tâche ardue, exigeant de judicieusement balancer réalisme et coût de calcul. Dans ce mémoire, nous présentons un ensemble de techniques pour sa simulation en temps réel tout en modélisant une interaction à des forces externes. Nous désirons minimiser son coût de calcul tout en préservant une apparence convaincante dans l'optique d'une intégration au sein de systèmes existants, n'affectant pas indûment leurs performances. Un champ de vélocité est extrait d'une simulation de ressorts et mis à profit dans le déplacement de chaînes de particules modélisant la forme de la flamme par l'entremise de la paramétrisation d'une surface NURBS. Considérant l'importance qu'ils ont sur notre perception de la combustion, nous prenons également soin de reproduire l'illumination, les ombres, et l'effet d'éblouissement qu'elle engendre. / The synthesis of an open flame in a virtual 3D environment, remains to this day an arduous task, requiring a wise balance between realism and processing cost. In this M. Sc. thesis, we present a set of techniques for its simulation in real time while also modeling the interaction with external forces. Our goal is to minimize the cost while preserving a convincing appearance, thus facilitating integration of the techniques into existing systems without unduly affecting their performance. A velocity field is extracted from a spring-mass simulation which contributes to moving chains of particules that are used in modeling the flame shape through the configuration of a NURBS surface. In light of the importance they have on our perception of combustion, we also take care to duplicate the lighting, shadows and bloom the flame gives rise to.

Nous proposons une approche semi-automatique pour la rétro-ingénierie des diagrammes de séquence d’UML. Notre approche commence par un ensemble de traces d'exécution qui sont automatiquement alignées pour déterminer le comportement commun du système. Les diagrammes de séquence sont ensuite extraits avec l’aide d’une visualisation interactive, qui permet la navigation dans les traces d'exécution et la production des opérations d'extraction. Nous fournissons une illustration concrète de notre approche avec une étude de cas, et nous montrons en particulier que nos diagrammes de séquence générés sont plus significatifs et plus compacts que ceux qui sont obtenus par les méthodes automatisées. / We propose a semi-automated approach for the reverse engineering of UML sequence diagrams. Our approach starts with a set of execution traces that are automatically aligned to determine the common behavior. Sequence diagrams are then extracted with the help of an interactive visualization, which allows navigating though execution traces and performing extraction operations. We provide a concrete illustration of our approach with a case study, and show in particular that the resulting diagrams are more meaningful and more compact than those extracted by automated approaches.

Les systèmes de traduction statistique à base de segments traduisent les phrases un segment à la fois, en plusieurs étapes. À chaque étape, ces systèmes ne considèrent que très peu d’informations pour choisir la traduction d’un segment. Les scores du dictionnaire de segments bilingues sont calculés sans égard aux contextes dans lesquels ils sont utilisés et les modèles de langue ne considèrent que les quelques mots entourant le segment traduit.Dans cette thèse, nous proposons un nouveau modèle considérant la phrase en entier lors de la sélection de chaque mot cible. Notre modèle d’intégration du contexte se différentie des précédents par l’utilisation d’un ppc (perceptron à plusieurs couches). Une propriété intéressante des ppc est leur couche cachée, qui propose une représentation alternative à celle offerte par les mots pour encoder les phrases à traduire. Une évaluation superficielle de cette représentation alter- native nous a montré qu’elle est capable de regrouper certaines phrases sources similaires même si elles étaient formulées différemment. Nous avons d’abord comparé avantageusement les prédictions de nos ppc à celles d’ibm1, un modèle couramment utilisé en traduction. Nous avons ensuite intégré nos ppc à notre système de traduction statistique de l’anglais vers le français. Nos ppc ont amélioré les traductions de notre système de base et d’un deuxième système de référence auquel était intégré IBM1. / Phrase-based statistical machine translation systems translate source sentences one phrase at a time, conditioning the choice of each phrase on very little information. Bilingual phrase table scores are computed regardless of the context in which the phrases are used and language models only look at few words surrounding the target phrases. In this thesis, we propose a novel model to predict words that should appear in a translation given the source sentence as a whole. Our model differs from previous works by its use of mlp (multilayer perceptrons). Our interest in mlp lies in their hidden layer that encodes source sentences in a representation that is only loosely tied to words. We observed that this hidden layer was able to cluster some sentences having similar translations even if they were formulated differently. In a first set of experiments, we compared favorably our mlp to ibm1, a well known model in statistical machine translation. In a second set of experiments, we embedded our ppc in our English to French statistical machine translation system. Our MLP improved translations quality over our baseline system and a second system embedding an IBM1 model.