L'utilisation à grande échelle de UML dans l'industrie informatique est en train d'en faire une norme incontournable pour toute activité de modélisation conceptuelle requise par l'informatisation de systèmes d'information. Toutefois, UML a ses limites. En effet, l'expression de contraintes sémantiques se fait par OCL (Object Constraint Language), un langage basé sur la logique des prédicats du premier ordre. Les avantages d'avoir un formalisme formel, simple et graphique se perdent donc lorsque les contraintes associées au domaine doivent être décrites soit sous une forme textuelle, soit en logique des prédicats du 1er ordre. La méthodologie envisagée consiste donc en l'élaboration d'un formalisme graphique d'expression de contrainte de telle sorte que les contraintes ainsi exprimées puissent être automatiquement transformées en OCL. Les contraintes OCL peuvent alors être vérifiées afin qu'elles soient toutes satisfaites et qu'elles évitent l'introduction d'incohérence dans les données. Dans ce cas, le modélisateur pourra en être averti et pourra ajuster le modèle ou valider l'acquisition de données. Éventuellement, nous visons à ce que ces contraintes puissent s'assurer que la génération du code en tienne compte, d'où leur possible intégration à un outil de modélisation et de génération de code (outil CASE).

L'une des difficultés de l'application pratique du code incorporant une preuve (Proof-Carrying Code (PCC)) est la difficulté de communiquer les preuves car celles-ci sont généralement d'une taille importante. Les approches proposées pour atténuer ce problème engendrent de nouveaux problèmes, notamment celui de l'élargissement de la base de confiance (Trusted Computing Base): un bogue peut alors provoquer l'acceptation d'un programme malicieux. Au lieu de transmettre une preuve avec le code, nous proposons de transmettre un générateur de preuve dans un cadre générique et étendu de PCC (EPCC) (Extended Proof-Carrying Code). Un générateur est un programme dont la seule fonction est de produire une preuve; c'est-à-dire la preuve que le code qu'elle accompagne est correct. Le générateur a pour but principal d'être une représentation plus compacte de la preuve qu'il sert à générer. Le cadre de EPCC permet l'exécution du générateur de preuve du côté client d'une manière sécurisée. / One of the key issues with the practical applicability of Proof-Carrying Code (PCC) and its related methods is the difficulty in communicating the proofs which are inherently large. The approaches proposed to alleviate this, suffer with drawbacks of their own especially the enlargement of the Trusted Computing Base, in which any bug may cause an unsafe program to be accepted. We propose to transmit, instead, a proof generator for the program in question in a generic extended PCC framework (EPCC). A proof generator aims to be a more compact representation of its resulting proof. The EPCC framework enables the execution of the proof generator at the consumer side in a secure manner.

L'analyse statique des programmes consiste en un ensemble de techniques permettant de déterminer des propriétés des programmes sans avoir à les exécuter. Parmi les applications de l'analyse statique des programmes, nous retrouvons l'optimisation du code source par des compilateurs et la détection de code malveillant ou de code qui pourrait être exploité à des fins malveillantes. L'évidente pertinence et l'importance (parfois critique) de telles applications expliquent les nombreuses tentatives de compréhension du cadre théorique général de l'analyse statique des programmes. Les algèbres de Kleene sont la théorie algébrique des automates finis et des expressions régulières. Cet outil algébrique s'est avéré très approprié pour l'analyse statique et la vérification des programmes. Le but de cette thèse est de développer un cadre algébrique basé sur les algèbres de Kleene pour calculer les solutions d'une classe générale de problèmes intraprocéduraux d'analyse de flot de données. Ce cadre permet de représenter les programmes, ainsi que leurs propriétés, d'une manière homogène, compacte et expressive. Les algorithmes traditionnels employés pour calculer le résultat d'une analyse sont alors remplacés par des manipulations algébriques des éléments d'une algèbre de Kleene. / L'analyse statique des programmes consiste en un ensemble de techniques permettant de déterminer des propriétés des programmes sans avoir à les exécuter. Parmi les applications de l'analyse statique des programmes, nous retrouvons l'optimisation du code source par des compilateurs et la détection de code malveillant ou de code qui pourrait être exploité à des fins malveillantes. L'évidente pertinence et l'importance (parfois critique) de telles applications expliquent les nombreuses tentatives de compréhension du cadre théorique général de l'analyse statique des programmes. Les algèbres de Kleene sont la théorie algébrique des automates finis et des expressions régulières. Cet outil algébrique s'est avéré très approprié pour l'analyse statique et la vérification des programmes. Le but de cette thèse est de développer un cadre algébrique basé sur les algèbres de Kleene pour calculer les solutions d'une classe générale de problèmes intraprocéduraux d'analyse de flot de données. Ce cadre permet de représenter les programmes, ainsi que leurs propriétés, d'une manière homogène, compacte et expressive. Les algorithmes traditionnels employés pour calculer le résultat d'une analyse sont alors remplacés par des manipulations algébriques des éléments d'une algèbre de Kleene. / Static program analysis consists of techniques for determining properties of programs without actually running them. Among the applications of static program analysis are the optimization by compilers of object code and the detection of malicious code or code that might be maliciously exploited. The obvious relevance and (sometimes critical) importance of such applications explain the many attempts to try to understand the general theoretical framework of static program analysis. Kleene algebra is the algebraic theory of finite automata and regular expressions. This algebraic tool has proven to be very suitable for the purpose of static analysis and verification of programs. The goal of this thesis is to develop an algebraic framework based on Kleene algebra to compute the solutions to a general class of intraprocedural dataflow analysis problems. The framework allows one to represent both the programs and the relevant properties in an homogeneous, compact and readable way. Traditional algorithms used to compute the result of an analysis are then replaced by algebraic manipulations of elements of a Kleene algebra. / Static program analysis consists of techniques for determining properties of programs without actually running them. Among the applications of static program analysis are the optimization by compilers of object code and the detection of malicious code or code that might be maliciously exploited. The obvious relevance and (sometimes critical) importance of such applications explain the many attempts to try to understand the general theoretical framework of static program analysis. Kleene algebra is the algebraic theory of finite automata and regular expressions. This algebraic tool has proven to be very suitable for the purpose of static analysis and verification of programs. The goal of this thesis is to develop an algebraic framework based on Kleene algebra to compute the solutions to a general class of intraprocedural dataflow analysis problems. The framework allows one to represent both the programs and the relevant properties in an homogeneous, compact and readable way. Traditional algorithms used to compute the result of an analysis are then replaced by algebraic manipulations of elements of a Kleene algebra.

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.

La fouille archéologique est un processus technique visant à recueillir toutes les informations pertinentes sur les manifestations présentes dans un site archéologique; Le processus de la fouille d’un site archéologique peut être décrit par les étapes suivantes : - Explorer le site pour repérer les vestiges; - Récolter et enregistrer les objets trouvés; - Agréger et interpréter les objets pour reconstruire le site; - Analyser ces objets par des requêtes prédéfinies par les archéologues et diffuser les résultats. Les démarches de la fouille nécessitent le développement d’un système informatique qui aide l’archéologue à structurer les données dans une base de données et qui facilite, par la suite, l’interrogation de ces données pendant l’étape d’analyse et d’interrogation, qui peut être considérée comme l’étape la plus importante dans le processus de fouille archéologique. L’objectif de ce mémoire est la réalisation du système NESTOR. C’est un logiciel qui permet aux archéologues d’enregistrer, d’une manière conviviale, toutes les données que les fouilleurs peuvent recueillir sur un chantier de fouilles. Il permet aussi de modifier ces données, une fois enregistrées, afin de tenir compte de l’évolution des travaux sur le terrain, ou tout simplement de les consulter en cours de fouille pour s’assurer de leur adéquation avec la réalité du chantier et de la complétude de l’enregistrement. NESTOR, offre aussi aux archéologues la possibilité de regrouper et d’agréger les données archéologiques. Ce processus est modifiable et réversible. Enfin, les archéologues/fouilleurs pourront interroger la base de données par l’entremise des requêtes préprogrammées dans le système. / An archaeological excavation is a technical process aiming to collect all relevant information related to every entity or fact that appears on an archeological site. The excavation process of an archeological site can be described according to the following stages: - To explore the site in order to locate the uncovered remains ; - To collect and record excavated objects; - To assemble and interpret these objects in order to reconstruct the site; - To analyze these objects following predefined queries by archaeologists, and to disseminate the results. The steps of an excavation require the development of a computing system which could help field archaeologists to structure their data in a data base and to explore their data by meaningful queries during the analytical stage, the latter being considered as the main one in the process of excavation. Our project aims to develop such a computing system; we named it NESTOR. It is a database system that helps archaeologists to store every collected data from an excavated site in a user-friendly way. It also allows updating data, once recorded, in order to take into account the evolution of related works on site, or to check them in the course of the excavation in order to make sure of their adequacy with the reality of the excavation site and the completeness of the stored data. NESTOR also makes it possible for archaeologist’s to collect and incorporate archaeological data in the database. This process is modifiable and reversible. Lastly, archaeologists are able to query the database using some predefined queries offered by the NESTOR system.

La planification d'un réseau mobile nécessite la modélisation adéquate du trafic, en tenant compte de ses diverses composantes multimédia, ainsi que de la mobilité des usagers. La modélisation d'un tel trafic demeure difficile à faire, car ce dernier dépend du comportement de chaque usager mobile, en plus de la structure du réseau, de l'environnement de propagation, et d'autres paramètres liés à l'usager, comme la durée moyenne des communications, la durée d'occupation des ressources, la nature et la quantité des informations échangées. Dans ce contexte, il est difficile de connaître à tout instant le trafic exact dans une zone donnée. Plusieurs modèles de trafic ont été élaborés ces dernières années. Cependant, peu d'entre eux tiennent compte de la diversité des composantes multimédia du trafic et des services offerts dans les réseaux mobiles. Dans ce mémoire, nous proposons un modèle de trafic multimédia qui permet de privilégier l'accès des demandes de communication aux ressources selon les classes de services auxquelles ces demandes appartiennent et selon le nombre de ressources occupées dans la cellule. Les classes de services considérées dans la modélisation sont les mêmes que celles adoptées pour les systèmes UMTS. Grâce à ce modèle, nous pouvons prédire des paramètres importants de qualité de service : les probabilités de blocage et d'interruption de chaque classe de services. Le modèle est implémenté à l'aide de programmes écrits en C et en Matlab. A partir des résultats de simulations, nous trouvons que notre modèle garantit aux deux premières classes de services prioritaires une bonne qualité de service : aucune rupture ou blocage des communications. Pour les deux autres classes, le modèle garantit que les probabilités de blocage et d'interruption soient inférieures à 0.06, sachant que les données utilisées dans les simulations sont 100 fois plus contraignantes que celles de la littérature.

Avec l'amélioration et la prolifération de la téléinformatique, les systèmes informatiques distribués connaissent un véritable essor dans l’industrie du logiciel. Un système distribué est un système pour lequel chaque composante est indépendante et souvent située à un endroit éloigné des autres composantes. Dans un tel système, les composantes communiquent entre elles pour échanger des informations, coordonner leurs actions, prendre des décisions collectives, etc. Cependant, dans ces systèmes, certaines problématiques subsistent ; comment représenter les informations, comment transmettre les informations et comment gérer la mise à jour de ces informations? Ce mémoire s’intéresse principalement à ces problèmes pour les systèmes distribués où les informations sont centralisées sur un serveur. Pour le cas qui nous intéresse, une partie seulement de ces informations est dupliquée dans les composantes et cette duplication peut ne pas être exacte. Ce mémoire porte sur le partage de connaissances entre les différentes composantes d’un tel système distribué. Nous détaillerons plus particulièrement le mode de représentation des connaissances, basé sur les graphes conceptuels, ainsi qu’une méthode d’indexation appliquée à ce mode de représentation des informations. Nous proposons une technique originale de gestion des mises à jour. Cette technique, basée sur une analyse statistique des mises à jour, permet d’appréhender et de maintenir à jour les informations entre les composantes du système et le serveur. Avec ces techniques, nous espérons diminuer l’utilisation de la bande passante ainsi que l’incohérence momentanée des informations chez les composantes du système. / With the improvement and the proliferation of teleinformatics, the distributed systems are widely used in the software industry. A distributed system is a system for which each component is independent and often located in a place away from the other components. In such system, components communicate with each other to exchange information, to coordinate their actions, to make group decisions, etc. However, in these systems, some problematic remain; how to represent information, how to transmit information and how to manage the update information? This study is mainly interested in these problematic of distributed systems where information is centralized on a server. For the case which interests us here, only a part of information is duplicated in the components and it may not be exact. This study is related to the way of sharing knowledge between components of such distributed system. We will more particularly detail the knowledge representation, based on conceptual graphs, as well as a method of indexing this knowledge representation. We proposed an original technique of management of the updates. This technique, based on a statistical analysis of the updates, makes it possible to perceive and maintain up to date the information between the components of the system and the server. With these techniques, we hope to decrease the use of the bandwidth as well as the temporary inconsistency of information between the components and the server.

Ce document examine différentes méthodes pour calculer des chemins optimaux sur des graphes dynamiques. Deux grandes approches sont comparées: l’approche déterministe et l’approche probabiliste. L’approche déterministe prend pour acquise une certaine connaissance préalable des changements à venir dans l’environnement. L’approche probabiliste tente de modéliser et traiter l’incertitude. Une variante dynamique de l’algorithme de Dijkstra est détaillée dans le contexte déterministe. Les paradigmes des Markov Decision Processes (MDP) et Partially Observable Markov Decision Processes sont explorés dans le cadre du problème probabiliste. Des applications et mesures sont présentées pour chaque approche. On constate une relation inverse entre la calculabilité des approches proposées et leur potentiel d’application pratique. L’approche déterministe représente une solution très efficace à une version simplifiée du problème. Les POMDP s’avèrent un moyen théorique puissant dont l’implantation est impossible pour des problèmes de grande taille. Une alternative est proposée dans ce mémoire à l’aide des MDP. / This document examines different methods to compute optimal paths on dynamic graphs. Two general approaches are compared: deterministic and probabilistic. The deterministic approach takes for granted knowledge of the environment’s future behaviour. The probabilistic approach attempts to model and manage uncertainty. A dynamic version of Dijkstra’s algorithm is presented for the deterministic solution. Markov Decision Processes and Partially Observable Markov Decision Processes are analysed for the probabilistic context. Applications and measures of performance are given for each approach. We observe a reverse relationship between computability and applicability of the different approaches. Deterministic approaches prove a fast and efficient way to solve simpler versions of the problem. POMDPs are a powerful theoretical model that offers little potential of application. An alternative is described through the use of MDPs.

L'industrie des transports est un acteur important de l'économie mondiale. Des millions d'emplois sont touchés de près ou de loin par cette industrie. De plus, le nombre de véhicules sur terre ne cesse d'augmenter et il est rendu courant dans plusieurs pays industrialisés d'avoir plus d'une voiture par famille. Tout cela entraîne également son lot de problèmes, notamment au niveau de la sécurité routière et de la pollution. Depuis des décennies, des compagnies privées et des organisations publiques se penchent sur ces problèmes. Ils innovent constamment en améliorant les véhicules et les infrastructures du réseau routier. Les voitures ne sont pas seulement de plus en plus sécuritaires mais aussi de plus en plus confortables et conviviales. Cependant, la plupart des systèmes intelligents présents dans les voitures acquièrent de l'information grâce aux capteurs. Ceux-ci sont limités et certaines données ne peuvent être accessibles aux capteurs. La solution repose donc sur l'utilisation de la communication sans fil pour échanger des informations entre les véhicules et entre les infrastructures et les véhicules. Le sujet de cette maîtrise porte sur la communication inter-véhicules et route-à-véhicule. Elle se divise en deux parties. Tout d'abord, dans le cadre du projet AUTO21 au laboratoire DAMAS, un protocole de communication inter-véhicules doit être développé pour implanter un système de régulateur de vitesse collaboratif et adaptatif (" Collaborative Adaptative Cruise Control ", CACC). La théorie multi-agents et l'apprentissage par renforcement sont utilisés pour apprendre une politique de communication optimale. La deuxième partie porte sur la communication route-à-véhicule appliquée au problème d'optimisation des feux de signalisation. Deux approches multiagents sont utilisées pour optimiser la gestion des feux. Les agents placés aux intersections reçoivent de l'information relative au trafic grâce à la communication route-à-véhicule et tentent d'adopter une politique de contrôle optimale.

Les systèmes informatiques offrent une grande flexibilité aux usagers en leur permettant l'accès, notamment par le biais de réseaux de télécommunication ou de l'Internet, à un vaste éventail de services. Toutefois, certains de ces services sont soumis à de fortes contraintes de sécurité, comme le télépaiement qui est au coeur du commerce électronique. Ainsi, les fournisseurs et les utilisateurs expriment des besoins croissants, et antagonistes, en sécurité. Répondre à ces deux besoins simultanément est un enjeu technologique transversal à de nombreux domaines de l'informatique. L'objectif de ce travail est de développer un mécanisme permettant de garantir la sécurité des systèmes, en s'appuyant sur l'expérience établie dans le domaine de la sécurité et des méthodes formelles. Pour se faire, nous définissons un nouveau cadre de vérification des propriétés de sécurité d'un programme informatique par l'analyse des flots de données et de contrôle construits à partir du code de ce dernier. L'idée principale consiste à définir un modèle pouvant abstraire la trace d'événements et les dépendances de ressources engendrés au moment de l'exécution du programme, et pouvant être soumis à des algorithmes de vérification de modèle (model-checking) pour l'analyse de la sûreté du programme vis-à-vis d'une propriété.