Dans ce mémoire, nous étudions les méthodes itératives de recherche dans le cadre de la résolution du problème d'ordonnancement de type jobshop<br /><br />Plus que les performances en elles-mêmes, nous nous intéressons tout particulièrement à la compréhension du fonctionnement des méthodes de résolution ainsi qu'à l'analyse de l'influence de la coopération de plusieurs méthodes de recherche sur la qualité des solutions engendrées.<br /> <br />Dans un premier temps, nous évaluons l'apport de critères secondaires intégrés dans la fonction coût. Nous utilisons des algorithmes itératifs de recherche pour étudier l'impact de l'intégration de ces critères sur le paysage adaptatif ainsi que sur la qualité des ordonnancements engendrés.<br /><br />Nous proposons ensuite quelques améliorations du schéma d'application des opérateurs dans les algorithmes génétiques. <br /><br />Finalement, nous étudions quelques modèles d'hybridation des méta-heuristiques basés sur la recherche tabou et les algorithmes évolutifs.

Ce travail de thèse porte sur la simulation interactive du comportement mécanique de corps biologiques. Nous nous sommes intéressés à la modélisation de deux aspects de la mécanique des tissus biologiques: les déformations et les ruptures. Pour aborder la modélisation des déformations, nous nous appuyons sur une étude bibliographique de la mécanique des milieux continus et des modèles déformables développés en informatique. Nous proposons ensuite un modèle volumique du foie humain de type masses-connecteurs. Ce modèle présente un comportement dynamique hétérogène et non-linéaire, conformément à la réalité. L'hétérogénéité du modèle du foie est obtenue en paramétrant la viscosité des connecteurs de façon différente pour ceux de la surface du modèle (capsule de Glisson) et ceux de son intérieur (parenchyme). Son caractère non-linéaire est modélisé par des connecteurs répondant à une loi de comportement polynomiale de degré trois. Le modèle du foie humain peut être manipulé de façon interactive à l'aide d'un dispositif à retour d'efforts. Nous proposons ensuite une approche pour modéliser en temps-réel les changements de topologie, c'est-à-dire la rupture ou la découpe de modèles déformables. Notre méthode permet de borner l'augmentation de la complexité des modèles dont la topologie est modifiée, augmentation qui est due aux opérations de remaillage. Pour cela, au lieu de "détruire" des primitives de simulation ou de les "subdiviser", comme cela est proposé dans la littérature, notre approche les "sépare" les unes des autres. Les algorithmes de changement de topologie proposés et implantés offrent une méthode générique pour simuler la rupture et la découpe de corps surfaciques, de façon interactive.

Les nouveaux supports d'exécution que sont les grilles de processeurs<br />apparaissent aujourd'hui comme une alternative économiquement viable aux grands systèmes de calcul centralisés. De grands projets nationaux comme GRID5000 sont basés sur ce concept de machines réparties. Ce changement du paysage du calcul parallèle haute performance a créé une nouvelle demande d'algorithmes spécifiques pour tirer le meilleur parti des ressources déployées. Pour concevoir ces algorithmes et démontrer leur efficacité, il faut s'appuyer sur des modèles qui tentent de décrire fidèlement le comportement réel des machines tout en restant suffisamment simples à manipuler. Dans cette thèse, nous avons étudié deux modèles parmi les plus importants pour ces nouveaux supports et nous avons fourni des algorithmes polynomiaux optimaux, des algorithmes d'approximations garantis, ou des preuves de NP-complètudes le cas échéant.

Cette thèse s'intéresse aux annotations produites par des apprenants sur des documents électroniques. Les annotations sont utiles tant pour mémoriser une démarche de compréhension que pour retrouver facilement des informations. Nous remarquons que l'annotation électronique est peu pratiquée en raison des inconforts de lecture et d'annotation. De plus les annotations sont porteuses d'une sémantique implicite, perdue lors des réutilisations, comme par exemple des liens entre couleur et objectif de l'annotation. Dans ce contexte, notre objectif est de proposer des formalismes et des outils efficaces pour l'annotation électronique de ressources pédagogiques par des apprenants. Cette efficacité signifie que les dispositifs doivent être adaptés aux niveaux logiciel et matériel, qu'ils anticipent les réutilisations pour éviter l'impression systématique des documents, et qu'ils offrent les avantages d'un traitement informatisé. Elle signifie également que les annotations doivent être conservées dans leur intégralité : il est donc nécessaire d'expliciter leur sémantique tant au niveau d'une représentation formelle qu'au niveau d'un annoteur.<br />Plus précisément, notre travail comporte une proposition de représentation formelle de l'annotation, que nous implantons et testons lors d'expérimentations écologiques. En résultat, nous produisons une spécification d'annoteur efficace basé sur les métaphores du papier et de la trousse : le lecteur conserve ses habitudes papier lors de la lecture et de la création et il bénéficie des avantages d'un traitement informatisé pour la valuation, la recherche et le partage.

L'étude des grands réseaux d'interactions, ou réseaux rencontrés dans des contextes pratiques, vise à expliquer les interactions entre les différents individus d'un réseau par l'étude des grandes lois le gouvernant et à comprendre les divers phénomènes pouvant se produire sur ces réseaux. Cette thèse, divisée en trois parties, est consacrée à l'étude de ces réseaux.<br />La première partie est centrée sur l'analyse des réseaux et fait un point critique sur les réseaux étudiés et les paramètres introduits pour mieux comprendre leur structure. Un certain nombre de ces paramètres sont partagés par la majorité des réseaux étudiés et justifient l'étude de ceux-ci de manière globale.<br />La seconde partie qui constitue le coeur de cette thèse s'attache à la modélisation des grands réseaux d'interactions, c'est-à-dire la construction de graphes artificiels semblables à ceux rencontrés en pratique. Ceci passe tout d'abord par la présentation des modèles existants puis par l'introduction d'un modèle basé sur certaines propriétés non triviales qui est suffisamment simple pour que l'on puisse l'étudier formellement ses propriétés et malgré tout réaliste.<br />Enfin, la troisième partie est purement méthodologique. Elle permet de présenter la mise en pratique des parties précédentes et l'apport qui en découle en se basant sur trois cas particuliers : une étude des échanges dans un réseau pair-à-pair, une étude de la robustesse des réseaux aux pannes et aux attaques et enfin un ensemble de simulations visant à estimer la qualité des cartes de l'Internet actuellement utilisées.<br />Cette thèse met en lumière la nécessité de poursuivre les travaux sur les grands réseaux d'interactions et pointe plusieurs pistes prometteuses, notamment sur l'étude plus fine des réseaux, que ce soit de manière pondérée ou dynamique. Mais aussi sur la nécessité d'étudier de nombreux problèmes liés à la métrologie des réseaux pour réussir à capturer leur structure de manière plus précise.

Cette thèse aborde le problème de la résolution des problèmes combinatoires à l'aide d'algorithmes génétiques. Ce type d'algorithme présente en effet nombres d'avantages. Cependant, ils sont généralement relativement lents. Cette thèse est donc centrée sur les algorithmes hybrides, c'est-à-dire des algorithmes construits à l'aide de plusieurs méthodes différentes. Dans notre cas, nous étudions les algorithmes qui réunissent algorithmes génétiques et heuristiques. Il existe deux méthodes pour générer de tels algorithmes qui sont la représentation directe et la représentation indirecte. Ces deux méthodes sont étudiés au travers de trois problèmes distincts : l'ordonnancement statique de programmes parallèles, le placement de composants électroniques et la planification de réseaux cellulaires. Pour chacun des trois problèmes, les algorithmes hybrides ont montrés leur efficacité. Pour le problème de la planification de réseaux cellulaires, une nouvelle modélisation a été faite. Cette modélisation permet d'effectuer en même temps le placement des émetteurs et l'allocation de fréquences.

Les manières de créer et de développer des systèmes informatiques ne cessent d'évoluer. La complexité croissante des logiciels informatiques (répartition du code, utilisation de composants externes, limitation des ressources, etc.) nécessite des méthodes de conception et de validation rigoureuses. Dans ce contexte la phase de test s'avère particulièrement importante car elle contribue à garantir un bon fonctionnement de l'implantation du logiciel, dans son environnement réel d'exécution. Cette thèse définit une méthode automatique de génération de tests destinés à évaluer la robustesse d'une implantation, c'est-à-dire sa capacité à respecter certaines propriétés comportementales malgré un environnement d'exécution dégradé (susceptible de fournir des entrées incorrectes, ou d'inclure des composants externes incapables de rendre le service attendu). L'approche que nous proposons est inspirée des techniques de génération de test utilisées en test de conformité des protocoles de communications dans lesquelles les suites de test sont générées à partir d'un modèle comportementale d'une spécification du logiciel. L'originalité de ce travail consiste à étendre cette technique pour prendre en compte un modèle de fautes (exprimant le comportement dégradé de l'environnement sous forme de mutations syntaxiques de la spécification) et un observateur (exprimant l'ensemble des comportements incorrects du point de vue de la robustesse). Les séquences de test produites sont alors correctes dans le sens où elles ne rejettent que des implantations non robustes vis-à-vis de cet observateur. Un prototype a été réalisé dans le cadre de la boîte à outils IF et évaluée sur des exemples d'implantation Java.

L'objet de ce mémoire est de montrer que désormais l'informatique permet de réaliser un vieux rève : se débarasser du carcan du plomb et créer de nouveaux caractères adaptés à de nouvelles technologies.<br /><br />Ce mémoire comprend deux parties. La première est une courte synthèse sur la typographie. Nous rappelons ce qu'est un caractère et comment on les fabriquait autrefois puis comment on les manipule aujourd'hui, c'est-à-dire ce qu'est une fonte numérique et comment, depuis peu, on arrive à atteindre les exigences du passé.<br /><br />La seconde partie montre les recherches auxquelles nous avons participé : nous montrons d'abord une possibilité fondamentale en matière de créativité : on peut désormais calculer la forme d'un caractère lorsque l'on l'utilise et non plus avant, une fois pour toutes. Nous donnons comme première application celui du dessin des symboles mathématiques. Nous montrons ensuite comment ce concept de fonte dynamique permet de créer de nouveaux caractères en fonction du contexte.<br /><br />En guise de conclusion, nous indiquons plusieurs voies de recherche.

Dans ce travail de thèse, nous présentons le problème de recherche d'information sur Internet et plus généralement de veille stratégique. Nous remarquons généralement qu'il est nécessaire de passer beaucoup de temps à analyser les résultats fournis par les moteurs de recherche traditionnels afin d'obtenir une réponse satisfaisante. Dans cette thèse, nous avons donc développé un outil de recherche automatique basé sur une stratégie de recherche évolutionnaire. Cet outil explore les pages Web en partant des résultats fournis par les moteurs de recherche traditionnels (comme Google, Altavista, ...). Plusieurs méthodes d'optimisation ont été comparées : une approche génétique, une approche à base de population de fourmis et un algorithme tabou. L'effort de recherche a également été parallélisé et peut être distribué sur plusieurs machines distantes afin de maximiser les ressources disponibles à l'exécution de cette tâche et d'utiliser une architecture parallèle de grande ampleur. Enfin, nous proposons un système de visualisation des résultats d'un moteur de recherche basé sur les propriétés des nuages d'agents afin d'aider les utilisateurs à mieux comprendre les éléments renvoyés par le moteur et de diminuer ainsi le temps nécessaire à leur analyse.

Cette thèse s'intéresse à améliorer la qualité de service (QdS) offerte par des mécanismes de gestion de file d'attente tels que RED (Random Early Detection). Nous étudions une approche adaptative de RED appelée ARED. Notre but est de trouver un extension simple de ARED afin d'améliorer la prédictibilité des mesures de performance comme le délai, le temps de gigue sans pour autant sacrifier le taux de perte. Pour cela, nous proposons un nouveau mécanisme nommé PSAND qui configure les paramètres de RED et l'évaluons à l'aide de simulations. Nos résultats de la comparaison de PSAND avec ARED et d'autres schémas bien connus ou récemment proposés ont montré que avec une complexité moindre, PSAND donne un compromis désiré et de bonnes performances telles qu'un faible délai d'attente dans la file, une faible gigue et une plus grande stabilité en présence d'un fort trafic. Une autre contribution de cette thèse est l'étude de l'interaction de FEC (Forward Error Correction) avec des schémas comme Drop Tail et RED. Les résultats ont montré que selon la valeur des paramètres comme le nombre de flux TCP actifs, le taux de redondance et de la taille des blocs FEC parfois RED ou parfois Drop Tail donne de meilleures performances. Un modèle analytique ayant confirmé les résultats obtenus par simulations a également été présenté.