Nous nous intéressons dans cette thèse à la simulation parallèle des systèmes multi-agent (SMA), plus particulièrement à des comportements d'agents situés : entités autonomes agissant dans un environnement. La simulation du trafic routier, de populations de personnes ou d'animaux sont quelques exemples de ses applications.<br /><br />Actuellement, il y a un manque de simulateurs parallèles efficaces pour ces systèmes, qui seraient très utiles, compte tenu des temps d'exécution pour des simulations à grande échelle. Dans ce contexte, notre apport se divise en trois parties : (1)~fournir un modèle de simulation de SMAs à grande échelle, appelé ParSSAP, (2)~faire un travail d'algorithmique parallèle dans les SMAs et (3)~fournir une implantation de ce modèle sous la forme d'une bibliothèque parallèle.<br /><br />Dans cette thèse nous commençons par introduire les SMAs, les problèmes de parallélisation qu'ils posent et l'état de l'art dans la simulation des SMAs. Nous présentons ensuite nos travaux et apports : le modèle de simulation que nous avons conçu, l'algorithmique parallèle utilisée dans deux percepts d'agents fournis dans notre bibliothèque (calcul des champs de visibilité et propagation des champs de potentiel), la documentation sur notre bibliothèque et quelques applications avec leurs performances à l'exécution. Finalement, nous présentons le bilan, positif, de nos travaux.<br /><br />Notre modèle et son implantation parallèle sont destinés à une utilisation facile et à des exécutions efficaces. Ils peuvent encore être enrichis, néanmoins notre bibliothèque permet déjà de construire rapidement des applications efficaces à l'exécution sur des machines parallèles modernes.

La théorie des intervalles permet de construire des sur-ensembles du domaine de variation d'une fonction réelle. Ainsi, de manière très naturelle, elle permet de construire une approximation extérieure de l'ensemble des solutions d'un système d'équations. Couplée aux théorèmes usuels d'existence (par exemple les théorèmes de Brouwer ou de Miranda) la théorie des intervalles permet aussi de prouver rigoureusement l'existence de solutions pour un système d'équations.<br /> <br />La théorie des intervalles modaux propose des interprétations plus riches que la théorie de intervalles classiques. En particulier, l'interprétation des extensions aux intervalles modaux permet de prouver directement l'existence de solution d'un système d'équations (sans faire intervenir explicitement les théorèmes d'existence). Malgré les récents développements qui ont montré le potentiel applicatif de la théorie des intervalles modaux, l'utilisation de cette théorie reste fort limitée. Cela peut s'expliquer de la manière suivante:<br /><br />A) La théorie des intervalles modaux a une construction originale mais compliquée qui est assez éloignée de la construction de la théorie des intervalles classiques. Cela rend par exemple difficile l'ajout de nouveaux concepts.<br />B) Aucun préconditionnement compatible avec les interprétations offertes par la théorie des intervalles modaux n'a été proposé.<br />C) Aucun protocole de linéarisation compatible avec les interprétations offertes par la théorie des intervalles modaux n'a été proposé.<br /> <br />Dans le cadre de cette thèse, ces trois points sont développés. D'une part, une nouvelle formulation des principaux résultats de la théorie des intervalles modaux est proposée. Cette nouvelle formulation est faite dans le cadre des intervalles généralisés (intervalles dont les bornes ne sont pas contraintes à être ordonnées) et reprend la construction de la théorie des intervalles classiques. D'autre part, un protocole de préconditionnement et un protocole de linéarisation compatibles avec les interprétations des nouvelles extensions aux intervalles généralisés sont proposés. Le protocole de linéarisation proposé aura la forme d'une nouvelle extension de la valeur moyenne aux intervalles généralisés.<br /> <br />Ces développements théoriques aboutissent à deux applications: d'une part, la nouvelle extension de la valeur moyenne aux intervalles généralisés est utilisée pour construire une approximation intérieure du domaine de variation d'une fonction à valeurs vectorielles. Ce problème est aujourd'hui mal traité par la théorie des intervalles classiques. D'autre part, un opérateur généralisé de Hansen-Sengupta dédié à l'approximation extérieure des "AE-solution sets" est proposé. Il est beaucoup plus simple et moins coûteux en temps de calcul que les autres techniques permettant de résoudre ce type de problèmes. Une comparaison de la puissance de résolution de ces différentes techniques nécessitera d'intégrer l'opérateur généralisé de Hansen-Sengupta au sein d'un algorithme de bissection.

Cette thèse se propose d'examiner sous un angle particulier quelques aspects de la morphologie mathématique. Nous montrons d'abord comment la notion de convergence d'ensembles fermés et celle d'ensemble aléatoire fermé peuvent être employées en géométrie algorithmique. Nous exposons ensuite une nouvelle technique permettant l'écriture d'algorithmes morphologiques efficace en imagerie binaire au moyen d'un codage de contours sous forme de chaînes et lacets. Les algorithmes concernés sont entre autres l'érosion, la dilatation, la fonction distance, tant dans le cas euclidien que géodésique, la fonction de propagation, en métrique hexagonale et dodécagonale, le labeling, la reconstruction. . . Nous abordons aussi les mesures morphologiques telles que variation diamétrale, diamètre de Ferret, périmètre, nombre d'Euler. . . L'emploi des transformations est alors illustré par la résolution complète d'un problème particulier en sciences des matériaux où nous discutons les qualités respectives d'une dizaine de solutions différentes. Enfin, un essai de formalisation de l'emploi des transformations morphologiques a abouti à l'écriture d'un système de programmation automatique.

La première partie de ce mémoire est consacrée à l'énumération de diverses familles de structures arborescentes, en général selon le nombre de sommets. Les trois premiers chapitres sont consacrés à l'étude des arborescences de Cayley telles que la racine est inférieure à ses fils et des arborescences alternantes. La plupart de nos résultats sont prouvés bijectivement. Nous nous intéressons ensuite aux arborescences coloriées, et plus particulièrement à la formule d'inversion de séries formelles multivariées de Good-Lagrange. Nous donnons une nouvelle preuve bijective d'une variante de cette formule et utilisons cette preuve pour prouver combinatoirement diverses formules d'énumération de structures arborescentes et en déduire des algorithmes de génération aléatoire pour ces structures (notamment les cactus planaires). Nous concluons cette première partie par un chapitre consacré aux constellations : en combinant notre preuve de la formule de Good-Lagrange et la conjugaison d'arborescences (due à Bousquet-Mélou et Schaeffer), nous prouvons bijectivement une formule (nouvelle) pour l'énumération de constellations selon le nombre de sommets et de faces. Dans la seconde partie, nous étudions le problème de la recherche de motifs dans une arborescence, en utilisant une structure de données classique pour les mots : l'arborescence des suffixes. Nous proposons notamment un algorithme de recherche de motifs dans une arborescence, basé sur un codage d'une arborescence par des mots et sur l'utilisation de l'arborescence des suffixes d'un de ces mots, qui semble avoir de bonnes propriétés expérimentales. Nous concluons en étendant la notion d'arborescence des suffixes des mots aux arborescences et en décrivant un algorithme de construction pour cette structure.

Le problème de l'assimilation de données sous sa forme générale peut se formuler : "comment utiliser simultanément un modèle théorique et des observations pour obtenir la meilleure prévision météorologique ou océanographique ?", sa résolution est très coûteuse, pour la prochaine génération de modèles elle nécessitera une puissance de calcul de l'ordre de 10 Tflops. à l'heure actuelle, aucun calculateur n'est capable de fournir de telles performances mais cela devrait être possible dans quelques années, en particulier grâce aux ordinateurs parallèles à mémoire distribuée. Mais, la programmation de ces machines reste un processus compliqué et on ne connaît pas de méthode générale pour paralléliser de manière optimale un algorithme donné. Nous tenterons, de répondre au problème de la parallélisation de l'assimilation de données variationnelle, ce qui nous conduira à étudier la parallélisation d'algorithmes numériques d'optimisation assez généraux. Pour cela, nous étendrons la méthodologie de l'écriture des modèles adjoints au cas où le modèle direct est parallèle avec échanges de messages explicites. Nous étudierons les différentes approches possibles pour paralléliser la résolution du problème de l'assimilation de données : au niveau des modèles météorologiques direct et adjoints, au niveau de l'algorithme d'optimisation ou enfin au niveau du problème lui-même. Cela nous conduira à transformer un problème séquentiel d'optimisation sans contraintes en un ensemble de problèmes d'optimisation relativement indépendants qui pourront être résolus en parallèle. Nous étudierons plusieurs variantes de ces trois approches très générales et leur utilité dans le cadre du problème de l'assimilation de données. Nous terminerons par l'application des méthodes de parallélisation précédentes au modèle de Shallow Water et comparerons leurs performances. Nous présenterons également une parallélisation du modèle météorologique ARPS (Advanced Regional Prediction System).

Les arrangements de droites du plan sont étudiés en géométrie algorithmique pour leur simplicité géométrique couplée à leur grande richesse combinatoire, ou topologique. Notre contribution porte en partie sur la recherche de structures de données couplées à des algorithmes, efficaces à la fois pour la construction des arrangements et l'exploitation de l'information minimale les définissant. Mais l'apport principal de notre travail est l'étude de la représentation géo-métrique des arrangements, notamment par la définition d'une équivalence géométrique entre deux ensembles de droites du plan euclidien par isotopie, qui justifie théoriquement l'algorithme d'optimisation géométrique que nous proposons. Cet algorithme se base sur des critères de ``lisibilité'' de la représentation d'un arrangement, que nous proposons et justifions. Nous donnons également des résultats d'optimisation analytique pour les très petits nombres de droites.

Avec l'explosion de la quantité de données biologiques disponible, développer de nouvelles méthodes de traitements efficaces est une problématique majeure en bioinformatique. De nombreuses structures biologiques sont modélisées par des structures arborescentes telles que les structures secondaires d'ARN et l'architecture des plantes. Ces structures contiennent des motifs répétés au sein même de leur structure mais également d'une structure à l'autre. Nous proposons d'exploiter cette propriété fondamentale afin d'améliorer le stockage et le traitement de tels objets. En nous inspirant du principe de filtres sur les séquences, nous définissons dans cette thèse une méthode de filtrage sur les arborescences ordonnées, permettant de rechercher efficacement dans une base de données, un ensemble d'arborescences ordonnées proches d'une arborescence requête. La méthode se base sur un découpage de l'arborescence en graines et sur une recherche de graines communes entre les structures. Nous définissons et résolvons le problème de chaînage maximum sur des arborescences. Nous proposons dans le cas des structures secondaires d'ARN une définition de graines (l−d) centrées. Dans un second temps, en nous basant sur des techniques d'instanciations utilisées, par exemple, en infographie et sur la connaissance des propriétés de redondances au sein des structures biologiques, nous présentons une méthode de compression permettant de réduire l'espace mémoire nécessaire pour le stockage d'arborescences non-ordonnées. Après une détermination des redondances, nous utilisons une structure de données plus compacte pour représenter notamment l'architecture de la plante, celle-ci pouvant contenir des informations topologiques mais également géométriques.

L'objet de cette thèse porte sur la conversion d'un modèle CSG vers un modèle BRep d'une scène définie par des quadriques. Cet algorithme est composé de quatre étapes : (i) le paramétrage de chaque courbe d'intersection entre quadriques ; (ii) la détermination des points d'intersection entre au moins trois quadriques ; (iii) la détection des segments ainsi obtenus qui bornent une face du modèle BRep sur chacune des quadriques séparément ; (iv) l'identification et le regroupement des chaînes de segments qui délimitent une même face sur chaque quadrique séparément (certaines faces peuvent avoir des <>, et par conséquent être constituées par au moins deux chaînes de segments). Les deux premières étapes ont été résolues grâce à deux algorithmes de la littérature. Les deux étapes restantes sont traitées par des algorithmes que nous avons conçus : respectivement VE (Visible Edges) et CA (Chains Assembling). Notre algorithme est robuste au sens où tous les cas dégénérés sont traités dans le paradigme du calcul géométrique exact. Il résout intégralement le problème de conversion CSG-BRep de scènes définies par des quadriques. Sa complexité dans le pire des cas s'élève à $O(n^4)$ où $n$ est le nombre de quadriques. Une implantation partielle a été effectuée et des tests préliminaires réalisés.

La génomique comparative est une discipline de la biologie qui s'intéresse à l'évolution des génomes par le biais de la comparaison entre espèces de leur structure et de l'information qu'ils contiennent. Implicitement, identifier des similarités entre deux génomes revient à décrire une propriété ancestrale qu'ils partagent encore de nos jours. L'abondance de données génomiques provenant de centaines d'espèces différentes rend possible de nombreuses comparaisons de ce type, mais souvent restreinte à deux espèces comparées l'une à l'autre, hors de tout cadre unifié et sans références particulières. Ce travail de thèse décrit une nouvelle méthode, appelée AGORA (Algorithms for Gene Order Reconstruction in Ancestors), pour reconstruire de manière automatique et systématique l'ordre des gènes et les caryotypes de toutes les espèces ancestrales dans une phylogénie donnée. AGORA est capable de gérer les duplications de gènes, les délétions, et les gains, et interprète de manière réaliste des phylogénies complexes de gènes. Nous avons appliqué la méthode chez 46 espèces de vertébrés séquencées et annotées (en utilisant 8 espèces supplémentaires en référence externe) pour reconstruire des ordres de gènes ancestraux dans 43 génomes ancestraux sur près de 600 millions d'années d'évolution. Les performances d'AGORA ont été mesurées par des simulations de génomes de vertébrés, et par confrontation à des génomes ancestraux déjà connus. Les données, présentées graphiquement dans un serveur web nommé Genomicus (http://www.dyogen.ens.fr/genomicus) fournissent un nouveau cadre unifié dans lequel les génomes ancestraux peuvent servir de référence naturelle auxquelles comparer les génomes modernes qui en descendent. À ce titre, ces données fournissent une nouvelle ressource pour étudier l'évolution de l'organisation de l'information génétique dans les génomes.

La génomique comparative étudie les similarités et/ou les dissimilarités entre génomes et permet d'établir des relations entre les espèces afin notamment de construire des phylogénies. Elle permet également de mettre en évidence des régions conservées au sein des génomes et de trouver ainsi des ensembles de gènes impliqués dans des processus biologiques conservés au cours de l'évolution. Dans ce mémoire, nous nous intéressons au calcul de mesures entre deux génomes en présence de gènes dupliqués, et plus particulièrement aux mesures à base de points de cassure, d'adjacences, d'intervalles communs et d'intervalles conservés. Suivant une démarche informatique, nous proposons tout d'abord une étude avancée de la complexité algorithmique des problèmes rencontrés, en prouvant notamment pour la plupart d'entre eux soit leur NP-Complétude soit leur APX-Difficulté. Par la suite, nous exposons plusieurs méthodes de calcul de mesures entre deux génomes, à savoir (i) une approche exacte basée sur une transformation en un problème de contraintes à variables booléennes, (ii) une heuristique et (iii) une méthode hybride qui s'appuie sur la méthode exacte et l'heuristique proposées. Par une étude sur un jeu de données réel, nous montrons les qualités respectives de ces méthodes. Enfin, nous proposons un protocole de calcul des intervalles communs et mettons en évidence, par son utilisation et par un outil de visualisation, l'aspect fonctionnel de certains intervalles communs.