Dans le domaine de l'Optimisation Combinatoire, la résolution de manière optimale de problèmes de grande taille par le biais d'algorithmes Branch-and-Bound requiert un nombre très élevé de ressources de calcul. De nos jours, de telles ressources sont accessibles grâce aux grilles de calcul, composées de grappes de clusters réparties sur différents sites géographiques. Ces environnements parallèles posent de nombreux défis scientifiques, notamment en termes de passage à l'échelle, de la prise en compte de l'hétérogénéité des ressources ainsi qu'en termes de tolérance aux pannes. La plupart des approaches existantes pour l'algorithme Branch-and-Bound parallèle sont basées sur une architecture de type Maître-Esclave, où un processus maître répartit les tâches à accomplir auprès de processus esclaves en charge de les traîter. L'utilisation d'une telle entité centrale constitue un obstacle majeur en ce qui concerne le passage à l'échelle. Dans cette thèse, nous proposons de relever ces défis ainsi que de surmonter cet obstacle grâce à une approche innovante et complètement distribuée, basée sur une architecture Pair-à-Pair (P2P). Celle-ci repose sur un seul type de processus (le pair), qui a pour mission d'explorer son propre ensemble de tâches, de le partager avec d'autres pairs et de diffuser l'information globale. Nous définissons des mécanismes adaptés en lien avec l'algorithme Branch-and-Bound, qui traitent de la répartition de la charge, de la diffusion de la meilleure solution trouvée et de la détection de la terminaison des calculs. En plus de multiples expérimentations sur le problème d'ordonnancement du Flow-Shop sur la grille de calcul Grid'5000, nous proposons une preuve formelle de la correction de notre approche. Par ailleurs, nous traîtons une problématique souvent ignorés dans les travaux relatifs au calcul P2P, qui est l'importance de la topologie du réseau P2P. Généralement, une topologie très simple est utilisée. Les résultats obtenus montrent que notre approche permet le déploiement de réseaux de calculs à de très grandes échelles, constitués potentiellement de centaines de milliers de coeurs de calcul. Notre dernière contribution consiste en une approche Pair-à-Pair tolérante aux pannes afin de prendre en compte la nature généralement très volatile des ressources de calcul. Les résultats obtenus prouvent la robustesse de l'approche dans des environnements à la fois réalistes et sujets à de nombreux dysfinctionnements

Les travaux présentés ici, dans le cadre des Systèmes Multi-Agents (SMA) et de l'Intelligence Artificielle Distribuée (IAD), s'intéressent au problème de l'organisation dans les "systèmes ouverts". Dans ce cadre, nos recherches visent à définir des modèles de comportement sociaux permettant aux agents de s'organiser pour s'adapter à leur environnement. Notre démarche fait appel, entre autres principes méthodologiques, au concept de "cercle vertueux" qui se propose d'emprunter des métaphores à d'autres disciplines scientifiques pour concevoir des modèles informatiques. Dans un premier temps, nous recherchons dans les sociétés animales (en l'occurrence chez les primates) des métaphores de comportements proches de nos besoins. Nous définissons alors des modèles d'agent qui permettent, en simulation, de reproduire une des caractéristiques sociales observées chez les primates, la reconnaissance des relations de dominance. Ces modèles font ensuite l'objet d'une transposition à un domaine différent, la construction collective d'un lexique, pour estimer plus finement les dynamiques collectives sous-jacentes. Dans un second temps, nous nous intéressons à une expérimentation de "Robotique Collective Ouverte", dans laquelle un groupe de robots doit s'adapter à un environnement où travaillent des humains (projet MICRobES). Nous montrons que dans ces conditions, une simple transposition n'est plus possible et qu'il faut prendre en compte la corporéité des robots. Nous proposons alors pour cela des principes de conception de comportements d'agents faisant appel à la sélection naturelle (l'Ethogénétique) et nous présentons les résultats obtenus avec un framework implémentant ces concepts (ATNoSFERES). Nous montrons ainsi comment élargir les principes de départ en conciliant approche multi-agent et algorithmes évolutionnistes, en empruntant des concepts issus de l'éthologie.

Dans cette thèse, nous abordons le problème de la génération automatique de contenu graphique avec un haut niveau de détails pour la génération de mondes. Dans cette quête du réalisme, les principaux verrous scientifiques et techniques sont : la gestion des masses de données géométriques nécessaires à la création de variétés d'objets naturels, la prise en compte des interactions en les différents objets et le contrôle utilisateur.Notre approche s'appuie sur un modèle volumique original et unificateur permettant de représenter les différents matériaux d'un terrain. Nous proposons un ensemble d'algorithmes de haut niveau, combinant des étapes de simulation pour assurer la plausibilité physique et le réalisme visuel à des techniques de génération procédurale permettant de gérer efficacement la complexité. Nos algorithmes permettent ainsi de sculpter des terrains complexes avec des grottes ou des surplombs et de générer des routes avec des tunnels et des ponts permettant le franchissement d'obstacles naturels.

La découverte de motifs fréquents est un des problèmes en fouille de données. Afin de mieux comprendre l'influence des données sur les algorithmes, nous présentons une étude expérimentale des jeux de données communément utilisés par la communauté. Cette étude permet d'aboutir à une nouvelle classification des données en fonction des bordures : stable et en accord avec les performances des algorithmes. Malgré le grand nombre de travaux et un cadre théorique des problèmes d'extraction de motifs intéressants, l'utilisation de ces algorithmes pour résoudre des problèmes "équivalents" est peu répandue et reste délicate. Face à ces limites, nous proposons un algorithme générique de découverte des bordures des motifs intéressants, appelé ABS (Adaptive borders Search), adaptant dynamiquement sa stratégie en fonction des données. De plus, une librairie générique de composants C++ a été proposée pour faciliter le développement de solutions logicielles pour cette famille de problèmes.

Cette thèse est consacrée à l'étude de certains modèles de déformation semi-paramétriques. Notre objectif est de proposer des méthodes récursives, issues d'algorithmes stochastiques, pour estimer les paramètres de ces modèles. Dans la première partie, on présente les outils théoriques existants qui nous seront utiles dans la deuxième partie. Dans un premier temps, on présente un panorama général sur les méthodes d'approximation stochastique, en se focalisant en particulier sur les algorithmes de Robbins-Monro et de Kiefer-Wolfowitz. Dans un second temps, on présente les méthodes à noyaux pour l'estimation de fonction de densité ou de régression. On s'intéresse plus particulièrement aux deux estimateurs à noyaux les plus courants qui sont l'estimateur de Parzen-Rosenblatt et l'estimateur de Nadaraya-Watson, en présentant les versions récursives de ces deux estimateurs.Dans la seconde partie, on présente tout d'abord une procédure d'estimation récursive semi-paramétrique du paramètre de translation et de la fonction de régression pour le modèle de translation dans la situation où la fonction de lien est périodique. On généralise ensuite ces techniques au modèle vectoriel de déformation à forme commune en estimant les paramètres de moyenne, de translation et d'échelle, ainsi que la fonction de régression. On s'intéresse finalement au modèle de déformation paramétrique de variables aléatoires dans le cadre où la déformation est connue à un paramètre réel près. Pour ces trois modèles, on établit la convergence presque sûre ainsi que la normalité asymptotique des estimateurs paramétriques et non paramétriques proposés. Enfin, on illustre numériquement le comportement de nos estimateurs sur des données simulées et des données réelles.

Nous étudions le comportement des extensions linéaires au travers de deux invariants de comparabilité: le nombre de sauts et la dimension. La reconnaissance des ordres de Dilworth est montrée comme étant NP-complète, nous donnons des algorithmes polynomiaux pour résoudre ce problème sur deux sous-classes. Nous définissons les notions de dimension gloutonne et dimension dfgloutonne et étudions les cas d'égalité avec la dimension classique. Nous montrons la relation très étroite entre les extensions linéaires dfgloutonnes et les parcours en profondeur. Deux problèmes concernant les extensions linéaires dfgloutonnes sont montrés comme étant NP-difficiles.

Dans une première partie théorique, nous nous penchons sur une analyse rigoureuse des performances de l'algorithme Sequential Monte Carlo (SMC) conduisant à des résultats de type bornes L^p et inégalités de concentration. Nous abordons notamment le cas particulier des SMC associés à des schémas de température, et analysons sur ce sujet un processus à schéma adaptatif.Dans une seconde partie appliquée, nous illustrons son utilisation par la résolution de problèmes inverses concrets en électromagnétisme. Le plus important d'entre eux consiste à estimer les propriétés radioélectriques de matériaux recouvrant un objet de géométrie connue, et cela à partir de mesures de champs rétrodiffusés. Nous montrons comment l'algorithme SMC, couplé à des calculs analytiques, permet une inversion bayésienne, et fournit des estimées robustes enrichies d'estimations des incertitudes.

Lorsqu'une entreprise prend la décision stratégique de lancer une nouvelle famille de produits ou de reconcevoir un produit existant, l'architecte système a pour mission de concevoir ou de faire évoluer l'architecture de ce produit. L'architecte joue aussi le rôle de chef de projet et doit concevoir ou faire évoluer en même temps, l'organisation du projet pour la rendre plus performante. Dans ce mémoire, notre objectif est de développer des modèles et méthodes permettant d'aider les architectes système dans cette double activité. Dans le cadre de l'Ingénierie Système, notre méthode se base sur la définition de nos propres concepts d'architecture et de conception modulaire pour les étendre à la définition de l'architecture de l'organisation du projet. Nous proposons ensuite en cohérence avec notre positionnement, un algorithme de clustering utilisant l'outil DSM comme méthode de représentation, cet algorithme a pour fonction de révéler l'architecture d'un domaine en partant de sa représentation matricielle (DSM). L'application de notre méthode de développement des architectures est liée aux quatre situations de conception identifiées. Pour chacune de ces situations, nous proposons une méthode de conception des architectures, faisant appel à un traitement flou et/ou à des opérations matricielles. Chacune de ces situations est ensuite illustrée par une application à la conception d'un moteur thermique dans l'industrie automobile. La démarche présentée dans ce chapitre est une vision statique de la conception des architectures. Face cette vision statique, nous montrons la nécessité de faire « coévoluer » les architectures couplées. Nous proposons alors l'exploration des incertitudes comme méthode pour suivre l'évolution des systèmes (perturbations) étudiés. Nous développons une méthode basée sur un traitement flou pour faire coévoluer les architectures perturbées et pour les rendre cohérentes.

La première partie de cette thèse est consacrée à l'étude des algorithmes stochastiques aléatoirement tronqués de Chen et Zhu. La première étude de cet algorithme concerne sa convergence presque sûre. Dans le second chapitre, nous poursuivons l'étude de cet algorithme en nous intéressant à sa vitesse de convergence. Nous considérons également une version moyenne mobile de cet algorithme. Enfin nous terminons par quelques applications à la finance.<br />La seconde partie de cette thèse s'intéresse à l'évaluation des options parisiennes en s'appuyant sur les travaux de Chesney, Jeanblanc et Yor. La méthode d'évaluation se base sur l'obtention de formules fermées pour les transformées de Laplace des prix par rapport à la maturité. Nous établissons ces formules pour les options parisiennes simple et double barrières. Nous étudions ensuite une méthode d'inversion numérique de ces transformées dont nous établissons la précision.

Nous proposons dans ces travaux une étude des marches aléatoires dans l'algorithmique distribuée pour les réseaux dynamiques. Nous montrons dans un premier temps que les marches aléatoires sont un outil viable pour la conception d'algorithmes distribués. Ces <br />algorithmes reposent principalement sur les trois propriétés fondamentales des marches aléatoires (Percussion, Couverture, Rencontre). Nous fournissons une méthode qui évalue <br />le temps ́ecoulé avant que ces trois propriétés soient vérifiées. Cela nous permet d'évaluer de la complexité de nos algorithmes. Dans un second temps, nous proposons l'utilisation d'un jeton circulant aléatoirement sous forme de mot circulant afin de collecter sur ce jeton des informations topologiques. Ces informations permettent la construction et la maintenance d'une structure couvrante du réseau de communication. Ensuite, nous <br />avons utilisé cette structure pour concevoir un algorithme de circulation de jeton tolérant aux pannes pour les environnements dynamiques. Cet algorithme a la particularité d'être complètement décentralisé. Nous proposons dans un dernier temps d'adapter notre circulation de jeton pour proposer une solution au problème d'allocation de ressources dans les réseaux ad-hoc.