Dans de multiples domaines, des structures qui semblent à première vue très simples sont très mal comprises. Un exemple qui nous vient vite à l'esprit, c'est la structure de l'ADN qui n'est qu'une suite d'un alphabet de quatre bases azotées, mais dont la combinaison cache encore de nombreux mystères. Dans ce mémoire nous nous sommes attardés à la rotation, la réflexion et à la permutation des lettres d'un mot. Si l'on ne prend que la rotation, l'ensemble de tous les mots que l'on peut fabriquer par rotation des lettres d'un mot donné est appelé collier. Cette notion mathématique bien connu revient, dans le concret, à écrire notre mot donné sur les perles d'un collier et à constater que le fait de tourner le collier autour de notre cou ne change pas l'objet lui-même. En ajoutant la réflexion à la rotation, on obtient les bracelets. Toutefois, lorsque l'on combine la permutation des lettres de l'alphabet aux bracelets ou aux colliers, on obtient des objets beaucoup moins connus et moins bien compris. Au cours de ce mémoire, nous nous sommes donc intéressés aux mots dont la permutation des lettres est combinée à d'autres actions. Deux principaux problèmes ont occupés nos recherches: le comptage de ces objets ainsi que l'énumération de ceux-ci. Ces deux avenues ont été fructueuses et nous ont donné de nouveaux résultats. Nous avons de plus trouvé divers domaines où ces objets semblent être un modèle pertinent et où nos résultats pourraient s'appliquer. / Simple structures seem to emerge from many different sciences. However, we still have a limited undertanding of those structures. A good exemple is DNA structure which is simply a series of nitrogenous bases taken from a four letter alphabet. Unfortunately, even if its structure is very simple, DNA still keeps many secrets to the scientific community. A better understanding of basic structures seems to be the basis to a better understanding of our environment. This is why we have focused on words under the action of rotation, reflexion and permutation of letters. Words under the action of rotation are called necklaces and are well studied. If the reflection is added to necklaces, bracelets are obtained. However, if we combine alphabet permutation with rotation and/or reflection, less understood objects are obtained. We focused on two major problems: counting objets and generating them. In both directions we have found interesting new results. We also found some fields in which our results could contribute.

Il peut s'avérer ardu, même pour une organisation de petite taille, de se retrouver parmi des centaines, voir des milliers de documents électroniques. Souvent, les techniques employées par les moteurs de recherche dans Internet sont utilisées par les entreprises voulant faciliter la recherche d'information dans leur intranet. Ces techniques reposent sur des méthodes statistiques et ne permettent pas de traiter la sémantique contenue dans la requête de l'usager ainsi que dans les documents. Certaines approches ont été développées pour extraire cette sémantique et ainsi, mieux répondre à des requêtes faites par les usagers. Par contre, la plupart de ces techniques ont été conçues pour s'appliquer au Web en entier et non pas sur un domaine en particulier. Il pourrait être intéressant d'utiliser une ontologie pour représenter un domaine spécifique et ainsi, être capable de mieux répondre aux questions posées par un usager. Ce mémoire présente notre approche proposant l'utilisation du logiciel Text- To-Onto pour créer automatiquement une ontologie décrivant un domaine. Cette même ontologie est par la suite utilisée par le logiciel Sesei, qui est un filtre sémantique pour les moteurs de recherche conventionnels. Cette méthode permet ainsi d'améliorer la pertinence des documents envoyés à l'usager. / It can prove to be diffcult, even for a small size organization, to find information among hundreds, even thousands of electronic documents. Most often, the methods employed by search engines on the Internet are used by companies wanting to improve information retrieval on their intranet. These techniques rest on statistical methods and do not make it possible neither to evaluate the semantics contained in the user requests, nor in the documents. Certain methods were developed to extract this semantics and thus, to improve the answer given to requests. On the other hand, the majority of these techniques were conceived to be applied on the entire World Wide Web and not on a particular field of knowledge, like corporative data. It could be interesting to use domain specific ontologies in trying to link a specific query to related documents and thus, to be able to better answer these queries. This thesis presents our approach which proposes the use of the Text-To-Onto software to automatically create an ontology describing a particular field. Thereafter, this ontology is used by the Sesei software, which is a semantic filter for conventional search engines. This method makes it possible to improve the relevance of documents returned to the user.

Tableau d'honneur de la Faculté des études supérieures et postdoctorales, 2006-2007 / La vérification de modèle est une technique permettant de faire un modèle représentant le comportement d'un système ou d'un programme, de décrire une propriété à vérifier sur ce dernier et de faire la vérification au moyen d'un algorithme. Dans ce mémoire, nous décrivons notre propre méthode de vérification de modèle basée sur les algèbres de Kleene. Plus particulièrement, nous utilisons une extension appelée omégaalgèbre avec domaine. Cette méthode algébrique permet de vérifier des propriétés pouvant être exprimées au moyen de la logique CTL* basée sur les états et les actions du modèle à vérifier. Nous représentons ces propriétés au moyen d'expressions sur une oméga-algèbre avec domaine. / Les modèles que nous pouvons vérifier sont les systèmes à pile, une classe de systèmes de transitions pouvant avoir un nombre infini d'états. Les systèmes à pile peuvent représenter le flot de contrôle des programmes avec appels de procédures, incluant les appels récursifs. Des matrices sur une oméga-algèbre avec domaine sont utilisées pour représenter ces systèmes de transitions. Notre méthode génère, à partir de la matrice représentant le système à pile à vérifier et de l'expression représentant la propriété à vérifier sur ce dernier, une équation qu'il faut démontrer de façon axiomatique afin de conclure que le système satisfait la propriété.

La technologie d'accès radio 1xEV-DO, également connue sous le nom d'IS-856, fait partie des alternatives potentielles d'évolution pour les systèmes CDMA2000 (1x). Elle est conçue pour améliorer le support des services de données, et plus précisément, pour augmenter la capacité du débit binaire exigé par les applications évoluées, comme l'accès Internet à haut débit, le traitement d'images, la vidéo-conférence, la télécopie, la messagerie multimédia et le courrier électronique. Cette méthode d'accès repose sur des techniques évoluées, comme le codage et la modulation adaptatifs (AMC : Adaptive Modulation and Coding), les algorithmes d'ordonnancement (Scheduling Algorithm) et de demande de retransmission automatique hybride (H-ARQ : Hybrid Automatic Repeat reQuest). / Ces techniques permettent de satisfaire les contraintes de qualité de service qui caractérisent les futures applications à offrir aux usagers mobiles. Nos travaux de recherche présentent une étude approfondie sur la procédure à suivre pour évaluer la performance de la méthode d'accès radio 1xEV-DO. Ils proposent, à partir d'une série de simulations et d'expérimentations, une méthodologie d'évaluation de performance en vue de mieux présenter et d'analyser le débit binaire offert. Les résultats obtenus illustrent la capacité de la technologie 1xEV-DO offrir un débit binaire en fonction de celui requis par utilisateur, par service et par secteur. Ces résultats permettent également d'explorer les diverses stratégies à adopter en vue d'améliorer les performances d'une telle technologie.

Tableau d'honneur de la Faculté des études supérieures et postdoctorales, 2006-2007 / Ce travail présente une nouvelle approche pour l'intégration des systèmes d'information. Cette approche permet d'intégrer des systèmes hétérogènes en matières de : modèles de données, systèmes d'opérations, réseaux utilisés, etc. pour fournir enfin aux décideurs ou/et utilisateurs une information à jour et consistante qui sera la base de décisions correctes et fiables dans le processus décisionnel. Principalement, notre méthodologie est une approche multi-couche: une couche intégration des différentes sources de données, une couche fournit un service de messagerie qui envoie l'information provenant des différentes sources aux différents clients intéressés dans cette information, et une autre consiste en une application client. La première couche vise à connecter les différentes bases de données en éliminant les différences spécifiques à chacune de ces dernières. La seconde, service de messagerie, permet d'envoyer l'information aux multiple utilisateurs dans un mode asynchrone, ce qui libère l'application client de rester couplée avec la source de données et en même temps garantit la délivrance de cette information à ses abonnés. Pour la couche "application client", elle est responsable de : l'affichage et la présentation de l'information reçue à partir de l'intergiciel basé sur le service de messagerie; de la mise à jour en temps réel de l'affichage en reflétant l'état présent des sources de données; ainsi que d'autres processus de control et d'optimisation. Notre intergiciel, proposé au sein de cette thèse, est basé sur un ensemble d'APIs standards (surtout celles provenant du monde J2EE) ce qui lui offre une large interopérabilité et facilité d'extension. / This work presents a new approach for integrating information Systems. This approach allows Connecting Systems that are heterogenous in terms of: data models, operating Systems, used networks, etc. It ultimately provides decision makers or/and users with up-to-date, consistent and well presented information which will be the basis of correct and reliable decisions in the decision making process. Primarily, our integration modus operandi is a multi-layer approach: an integration connection layer, a messaging service layer, and a client application layer. The first one aims at Connecting the various databases by eliminating the differences that are specific to each one. The second, messaging service, allows to push information incoming from the multiple sources to customers interested in this information in an asynchronous mode. It releases the customer application to remain coupled with the data source, and at the same time guarantees the delivery of this information to different subscribers. The third layer, client application, is responsible for: display and presentation of information received from the messaging layer; real-time updating of display to reflect the state of the data sources; and other control and optimization procedures. Our middleware, proposed within this work, is platform, OS, and DBMS independent. It is based on a set of standard APIs (especially those coming from J2EE world) which offers broad interoperability and provides easy extensibility.

La technologie HSDPA (High Speed Downlink Packet Access) représente la première étape d’évolution de la méthode d’accès du réseau mobile de troisième génération UMTS (Universal Mobile Telecommmunications Service). Cette technologie permet d’obtenir des débits théoriques supérieurs à 10 Mbps sur le lien descendant et de supporter des services à valeur ajoutée, tels que l’accès Internet à haute vitesse, le téléchargement de fichiers audio et vidéo, la réception de programmes télévisés et la visiophonie. Ces améliorations sont rendues possibles grâce à une combinaison de propriétés qui sont à la base du HSDPA et qui consistent à adapter le codage et la modulation en fonction des conditions du canal radio (AMC : Adaptative Modulation and Coding), à effectuer des retransmissions rapides de paquets erronés (HARQ : Hybrid Automatic Repeat ReQuest) et à utiliser des méthodes d’ordonnancement intelligentes plus rapides. Même si l’introduction de ces nouvelles techniques contribue à une augmentation de la capacité du système, elle engendre toutefois une plus grande complexité dans l’évaluation de ses performances dans des conditions réelles. Dans ce contexte, nous proposons une implémentation et une évaluation de la méthode d’accès HSDPA qui prend en considération les spécifications techniques des Node B et des terminaux mobiles d’un système UMTS. Les résultats obtenus de cette implémentation, basés sur plusieurs scénarios utilisant des données géographiques réelles, montrent que le système réussit à satisfaire aux exigences des services multimédia. / High speed downlink packet access (HSDPA) is an add-on technology for W-CDMA that allows higher downlink data rates and greater base station capacity. With HSDPA, W-CDMA systems, which today are seemingly stuck at 384 kbps, will be able to shift gears and move ahead to so-called 3.5G performance with over 10 Mbps throughput on the downlink. The incorporation of HSDPA in Release 5 of the 3GPP W-CDMA specification is the most significant change on the RF side since Release 99. Advanced techniques such as adaptive modulation and coding (AMC) and hybrid automatic repeat request (HARQ) are used to modify the coding and physical layer parameters adaptively in response to the instantaneous channel quality, thus enabling gains in spectral efficiency and data rates. On the other hand, such improvements also bring a higher complexity degree in the evaluation of the radio subsystem performance. This evaluation is crucial for operators who are willing to provide value-added services with rich multimedia contents. This thesis aims at implementing and simulating a radio access network on a real geographic area using the HSDPA features. Results show that such features enable to satisfy the quality of service requirements needed to support the new data-oriented services.

La principale contribution de ce travail est de proposer une nouvelle logique, inspirée de la logique temporelle linéaire, qui permet d'améliorer les techniques standard de détection d'intrusions utilisant l'approche par scénarios, avec la possibilité de détecter des variantes d'attaques connues. La logique suggées pourrait trouver une trace de paquets qui correspondent, même partiellement avec une distance calculée, avec la formule qui décrit l'attaque. La deuxième partie consistera à décrire son implémentation et de montrer la contribution pour augmenter la performance et l'expressivité des règles des systèmes de détection d'intrusions et plus précisément, du système Snort.

Notre société est caractérisée par l'utilisation à grande échelle des équipements mobiles tels que téléphones cellulaires, assistants personnels et toutes autres sortes d'appareils embarqués. Avec l'évolution récente dans le domaine des réseaux sans fil et leur intégration à l'Internet, on assiste à une augmentation de la demande pour des services cartographiques accessibles par des appareils de plus en plus variés. Le but du présent travail est d'offrir un service permettant la production et la livraison des cartes sur le Web pour des terminaux mobiles de type PDA (Personal Digital Assistant). Cependant, la génération des cartes sur le Web pour des terminaux mobiles constitue un grand défi, non seulement le temps de génération de la carte doit être le plus court possible, mais il faut que la production de la carte s'adapte aux différentes contraintes de l'environnement mobile (caractéristiques techniques limitées des terminaux mobiles, faiblesse et instabilité de transfert de données, etc). Pour relever ce défi, nous avons opté pour une approche appelée «génération et transmission des cartes par couches d'intérêt », une approche basée sur l'utilisation d'une base de données à représentations multiples et un système multiagent pour la génération et l'adaptation de la carte finale en fonction des contraintes liées au contexte mobile. / Nowadays, the use of mobile devices such as cellular phones, personal assistants is increasing Worldwide. The recent advances in the field of the wireless networks and their integration with the Internet, results in the increased need for cartographic services accessible using mobile devices. The goal of this work is to offer a service allowing the production and the delivery of Web maps for PDA (Assisting Personal Digital). Furthermore, in order to generate maps on-the-fly for mobile devices, we must deal with several challenges. Indeed, in addition to processing time which must be short, we have to adapt the maps to the various constraints of the mobile environment (small amount of memory slow processor, display size, bandwidth, etc). In order to overcome these challenges, we chose an approach called " a progressive automatic map generation based on layers of interest ", this approach is based on the use of a multiple representation database and a multiagent System for the generation and the adaptation of maps according to the mobile context constraints.

La réponse automatique aux courriels est une solution envisagée pour faciliter le travail de certains services d’entreprises, tels que les services à la clientèle ou les relations avec des investisseurs, services confrontés à un grand nombre de courriels souvent répétitifs. Nous avons décidé d’adapter une approche de raisonnement à base de cas (CBR - Case-Based Reasoning) pour confronter ce problème. Cette approche vise à réutiliser des messages antérieurs pour répondre à de nouveaux courriels, en sélectionnant une réponse adéquate parmi les messages archivés et en l’adaptant pour la rendre pertinent par rapport au contexte de la nouvelle requête. L’objectif de nos travaux est de définir une démarche pour aider l’usager d’un système de réponse au courriel à réutiliser les entités nommées de courriels antécédents. Cependant, les entités nommées nécessitent une adaptation avant d’être réutilisées. Pour ce faire, nous effectuons deux tâches qui sont d’abord l’identification des portions modifiables du message antécédent et ensuite la sélection des portions qui seront adaptées pour construire la réponse à la requête. Les deux tâches nécessitent l’utilisation de connaissances. Notre problématique consiste à déterminer si les approches adaptatives, basées sur des techniques d’apprentissage automatique permettent d’acquérir des connaissances pour réutiliser efficacement des entités nommées. La première tâche d’identification des portions modifiables s’apparente à l’extraction d’information. Toutefois nous nous intéressons uniquement aux entités nommées et à leurs spécialisations. La seconde tâche, la sélection de portions à adapter, correspond à une catégorisation de textes dans laquelle nous utilisons la requête pour attribuer une classe à la réponse que nous devons construire. La classe nous indique quelles entités doivent être adaptées. ii Nous avons étudiés et comparées différentes approches pour les deux tâches. Ainsi, nous avons testés pour l’extraction, les approches manuelle et automatiques, de haut en bas (top-down) et de bas vers le haut (bottom-up) sur un corpus de courriels. Les résultats obtenus par l’approche manuelle sont excellents. Toutefois nous observons une dégradation pour les approches automatiques. Pour la catégorisation, Nous avons évalué différentes représentations des textes et des mots, l’utilisation de poids pour ces derniers, et l’impact d’une compression obtenue par l’utilisation de règles d’association. Les résultats obtenus sont généralement satisfaisants et nous indique que notre approche, composée des deux tâches décrites précédemment, pourrait s’appliquer à notre problème de réponse automatique aux courriels. / An automatic e-mail response system is a solution for improving the operations of certain business services, like customers’ services or investor relations. Those services are dealing with a large volume requests coming through e-mail messages, most of them being repetitive. We have decided to explore a CBR approach (Case-Based Reasoning) for this problem. Such an approach makes use of antecedent messages to respond to new incoming e-mails. Requests coming from customers or investors are often redundant; we could select an adequate answer among the archived messages, and then adapt it to make it coherent with the actual context of the new message request. In this project, we address the re-use problem, but more specifically the identification of named entity and their specialized roles. These entities are portions of text strongly depend on the context of the antecedent message, and hence need some adaptation to be re-used. We divide the reuse process in two tasks which are: a) the identification of modifiable portions of an antecedent message; b) the selection of portions to be adapted to build the answer of the request. For first task, we make use of information extraction techniques. But we will concentrate our efforts uniquely on the extraction of named entities and their specializations. For second task we make use of text classification techniques to decide which portions are subject to adaptation. This decision is based on the context of the request, words which compose it. We used different approaches for the two tasks. We tested manual and automatics top-down and bottom-up extraction techniques on an e-mail corpus for the identification of iv modifiable portions extraction task. Manual approach gives us excellent results. But, we notice a degradation of performance for automatic extraction techniques. For the selection of portions to be adapted, we compared made use of association rules and various word representation. Association rules use permits to compress data without degrades results a lot. Globally, results are good and indicate that our approach, desrcibes before, could be applied to our problem.

Tableau d'honneur de la Faculté des études supérieures et postdoctorales, 2006-2007 / L’algèbre de Kleene est la théorie algébrique des automates finis et des expressions régulières. Récemment, Kozen a proposé un cadre de travail basé sur l’algèbre de Kleene avec tests (une variante de l’algèbre de Kleene) pour vérifier qu’un programme satisfait une politique de sécurité spécifiée par un automate de sécurité. Malheureusement, cette approche ne permet pas de vérifier des propriétés de vivacité pour les programmes réactifs (programmes qui s’exécutent à l’infini). Le but de ce mémoire est d’étendre la méthode de vérification de programmes proposée par Kozen pour enlever cette limitation. Pour y arriver, nous développons la théorie de l’oméga-algèbre (une extension de l’algèbre de Kleene qui prend en compte les exécutions infinies) qui constitue la majeure partie de ce mémoire. En particulier, nous présentons des résultats de complétude concernant la théorie de Horn de cette algèbre. / Kleene algebra is the algebraic theory of finite automata and regular expressions. Recently, Kozen has proposed a framework based on Kleene algebra with tests (a variant of Kleene algebra) for verifying that a program satisfies a security policy specified by a security automaton. Unfortunately, this approach does not allow to verify liveness properties for reactive programs (programs that execute forever). The goal of this thesis is to extend the framework proposed by Kozen for program verification to remove this limitation. For that, we develop the theory of omega algebra, an extension of Kleene algebra suitable for reasoning about nonterminating executions. The main part of this thesis is about omega algebra. In particular, we show some completeness results about the Horn theory of omega algebra.