Au fil des ans, l’algèbre de Kleene s’est avérée être un outil formel très pratique et flexible quant vient le temps de raisonner sur les programmes informatiques. Cependant, actuellement, la plupart des applications à l’analyse de programmes de l’algèbre de Kleene se font en sélectionnant un problème précis et en voyant comment l’algèbre de Kleene permet de le résoudre, ce qui limite les applications possibles. L’objectif visé par ce mémoire est de déterminer dans quelle mesure la résolution d’équations, en algèbre de Kleene, peut être utilisée en analyse de programmes. Une grande partie de ce mémoire est donc consacrée à la résolution de différents types d’équations dans différentes variantes de l’algèbre de Kleene. Puis nous montrons comment la vérification de programmes ainsi que la synthèse de contrôleurs peuvent tirer profit de la résolution d’équations en algèbre de Kleene.

La prise de décision dans un environnement partiellement observable est un sujet d'actualité en intelligence artificielle. Une façon d'aborder ce type de problème est d'utiliser un modèle mathématique. Notamment, les POMDPs (Partially Observable Markov Decision Process) ont fait l'objet de plusieurs recherches au cours des dernières années. Par contre, résoudre un POMDP est un problème très complexe et pour cette raison, le modèle n'a pas été utilisé abondamment. Notre objectif était de continuer les progrès ayant été réalisé lors des dernières années, avec l'espoir que nos travaux de recherches seront un pas de plus vers l'application des POMDPs dans des applications d'envergures. Dans un premier temps, nous avons développé un nouvel algorithme hors-ligne qui, sur des problèmes tests, est plus performant que les meilleurs algorithmes existants. La principale innovation vient du fait qu'il s'agit d'un algorithme stochastique alors que les algorithmes traditionnels sont déterministes. Dans un deuxième temps, nous pouvons également appliquer cet algorithme dans des environnements en-lignes. Lorsque ceux-ci revêtent une certaine particularité, notre algorithme est beaucoup plus performant que la compétition. Finalement, nous avons appliqué une version simplifiée de notre algorithme dans le cadre du projet Combat Identification du RDDC-Valcartier. / Decision making under uncertainty is a popular topic in the field of artificial intelligence. One popular way to attack such problems is by using a sound mathematical model. Notably, Partially Observable Markov Processes (POMDPs) have been the subject of extended researches over the last ten years or so. However, solving a POMDP is a very time-consuming task and for this reason, the model has not been used extensively. Our objective was to continue the tremendous progress that has been made over the last couple of years, with the hope that our work will be a step toward applying POMDPs in large-scale problems. To do so, we combined different ideas in order to produce a new algorithm called SSVI (Stochastic Search Value Iteration). Three major accomplishments were achieved throughout this research work. Firstly, we developed a new offline POMDP algorithm which, on benchmark problems, proved to be more efficient than state of the arts algorithm. The originality of our method comes from the fact that it is a stochastic algorithm, in comparison with the usual determinist algorithms. Secondly, the algorithm we developed can also be applied in a particular type of online environments, in which this algorithm outperforms by a significant margin the competition. Finally, we also applied a basic version of our algorithm in a complex military simulation in the context of the Combat Identification project from DRDC-Valcartier.

L’évolution et le succès qu’a connu Internet les dernières années a profondément marqué le domaine du génie logiciel et plus particulièrement des aspects tels que la conception, l’implémentation et l’exploitation de systèmes distribués. Cette ouverture qu’offre la toile aux systèmes brave les limites architecturales et géographiques pour permettre une interconnexion permanente des utilisateurs. Cependant, ce flux de communication et de code mobile comporte des risques de sécurité qui vont à l’encontre des politiques des entreprises concernées par ces échanges. Étant données la multitude et la diversité des intervenants, des mesures préventives s’imposent pour remédier à cette faille sécuritaire. Ce mémoire s’inscrit dans le cadre d’une contribution à cet effort, par la voie de la certification. En effet, le potentiel de l’approche proposée émerge de la synthèse des techniques fondamentales de ce domaine, qui sont le code incorporant une preuve (PCC), le langage assembleur typé (TAL) et le code incorporant un modèle (MCC). Toujours dans l’optique de renforcer la relation de confiance entre le producteur et le consommateur, et au-delà de la vérification du respect du code envers une politique de sécurité, notre projet qui s’intitule «code incorporant un modèle certifié» (CMCC) couvre en plus des aspects pratiques jusque là souvent délaissés par les concepteurs.

Les mathématiques offrent un cadre convenable pour raisonner rigoureusement sur les systèmes et phénomènes réels. Par exemple, en génie logiciel, les méthodes formelles sont parmi les outils les plus efficaces pour détecter les anomalies dans les logiciels. Plusieurs systèmes réels sont stochastiques par nature dans le sens où leur comportement est sujet à un aspect d'incertitude. La représentation de ce genre de systèmes requiert des modèles stochastiques comme les processus de Markov étiquetés (LMP), les processus de Markov décisionnels (MDP), etc. Cette thèse porte sur la quantification de la différence entre les systèmes stochastiques. Les contributions majeures sont : 1. une nouvelle approche pour quantifier la divergence entre les systèmes stochastiques basée sur l'apprentissage par renforcement, 2. une nouvelle famille de notions d'équivalence qui se situe entre l'équivalence par trace et la bisimulation, et 3. un cadre plus flexible pour la définition des notions d'équivalence qui se base sur les tests. Le résultat principal de la thèse est que l'apprentissage par renforcement, qui est une branche de l'intelligence artificielle particulièrement efficace en présence d'incertitude, peut être utilisé pour quantifier efficacement cette divergence. L'idée clé est de définir un MDP à partir des systèmes à comparer de telle sorte que la valeur optimale de cet MDP corresponde à la divergence entre eux. La caractéristique la plus attrayante de l'approche proposée est qu'elle est complètement indépendante des structures internes des systèmes à comparer. Pour cette raison, l'approche peut être appliquée à différents types de systèmes stochastiques. La deuxième contribution est une nouvelle famille de notions d'équivalence, que nous appelons moment, qui est plus forte que l'équivalence par trace mais plus faible que la bisimulation. Cette famille se définit naturellement à travers la coïncidence de moments de variable aléatoires (d'où son nom) et possède une caractérisation simple en terme de tests. Nous montrons que moment fait partie d'un cadre plus grand, appelé test-observation-equivalence (TOE), qui constitue la troisième contribution de cette thèse. Il s'agit d'un cadre plus flexible pour la définition des notions d'équivalence basé sur les tests. / Modelling real-life systems and phenomena using mathematical based formalisms is ubiquitous in science and engineering. The reason is that mathematics offer a suitable framework to carry out formal and rigorous analysis of these systems. For instance, in software engineering, formal methods are among the most efficient tools to identify flaws in software. The behavior of many real-life systems is inherently stochastic which requires stochastic models such as labelled Markov processes (LMPs), Markov decision processes (MDPs), predictive state representations (PSRs), etc. This thesis is about quantifying the difference between stochastic systems. The main contributions are: 1. a new approach to quantify the divergence between pairs of stochastic systems based on reinforcement learning, 2. a new family of equivalence notions which lies between trace equivalence and bisimulation, and 3. a refined testing framework to define equivalence notions. The important point of the thesis is that reinforcement learning (RL), a branch of artificial intelligence particularly efficient in presence of uncertainty, can be used to quantify efficiently the divergence between stochastic systems. The key idea is to define an MDP out of the systems to be compared and then to interpret the optimal value of the MDP as the divergence between them. The most appealing feature of the proposed approach is that it does not rely on the knowledge of the internal structure of the systems. Only a possibility of interacting with them is required. Because of this, the approach can be extended to different types of stochastic systems. The second contribution is a new family of equivalence notions, moment, that constitute a good compromise between trace equivalence (too weak) and bisimulation (too strong). This family has a natural definition using coincidence of moments of random variables but more importantly, it has a simple testing characterization. moment turns out to be part of a bigger framework called test-observation-equivalence (TOE), which we propose as a third contribution of this thesis. It is a refined testing framework to define equivalence notions with more flexibility.

No description available.

Ce mémoire de maîtrise s’inscrit dans le domaine de l’ingénierie de connaissances et plus précisément dans une tâche de construction de contenu pédagogique pour un système éducationnel. Jusqu’ici, divers outils de présentation, d’échange et de stockage des informations ont été développés pour favoriser l’apprentissage de l’étudiant dans les systèmes éducationnels. Cependant, à notre connaissance, peu d’outils visent à minimiser l’effort de l’enseignant dans la construction de contenu pédagogique. L’objectif de notre projet est d’approfondir la notion d’acquisition des connaissances pour aider l’enseignant à construire les connaissances associées à un système éducationnel. Ce projet s’insère dans le cadre de la conception d’un système informatique, disponible en ligne, pour l’apprentissage humain à partir d’exemples. Un agent d’acquisition est proposé pour entrer des exemples et générer automatiquement des documents électroniques représentant ces exemples. Cet agent a été développé et permet de créer des patrons représentant la structure d’un exemple donné. Une interface d’acquisition est générée à partir d’un patron pour permettre la saisie des données qui vont servir à générer l’exemple. Cet exemple sera stocké dans un fichier XML, puis présenté à l’apprenant par le système éducationnel. La technologie XML se prête bien à ces tâches de gestion des connaissances, car elle permet d’inclure une logique de traitement des informations et d’automatiser les traitements, et ce de façon indépendante de la plate-forme utilisée. L’enseignant dispose ainsi d’un outil lui permettant d’ajouter des exemples d’exercices résolus d’une manière plus conviviale et plus flexible, peu importe le contenu de l’exemple.

No description available.

Depuis quelques années, on assiste à une expansion fulgurante du marché des terminaux mobiles et sans fil. Dans ce cadre, le déploiement de la technologie Java sur ce type de terminaux connaît un grand succès à cause de ses caractéristiques attrayantes, à savoir la mobilité, la portabilité et la sécurité. En particulier, la plate-forme J2ME/CLDC (Java 2 Micro Edition for Connected Limited Device Configuration) est dédiée au développement d’applications Java qui s’exécutent sur des téléphones cellulaires, des assistants digitaux et de façon générale sur tous les systèmes embarqués dans des appareils électroniques ou industriels. Par ailleurs, la plate-forme J2ME est dotée d’une version allégée de la machine virtuelle Java, appelée KVM (Kilobyte Virtual Machine). Comme toutes machines virtuelles Java, le principal inconvénient de la KVM est sa lenteur d’exécution due au mécanisme d’interprétation. Par conséquent, il y a un besoin réel de disposer de techniques d’accélération qui permettent d’améliorer la performance de la KVM, étant données les contraintes matérielles des plates-formes Java mobiles (ressources mémoire restreintes, puissance de traitement limitée et faible batterie). C’est dans ce contexte particulier que nous abordons la problématique de l’accélération d’une machine virtuelle dédiée à une plate-forme Java mobile. Dans le cadre de cette thèse, nous proposons de concevoir et d’implanter des techniques d’accélération de la machine virtuelle Java pour la plate-forme J2ME/CLDC. Nous proposons également d’élaborer un cadre sémantique pour capturer de manière formelle le langage de bytecode de la plate-forme J2ME/CLDC. Les principaux résultats qui nous ont permis d’atteindre nos objectifs sont : 1. La conception et l’implantation d’un compilateur dynamique sélectif qui accélère la KVM d’un facteur de 400%. également, des techniques accélérant l’appel de méthodes ont été conçues et implantées. 2. élaboration d’un cadre formel dans un style dénotationnel par passage de continuations supportant les aspects intrinsèques du langage Java, à savoir : parallélisme, le non-déterminisme non borné, les structures d’échappement et les données. 3. Spécification du langage de bytecode de la plate-forme J2ME/CLDC dans le cadre sémantique élaboré. / Nowdays, we are witnessing a high expansion of the mobile and wireless devices market. In this context, the Java technology is emerging as a standard execution environment due to its appealing features such as mobility, portability and security. In particular, The J2ME/CLDC platform (Java 2 Micro Edition for Connected Limited Device Configuration) is dedicated to the Java application development for mobile devices and embedded systems. The J2ME/CLDC platform is equipped with a light Java virtual machine, called KVM (Kilobyte Virtual Machine). The main issue of this virtual machine is its performance due to the interpretation mechanism. Consequently, there is a real need to design and implement acceleration techniques for the KVM. Moreover, constraints of wireless and mobile devices in terms of footprint, computation and energy consumption should be considered in the design of these techniques. The main objectives of this thesis are the design and the implementation of acceleration techniques dedicated to the Java virtual machine for the J2ME/CLDC platform. We also intent to elaborate a semantic model to formally capture the bytecode language of the J2ME/CLDC platform.The main research results that achieved these objectives are : 1. The design and implementation of a dynamic selective compiler that speeds up the KVM by a rate of 400%. Other acceleration techniques has been designed and implemented to enhance the method call mechanism. 2. The elaboration of a denotational semantic model with continuations that supports the particular features of the Java language : concurrency, unbounded nondeterminism, escaping constructs and data. 3. The specification of the bytecode language of the J2ME/CLDC platform in the elaborated semantic model.

No description available.

La géosimulation est une approche qui permet la modélisation et la simulation de phénomènes dynamiques. Elle est appliquée dans un grand nombre de domaines tels que l’urbanisme, la gestion de l’environnement et la santé publique. La géosimulation se base sur des données géo-référencées qui fournissent le contexte spatial virtuel de la simulation. La dynamique du phénomène simulé est généralement fondée sur des modèles, des algorithmes et/ou des équations mathématiques. Dans le domaine de la santé publique qui nous concerne ici, plusieurs approches de simulation ont été proposées pour simuler la propagation des maladies vectorielles ou zoonoses. Une zoonose est une maladie propagée par un virus ou une bactérie transmise par des insectes (ex. moustiques, tiques) à des animaux (rongeurs, oiseaux, mammifères) qui peuvent être infectés, et à leur tour transmettre le virus ou la bactérie à des insectes sains qui les piquent. Éventuellement les insectes peuvent aussi piquer les humains et leur transmettre la maladie. Dans ces approches, on représente habituellement la dynamique de la zoonose par des modèles mathématiques (dits ‘à base de compartiments’) en faisant l’hypothèse que l’espace est homogène. Ainsi elles ne tiennent pas compte de l’influence du ‘paysage’ (en particulier de la couverture du sol). Pourtant prendre en compte les caractéristiques spatiales est important si on veut simuler de façon plausible la dynamique des zoonoses en tenant compte des zones favorables à la survie ou à la prolifération de certaines espèces (ex. moustiques, tiques) de leur dispersion par les espèces transportrices (ex. oiseaux, chevreuils) et de leurs comportements de mobilité. Dans le projet ZoonosisMAGS, dans lequel s’insère ce travail de maîtrise, on vise à développer une approche générique de simulation de la propagation des zoonoses en utilisant des données géo-référencées et en créant un environnement géographique virtuel efficace pour tenir compte de l’influence de la couverture du sol. Pour la dynamique du phénomène qui reflète l’évolution des espèces (des stades œuf, larve, nymphe à adulte), leurs interactions et leur statut épidémiologique (sain, susceptible, infecté) on utilise un modèle enrichi à base de compartiments qui représente les stades d’évolution biologiques et épidémiologiques des différentes espèces impliquées dans la zoonose. Les populations de chaque espèce en interaction et à divers stades de maturité sont associées aux cellules qui représentent les unités de l’environnement géographique virtuel. La transition des individus d’une espèce d’un compartiment à un autre, ainsi que l’interaction entre les espèces se fait à travers des calculs d’expressions mathématiques à chaque pas de simulation, et ceci pour chaque cellule. Par exemple, dans le cadre d’une simulation de la propagation de la maladie de Lyme sur 365 jours d’une année, sur une région d’environ 300km2, on doit évaluer environ 150 expressions mathématiques pour une trentaine de compartiments et environ 20000 cellules à chaque pas de temps. On comprend qu’un défi majeur est celui de l’efficacité de la spécification et de l’évaluation des expressions mathématiques. Aussi, nous traitons dans ce mémoire une première problématique qui concerne la spécification et l’évaluation efficace des expressions mathématiques et booléennes pour de telles simulations. C’est dans ce contexte que nous avons développé un système qui permet à l’usager de spécifier les expressions mathématiques requises par de telles simulations, ainsi qu’un système qui les évalue par la suite de manière très efficace. La spécification des modèles de compartiments des espèces, de leurs interactions et de l’infection peut être une tâche complexe pour certaines zoonoses comme la maladie de Lyme. À cet effet, nous avons traité une deuxième problématique visant à simplifier la tâche de spécification des modèles en créant un module graphique couplé au système d’expressions mathématiques. En nous basant sur la librairie de dessin Visio, nous avons développé un tel système qui est complètement intégré au simulateur ZoonosisMAGS (version C++). Dans ce mémoire nous présentons le contexte de la recherche, les étapes d’analyse et de conception des systèmes développés. Nous montrons à travers des cas d’utilisation comment ces systèmes sont pratiquement utilisés grâce aux interfaces utilisateurs pratiques que nous avons développées. Nous rendons compte de tests d’efficacité qui ont été conduits pour montrer la contribution de notre travail à travers les résultats d’exécution des expressions mathématiques dans une simulation utilisant un modèle à base de compartiments de la maladie de Lyme.