Cette thèse concerne le contrôle coopératif de systèmes multi-agents. Ce sujet a été largement étudié dans la littérature récente en raison de son grand nombre d'applications. Cette thèse propose des nouvelles conceptions de stratégies de contrôle collaboratif afin de réaliser une mission d'exploration sous-marine. En particulier, l'objectif final est de diriger une flotte de véhicules autonomes sous-marins, équipés de capteurs appropriés, jusqu'à l'emplacement d'une source de température, de polluants ou d'eau douce. Dans cette situation, il est pertinent de considérer les contraintes de communication entre véhicules qui sont décrites au moyen d'un graphe de communication. Les premières contributions traitent du développement des lois de commande d'une formation qui stabilisent la flotte vers des formations variant dans le temps, et qui, de plus, distribuent uniformément les véhicules le long de la formation. Enfin, le problème de recherche d'une source est abordé par l'interprétation de la flottille de véhicules comme un réseau de capteurs mobiles. En particulier, il est démontré que les mesures recueillies par la flotte de véhicules permettent d'estimer le gradient de concentration de la quantité d'intérêt. En suivant cette idée, un algorithme distribué basé sur des algorithmes de consensus est proposé pour estimer la direction du gradient d'une distribution de signal.

Les travaux effectués lors de cette thèse portent sur 1a construction d'algorithmes géométriques dit adaptatifs dans 1e sens ou leur temps de calcul s'adapte a la solution construite. Nous décrivons tout d'abord les principaux paradigmes qui permettent d'obtenir des algorithmes adaptatifs. Puis , nous proposons un algorithme quasi-optimal adaptatif pour le calcul d'enveloppe convexe d'objets planaires dont la complexité de l'enveloppe convexe de toute paire soit bornée. L'algorithme est basé sur une approche composite combinant 1e paradigme mariage avant conquête et 1a méthodologie du groupement en paquets. Nous considérons également le calcul de l'enveloppe supérieure de fonctions et la décomposition convexe partielle d'un ensemble de points. Finalement, nous nous sommes intéressés aux problèmes de perçabílíté d'objets qui ont été montré NP-difficiles. En premier lieu, nous avons étudié le cas de boîtes ísothétíques en donnant une heuristique adaptative dont 1a précision soit elle-même adaptative. Ensuite, nous avons étudié les propriétés combinatoires des objets convexes pour 1a perçabílíté. Nous obtenons une batterie d'algorithmes pour des classes variées d'objets dont certains prouvent l'exístence de théorèmes de type Helly.

Nous nous intéressons dans ce mémoire à des méthodes de parallélisation par découplage du système dynamique. Plusieurs applications numériques de nos jours conduisent à des systèmes dynamiques de grande taille et nécessitent des méthodes de parallélisation en conséquence pour pouvoir être résolues sur les machines de calcul à plusieurs processeurs. Notre but est de trouver une méthode numérique à la fois consistante et stable pour réduire le temps de la résolution numérique. La première approche consiste à découpler le système dynamique en sous-systèmes contenant des sous-ensembles de variables indépendants et à remplacer les termes de couplage par l'extrapolation polynomiale. Une telle méthode a été introduite sous le nom de schéma C (p, q, j), nous améliorons ce schéma en introduisant la possibilité à utiliser des pas de temps adaptatifs. Cependant, notre étude montre que cette méthode de découplage ne peut satisfaire les propriétés numériques que sous des conditions très strictes et ne peut donc pas s'appliquer aux problèmes raides présentant des couplages forts entre les sous-systèmes. Afin de pouvoir répondre à cette problématique de découplage des systèmes fortement couplés, on introduit le deuxième axe de recherche, dont l'outil principal est la réduction d'ordre du modèle. L'idée est de remplacer le couplage entre les sous-ensembles de variables du système par leurs représentations sous forme réduite. Ces sous-systèmes peuvent être distribués sur une architecture de calcul parallèle. Notre analyse du schéma de découplage résultant nous conduit à définir un critère mathématique pour la mise à jour des bases réduites entre les sous-systèmes. La méthode de réduction d'ordre du modèle utilisée est fondée sur la décomposition orthogonale aux valeurs propres (POD). Cependant, ne disposant pas à priori des données requises pour la construction de la base réduite, nous proposons alors un algorithme de construction incrémentale de la base réduite permettant de représenter le maximum des dynamiques des solutions présentes dans l'intervalle de simulation. Nous avons appliqué la méthode proposée sur les différents systèmes dynamiques tels que l'exemple provenant d'une EDP et celui provenant de l'équation de Navier Stokes. La méthode proposée montre l'avantage de l'utilisation de l'algorithme de découplage basé sur la réduction d'ordre. Les solutions numériques sont obtenues avec une bonne précision comparées à celle obtenue par une méthode de résolution classique tout en restant très performante selon le nombre de sous-systèmes définis.

Cette thèse a pour but d'estimer la position et la puissance de sources sonores ponctuelles à l'aide d'une antenne acoustique. Nous nous intéressons d'abord à la directivité des antennes acoustiques pondérées. On montre qu'une telle antenne, appelée antenne conventionnelle, même si elle est à directivité optimale, est inutilisable pour localiser plusieurs sources sonores. Des traitements adaptatifs d'antenne sont donc exigés et les méthodes dites à haute résolution sont introduites. Elles sont basées sur l'estimation de la matrice de covariance des signaux issus des capteurs et présentent l'avantage de s'affranchir des limitations naturelles du traitement d'antenne conventionnel. Cependant, ces méthodes nécessitent l'emploi d'un modèle de propagation et sont donc par nature peu robustes aux erreurs de modèle, ce qui peut être parfois un handicap et dégrader leurs performances. Par la suite, nous présentons une nouvelle méthode de séparation des sources utilisant une représentation parcimonieuse des signaux. Nous montrons que ses performances sont meilleures que celles obtenues par les méthodes à haute résolution et notre algorithme parvient à une bonne résolution spatiale, même sous des conditions défavorables. Cette méthode est appliquée aux sources corrélées et décorrélées, à bande étroite et à large bande, en champ proche et en champ lointain. Pour finir, nous présentons des méthodes pour estimer la puissance des sources sonores. Des simulations numériques et des expérimentations en chambre anéchoïque sont effectuées afin de vérifier et de valider les analyses et les résultats théoriques

Presque aussi ancienne que l'informatique elle-même la lecture optique automatique a maintenant plus de trente ans. Comme l'informatique, elle a connu une évolution constante les systèmes lourds, peu flexibles et entièrement câblés du début laissent peu à peu la place à d'autres beaucoup plus légers, flexibles (orientés multipolice) et plus faciles à mettre en oeuvre (logique programmée). Deux facteurs en sont responsables. - Le premier a trait aux algorithmes employés : les premiers algorithmes, inspirés des méthodes connues de détection des signaux radio, ont laissé la place à des algorithmes basés sur l'analyse des caractères ; la structure de ceux-ci variant peu d'une police à l'autre, les machines deviennent du coup multipolice. - Le second est un facteur proprement technologique : l'avènement du microprocesseur. Il permet d'augmenter l'intelligence des algorithmes en les distribuant sur les différentes parties d'un même système. Les machines construites autour d' un seul processeur sont ainsi remplacées par d'autres, aussi rapides mais plus fiables et plus compactes, ayant une structure multiprocesseur.

L'émergence des systèmes pair-à-pair et la possibilité de réaliser des calculs et d'échanger des données par des services web conduit à des systèmes d'intégration de données à large échelle où l'évaluation de requêtes et d'autres traitements complexes sont réalisés par composition de services. Un problème important dans ce type de systèmes est l'absence de connaissances globales. Il est difficile par exemple de choisir le meilleur pair pour le routage des requêtes, le meilleur service lors de la composition de services ou de décider parmi les données locales à un pair celles à rafraîchir, à mettre en cache, etc. La notion de choix implique celle de classement. Bien qu'il soit possible de comparer et classer des entités d'après leur contenu ou d'autres métadonnées associées, ces techniques sont généralement basées sur des descriptions homogènes et sémantiquement riches. Une alternative intéressante dans le contexte d'un système à large échelle est le classement basé sur les liens qui exploite les relations entre les différentes entités et permet de faire des choix fondés sur des informations globales. Cette thèse présente un nouveau modèle générique de classement de services fondé sur leurs liens de collaboration. Nous définissons une importance globale de service en exploitant des connaissances spécifiques sur sa contribution aux autres services à travers les appels reçus et les données échangées. L'importance peut être calculée efficacement par un algorithme asynchrone sans génération de messages supplémentaires. La notion de contribution est abstraite et nous avons étudié son instanciation dans le cadre de trois applications: (i) le classement de services basé sur les appels où la contribution reflète la sémantique des services ainsi que leur utilisation avec le temps; (ii) le classement de services par l'utilisation des données où la contribution des services est fondée sur l'utilisation de leurs données pendant l'évaluation des requêtes dans un entrepôt distribué; (iii) la définition des stratégies de cache distribuées qui sont basées sur la contribution d'une mise en cache des données à réduire la charge du système.

Plusieurs méthodes d'optimisation sont proposées. Un algorithme original d'antialiassage rapide est présenté pour améliorer la qualité des images sans trop augmenter les temps de calcul. Une méthode de construction d'une table de couleurs variable par quantification des couleurs dans un OCTREE en utilisant le balayage de PEANS est étudiée.

K. E. Iverson a défini le langage APL en 1962 dans un ouvrage intitulé "A Programming Language". Malgré les difficultés nouvelles que posait ce langage aux implémenteurs, des interprètes APL furent rapidement disponibles chez I.B.M., d'abord à titre expérimental en 1965, puis commercialisés sur ordinateurs 1130 et 360 (R3,R7). En effet, ce langage s'était d'emblée révélé intéressant pour toutes les applications réclamant plus de programmation que de longs calculs. Depuis cette époque, d'autres interprètes APL ont vu le jour chez d'autres constructeurs (R 1,R2,R5). Réalisés pour la plupart sur de gros ordinateurs, ils réclament des ressources hors de proportion avec les moyens habituels des ingénieurs ou des étudiants. Parallèlement, de nombreuses recherches ont été menées pour tenter d'accélérer l'interprétation du langage. P.S. Abrams a, en premier, introduit certaines notions fondamentales d*optimisation et envisagé la construction d'un matériel muni d'un code machine très voisin du langage APL (I5). Plusieurs propositions tendant à restreindre le langage afin de pouvoir le compiler plus facilement ont été faites (IlO,Il3,Il5,Il6,Il8). Chez Hewlett Packard, un système APL a été réalisé et doté d*un compilateur dynamique incrémental générant à partir du langage source un code directement exécutable et pouvant être réutilisé. D'autres approches, moins théoriques, ont consisté à réaliser un maximum de fonctions possibles au niveau matériel, en microprogrammant un sous-interprète scalaire ou vectoriel et en rédigeant ensuite dans l'APL restreint ainsi obtenu l'interprète complet.

Ces travaux concernent les études des algorithmes d'une part pour prédire les quantités thermodynamiques et la structure secondaire des ARN, d'autre part pour l'alignement de séquences. Dans une première partie, nous appliquons un algorithme de Monte Carlo non-Boltzmann pour estimer la densité d'états d' énergie des structures secondaires d'une séquence d'ARN, ou d'une hybridation de deux molécules d'ARN. Nous montrons d'abord que la densité estimée par notre programme est aussi bonne que la densité exacte, et le temps d'exécution de notre pro- gramme est beaucoup plus rapide. Nous calculons ensuite la température de dénaturation d'une hybridation de deux molécules d'ARN. Nous montrons que nos températures de dénaturation sont plus proches des valeurs expérimentales que les deux autres programmes existants. Puis, dans une deuxième partie, nous implémentons un algorithmes de type programmation dynamique qui engendre des structures sous-optimales dans lesquelles, nous espérons de trouver les deux structures fonctionnelles de riboswitch. Nous appliquons d'abord notre programme sur un exemple du riboswitch TPP dans lequel nous avons réussi à détecter ses deux structures fonctionnelles. Nous montrons ensuite que les structures prédites par notre programme sont plus proches de la structure réelle que celles des cinq autres programmes existants. Enfin, dans une troisième partie, nous présentons un algorithme de recherche des alignements sous-optimaux de séquences. Dans le cas de protéines, nous nous intéressons surtout à l'amélioration de la qualité d'alignement de séquences pour un niveau d'identité de séquence de 10-15%. Nous comparons d'abord nos alignements à ceux produits par l'algorithme de Needman-Wunsch. Nous prédisons plus d'alignements de référence que l'algorithme de Needman-Wunsch. Nous calculons ensuite les fréquences des paires de bases alignées et les entropies de position spécifique dans nos alignements sous-optimaux. Nous montrons que les entropies calculées à partir de notre programme sont plus corrélées avec les positions des paires de résidus fiablement alignées selon BAliBASE.

Nous défendons la thèse selon laquelle la modélisation des Algorithmes Génétiques Coévolutionnaires (AGCs) sous forme de systèmes multi-agent organisationnels répond au manque d'expressivité en termes de structure, d'interactions et d'adaptation de ces algorithmes dans les modèles et plateformes existants. Dans cette optique nous introduisons MAS4EVO, Multi-Agent Systems for EVolutionary Optimization, un nouveau modèle agent (re-)organisationnel basé sur Moise+. MAS4EVO est implémenté dans DAFO (Distributed Agent Framework for Optimization), un framework multi-agent organisationnel permettant l'utilisation, la manipulation et la distribution d'AGCs existants et nouvellement créés (hybride et dynamique) pour l'optimisation de problèmes difficiles. Les expérimentations de ces AGCs ont été conduites sur deux problèmes d'optimisation métier, le premier étant un problème de gestion de stock et le second étant un problème de contrôle de topologie dans les réseaux ad hoc sans fil.