Un des challenges actuels de la planification est la résolution de problèmes pour lesquels on cherche à optimiser la qualité d'une solution telle que le coût d'un plan-solution. Dans cette thèse, nous développons une méthode originale pour la planification de coût optimal dans un cadre classique non temporel et avec des actions valuées.<br /><br />Pour cela, nous utilisons une structure de longueur fixée appelée graphe de planification. L'extraction d'une solution optimale, à partir de ce graphe, est codée comme un problème de satisfaction de contraintes pondérées (WCSP). La structure spécifique des WCSP obtenus permet aux solveurs actuels de trouver, pour une longueur donnée, une solution optimale dans un graphe de planification contenant plusieurs centaines de nœuds. <br /><br />Nous présentons ensuite plusieurs méthodes pour déterminer la longueur maximale des graphes de planification nécessaire pour garantir l'obtention d'une solution de coût optimal. Ces méthodes incluent plusieurs notions universelles comme par exemple la notion d'ensembles d'actions indispensables pour lesquels toutes les solutions contiennent au moins une action de l'ensemble. <br /><br />Les résultats expérimentaux effectués montrent que l'utilisation de ces méthodes permet une diminution de 60% en moyenne de la longueur requise pour garantir l'obtention d'une solution de coût optimal. La comparaison expérimentale avec d'autres planificateurs montre que l'utilisation du graphe de planification et des CSP pondérés pour la planification optimale est possible en pratique même si elle n'est pas compétitive, en terme de temps de calcul, avec les planificateurs optimaux récents.

Cette thèse présente l'étude et l'implantation de deux méthodes pour le placement automatique de circuits intégrés. Un circuit intégré peut être considéré comme un ensemble de blocs et une liste d'interconnexions entre ces blocs. Le probleme du placement consiste a disposer les blocs sur la surface hôte en respectant diverses contraintes et en optimisant des critères comme la surface occupée et la longueur totale de connexions. Les méthodes présentées ici sont toutes les deux guidées par l'optimisation de la connectique. La première fait appel a une technique d'analyse de données, l'analyse d'un tableau de proximités. Dans un premier temps, des proximités sont definies entre les blocs de façon a refléter un agencement ideal en fonction de la connectique. L'utilisation de l'atp permet alors d'obtenir une disposition planaire des blocs respectant au mieux les proximités qui ont été définies. L'analyse effectuée fait le point sur les diverses façons de définir les proximités entre les blocs, ainsi que sur les traitements ultérieurs destines a l'obtention d'un placement réalisable. Les qualités et les limitations de cette approche sont ensuite discutées. La seconde methode est connue sous le nom de placement par bipartitionnements successifs. L'ensemble des blocs du circuit et la surface hôte sont ainsi bipartitionnes récursivement jusqu'à ce que l'emplacement de chaque bloc soit déterminé. A partir des algorithmes existants, des heuristiques ont été mises au point afin de permettre la prise en compte de contraintes supplémentaires comme le traitement des plots d'entrées-sorties ou des blocs pré-fixes. L'expérimentation a permis de valider ces heuristiques et de comparer les résultats du placement a ceux fournis par la première methode

Ce travail traite la problématique de la Modélisation 3D d'un environnement intérieur supposé inconnu par un robot mobile. Notre principale contribution concerne la construction d'un modèle géométrique dense représenté par une carte hétérogène qui combine des amers plans texturés, des lignes 3D et des points d'intérêt. Afin de réaliser cette tâche, nous devons fusionner des données géométriques et photométriques. Pour cela, nous avons d'abord amélioré la stéréovision dense, en proposant une approche qui transforme le problème de la mise en correspondance stéréoscopique en un problème de minimisation d'une fonction d'énergie globale. Le minimum de cette fonction est trouvé par une coupure minimale dans un graphe. Notre contribution réside dans la construction d'un graphe réduit qui a permis d'accélérer considérablement cette méthode globale de l'appariement stéréoscopique et d'obtenir de meilleurs résultats que les méthodes locales. Néanmoins, cette méthode reste non applicable en robotique mobile. Aussi, pour percevoir l'environnement, le robot est équipé d'un télémètre laser pivotant autour d'un axe horizontal et d'une caméra. Nous proposons une chaîne algorithmique permettant de construire de manière incrémentale une carte hétérogène, par l'algorithme de Cartographie et Localisation Simultanées basé sur le filtre de Kalman étendu (EKF-SLAM). Le placage de la texture sur les facettes planes rend le modèle plus réaliste pour un opérateur ; il a permis aussi de solidifier l'étape d'association de données, une étape essentielle pour garantir la cohérence de la carte. Les différents mécanismes développés sont illustrés et validés par des résultats expérimentaux.

Parallélisation de quelques algorithmes d'algèbre linéaire à l'aide du formalisme du graphe des taches

.

Cette thèse vise à questionner le processus de médiation sémiotique mis en place lors de l'utilisation de un artefact technologique, dans des séquences d'enseignement qui ont pour objectif l'apprentissage des notions de variable, fonction et graphe de fonction. <br />Elle se développe selon trois axes de recherche principaux : <br />I. la conception de séquences d'activités en partant du cadre inhabituel de la géométrie dynamique, rendu possible par l'environnement Cabri-géomètre. En offrant une modélisation des objets géométriques en tant qu'objets variables, ce cadre peut conduire à une appréhension dynamique et co- variationnelle des notions visées. <br />II. La réflexion théorique sur l'articulation possible entre les deux cadres théoriques qui ont guidé la conception des séquences : inspirée par Vygotskij et particulièrement développé en Italie et celui de la « Théorie des situations didactiques » élaborée en France par Brousseau. <br />III. L'analyse du rôle de l'enseignant dans le processus de médiation sémiotique lors de l'orchestration de discussions collectives. En fait, à l'intérieur du processus de médiation sémiotique, l'enseignant occupe une place critique et cruciale. Par la proposition de tâches spécifiques, il organise l'accès aux signes et, par une orchestration adéquate des discussions collectives, il soutient leur internalisation éventuelle de la part des élèves.

Des mesures de l'activité du cerveau humain peuvent être obtenues par diverses techniques d'imagerie neuro-fonctionnelle. Dans le domaine des neurosciences, les études menées grâce à ces nouvelles techniques sont appelées études d'activation. Elles mettent en évidence l'organisation en réseau des aires cérébrales mises en jeux lors de la réalisation de tâches cognitives particulières. La complexité du traitement de l'information cérébrale et l'incomplétude de l'observation rendent difficile l'interprétation de ce fonctionnement et rendent nécessaire la construction d'un outil de modélisation et de simulation. La nécessité de comprendre l'organisation fonctionnelle du cerveau humain, nous impose en plus de recourir à des formalismes permettant d'en avoir une représentation explicite. Dans cette optique, nous proposons un formalisme original, basé sur des graphes d'influences causales et une représentation qualitative de l'information. Les graphes d'influences sont tout à fait appropriés à la représentation de la double organisation du cerveau, en réseaux anatomiques (structurels) et fonctionnels. L'originalité de notre approche est double. D'une part, nous proposons une architecture hiérarchique fondée sur la notion de composant et qui permet de réduire la complexité des modèles tout en augmentant leur réutilisabilité. D'autre part, nous utilisons un formalisme unique pour décrire les niveaux structurels et fonctionnels cérébraux. La modélisation explicite de l'information cérébrale nous a conduit à proposer une représentation qualitative mixte, sous la forme de couples (intervalle, symbole). Ceci permet à la fois de prendre en compte l'amplitude de cette information, bruitée par les techniques d'imagerie, et sa catégorie. Nous proposons le simulateur BIOCAEN, fondé sur le formalisme ci-dessus. La simulation consiste en la propagation des influences à chaque instant d'une horloge discrète. Ce mécanisme permet de prendre en compte les processus automatiques qui constituent la majeure partie du fonctionnement cérébral. La contribution de notre travail à l'exploration du fonctionnement du cerveau humain réside dans la mise à disposition des chercheurs en neurosciences, d'un formalisme permettant d'exprimer explicitement, à un haut niveau d'abstraction, les hypothèses sur la propagation de l'information cérébrale et d'un simulateur permettant de les mettre en œuvre. Les hypothèses sont décrites dans des modèles où l'architecture causale offre un support à l'expression des réseaux anatomiques d'aires cérébrales, chacune d'entre elles étant représentée par un sous-réseau fonctionnel de processeurs d'information. La validation des hypothèses est réalisée par la confrontation des résultats de la simulation du modèle par BIOCAEN aux données de l'imagerie neuro-fonctionnelle.

Notre étude porte sur les transporteurs ABC dans les génomes bactériens complets. L'analyse bioinformatique du répertoire de ces systèmes comprend l'identification des partenaires, l'assemblage, la reconstruction des systèmes incomplets, la classification en sous-familles, et l'identification du substrat transporté. Cette thèse propose des outils permettant l'étude de ces problèmes par l'utilisation de méthodes informatiques. Les hypothèses biologiques employées sont que : (i) des gènes voisins sur le chromosome peuvent être impliqués dans un même processus métabolique s'ils ont été conservés au cours de l'évolution, et (ii) des gènes présentant des similarités de séquence peuvent permettre la synthèse de protéines de même fonction. Trois études ont été menées sur le répertoire des transporteurs ABC : * L'exploration du voisinage chromosomique. D'après l'hypothèse selon laquelle plus les gènes conservés dans le voisinage d'un transporteur sont proches, plus leur lien fonctionnel avec le transporteur est fort, on essaye d'identifier le substrat transporté ou des associations de gènes. Ce problème est traité par une méthode de résolution issue des problèmes de satisfaction de contraintes. * La classification. Les transporteurs ABC sont classés par grandes catégories en fonction des molécules qu'ils transportent (sucres, ...). Pour chaque domaine, en représentant les relations d'homologie par un graphe, la recherche des zones de forte densité permet de déterminer des sous-classes de substrat. * La reconstitution des systèmes incomplets. Les transporteurs ABC sont assemblés en utilisant la proximité chromosomique des gènes codant pour les domaines et la compatibilité des sous-familles de domaines. Lorsque la proximité n'est pas respectée, on utilise une stratégie développée à partir d'une méthode d'analyse de graphes pour assembler les domaines et prédire des systèmes actifs. Ces méthodes, en complément de l'identification des partenaires et de l'assemblage, permettent une étude fonctionnelle des transporteurs ABC. Elles pourraient être appliquées à d'autres systèmes biologiques.

Le contexte général de ce travail est l'étude du comportement d'applications parallèles, représentées par un graphe de précédence. La programmation de telles applications dépend fortement des supports d'exécution. Nous présentons et discutons les principaux modèles d'exécution et leur influence sur les problèmes d'ordonnancement des tâches du programme parallèle. Nous étudions en détail quatre problèmes d'ordonnancement sur des modèles d'exécution où le coût de communication est pris en compte. Nous proposons une solution pour un problème à grain très fin, le problème du sac à dos, sur hypercube dans un modèle d'exécution synchrone où le coût de communication est implicite. Nous étudions l'ordonnancement de chaînes sur un modèle à gros grain de communication, le modèle BSP. Nous démontrons qu'ici la recherche d'un ordonnancement optimal est un problème NP-difficile. Nous proposons des solutions avec un compromis entre le nombre de phases de communication/synchronisation et le temps d'inactivité dans chaque processeur. Les deux derniers problèmes étudiés concernent des techniques qui permettent de réduire l'impact du coût des communications inter processeurs. La première technique considère la duplication des tâches. Nous proposons un algorithme de liste avec garantie de performance 2 pour les problèmes à petit temps de communication sur un nombre limité de processeurs. Le deuxième méthode consiste à optimiser les phases de communication en ordonnançant les transmissions de messages. La recherche de la solution optimale étant NP-difficile, nous proposons plusieurs heuristiques.

Les réseaux ad hoc sont des réseaux distribués, auto-organisés ne nécessitant pas d'infrastructure. Les entités formant un tel réseau doivent collaborer afin d'assurer le bon fonctionnement des services réseaux, tel que le routage. Dans un tel environnement, de nombreux algorithmes développés pour le monde filaire ne peuvent être adaptés de façon naïve sans entraîner une congestion importante du réseau qui va réduire son efficacité. Notre travail de thèse se penche sur l'étude de la gestion de services. En effet, sans application, le développement d'une architecture comme les réseaux ad hoc est inutile. La gestion de services consiste à fournir tout les moyens possibles pour faciliter et rendre fiable l'utilisation d'applications distribuées. Nos travaux contribuent à l'étude de deux points précis de la gestion de services. Premièrement, nous fournissons un algorithme permettant de répartir efficacement une information dans le réseau en sélectionnant certains objets du réseau pour être des réplicats de l'information. Cet algorithme peut alors être utilisé pour publier les informations relatives à un service afin de permettre sa recherche. Deuxièmement, nous avons étudié la prédiction de déconnexion entrainée par la mobilité des noeuds. Nous proposons trois solutions basées sur la recherche d'ensemble de chemins disjoints, la recherche de liens critiques et la recherche de noeuds critiques. Les recherches que nous proposons sont entièrement réalisées à partir d'informations locales. Les résultats obtenus fournissent une base au développement d'un gestionnaire de services distribués. De plus, certains de nos algorithmes (comme la recherche d'ensembles de chemins disjoints) peuvent être réutilisés dans d'autres applications, comme le routage QoS multi-chemins.