Dans ce mémoire nous abordons de prime abord la reconstruction d'arbres et de réseaux phylogénétiques, à travers deux méthodes d'inférence. Les arbres et les réseaux sont deux supports pour la représentation de l'évolution d'un groupe d'espèces étudiées. Les modèles d'évolution d'espèces qui seront traités sont les suivants : 1) Le modèle arborescent classique qui a longtemps été le seul support formel pour la représentation des relations génétiques entre les espèces. 2) Le modèle en réseau qui permet de représenter des mécanismes phylogénétiques importants pouvant jouer un rôle clé dans l'évolution et pouvant s'expliquer par le phénomène de l'évolution réticulée. Nous nous sommes particulièrement intéressés aux algorithmes d'inférence de réseaux de transferts horizontaux de gènes. Un transfert horizontal de gènes permet à deux espèces de s'échanger, partiellement ou totalement, différents gènes au cours de l'évolution. Le travail effectué sur la reconstruction d'arbres et de réseaux phylogénétiques a mené à la publication de trois articles. Ensuite, nous abordons le problème de réduction du temps d'exécution de différents programmes bioinformatiques. Ce problème a pris de l'ampleur à cause de la croissance du volume de données biologiques et du blocage de la puissance des ordinateurs autour de 3,4GHZ depuis environ deux ans. Nous décrivons un procédé d'accélération des calculs effectués par différents algorithmes d'inférence et de représentation de l'évolution des espèces, en utilisant le parallélisme. Le parallélisme mis en place a été réalisé à travers une librairie standard de passage de messages (Message Passing Interface). Nous montrons les différentes formes de parallélisme, les architectures de systèmes parallèles, quelques environnements qui permettent de supporter l'exécution des applications de façon à exprimer le parallélisme, ainsi que les approches utilisées pour paralléliser différents modèles d'évolution. Les versions parallèles des algorithmes d'évolution ont été développées et installées sur une « grappe » (i.e. cluster) Linux ayant 16 lames possédant chacune deux processeurs et sa propre mémoire. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : algorithmes d'évolution, arbre phylogénétique, réseau phylogénétique, transferts horizontaux de gènes, programmation parallèle, Message Passing Interface (MPI).

Nous nous sommes intéressés à la problématique de la communication au sein des systèmes multi-agents en nous inspirant de la nature et plus particulièrement des fourmis qui sont un parfait exemple de l'intégration de l'apprentissage du vivant (ontogenèse) au capital génétique de celui-ci (phylogénie) : l'effet Baldwin.<br />Nous avons choisi de travailler avec des systèmes de classeurs à algorithme génétique pour représenter les agents. Nous avons introduit un nouveau type de système de classeurs à base de connaissance de taille fixe, les systèmes de classeurs de type Pittsburgh simplifié, dont nous avons étudié les propriétés dans un contexte multi-agents de coordination spontanée.<br />Nous avons ensuite proposé avec succès aux agents "homogènes" de communiquer pour échanger leur "connaissance" à l'aide de l'élitisme distribué.<br />Enfin, les agents "hétérogènes" ont échangé efficacement des informations grâce à un modèle minimal de communication que nous avons ancré dans la réalité puis étendu.

Les systèmes de vélos en libre-service ont connu ces dernières années un développement sans précédent. Bien que les premières tentatives de mise en place remontent aux années 60, l'arrivée de technologies permettant un suivi des différents véhicules mis à la disposition du grand public et de l'état des bornes de stationnement en temps réel a rendu ces systèmes plus attractifs. Plus de 200 villes disposent de tels systèmes et cette tendance se poursuit avec l'entrée en fonctionnement du système de New York prévue pour l'été 2012. La fin de l'année 2011 a été marquée par l'arrivée d'un nouvel avatar de ce type de transport avec la mise en place d'Autolib à Paris. L'objectif de cette thèse est de proposer des algorithmes d'aide à la décision pour l'optimisation de réseaux de transport en libre-service. L'exploitation de ces systèmes, qui fleurissent actuellement un peu partout dans le monde, pose en effet de nombreux problèmes, l'un des plus cruciaux étant celui de la régulation. Cette dernière a pour objectif de maintenir dans chaque station un nombre de vélos ni trop faible, ni trop élevé, afin de satisfaire au mieux la demande. Cette régulation se fait souvent par le biais de camions qui effectuent des tournées sur le réseau. Il apparaît rapidement que la question d'une régulation optimale à l'aide d'une flotte fixée de camions est une question difficile. La thèse est divisée en deux parties. Dans la première partie, le cas "statique" est considéré. Les déplacements de véhicules dus aux usagers sont négligés. Cela traduit la situation la nuit ou lorsque le système est fermé à la location. L'opérateur doit redistribuer les véhicules afin que ceux-ci soient disposés selon une répartition définie. Les problèmes de rééquilibrage avec un ou plusieurs camions sont traités. Pour chacun des deux cas, un algorithme est proposé et utilisé pour résoudre des instances de tailles variées. La seconde partie traite du cas "dynamique" dans lequel les utilisateurs interagissent avec le système. Afin d'étudier ce système complexe, un simulateur a été développé. Il est utilisé pour comparer différentes stratégies de redistribution des véhicules. Certaines utilisent des camions se déplaçant dans la ville pendant la journée. D'autres tentent d'organiser une régulation intrinsèque du système par le biais d'une politique d'incitation : des prix mis à jour régulièrement encouragent les usagers à rendre leur véhicule dans certaines stations. Enfin, si on choisit de ne pas utiliser de camion durant la journée, la question de la détermination du nombre optimal de véhicules à disposer à chaque station se pose. Deux méthodes de recherche locale visant à minimiser le temps total perdu par les usagers sont présentées. Les résultats obtenus peuvent servir pour la définition des répartitions cibles de la première partie.

Longtemps considérée comme une curiosité de laboratoire, la distribution quantique de clés s'est aujourd'hui imposée comme une solution viable de sécurisation des données. Les lois fondamentales de la physique quantique permettent en effet de garantir la sécurité inconditionnelle des clés secrètes distribuées.<br /><br />Nous avons proposé un système de distribution quantique de clés par photons uniques exploitant un véritable codage en fréquence de l'information. Cette nouvelle méthode de codage permet de s'affranchir de dispositifs interférométriques et offre donc une grande robustesse. Un démonstrateur basé sur des composants optiques intégrés standard a été réalisé et a permis de valider expérimentalement le principe de codage. Nous avons ensuite étudié un système mettant en oeuvre un protocole de cryptographie quantique par « variables continues », codant l'information sur l'amplitude et la phase d'états cohérents. Le dispositif proposé est basé sur un multiplexage fréquentiel du signal porteur d'information et d'un oscillateur local. <br /><br />Les débits atteints par les systèmes de distribution de clés ne sont pas uniquement limités par des contraintes technologiques, mais aussi par l'efficacité des protocoles de réconciliation utilisés. Nous avons proposé un algorithme de réconciliation de variables continues efficace, basé sur des codes LDPC et permettant d'envisager de réelles distributions de clés à haut débit avec les protocoles à variables continues.

Les éboulements de terrain posent des problèmes importants pour la gestion des risques, à cause de leur soudaineté et de l'absence de signe précurseur. La détection d'un compartiment instable, l'évaluation de sa stabilité ainsi que la compréhension de la dynamique de sa propagation sont des éléments majeurs dans l'évaluation de l'aléa d'éboulement. En premier lieu, le géoradar a permis de mieux contraindre la géométrie 3D du réseau de fracture. Une stratégie d'inversion des caractéristiques des fractures (épaisseur et remplissage), basée sur la sensibilité fréquentielle et angulaire des réflexions des ondes électromagnétiques avec une approche de couche mince a été développé et appliqué de façon convaincante sur des données réelles acquises sur deux sites différents.<br /><br />La seconde partie est consacrée à l'exploitation des signaux sismiques enregistrés lors de douze éboulements différents. Une nouvelle échelle de magnitude a été définie, qui a permis de classer les différents événements. Aucune relation n'a été trouvée entre les paramètres géométriques (et l'énergie potentielle dérivée) et la magnitude. Par contre la durée du signal montre une bonne corrélation avec l'énergie potentielle. L'analyse détaillée des signaux suggère l'existence d'au moins deux sources sismiques, une correspondant à la rupture associée au rebond élastique induit par le détachement de la masse rocheuse et une autre générée par l'impact de la masse sur la pente, dont l'aspect fréquentiel a été confirmé par une analyse numérique 2D par la méthode des éléments finis.

La plupart des essais géotechniques in situ ne permettent pas d'identifier directement les paramètres constitutifs des couches de sol. L'utilisation de calculs par éléments finis pour dimensionner les ouvrages est ainsi limitée par une mauvaise connaissance des propriétés mécaniques des sols. C'est dans ce contexte que se pose la problématique d'analyse inverse en géotechnique : quelles informations concernant les paramètres constitutifs du sol est-il possible d'obtenir à partir de mesures in situ ? <br />L'objectif de ce travail est de développer une méthode d'analyse inverse permettant d'identifier l'ensemble des paramètres constitutifs d'un sol à partir de mesures géotechniques in situ. La procédure est basée sur un processus d'optimisation par algorithme génétique. L'ensemble des solutions identifiées sont ensuite décrites mathématiquement par une étude statistique de type analyse en composantes principales. Cette étude montre que ce type d'optimisation par algorithme génétique permet d'estimer différentes solutions approchées pour les problèmes inverses de géotechnique. Si toutes les solutions d'un problème ne sont pas identifiées directement par l'algorithme génétique, leur exploitation par une analyse en composantes principales permet d'estimer l'ensemble des solutions du problème inverse. Cette méthode est développée sur des exemples d'ouvrages de soutènement et d'essais pressiométriques.

Ce travail concerne les techniques d'identification ensembliste dites à erreur inconnue mais bornée. On s'est ici exclusivement intêressé à l'approche ensembliste ellipsoïdale. Dans ce contexte précis, nos contributions portent sur une évaluation réaliste de la borne, basée sur l'analyse du kurtosis du signal d'erreur. On propose également une approche unifiée des algorithmes conduisant à leur formulation numériquement stable, à la différence de la quasi-totalité des solutions publiées. L'analyse de la convergence de ce type de techniques fait intervenir la notion habituelle d'excitation persistante pour laquelle on donne une solution algorithmique permettant de qualifier l'entrée, et comment construire des entrées " optimales ". Enfin on s'est intêressé au compromis que l'on pouvait établir entre algorithme séquentiel sous optimal et une approche globale optimale mais numériquement inaccessible. L'ensemble de ces points est illustré tant en simulation qu'avec des données réelles provenant du monde industriel.

L'objectif de notre travail est la réalisation d'un système interactif d'aide aux déplacements, en mode normal, et en mode dégradé de fonctionnement du réseau de transport en commun. Ce système vise par ailleurs à minimiser le temps d'attente des voyageurs, en mode dégradé, dans les pôles d'échanges et à leur assurer, dans la mesure du possible, la continuité des déplacements dans les réseaux multimodaux. Il s'agit donc d'améliorer la qualité du service rendu aux voyageurs et les maintenir informés. Une grande partie du travail de cette thèse concerne la conception, le développement et la validation des approches qui permettent de donner des solutions optimales ou quasi optimales, pour un réseau de transport normal et perturbé. Ces approches utilisent une méthode multicritère de recherche d'itinéraire qui s'appuie sur une hybridation entre un algorithme de Dijkstra modifié et un algorithme génétique, pour générer une population de chemins minimums . L'algorithme de Dijkstra modifié nous donne un ensemble de solutions servant de population initiale pour l'algorithme génétique.<br />La modélisation du réseau de transport est représentée par une architecture multi-zones . Cette architecture nous montre l'aspect distribué du système, les interactions et les relations qui peuvent avoir lieu entre les différenttes zones. Nous présentons dans ce travail un Système Multi-Agent d'Aide au Déplacement, SMAAD. Les agents de ce système utilisent le module d'optimisation développé dans la première partie. Notre travail est réalisé dans le cadre du projet « VIATIC-MOBILITE », qui est le projet 6 du pôle de compétitivité I-Trans.

La première partie de la thèse concerne le calcul numérique des ondes de gravité en 3D. Le modèle résout les équations d'Euler incompressibles avec surface libre pour un écoulement potentiel. L'association de l'Algorithme des Multipôles Rapides avec la Méthode des Eléments aux Frontières permet d'améliorer significativement l'efficacité du modèle. Deux applications sont alors considérées : le déferlement d'une onde solitaire sur un fond tridimensionnel et la focalisation spatiale générée par un batteur à houle. Dans la seconde partie, une étude plus en amont est effectuée dans le contexte des ondes internes en deux dimensions. A l'aide d'un système de type Korteweg de Vries, des ondes solitaires généralisées sont discutées dans le cas où la vitesse approche la valeur critique correspondant à l'apparition des fronts. Ces solutions résultent de la résonance entre une onde solitaire large ayant une amplitude limite et une onde courte, qui se propagent à la même vitesse de phase.

La thématique principale de cette thèse est la construction et l'étude de méthodes implémentables par ordinateur permettant d'approcher le régime stationnaire d'un processus ergordique multidimensionnel solution d'une EDS dirigée par un processus de Lévy. S'appuyant sur une approche développée par Lamberton&Pagès puis Lemaire dans le cadre des diffusions Browniennes, nos méthodes basées sur des schémas <br />d'Euler à pas décroissant, « exacts » ou « approchés », permettent de simuler efficacement la probabilité invariante mais également la loi globale d'un tel processus en régime stationnaire. <br />Ce travail possède des applications théoriques et pratiques diverses dont certaines <br />sont développées ici (TCL p.s. pour les lois stables, théorème limite relatif aux valeurs extrêmes, pricing d'options pour des modèles à volatilité stochastique stationnaire...).