L'orientation service occupe de plus en plus une place importante dans la structuration des systèmes complexes. La conception et le développement d'applications évoluent progressivement d'un modèle traditionnel vers un modèle plus dynamique orienté services où la réutilisation et l'adaptabilité jouent un rôle important. Dans cette thèse, nous proposons une étude portant sur la conception et le développement d'applications par composition de services. Nous décrivons un environnement de partage de services : DyCoSe. Il consiste en un écosystème coopératif où les entreprises membres, organisées en communautés, partagent un consensus global représentant les fonctionnalités métier récurrentes et les propriétés non fonctionnelles communes. La composition d'applications dans DyCoSe repose sur une architecture à trois niveaux combinant à la fois une démarche descendante et une autre ascendante. La démarche descendante permet de décrire l'application à travers une interaction de composants haut niveau et de la raffiner en une ou plusieurs orchestrations de services. La démarche ascendante projette les caractéristiques de l'infrastructure réseau sous-jacente au niveau services. Un processus d'instanciation visant à réaliser une application composite est détaillé. Il formalise le choix des services, selon un ensemble de contraintes données, comme un problème d'optimisation de coûts. Deux solutions au problème d'instanciation sont étudiées. Une solution globale tient compte de l'ensemble des services disponibles dans l'écosystème et une solution locale favorise les services de certaines communautés. Un algorithme génétique est décrit comme implémentation de l'instanciation globale. Une simulation stochastique de l'environnement DyCoSe est proposée. Elle permet d'étudier les possibilités d'instanciation d'une application donnée dans un environnement où la disponibilité des services n'est pas garantie. Elle permet d'étudier aussi, le taux de réussite de l'exécution d'une instance d'une application donnée.

La Radio Logicielle (SDR) est une radio dont les transformations de la forme d'onde, modulation, démodulation des signaux d'un système radio sont mises en œuvre par du logiciel plutôt que par du matériel à fonctionnalité spécifique. Avec cette approche, l'adaptation du système à une autre norme de communication, ou même l'évolution vers une technologie plus récente peuvent être réalisés par mise à jour du logiciel sans remplacement du matériel qui serait long et coûteux. L'architecture de communication logicielle (Software Communication Architecture, SCA), est une architecture ouverte largement acceptée pour les projets de SDR. La spécification SCA minimise le coût de portage des applications en fournissant une couche d'abstraction qui rend transparentes les méthodes spécifiques de chaque système. Dans cette thèse, on s'intéresse au développement et à la programmation d'une plateforme SDR conforme à SCA.Les nouvelles plateformes de SDR sont en général implémentées sur des plateformes multiprocesseurs système sur puce (MPSoC) exploitant ses importantes ressources de calculs avec une bonne efficacité énergique. Les possibilités d'un rapide développement, déploiement et vérification des logiciels embarqués parallèles sur ces nouvelles plateformes MPSoC sont autant de points clés pour satisfaire les objectifs de performance tout en respectant les délais de mise à disposition sur le marché et le coût de développement.On a proposé un flot de conception pour la SDR avec l'exploration architecturale systématique et l'optimisation multi-objective utilisant le modèle de programmation hybride (distribué client/serveur + parallèle).On a étudié aussi la synthèse de topologie de réseau-sur-puce (PSTRP) qui est une partie du flot de conception. Le problème de la synthèse de la topologie du réseau-sur-puce peut se modéliser sous forme de programme linéaire en nombres entiers. Les résultats montrent que les contraintes d'implémentation, comme la hiérarchie du réseau sur puce, doivent être prises en compte pour obtenir un résultat à la fois mathématiquement optimisé et électroniquement réalisable.

Les machines actuelles offrent de plus en plus de fonctionnalités arithmétiques au niveau matériel. Les générations actuelles de processeurs proposent des opérateurs matériels rapides pour le calcul des divisions, des racines carrées, des sinus, des cosinus, des logarithmes... La littérature du domaine montre qu'en changeant notre façon de représenter les nombres et/ou en utilisant des algorithmes spécifiques de calcul, il est possible de réaliser des opérateurs matériels particulièrement efficaces. Le but de cette thèse est d'étudier et d'illustrer les liens profonds existants entre l'arithmétique et l'architecture des ordinateurs à travers quatre problèmes. Les Opérateurs Arithmétiques Asynchrones permettent de calculer les fonctions arithmétiques (addition, multiplication, division) avec un délai variable. En particulier, nous avons développé un additionneur asynchrone dont le temps moyen de calcul est O(sqrt(\log n)). L'Arithmétique En-Ligne permet de réaliser des architectures où les nombres circulent en série, chiffre par chiffre, les poids forts en tête. L'intérêt de cette arithmétique est de pouvoir calculer toutes les fonctions (en arithmétique série poids faibles en tête, il n'est pas possible de calculer les divisions et les maximums) et d'obtenir des opérateurs de petite taille avec un nombre d'entrées/sorties plus faible que leur équivalents parallèles. L'Arrondi Exact des Fonctions Elémentaires consiste à déterminer la précision intermédiaire permettant de toujours pouvoir arrondir "exactement" les résultats du calcul des fonctions élémentaires (sinus, cosinus, exponentielle...). Nous proposons dans cette thèse une méthode qui permet d'arrondir exactement les fonctions élémentaires assez rapidement. Le Système Semi-Logarithmique de Représentation des Nombres est un système permettant d'effectuer rapidement les calculs de problèmes dont le nombre de multiplications/divisions est grand devant le nombre d'additions/soustractions.

Ce travail de thèse explore la conception d'applications collaboratives destinées a être exécutées dans des environnements ubiquitaires. Les applications collaboratives fournissent des moyens pour que des utilisateurs organisés dans des groupes puissent coopérer afin d'effectuer une tâche commune. Jusqu'à présent, ces applications ont été conçues pour une utilisation avec des systèmes de type "bureau". Dans ce travail nous proposons de faire profiter ces applications des possibilités offertes par les environnements issus de l'informatique ubiquitaire, notamment la sensibilité au contexte et l'adaptation. En premier lieu, un modèle sémantique de la collaboration, appelé GCO, est proposé afin de permettre l'expression des besoins de collaboration indépendamment du domaine d'application. Ce modèle est une ontologie de la collaboration incorporant des règles permettant d'effectuer d'inférences pour déduire un schéma de déploiement à partir des besoins de collaboration. En deuxième lieu, une approche de modélisation est proposée afin de faciliter la conception d'applications collaboratives ubiquitaires. Cette approche se base sur une décomposition multi-niveau permettant la mise en Suvre d'une adaptation de l'architecture du système aux changements du contexte haut niveau (exigences de l'application) et bas niveau (contraintes liées aux ressources). Ensuite, le framework FACUS, qui est une implantation de l'approche utilisant GCO comme modèle pivot pour l'interopérabilité entre les exigences et les contraintes, est proposé. Enfin, FACUS est évalué tant du point de vue fonctionnel que de celui des performances, montrant la faisabilité de notre approche.

Cette thèse étudie d'un point de vue algorithmique diverses méthodes de consensus portant sur des collections d'objets étiquetés. Les problèmes étudiés impliquent des objets étiquetés sans répétition d'étiquettes ; ces objets peuvent être des arbres enracinés ou des séquences, avec des applications à la bioinformatique. Ainsi, les problèmes sur les arbres considérés dans cette thèse peuvent trouver des applications pour l'estimation de congruence entre phylogénies, pour la construction de superarbres, et pour l'identification de transferts horizontaux de gènes. Pour leur part, les problèmes sur les séquences considérés dans cette thèse ont des applications potentielles pour le calcul de distance génomique basé sur les ordres de gènes. De manière générale, ce travail met à profit les théories de la complexité paramétrique et de l'approximabilité pour obtenir des algorithmes et des résultats de difficulté pour les problèmes étudiés.

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.