Ce manuscrit de thèse développe certains aspects autour de trois thèmes généraux, sur la représentation arborescente des familles d'ensembles, les décompositions de graphes, et les algorithmes de graphes. Les thèmes abordés vont de la combinatoire théorique à l'algorithmique en bio-informatique, en passant par plusieurs décompositions de graphes et aussi par l'optimisation combinatoire.<br /><br />La première moitié du manuscrit développe deux études. D'abord, afin d'estimer le nombre de familles d'ensembles satisfaisant certains axiomes de clôture, de nouveaux outils et techniques pour obtenir des représentations arborescentes de celles-ci ont été développés. Puis, l'étude se poursuit avec une des applications des propriétés ci-dessus : celle concernant les décompositions de graphes.<br /><br />La deuxième moitié du manuscrit est consacrée aux applications des décompositions de graphes dans l'algorithmique de graphes. Trois problèmes algorithmiques seront à l'étude.<br />Dans chacun des trois, il est montré pourquoi et comment on peut appliquer l'idée de la décomposition de graphes pour résoudre le problème posé de manière efficace.<br />Il est également montré comment appliquer les trois solutions proposées pour résoudre trois autres problèmes d'algorithmique de graphes.

Avec l'émergence de l'informatique dans les nuages, une nouvelle approche consiste à externaliser des tâches de calcul, de façon à réduire les coûts d'hébergement et à augmenter la flexibilité des systèmes. L'infrastructure actuelle des services permettant cette externalisation repose sur l'utilisation de centres de traitement de données centralisés, qui sont dédiés à l'approvisionnement de ressources de calcul. Dans cette thèse, nous étudions la possibilité de fournir de tels services en utilisant une infrastructure pair-à-pair, c'est-à-dire une infrastructure totalement décentralisée pouvant être déployée sur une fédération de noeuds de calcul hétérogénes et de provenances diverses. Nous nous focalisons sur le problème de l'allocation des noeuds et présentons Salute, un service d'allocation de noeuds, qui organise les noeuds en réseaux virtuels non-structurés et repose sur des mécanismes de prédiction de disponibilité pour assurer, avec une grande probabilité, que les requêtes d'allocation sont satisfaites dans le temps, malgré le dynamisme de l'environnement hôte. Pour ce faire, le service Salute repose sur la collaboration de plusieurs protocoles pair-à-pair appartenant à la catégorie des protocoles épidémiques. Afin de valider nos propositions, nous évaluons Salute en utilisant des traces provenant d'un échantillonnage de plusieurs systèmes pair-à-pair de référence.

Dans cette thèse, nous nous sommes intéressés à l 'étude d'un micro-robot destiné à la mise en oeuvre d'une technique de chirurgie mini-invasive pour le traitement des anévrismes de l'artère aorte abdominale. Ce micro-robot placé à l'extrémité d'un cathéter, rendant ce dernier actif, permettra la navigation à l'intérieur de l'artère en évitant les contacts avec les parois de celle-ci. Le système sera destiné à l'apprentissage du geste chirurgical et à l'assistance du chirurgienpendant l'opération. De par sa structure et ses propriétés physiques, le micro-robot, pouvantêtre composé de plusieurs modules élémentaires, entre dans la catégorie des robots continuum. Dans notre étude, un module élémentaire est considéré comme étant un robot parallèle. Lesmodèles géométriques et cinématiques inverses ont alors été établis en utilisant les techniques dela robotique parallèle. L'approche de modélisation proposée permet de faire ressortir explicitement du modèle les paramètres géométriques du micro-robot. Une étude sur l'identificationde ces paramètres a été effectuée par le calibrage du modèle géométrique inverse. Des résultatsde simulation sont présentés validant d'une part les modèles développés et d'autre part la méthode de calibrage proposée. Afin de mettre nos modèles en situation, nous avons développé unsimulateur tridimensionnel intégrant le modèle d'un segment de l'artère, le modèle du micro-robotet un syntaxeur à retour de force. La mise en place d'une navigation active, planifiée etguidée dans ce simulateur permet de contraindre les gestes du chirurgien lors de la navigation du micro-robot à l'intérieur de l'artère

La compréhension et l'étude du système nerveux est un des grands enjeux du XXIème siècle à la fois pour la recherche fondamentale, mais également pour la mise au point de neuroprothèses implantables pour la réhabilitation fonctionnelle (exemple : implants rétiniens, implants cochléaires). Depuis quelques années, des systèmes basés sur l'utilisation de multi-électrodes (MEA : Multi-Electrode-Array) offrent la possibilité d'enregistrer des milliers de cellules interconnectées entre-elles sur plusieurs jours sur des tranches de tissu nerveux ou des systèmes nerveux complets. Mais une des limites de cette technique est le faible nombre de voies de ces systèmes (64 voies). Les travaux de cette thèse ont consisté à développer une technologie de fabrication permettant la réalisation d'un système multiélectrode s " haute densité 3D ". Cela passe par le développement d'une nouvelle technologie dans la réalisation de micro pointes basée sur la gravure profonde du silicium (DRIE), qui permet d'obtenir des pointes en silicium de 80 µm de haut espacées de 50 µm. Des matrices 60, 256 et 1024 voies ont été fabriquées par cette technique. L'utilisation de la stimulation est aussi un point important dans l'étude de ces grands réseaux, mais il n'est pas possible actuellement de disposer de système permettant une stimulation focale. Pour résoudre ce problème, nous avons développé des matrices spécifiques permettant d'obtenir des stimulations focales du tissu. Nous avons également dans ces travaux de thèse étudié le comportement de l'interface métal/liquide, qui est cruciale pour la réalisation de MEA, en utilisant des techniques d'électrochimie

Cette thèse décrit la conception d'un système de dialogue Homme- Machine pour la recherche d'informations capable d'interagir avec l'utilisateur en langue naturelle en utilisant des stratégies coopératives. Pour étudier les processus dialogiques impliqués dans la recherche d'informations, une méthodologie ascendante a été adoptée. Une série d'expérimentations a permis le recueil de corpus de dialogues humains présentant de telles recherches dans le cadre du système de documentation médicale CISMeF. L'analyse des dialogues recueillis a montré que leur structure correspond bien aux structures sémantiques de l'approche " questionsréponses ". Fondé sur un modèle existant nommé GoDIS, notre système y intègre de nombreux ajouts permettant d'améliorer la cohérence du dialogue et de proposer des exemples, des choix, des assistances. Une implémentation de ce modèle est réalisée et des pistes d'évaluation sont proposées.

Cette thèse s'inscrit dans le contexte de la vision embarquée pour la détection et la reconnaissance d'obstacles routiers, en vue d'application d'assistance à la conduite automobile.A l'issue d'une étude bibliographique, nous avons constaté que la problématique de détection d'obstacles routiers, notamment des piétons, à l'aide d'une caméra embarquée, ne peut être résolue convenablement sans recourir aux techniques de reconnaissance de catégories d'objets dans les images. Ainsi, une étude complète du processus de la reconnaissance est réalisée, couvrant les techniques de représentation,de classification et de fusion d'informations. Les contributions de cette thèse se déclinent principalement autour de ces trois axes.Notre première contribution concerne la conception d'un modèle d'apparence locale basée sur un ensemble de descripteurs locaux SURF (Speeded Up RobustFeatures) représentés dans un Vocabulaire Visuel Hiérarchique. Bien que ce modèle soit robuste aux larges variations d'apparences et de formes intra-classe, il nécessite d'être couplé à une technique de classification permettant de discriminer et de catégoriser précisément les objets routiers. Une deuxième contribution présentée dans la thèse porte sur la combinaison du Vocabulaire Visuel Hiérarchique avec un classifieur SVM.Notre troisième contribution concerne l'étude de l'apport d'un module de fusion multimodale permettant d'envisager la combinaison des images visibles et infrarouges.Cette étude met en évidence de façon expérimentale la complémentarité des caractéristiques locales et globales ainsi que la modalité visible et celle infrarouge.Pour réduire la complexité du système, une stratégie de classification à deux niveaux de décision a été proposée. Cette stratégie est basée sur la théorie des fonctions de croyance et permet d'accélérer grandement le temps de prise de décision.Une dernière contribution est une synthèse des précédentes : nous mettons à profit les résultats d'expérimentations et nous intégrons les éléments développés dans un système de détection et de suivi de piétons en infrarouge-lointain. Ce système a été validé sur différentes bases d'images et séquences routières en milieu urbain.

La mise en correspondance sémantique appliquée à des schémas hétérogènes dans les systèmes de partage de données est une tache fastidieuse et source d'erreurs. La thèse présente une nouvelle méthode automatique et robuste qui intègre un grand nombre de schémas sous forme arborescente et de domaine spécifique. Elle permet de découvrir des correspondances sémantiques entre eux. La méthode crée également les mappings entre des schémas sources et le schéma intégré. Puis, le manuscrit présente une technique pour découvrir d'une manière automatique des correspondances complexes entre deux schémas. <br /><br />Les outils de mise en correspondance existants utilisent des techniques semi-automatiques uniquement entre deux schémas. Dans un scénario à grande échelle, où le partage des données implique un grand nombre de sources de données, ces techniques ne sont pas adaptées. De plus, la mise en correspondance semi-automatique nécessite l'intervention de l'utilisateur pour finaliser les mappings. Bien qu'elle offre la possibilité de découvrir les mappings les plus appropriés, les performances s'en trouvent fortement dégradées. Dans un premier temps, le manuscrit présente en détails l'état de l'art sur la mise en correspondance. Nous expliquons les inconvénients des outils actuellement disponibles pour répondre aux contraintes d'un scénario à grande échelle. Notre approche, PORSCHE (Performance ORiented SCHEma mediation) évite ces inconvénients et ses avantages sont mis en évidence de manière empirique.<br /><br />Le principe de l'algorithme de PORSCHE consiste à regrouper d'abord les nœuds de l'arbre selon la similarité linguistique de leurs labels. Ensuite, des techniques de fouilles d'arbres utilisant les rangs des nœuds calculés au moyen du parcours en profondeur de l'arbre sont appliquées. Cela réduit l'espace de recherche d'un nœud cible et améliore par conséquent les performances, ce qui en fait une technique adaptée au contexte large échelle. PORSCHE implémente une approche hybride, qui crée également en parallèle et de manière incrémentale un schéma intégré qui englobe tous les schémas, tout en définissant les correspondances entre ces derniers et le schéma intégré. L'approche découvre des correspondances 1:1 dans un but d'intégration et de médiation. Finalement, des expérimentations sur des jeux de données réels et synthétiques montrent que PORSCHE passe à l'échelle avec de scénarios de grande échelle. La qualité des correspondances découvertes et l'intégrité du schéma intégré sont également vérifiées par une évaluation empirique.<br /><br />Par ailleurs, nous présentons une technique CMPV ({\bf C}omplex {\bf M}atch {\bf P}roposition et {\bf V}alidation), pour la découverte de correspondances complexes (1:n, n:1 et n:m), entre deux schémas, validée par l'utilisation de mini-taxonomies. Cette partie est une version étendue de l'aspect de mise en correspondance de PORSCHE. Les mini-taxonomies sont extraites d'un vaste ensemble de métadonnées de domaine spécifique représenté comme des structures arborescentes. Nous proposons un cadre, appelé ExSTax ({\bf Ex}tracting {\bf S}tructurally Coherent Mini-{\bf Tax}onomies) basé sur la fouille d'arbres pour appuyer notre idée. C'est l'extension de la méthode fouille d'arbres de PORSCHE. Enfin, on utilise la technique ExSTax pour extraire une taxonomie fiable spécifique à un domaine.

La sécurité des systèmes informatiques répartis est un problème de plus en plus important, en particulier avec l'utilisation massive du réseau Internet. Il est donc essentiel de pouvoir imaginer des techniques de protection efficaces de nos systèmes et de nos réseaux. Ces travaux proposent une contribution à la protection des systèmes informatiques vis-a-vis des malveillances, en abordant le problème sous deux angles : un angle architectural et un angle expérimental. L'angle architectural concerne la conception d'architectures de sécurité permettant de faire face aux menaces actuelles, en proposant plusieurs approches suivies dans la cadre de différentes thèses. L'angle expérimental se focalise sur des techniques permettant d'améliorer notre connaissance des attaquants et des processus d'attaques, en particulier, les processus qui utilisent le réseau Internet comme support.

Dans cette thèse nous nous sommes intéressés à l'extension du problème job-shop en ajoutant la contrainte du transport des jobs entre les différentes machines. Dans cette étude nous avons retenu l'existence de deux types de robots, les robots de capacité de chargement unitaire (capacité=1 veut dire qu'un robot ne peut transporter qu'un seul job à la fois) et les robots de capacité de chargement non unitaire (capacité>1 veut dire qu'un robot peut transporter plusieurs job à la fois). Nous avons traité cette extension en deux étapes. Ainsi, la première étape est consacrée au problème du job-shop avec plusieurs robots de capacité de chargement unitaire et en seconde étape en ajoutant la capacité de chargement non unitaire aux robots. Pour les deux problèmes étudiés nous avons proposé :* Une modélisation linéaire ;* Une modélisation sous forme de graphe disjonctif ;* Plusieurs heuristiques de construction de solutions ;* Plusieurs recherches locales qui améliorent les solutions obtenues ;* Utilisation des algorithmes génétiques / mémétiques comme schéma global d'optimisation ;* De nouveaux benchmarks, des résultats de test de nos approches sur nos benchmarks et ceux de la littérature et ces résultats sont commentés et comparés à ceux de la littérature. Les résultats obtenus montrent la pertinence de notre modélisation ainsi que sa qualité.

Le développement des systèmes de communication et de localisation et les progrès des dispositifs mobiles rendent possible la mise en œuvre de nouvelles applications et services, permettant l'accès à des informations temps réel et l'amélioration de l'intégration des personnes aveugles. Dans ce contexte, la thèse a contribué au développement d'un système d'information et de guidage destiné aux personnes aveugles dans les transports en commun. La thèse a porté sur deux aspects critiques de ce type de systèmes: la fiabilité de la transmission de données et la capacité à localiser et à guider l'utilisateur de manière robuste. Elle a d'autre part développé un environnement de simulation pour le prototypage et l'analyse du fonctionnement de l'application nomade ainsi que l'étude des aspects réseaux de communication mobile. Les travaux se sont appuyés sur les acquis des projets RAMPE et INFOMOVILLE