L'utilisation d'équipes de robots a pris de l'ampleur ces dernières années. Cela est dû aux avantages que peut offrir une équipe de robot par rapport à un robot seul pour la réalisation d'une même tâche. Cela s'explique aussi par le fait que ce type de plates-formes deviennent de plus en plus abordables et fiables. Ainsi, l'utilisation d'une équipe de véhicules aériens devient une alternative viable. Cette thèse se concentre sur le problème du déploiement d'une équipe de Micro-Véhicules Aériens (MAV) pour effectuer des missions de surveillance sur un terrain inconnu de morphologie arbitraire. Puisque la morphologie du terrain est inconnue et peut être complexe et non-convexe, les algorithmes standards ne sont pas applicables au problème particulier traité dans cette thèse. Pour y remédier, une nouvelle approche basée sur un algorithme d'optimisation cognitive et adaptatif (CAO) est proposée et évaluée. Une propriété fondamentale de cette approche est qu'elle partage les mêmes caractéristiques de convergence que les algorithmes de descente de gradient avec contraintes qui exigent une connaissance parfaite de la morphologie du terrain pour optimiser la couverture. Il est également proposé une formulation différente du problème afin d'obtenir une solution distribuée, ce qui nous permet de surmonter les inconvénients d'une approche centralisée et d'envisager également des capacités de communication limitées. De rigoureux arguments mathématiques et des simulations étendues établissent que l'approche proposée fournit une méthodologie évolutive et efficace qui intègre toutes les contraintes physiques particulières et est capable de guider les robots vers un arrangement qui optimise localement la surveillance. Finalement, la méthode proposée est mise en œuvre sur une équipe de MAV réels pour réaliser la surveillance d'un environnement extérieur complexe.

Ma thèse a pour but l'étude des désignations nominales des événements pour l'extraction automatique. Mes travaux s'inscrivent en traitement automatique des langues, soit dans une démarche pluridisciplinaire qui fait intervenir linguistique et informatique. L'extraction d'information a pour but d'analyser des documents en langage naturel et d'en extraire les informations utiles à une application particulière. Dans ce but général, de nombreuses campagnes d'extraction d'information ont été menées~: pour chaque événement considéré, il s'agit d'extraire certaines informations relatives (participants, dates, nombres, etc.). Dès le départ, ces challenges touchent de près aux entités nommées (éléments " notables " des textes, comme les noms de personnes ou de lieu). Toutes ces informations forment un ensemble autour de l'événement. Pourtant, ces travaux ne s'intéressent que peu aux mots utilisés pour décrire l'événement (particulièrement lorsqu'il s'agit d'un nom). L'événement est vu comme un tout englobant, comme la quantité et la qualité des informations qui le composent. Contrairement aux travaux en extraction d'informations générale, notre intérêt principal est porté uniquement sur la manière dont sont nommés les événements qui se produisent et particulièrement à la désignation nominale utilisée. Pour nous, l'événement est ce qui arrive, ce qui vaut la peine qu'on en parle. Les événements plus importants font l'objet d'articles de presse ou apparaissent dans les manuels d'Histoire. Un événement peut être évoqué par une description verbale ou nominale. Dans cette thèse, nous avons réfléchi à la notion d'événement. Nous avons observé et comparé les différents aspects présentés dans l'état de l'art jusqu'à construire une définition de l'événement et une typologie des événements en général, et qui conviennent dans le cadre de nos travaux et pour les désignations nominales des événements. Nous avons aussi dégagé de nos études sur corpus différents types de formation de ces noms d'événements, dont nous montrons que chacun peut être ambigu à des titres divers. Pour toutes ces études, la composition d'un corpus annoté est une étape indispensable, nous en avons donc profité pour élaborer un guide d'annotation dédié aux désignations nominales d'événements. Nous avons étudié l'importance et la qualité des lexiques existants pour une application dans notre tâche d'extraction automatique. Nous avons aussi, par des règles d'extraction, porté intérêt au cotexte d'apparition des noms pour en déterminer l'événementialité. À la suite de ces études, nous avons extrait un lexique pondéré en événementialité (dont la particularité est d'être dédié à l'extraction des événements nominaux), qui rend compte du fait que certains noms sont plus susceptibles que d'autres de représenter des événements. Utilisée comme indice pour l'extraction des noms d'événements, cette pondération permet d'extraire des noms qui ne sont pas présents dans les lexiques standards existants. Enfin, au moyen de l'apprentissage automatique, nous avons travaillé sur des traits d'apprentissage contextuels en partie fondés sur la syntaxe pour extraire de noms d'événements.

Cette thèse s'inscrit dans le domaine de l'ingénierie des méthodes de développement des systèmes d'information et plus particulièrement dans une optique d'évolution de ces méthodes. Les Objectifs de cette Thèse sont : 1. Proposer un cadre général pour l'ingénierie de l'évolution de méthodes, 2. Proposer un méta-modèle générique de méthodes capable de décrire la plupart des méthodes d'ingénierie de SI. Ce méta-modèle permet de venir à bout du problème de la diversité des méthodes évoqué ci-dessus. Notre approche d'évolution sera entièrement basée sur ce méta- modèle. 3. Définir une démarche de rétro-ingénierie de méthodes permettant de formaliser les modèles de produit et de processus d'une méthode informelle ou mal définie. 10 Introduction MIME (Méthode d'Ingénierie de Méthodes par Evolution) 4. Définir une démarche pour l'ingénierie de méthodes par évolution. L'objectif de cette démarche est d'assister l'ingénieur de méthodes dans toutes les étapes du projet d'évolution d'une méthode. 5. Positionner l'approche proposée dans le contexte général de l'ingénierie des méthodes. 6. Valider l'approche proposée sur un cas d'étude. Ce cas est celui de la méthode industrielle Lyee [Negoro 01a], [Negoro 01b].

L'objet de cette thèse est la perception dans les environnements immersifs de jeux de données complexes, une des applications est la visualisation scientifique de données volumiques scalaires issues de simulations de modèles physiques. Un exemple classique de ceci est la distribution de températures à l'intérieur d'un habitacle de véhicule.Dans la première partie de ce travail, notre objectif est d'étudier les limites perceptives dans le cadre d'un rendu volumétrique de données scientifiques dans un système de réalité virtuelle offrant la vision en stéréoscopie, et le suivi du point de vue de l'utilisateur. Nous étudions l'effet sur la perception de l'utilisateur de trois facteurs principaux : la taille des points utilisés pour le rendu, la densité du nuage de points, et enfin la position par rapport à l'utilisateur du premier plan de coupe. Nous présentons une étude dans laquelle une tâche de pointage est proposée à un ensemble d'utilisateurs. Les déplacements de celui-ci ainsi que les performances de pointage sont mesurées. L'étude a permis d'évaluer l'impact des paramètres de rendu du nuage de points et proposer un rendu améliorant la perception.La seconde partie du travail propose d'ajouter une dimension interactive à la première approche en permettant à l'utilisateur d'explorer plus activement la scène. L'hypothèse d'une meilleure compréhension des données par l'action est ici mise en avant. Nous évaluons une méthode d'interaction et quatre méthodes de rendu associées. L'approche proposée est de n'afficher qu'un sous ensemble des données volumiques, en l'occurrence des isosurfaces, et de permettre à l'utilisateur de naviguer par une gestuelle naturelle et interactive dans l'ensemble des isosurfaces du jeu de données explorées, dans cadre de manipulation directe. Une nouvelle étude est proposée, dans laquelle l'utilisateur doit effectuer une tâche de recherche et de pointage d'une propriété locale dans un jeu de températures 3D. Cette étude a permis de choisir une méthode de rendu adaptée à l'affichage immersif d'isosurfaces et de valider l'approche interactive pour l'exploration de données.

Les cartes à puce jouent un rôle crucial dans de nombreuses applications que nous utilisons quotidiennement : paiement par carte bancaire, téléphonie mobile, titres de transport électroniques, etc. C'est dans ce contexte que la technologie Java Card s'est imposée depuis son introduction en 1996, réduisant les coûts de développement et de déploiement d'applications pour cartes à puce et permettant la cohabitation de plusieurs applications au sein d'une même carte. La communauté scientifique a rapidement démontré que la possibilité donnée à un attaquant d'installer des applications sur les cartes représente une menace. Mais dans le même temps, la sécurité des systèmes embarqués a également été un sujet d'étude très productif, révélant que des algorithmes cryptographiques considérés comme sûrs pouvaient être facilement cassés si leurs implémentations ne prenaient pas en compte certaines propriétés physiques des composants électroniques qui les accueillent. En particulier, une partie des attaques publiées repose sur la capacité de l'attaquant à perturber physiquement le composant pendant qu'un calcul est exécuté. Ces attaques par injections de fautes n'ont que très peu été étudiées dans le contexte de la technologie Java Card. Cette thèse étudie et analyse la sécurité des Java Cards contre des attaques combinant injections de fautes et installations d'applications malicieuses. Tout d'abord, nous présentons différents chemins d'attaques combinées et exposons dans quelle mesure ces attaques permettent de casser différents mécanismes sécuritaires de la plateforme. En particulier, notre analyse sécuritaire permet de démontrer que la propriété de sûreté du typage, l'intégrité du flot de contrôle, ainsi que le mécanisme d'isolation des applications peuvent être contournés et exploités par des combinaisons adéquates. Puis, nous présentons différentes approches permettant d'améliorer la résistance de la plateforme Java Card ainsi que des applications qu'elle accueille contre des attaques combinées. Ainsi, nous définissons plusieurs contremesures rendant les attaques exposées ainsi que certaines attaques de l'état de l'art inopérantes, et ce en gardant à l'esprit les fortes contraintes inhérentes au monde des cartes à puce.

Le sujet porte sur l'étude de deux modèles d'automates à jetons sur des arbres binaires finis étiquetés par un alphabet fini. Ces automates séquentiels se déplacent le long des arêtes et peuvent utiliser un nombre fixé de jetons pour se repérer dans un arbre. Une discipline de pile est imposé au placement des jetons, de plus, dans le modèle fort un jeton peut être levé à distance alors que dans le modèle faible un jeton peut être levé uniquement s'il est posé sur le n\oe ud courant. Les automates cheminants correspondent au cas des automates d'arbres à 0 jeton. L'étude des automates d'arbres à jetons est motivée par la caractérisation du pouvoir d'expression et de la complexité du langage de requêtes XPATH qui permet de sélectionner des éléments et de définir des chemins dans des documents XML et qui est le noyau de langages de transformation de documents XML tels que XSLT.<br /><br />Une première contribution a été de prouver que les variantes déterministes des deux modèles d'automates d'arbres à jetons sont fermées par complément. Nous donnons alors une nouvelle présentation de la preuve de la caractérisation du modèle fort des automates d'arbres à jetons qui a été établie par Engelfriet et Hoogeboom. <br /><br />Une autre contribution a été de montrer que les deux modèles d'automates à jetons sont équivalents, que le pouvoir d'expression des automates d'arbres à jetons augmente avec le nombre de jetons et qu'il n'est pas toujours possible de déterminiser un automate d'arbres cheminant même si on s'autorise à ajouter un nombre fixé de jetons.<br /><br />Une dernière contribution a été de prouver que les problèmes du vide et de l'inclusion sont n-EXPTIME complets pour les classes d'automates à n jetons avec n supérieur à 1.

In the last decade XML became one of the main standards for data storage and exchange on the Web. Detecting XML query-update independence is crucial to efficiently perform data management tasks, like those concerning view-maintenance, concurrency control, and security. This thesis presents a novel static analysis technique to detect XML query-update independence, in the presence of a schema. Rather than types, the presented system infers chains of types. Each chain represents a path that can be traversed on a valid document during query/update evaluation. The resulting independence analysis is precise, although it raises a challenging issue: recursive schemas may lead to infer infinitely many chains. This thesis presents a sound and complete approximation technique ensuring a finite analysis in any case, together with an efficient implementation performing the chain-based analysis in polynomial space and time.

Cette thèse concerne l'utilisation de l'interaction entre un algorithme et un expert pour la résolution de problèmes complexes, typiquement NP-difficiles. Plusieurs définitions de l'expert sont possibles. L'objectif étant d'obtenir des algorithmes dont les performances sont garanties, ce travail est centré sur les interactions avec un expert de type "oracle", plutôt que "humain". Ainsi, on s'intéresse à des compromis entre performance, coût (typiquement temps d'exécution), et quantité d'information donnée par l'oracle. Le premier objectif de cette thèse est de comprendre quel est l'état de l'art des différentes techniques interactives dans différents domaines (algorithmique distribuée et online, complexité, optimisation combinatoire). Le second objectif est centré sur l'optimisation combinatoire, et plus particulièrement les problèmes d'ordonnancement et d'empaquetage. Nous proposons un formalisme interactif pour le contexte des problèmes d'optimisations (offline). Le but est de montrer en quoi ce formalisme facilite la conception d'algorithmes d'approximation, en le situant par rapport aux techniques classiques de conception de schémas d'approximation, et en l'utilisant pour fournir de nouveaux résultats sur des problèmes d'ordonnancement et d'empaquetage. Nous avons principalement abordé deux problèmes : le "discrete Resource Sharing Scheduling Problem ($dRSSP$)" et le problème du "Multiple Strip Packing" ($MSP$). Le $dRSSP$ est un problème d'hybridation d'algorithmes. Etant donné un ensemble d'algorithmes (appelé un "portfolio"), un nombre fini de ressources (des processeurs par exemple), et un ensemble représentatif d'instances (appelé "benchmark"), le but est de distribuer ces ressources aux algorithmes afin de minimiser le temps nécessaire à la résolution de toutes les instances du benchmark, en exécutant les algorithmes en parallèle selon le modèle dit du "space sharing" . Nous avons étudié l'impact de plusieurs questions à poser à l'oracle, ainsi que comment communiquer efficacement avec ce dernier (signifiant que la réponse de l'oracle est courte), aboutissant à plusieurs schémas d'approximation. Le $MSP$ est une extension du problème célèbre du "Strip Packing" consistant à placer des rectangles dans un nombre fixé de boîtes, en minimisant la hauteur atteinte. Nous avons fourni plusieurs algorithmes/schémas d'approximation pour différentes variantes de ce problème, dans lesquelles les boîtes ont des largeurs égales/différentes, ou les rectangles doivent être placés de façon "continue" ou non (correspondant alors à un problème classique d'ordonnancement de tâches parallèles). D'une manière générale l'utilisation de l'interactivité permet d'isoler la difficulté des problèmes, et donc de les étudier différemment.

Le Benchmarking des systèmes client-serveur implique des infrastructures techniques réparties complexes, dont la gestion nécessite une approche autonomique. Cette gestion s'appuie sur une suite d'étapes, observation, analyse et rétroaction, qui correspond au principe d'une boucle de contrôle autonome. Des travaux antérieurs dans le domaine du test de performances ont montré comment introduire des fonctionnalités de test autonome par le biais d'une injection de charge auto-régulée. L'objectif de cette thèse est de suivre cette démarche de calcul autonome (autonomic computing) en y introduisant des fonctionnalités d'optimisation autonome. On peut ainsi obtenir automatiquement des résultats de benchmarks fiables et comparables, mettant en oeuvre l'ensemble des étapes de self-benchmarking. Notre contribution est double. D'une part, nous proposons un algorithme original pour l'optimisation dans un contexte de test de performance, qui vise à diminuer le nombre de solutions potentielles à tester, moyennant une hypothèse sur la forme de la fonction qui lie la valeur des paramètres à la performance mesurée. Cet algorithme est indépendant du système à optimiser. Il manipule des paramètres entiers, dont les valeurs sont comprises dans un intervalle donné, avec une granularité de valeur donnée. D'autre part, nous montrons une approche architecturale à composants et une organisation du benchmark automatique en plusieurs boucles de contrôle autonomes (détection de saturation, injection de charge, calcul d'optimisation), coordonnées de manière faiblement couplée via un mode de communication asynchrone de type publication-souscription. Complétant un canevas logiciel à composants pour l'injection de charge auto-régulée, nous y ajoutons des composants pour reparamétrer et redémarrer automatiquement le système à optimiser.Deux séries d'expérimentations ont été menées pour valider notre dispositif d'auto-optimisation. La première série concerne une application web de type achat en ligne, déployée sur un serveur d'application JavaEE. La seconde série concerne une application à trois tiers effectifs (WEB, métier (EJB JOnAS) et base de données) clusterSample. Les trois tiers sont sur des machines physiques distinctes.

Cette thèse se concentre sur la mise en œuvre d'implantations matérielles dédiées des filtres morphologiques fondamentaux, basés sur des itérations d'érosions/dilatations. L'objectif principal de cette thèse est de proposer une mise en oeuvre efficace et programmable de ces opérateurs en utilisant des algorithmes en flot de données et considérant les besoins applicatifs globaux. Dans la première partie, nous étudions les algorithmes existants pour les opérateurs morphologiques fondamentaux et leur réalisation sur des différentes plates-formes informatiques. Nous nous intéressons plus particulièrement à un algorithme basé sur la file d'attente pour la mise en œuvre de la dilatation car il permet de réaliser l'accès séquentiel aux données avec une latence minimale, ce qui est très favorable pour le matériel dédié. Nous proposons ensuite un autre algorithme réalisant l'ouverture morphologique, sous angle arbitraire, basé sur le même principe d'une file d'attente, permettant d'obtenir directement des mesures de granulométrie. La deuxième partie présente la mise en oeuvre matérielle des algorithmes efficaces au moyen d'unités de traitement à flot de données. Nous commençons par l'unité de dilatation 1-D, puis grâce à la séparabilité de la dilatation nous construisons des unités 2-D rectangulaire et polygonale. L'unité de traitement pour l'ouverture orientée et spectre modèle est ainsi décrit. Nous présentons également une méthode de parallélisation de calcul en dupliquant des unités de traitement. Toutes les unités de traitement proposés sont évalués expérimentalement par la réalisation des prototypes à base de circuits programmables (FPGA), et les résultats en termes d'occupation de surface et de vitesse de traitement sont discutées. Dans la troisième partie, les unités de calcul proposées sont utilisées dans deux applications différentes, illustrant ainsi leur capacité de répondre exigences des applications embarquées a basse consommation. Les principales contributions de cette thèse sont : i) proposition d'un nouvel algorithme d'ouverture sous angle arbitraire, ii) réalisation des architectures matérielles dédiées et programmables d'opérateurs morphologiques fondamentaux à l'élément structurant large et sous angle arbitraire ; iii) amélioration de la performance obtenue grâce à l'exploitation de plusieurs niveaux de parallélisme. Les résultats suggèrent que les performances de temps réel précédemment irréalisable de ces opérateurs traditionnellement coûteux peuvent être atteints même pour des longues concaténations d'opérateurs ou des images à haute résolution.