Nous étudions des classes d'automates à états finis calculant sur les arbres, étendus par des contraintes permettant de tester des égalités et diségalités entre sous-arbres. Nous nous concentrons sur des automates d'arbres à contraintes globales où les tests sont opérés en fonction des états que l'automate atteint lors de ses calculs. De tels automates ont été introduit dans le cadre de travaux sur les documents semi-structurés. Nous procédons ici à une comparaison détaillée en expressivité entre ces automates et d'autres modèles permettant de réaliser des tests similaires, comme les automates à contraintes entre frères ou les automates d'arbres avec une mémoire auxiliaire. Nous montrons comment de tels automates peuvent être utilisés pour vérifier des propriétés de sécurité sur les protocoles cryptographiques. Les automates d'arbres ont déjà été utilisés pour modéliser les messages échangés lors d'une session d'un protocole. En ajoutant des contraintes d'égalité, nous pouvons décrire précisement des sessions qui utilisent à plusieurs reprises un même message, évitant ainsi une approximation trop grande. Nous répondons ensuite positivement au problème de la décision du vide des langages reconnus par les automates à contraintes globales. En montrant que leur expressivité est très proche de celle des automates opérant sur des représentations de termes par des graphes orientés acycliques, nous en déduisons une procédure de décision du vide en temps non-déterministe doublement exponentiel. Finalement, nous étudions le problème de la décision du vide pour des automates à contraintes globales pour lesquels on autorise des contraintes dites de clé, exprimant intuitivement que tous les sous arbres d'un certain type dans un arbre en entrée sont distincts deux à deux. Le type des clés est classiquement utilisé pour représenter un identifiant unique, comme un numéro de sécurité sociale.Nous décrivons alors une procédure de décision du vide de complexité non-élementaire. Nous montrons que cette procédure est très robuste, et qu'il est possible d'étendre les automates avec des contraintes supplémentaires, comme des contraintes de comptage ou des tests locaux, tout en préservant la décidabilité du vide.

La thèse concerne la transformation de données textuelles non structurées en données structurées et exploitables par des systèmes de recommandation. Deux grandes catégories d'informations sont utilisées dans le domaine des moteurs de recommandation : les données descriptives de contenus comme les méta-données ou les tags (filtrage thématique), et les données d'usages qui peuvent être des notes ou encore des pages Web visitées par exemple (filtrage collaboratif). D'autres données sont présentes sur le Web et ne sont pas encore réellement exploitées. Avec l'émergence du Web 2.0, les internautes sont de plus en plus amenés à partager leurs sentiments, opinions, expériences sur des produits, personnalités, films, musiques, etc. Les données textuelles produites par les utilisateurs représentent potentiellement des sources riches d'informations qui peuvent être complémentaires des données exploitées actuellement par les moteurs de recommandation et peuvent donc ouvrir de nouvelles voies d'études dans ce domaine en plein essor. Notre objectif dans le cadre de la thèse est de produire, à partir de commentaires issus de sites communautaires (blogs ou forums), des matrices d'entrées pertinentes pour les systèmes de recommandation. L'idée sous-jacente est de pouvoir enrichir un système pour un service débutant, qui possède encore peu d'utilisateurs propres, et donc peu de données d'usages, par des données issues d'autres utilisateurs. Nous faisons tout d'abord un état de l'art de la recommandation automatique. Nous présentons ensuite le moteur ainsi que les données utilisées pour les expérimentations. Le chapitre suivant décrit les premières expérimentations en mode thématique. Nous faisons ensuite un nouvel état de l'art sur la classification d'opinion. Pour finir, nous décrivons les expérimentations menées pour l'approche collaborative à l'aide de la classification d'opinion.

Cette thèse traite du problème d'une protection en profondeur qui puisse être assurée par un système d'exploitation. Elle établit la faiblesse des solutions existantes pour l'expression des besoins de sécurité. Les approches supportent en général une seule propriété de sécurité. Nous proposons donc un langage qui permet de formaliser un large ensemble de propriétés de sécurité. Ce langage exprime les activités système directes et transitives. Il permet de formaliser la majorité des propriétés de confidentialité et d'intégrité de la littérature. Il est adapté à l'expression de modèles de protection dynamique. A titre d'exemple, un nouveau modèle dynamique est proposé pour la protection des différents domaines d'usage d'un navigateur Web. Nous définissons une méthode de compilation du langage pour analyser les appels systèmes réalisés par les processus utilisateurs. La compilation repose sur la construction et l'analyse d'un graphe de flux d'information. Nous montrons qu'en pratique la complexité reste faible. Une implantation de ce langage est proposée sous la forme d'un contrôle d'accès mandataire dynamique pour Linux. Une expérimentation à large échelle a été réalisée sur des pots-de-miel à haute interaction. Notre protection a montré son efficacité aussi bien pour les serveurs que les postes client. Il présente des perspectives intéressantes aussi bien pour la protection des systèmes que pour l'analyse de vulnérabilités. Ce travail a contribué au projet SPACLik vainqueur du défi sécurité de l'ANR SEC&SI.

No description available.

Cette thèse est une contribution à l'étude énumérative et statistique d'objets combinatoires appelés cartes. Une carte est une surface discrète formée par le recollement d'un nombre fini de polygones, ou de manière équivalente un graphe qui a été plongé sans croisements d'arêtes dans une surface orientable. Si de nombreux travaux concernent la combinatoire des cartes planaires, nous nous intéressons ici aux cartes de genre g>0, c'est-à-dire dont la surface sous-jacente possède g anses indépendantes. Nous donnons des bijections nouvelles reliant les cartes de genre fixé à des objets de nature arborescente. Nous en déduisons des résultats énumératifs (formules et identités combinatoires, formules d'énumération asymptotique), des résultats probabilistes concernant la limite continue de ces objets (caractérisation du profil métrique limite d'une grande carte de genre g), et de génération aléatoire (algorithmes efficaces pour engendrer ces objets).

No description available.

Nous nous intéressons dans la présente thèse aux problèmes de communication dans les systèmes distribués, qu'il s'agisse d'une absence de transmission de l'information ou d'une corruption de l'information échangée. Dans un premier temps, nous généralisons le modèle HO, défini par Charron-Bost et Schiper pour l'étude des systèmes distribués sujets à des pannes bénignes, au cas des erreurs de transmission par valeurs. Nous étudions la capacité de ce modèle à couvrir les systèmes classiques rencontrés dans la littérature, qu'ils soient à mémoire partagée ou à échanges de messages et décrivons de nouvelles solutions algorithmiques pour le Consensus en présence d'erreurs de transmission par valeurs. Dans un second temps, nous nous penchons sur deux algorithmes de routage introduits par Gafni. Nous présentons une formalisation simple qui unifie de manière élégante ces deux algorithmes et permet une analyse exacte de leur complexité en travail. De plus, nous présentons une analyse partielle de la complexité en temps de notre algorithme pour un sous-ensemble des graphes d'entrée, qui améliore tous les résultats existants.

A mi-chemin entre l optimisation et l astronautique ce travail de recherche s attaque au problème du design de constellations de satellites Déterminer le nombre de satellites nécessaires pour ré- pondre à un besoin et les positionner de manière correcte tels sont les enjeux techniques de cette thèse Minimiser les coûts et les délais tels sont les enjeux économiques auxquels est confronté le domaine spatial au quotidien Les difficultés majeures de ce problème sont d une part la taille et les caractéristiques de l espace de recherche; D autre part la non-régularité des critères utilisés et la nature mathématique et phy- sique hétérogène de l ensemble des paramètres (paramètres entiers et paramètres réels) interdisant l utilisation d algorithmes classiques; Enfin l évaluation des solutions qui met en oeuvre une simu- lation coûteuse en temps et en calculs sans retourner d information pertinente sur les bonnes ou mauvaises propriétés de la constellation évaluée interdit une exploration massive de l espace de recherche De ces constatations et de diverses études préliminaires est née une nouvelle approche Basé sur une meilleure exploitation de la simulation et sur une simplification des critères utilisés l algorithme composé de plusieurs niveaux met en oeuvre plusieurs techniques d optimisation En intégrant une base de connaissance sur les orbites et une méthode numérique de recherche d optimum le tout or- chestré par un algorithme métaheuristique cette nouvelle approche tente de résoudre les difficultés intrinsèques au domaine d application en décomposant le problème.

Disponible dans le fichier attaché

De nombreux travaux en ingénierie des connaissances reposent sur des ontologies qui organisent les connaissances autour de la relation de subsomption. Les hiérarchies de subsomption sont parfois exploitée à l'aide de mesures sémantiques. On trouve dans la littérature diverses mesures généralement définies pour les besoins d'une application spécifique. La diversité des domaines considérés rend complexe la comparaison des mesures existantes ainsi que leur réutilisation. Cependant, le choix préalable d'une " bonne " mesure est cruciale puisqu'il influe sur la pertinence des résultats obtenus en aval. Notre thèse pose un cadre théorique qui supporte l'analyse, la comparaison et la définition de mesures sémantiques. La singularité de notre approche est qu'elle repose sur l'utilisation du contenu informationnel sans toutefois nécessiter l'utilisation d'un corpus. Nous proposons des approximations de la mesure de probabilité qui permettent d'exploiter divers aspects d'une hiérarchie de subsomption. Le problème de l'évaluation de liaisons entre deux objets sur la base d'une représentation ensembliste est largement traité dans la littérature. Nous faisons une analogie qui permet de les transposer à une hiérarchie de subsomption. Nous présentons un outil qui reprend l'approche théorique développée dans cette thèse. Nous avons développé une interface utilisateur qui permet la définition de similarités sémantiques. Notre outil offre différents angles d'analyse du comportement de ces similarités sur une hiérarchie réelle. Nous avons également proposé une adaptation de outil pour la base de connaissance UEML développée dans le cadre du réseau d'excellence INTEROP-NoE.