Aujourd'hui les réseaux de capteurs sont devenus des systèmes pouvant atteindre un très grand nombre de nœuds, avec une zone de couverture déterminée et déployés d'une manière plus ou moins dense dans un environnement hétérogène dont on mesure ainsi son état global. La problématique de cette thèse consiste à concevoir une architecture pour les objets communicants à faible consommation en utilisant des antennes " intelligentes " pour l'instrumentation et la mesure. Intégrant une approche pluridisciplinaire, cette architecture couvre les services offerts depuis les couches MAC jusqu'à celles de plus haut niveau. Basés sur une partie matérielle complètement reconfigurable (amplificateur de puissance et antennes à base de MEMS RF), les services des couches supérieures sont définis en partie sur circuits numériques pour la couche physique (bande de base) et la couche MAC, et de manière logicielle pour les protocoles de routages adaptés et les services innovants. En résumé, le travail consiste à concevoir un système autonome multi capteurs, d'acquisition et de traitement avec mémorisation, communicant à travers un réseau sans fil. Les principaux problèmes à résoudre seront : - Le contrôle de la topologie - La précision de la synchronisation - La consommation d'énergie.

L'aboutissement aux Commandes de Vol Électriques (CDVE) des avions civils actuels s'est fait par étapes, après une longue maturation des différentes technologies mises en place. La prochaine étape est l'utilisation de communications intégralement numériques et d'actionneurs intelligents. Cette thèse propose de nouvelles architectures, en rupture avec l'état de l'art, avec de nouvelles répartitions des fonctions intelligentes entre l'avionique centrale (calculateurs de commandes de vols) et l'avionique déportée (électroniques locales des actionneurs) dont l'avantage est d'exiger moins de ressources par rapport aux architectures conventionnelles tout en satisfaisant les mêmes exigences de sécurité et de disponibilité ainsi que les exigences croissantes en fiabilité opérationnelle de la part des compagnies aériennes. La sûreté de fonctionnement et la robustesse des nouvelles architectures proposées ont été validées respectivement sous OCAS/Altarica et Matlab/Simulink.

Cette thèse s'attaque dans une première partie au problème du pilotage automatique des voiliers de compétition en s'appuyant sur la réalité virtuelle qui, via la simulation, permet de s'affranchir de tests en situation réelle généralement coûteux, contraignants et risqués. Une architecture multi-agents est proposée ainsi que sa modélisation en termes de réseaux de Petri. Une deuxième partie est consacrée à la présentation et à l'étude de plusieurs extensions algébriques de ces réseaux dans le but initial de prendre en charge certaines caractéristiques des systèmes à évènements discrets non couvertes par les réseaux places/transitions usuels. Un état de l'art présente différentes approches du problème du pilotage des voiliers et souligne son caractère complexe. Partant du constat que malgré tout, l'homme parvient généralement à faire face à la plupart des situations rencontrées en mer, nous proposons d'asseoir notre système sur une expertise très fine de la pratique du barreur de compétition. Cette dernière permet d'identifier et de caractériser les éléments importants liés à la technique de barre. Nous proposons ensuite une architecture multi-agents dont la partie commande est basée sur trois agents autonomes, asynchrones et concurrents ainsi que sa modélisation par réseaux de Petri synchronisés. Le système est implémenté sous ARéVi, moteur de simulation d'objets actifs et de rendu 3D développé au CERV. L'expérimentation montre que le barreur virtuel ainsi créé assure un niveau de sécurité intéressant pour un coureur au large en réagissant aux sollicitations de son voilier d'une manière proche de celle d'un homme. Le gain en performance semble plus limité du fait, en particulier, des faiblesses du modèle de bateau implémenté mais pourrait s'avérer intéressant sur un voilier réel. Dans la deuxième partie de cette thèse nous proposons différentes extensions algébriques des réseaux de Petri. Nous choisissons tout d'abord d'utiliser un groupe à la place de l'algèbre des places usuelle des réseaux de Petri et d'en priver l'accès à l'élément neutre pour interdire certaines transitions. Ces réseaux, appelés strict-group-nets, étendent en particulier les réseaux de Petri purs si on choisit pour groupe l'ensemble des entiers relatifs. L'adjonction d'arcs dits inconditionnels conduit aux group-nets et permet d'englober également les réseaux impurs. Nous montrons que les problèmes de savoir si les Z-nets et les strict-Z-nets sont bornés et si une place de ces réseaux est bornée sont décidables via la définition d'un arbre proche de celle d'un arbre de couverture. La notion de ressource disparaissant dans ces nouveaux réseaux, plutôt que de choisir une algèbre a priori nous cherchons à caractériser les algèbres permettant de singer le comportement des réseaux de Petri usuels. Cette démarche conduit aux réseaux lexicographiques pour lesquels la notion de ressource reste étrange car on peut consommer indéfiniment strictement. Nous montrons que les réseaux lexicographiques ont la puissance des machines de Turing et que les réseaux lexicographiques bornés sont les réseaux de Petri bornés. Nous démontrons enfin que le problème de la synthèse trouve une réponse polynomiale pour les Z/2Z-nets ainsi que pour les réseaux lexicographiques en termes de meilleure approximation d'un langage régulier donné.

Nous présentons un ensemble de résultats concernant deux types de problèmes biologiques: (1) la comparaison de structures de molécules d'ARN et (2) le calcul de distances intergénomiques en présence de gènes dupliqués. Dans ce manuscrit, nous déterminons la complexité algorithmique de certains problèmes liés soit à la comparaison de structures de molécules d'ARN (distance d'édition, problème APS, recherche de motifs de 2-intervalles, design d'ARN), soit aux réarrangements génomiques (distances de breakpoints et d'intervalles conservés). \\ L'approche adoptée pour l'ensemble de ces problèmes a été de déterminer, si possible, des algorithmes exacts et rapides répondants aux problèmes posés. Pour tout problème pour lequel cela ne semblait pas possible, nous avons essayé de prouver qu'il ne peut être résolu de fa\ccon rapide. Pour ce faire, nous démontrons que le problème en question est algorithmiquement difficile. Enfin, le cas échéant, nous poursuivons l'étude de ce problème en proposant, essentiellement, trois types de résultats: (1) Approximation, (2) Complexité paramétrée, (3) Heuristique. Nous utilisons, dans ce manuscrit, des notions d'optimisation combinatoire, de mathématique, de théorie des graphes et d'algorithmique.

De nombreux travaux ont montré que, à l'origine des limitations de l'interaction bureautique, il y a un manque à la fois d'espace moteur et d'espace visuel.Cette thèse explore des moyens pour optimiser l'usage de ces espaces.D'une part, à partir du constat que l'on contrôle la position et l'orientation d'un objet par un geste naturel, cette thèse étudie les bénéfices que peut offrir une souris dotée d'un capteur de rotation. Cette < souris rotative > permet à l'utilisateur de maîtriser avec aisance trois variables continues d'une tâche informatique. Un état de l'art présente des aspects perceptifs et moteurs des actions en question et les particularités ergonomiques et techniques d'un tel dispositif. Deux techniques d'interaction - visant à faciliter des tâches métier récurrentes - sont proposées :le réglage < quasi-intégral > et la < palette satellitaire >. Par ailleurs, une évaluation expérimentale compare la performance d'une souris rotative avec celle d'une souris traditionnelle.D'autre part, ce travail se penche sur les questions de la visualisation de documents dans le contexte des bibliothèques numériques. D'abord, il examine l'apport et la faisabilité technique de l'utilisation d'un dispositif d'affichage immersif pour la navigation dans un catalogue de titres virtuel. Puis, afin de faciliter l'inspection massive d'un lot de pages numérisées, il avance des techniques de visualisation zoomables et multi-focales. Ces dernières permettent, dans une recherche d'anomalies, de saisir vite les caractéristiques visuelles de quelques centaines de pages. Et cela grâce à un va-et-vient entre la vue d'ensemble et la navigation panoramique des détails.

La vérification en ligne de spécifications formelles permet de créer des détecteurs d'erreur dont le pouvoir de détection dépend en grande partie du formalisme vérifié à l'exécution. Plus le formalisme est puissant plus la séparation entre les exécutions correctes et erronées peut être précise. Cependant, l'utilisation des vérifieurs en-ligne dans le but de détecter des erreurs est entravée par deux problèmes récurrents : le coût à l'exécution de ces vérifications, et le flou entourant les propriétés sémantiques exactes des signaux d'erreur ainsi générés. L'objectif de cette thèse est de clarifier les conditions d'utilisation de tels détecteurs dans le cadre d'applications " temps réel " critiques. Dans ce but, nous avons donné l'interprétation formelle de la notion d'erreur comportementale " temps réel". Nous définissions la propriété de détection " au plus tôt " qui permet de d'identifier la classe des détecteurs qui optimisent la latence de détection. Pour illustrer cette classe de détecteurs, nous proposons un prototype qui vérifie un comportement décrit par un automate temporisé. La propriété de détection au plus tôt est atteinte en raisonnant sur l'abstraction temporelle de l'automate et non sur l'automate lui-même. Nos contributions se déclinent dans trois domaines, la formalisation de la détection au plus tôt, sa traduction pour la synthèse de détecteurs d'erreur à partir d'automate temporisés, puis le déploiement concret de ces détecteurs sur une plate-forme de développement temps réel, Xenomai.

Exprimer le parallélisme dans la programmation de manière simple et performante est un défi auquel l'informatique fait face, en raison de l'évolution actuelle des architectures matérielles. BSML est un langage permettant une programmation parallèle de haut niveau, structurée, qui participe à cette recherche. En s'appuyant sur le coeur du langage existant, cette thèse propose d'une part des extensions qui en font un langage plus général et plus simple (traits impératifs tels que références et exceptions, syntaxe spécifique...) tout en conservant et étendant sa sûreté (sémantiques formelles, système de types...) et d'autre part une méthodologie de développement d'applications parallèles certifiées

La planification du mouvement connait une utilisation croissante dans le contexte industriel. Qu'elle soit destinée à la programmation des robots dans l'usine ou au calcul de l'assemblage d'une pièce mécanique, la planification au travers des algorithmes probabilistes est particulièrement efficace pour résoudre des problèmes complexes et difficiles pour l'opérateur humain. Cette thèse CIFRE, effectuée en collaboration entre le laboratoire de recherche LAAS-CNRS et la jeune entreprise Kineo CAM, s'attache à résoudre la problématique de planification de mouvement dans l'usine numérique. Nous avons identifié trois domaines auxquels s'intéressent les partenaires industriels et nous apportons des contributions dans chacun d'eux: la détection de collision, le volume balayé et le mouvement en collision. La détection de collision est un opérateur critique pour analyser des maquettes numériques. Les algorithmes de planification de mouvement font si souvent appel à cet opérateur qu'il représente un point critique pour les performances. C'est pourquoi, il existe une grande variété d'algorithmes spécialisés pour chaque type de géométries possibles. Cette diversité de solutions induit une difficulté pour l'intégration de plusieurs types de géométries dans la même architecture. Nous proposons une structure algorithmique rassemblant des types géométriques hétérogènes pour effectuer les tests de proximité entre eux. Cette architecture distingue un noyau algorithmique commun entre des approches de division de l'espace, et des tests spécialisés pour un couple de primitives géométriques donné. Nous offrons ainsi la possibilité de facilement ajouter des types de données nouveaux sans pénaliser la performance. Notre approche est validée sur un cas de robot humanoïde qui navigue dans un environnement inconnu grâce à la vision. Concernant le volume balayé, il est utilisé pour visualiser l'étendue d'un mouvement, qu'il soit la vibration d'un moteur ou le geste d'un mannequin virtuel. L'app roche la plus innovante de la littérature repose sur la puissance du matériel graphique pour approximer le volume balayé très rapidement. Elle est toutefois limitée en entrée à un seul objet, qui lui-même doit décrire un volume fermé. Afin d'adapter cet algorithme au contexte de la conception numérique, nous modifions son comportement pour traiter des " soupes de polygones " ainsi que des trajectoires discontinues. Nous montrons son efficacité sur les mouvements de désassemblage pour des pièces avec un grand nombre de polygones. Une soupe de polygones est plus difficile à manipuler qu'un volume bien formé. Le calcul du volume balayé introduit des opérateurs d'agrandissement et de rétrécissement des objets discrétisés. Le rétrécissement peut être utilisé pour d'autres applications dans la planification du mouvement à condition que la topologie de l'objet soit conservée pendant la transformation. Afin de préserver celle-ci, nous définissons le calcul du squelette qui préserve l'équivalence topologique. En gardant le squelette, nous employons l'opérateur de rétrécissement pour chercher les passages étroits des problèmes difficiles de planification de mouvement. Enfin, nous abordons le problème de la planification de mouvement en collision. Cette antilogie exprime la capacité d'autoriser une collision bornée pendant la recherche de trajectoire. Ceci permet de résoudre certains problèmes d'assemblage très difficiles. Par exemple, lors du calcul des séquences de désassemblage, il peut être utile de permettre à des "pièces obstacles" telles que les vis de se déplacer pendant la planification. De plus, en autorisant la collision, nous sommes capables de résoudre des problèmes de passage en force. Cette problématique se pose souvent dans la maquette numérique où certaines pièces sont " souples " ou si le problème consiste à identifier la trajectoire "la moins pire" quand aucun chemin sans collision n'existe. Nous apportons dans ce travail plusieurs contributions qui s'appliq uent à la conception numérique pour la robotique industrielle. Nous essayons de marier une approche scientifique avec des critères de fonctionnalités strictes pour mieux s'adapter aux utilisateurs de la conception numérique. Nous cherchons à exposer les avantages et les inconvénients de nos approches tout au long du manuscrit.

Les entreprises de transport font face à des problèmes de taille grandissante où l'utilisation de transbordement peut avoir un impact significatif sur les coûts. ILOG TPO est un logiciel capable de résoudre de tels problèmes, mais il lui est difficile de prendre de bonnes décisions concernant le transbordement. De plus, le processus de résolution d'ILOG TPO est basé sur la recherche locale, et il peut être aidé pour certaines décisions globales comme le transbordement. Cette thèse se place dans ce contexte, et son objectif est d'aider ILOG TPO à trouver de meilleures solutions. Pour cela, une formulation complète est d'abord proposée pour résoudre les plus petites instances, et avec une technique de plans coupants, les solutions optimales sont généralement trouvées en un temps raisonnable. Ensuite, un algorithme à deux phases qui inclut un programme en variables mixtes (MIP) sur une relaxation de type réseau du problème est donné pour de plus grandes instances. Cet algorithme est une coopération entre le MIP et ILOG TPO, où le MIP donne à ILOG TPO, pour chaque ordre de transport, le chemin de hubs par lequel il devrait être acheminé. Cette heuristique trouve des solutions similaires à ILOG TPO seul, mais le temps de calcul est réduit de façon significative.

Cette thèse traite de la préservation de l'intégrité des systèmes d'exploitation courants. L'objectif est de répondre aux menaces actuelles et futures que représentent les logiciels malveillants qui s'implantent dans le noyau de ces systèmes (comme les rootkits "noyau") ou du moins en altèrent l'intégrité (comme les rootkits "hyperviseur"). La première partie de ce document se focalise sur ces logiciels malveillants. Tout d'abord, les attaques logiques sur les systèmes informatiques sont présentées dans leur globalité. Ensuite est proposée une classification des actions malveillantes qui provoquent la perte de l'intégrité d'un noyau. Enfin, les résultats d'une étude sur les rootkits "noyau" sont donnés et la création d'un rootkit original est expliquée. La seconde partie s'intéresse à la protection des noyaux. Après une description de l'état de l'art, une approche originale est proposée, fondée sur le concept de préservation de contraintes. En premier lieu, les éléments essentiels sur lesquels reposent un noyau sont identifiés et les contraintes sur ces éléments, nécessaires à un fonctionnement correct du noyau, sont exposées. Un hyperviseur léger (Hytux) a été conçu pour empêcher la violation de ces contraintes en interceptant certaines des actions du noyau. Sa mise en oeuvre est décrite pour un noyau Linux 64 bits sur architecture x86 qui dispose des technologies Intel VT-x et VT-d.