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.

Ce mémoire décrit les activités de recherche que j'ai menées depuis ma thèse et plus particulièrement celles que j'effectue dans le projet Opéra (outils pour les documents électroniques : recherche et applications) de l'INRIA sur les documents structurés multimédia. Ce document tente d'inscrire les différents travaux réalisés dans un cadre plus large qui comprend d'une part la modélisation des documents et d'autre part les applications de traitement de documents. Les principales contributions sont les suivantes : - Représentation abstraite des types de documents de façon à permettre de transformer les structures de documents. - Représentation de la structure logique et de la structure spatiale, ou comment intégrer des structures spatiales et logiques de façon à formater les documents structurés selon des modèles de pages complexes. - Représentation de l'information temporelle des documents multimédia qui s'intègre aux représentations logiques et spatiales et qui soit adaptée à la construction d'environnements d'édition.

Les récentes avancées techniques dans les domaines du logiciel, du matériel et des réseaux ont permis l'apparition du multimédia dans des environnements informatiques classiques. Il devient aujourd'hui envisageable d'utiliser le World Wide Web comme support de diffusion de contenu multimédia. Des extensions temporelles au langage HTML sont proposées sous la forme de quelques nouveaux tags permettant la description du comportement temporel et spatial, afin de pouvoir spécifier des présentations multimédia pour le WWW incluant plusieurs objets média. Une architecture de synchronisation a été conçue et mise en oeuvre en Java, celle-ci permettant de jouer des présentations complexes définies à l'aide de ces extensions dans un navigateur WWW. Les extensions à HTML sont analysées et transformées en code HTML classique et Java, produisant ainsi un document qu'il est possible de lire dans un navigateur standard. Enfin, le cas des sources de contenu sur réseau délivrant des flots contrôlés par l'architecture de synchronisation a été considéré à partir de l'analyse de la problématique du transport des données multimédia temporelles dans un environnement best effort distribué comme l'Internet. À terme l'objectif est de fournir une qualité de présentation optimale en traitant les problèmes au niveau le plus adapté dans la chaîne serveur-transport-client.

L'objectif de l'apprentissage dans le dialogue homme-machine est de donner à la machine des capacités accrues d'interaction et d'adaptation à l'utilisateur, spécialement pour l'acquisition de nouvelles tâches. Dans le cadre du dialogue coopératif finalisé, la tâche structure le dialogue. Et c'est à travers le dialogue que s'établit quoi faire mais aussi comment faire. Dans cette thèse, nous envisageons l'ordinateur comme un partenaire dans la réalisation d'une tâche, capable d'apprendre puis de reconnaître des situations apprises. Nous présentons un modèle de dialogue centré sur la notion d'apprentissage des savoirs et des savoir-faire. Nous proposons un modèle de dialogue indépendant de la tâche, dans lequel le domaine de travail est défini par l'application, mais où le système de dialogue ne connaît pas a priori la ou les tâches à faire. La machine apprend une tâche et à partir de cette nouvelle connaissance elle peut intervenir dans des situations analogues. Par ailleurs, nous fondons le modèle sur les états mentaux de l'utilisateur. Ces états mentaux, à partir desquels la machine peut interpréter et produire des réponses, expriment les croyances et les intentions de l'interlocuteur. La formalisation des échanges dialogiques est réalisée dans un cadre logique fondé sur l'action. Il contient des éléments d'une logique épistémique (pour la représentation des connaissances), d'une logique de l'action (pour décrire les actions et les effets produits), et d'une logique dialogique (pour exprimer les engagements, les ruptures et les incompréhensions lors des échanges dialogiques). De cette façon, notre modèle intègre (i) la gestion des échanges langagiers et non-langagiers, (ii) la coordination des actions à partir de la reconnaissance de plans, et (iii) la construction de connaissances communes à travers l'acquisition de nouvelles tâches. Enfin, nous avons implémenté le système ICPdraw adaptatif qui nous a permis de valider notre approche.

L'objectif de ce travail est la conception et la réalisation d'un Système de Gestion de Base de Données Relationnel (SGBDR) intégrant les concepts et la technologie "objets". Le principe de notre approche est d'étendre les domaines relationnels aux types abstraits (ADT) et revient à coupler de façon relativement faible les concepts et mécanismes objets au modèle et à un système relationnels. Cela introduit des problèmes de modélisation et d'optimisation nouveaux qui restent à étudier. Dans un premier temps, le modèle de données et les caractéristiques de l'extension sont définis. La notion de type abstrait est introduite pour exprimer de nouveaux domaines : un ADT définit une structure de données et un ensemble de méthodes (fonctions) qui constituent son unique interface de manipulation. Un mécanisme d'héritage simple est offert. Des constructeurs sont disponibles pour définir la structure de données d'un type ; on introduit ainsi la notion d'objet complexe. Le concept de partage, associé à l'identité d'objet, est un apport important de ce travail. Le langage associé au modèle est une extension de SQL appelée ESQL ; le langage d'écriture des méthodes actuellement disponible est une extension de C. La mise en oeuvre d'un tel système consiste à développer les composants nécessaires au support d'objets et à les intégrer à un noyau de SGBDR existant. Elle permet de mettre en évidence trois modules principaux. Le gestionnaire de types est un complément du gestionnaire de catalogue relationnel qui gère les définitions d'ADT. Le gestionnaire de méthodes regroupe un ensemble de fonctions allant de la compilation à l'exécution. Le gestionnaire d'objets assure le stockage et la manipulation des objets complexes (instances d'ADT) ; cette partie à notamment permis d'étudier des techniques évoluées de stockage d'objets.

Cette thèse porte sur les environnements permettant aux formateurs de développer des simulations pédagogiques. La première partie présente un état de l'art de ces environnements, au regard des différentes tâches identifiées par le modèle MARS (Modèle, Associations, Représentation, Scénario). Elle montre notamment l'intérêt d'une séparation nette entre la simulation proprement dite et le contrôle pédagogique, ce qui permet d'utiliser différentes approches pédagogiques sur une simulation. Cette étude théorique est complétée par une expérimentation que nous avons menée avec des enseignants, dans le cadre du projet européen ARIADNE, sur l'outil OASIS créé par l'équipe ARCADE sur la base du modèle MARS. Ces travaux montrent que les outils existants facilitent les tâches de l'auteur, mais que la distance cognitive entre ses abstractions et les abstractions proposées par les outils est encore trop grande. Partant de ce constat, l'idéal (utopique) serait d'offrir un outil adaptable au domaine particulier de l'auteur. Adoptant un point de vue génie logiciel, nous proposons dans la deuxième partie de cette thèse une solution permettant à un développeur de construire rapidement des outils adaptés. Cette solution s'appuie sur des techniques de réutilisation basées sur les architectures, les frameworks et les patrons. Nous présentons un framework que nous avons développé sur la base du modèle MARS. Nous avons utilisé ce framework pour construire une version d'OASIS, ainsi que l'outil FENIX dédié à la réalisation de simulations basées sur des modèles mathématiques simples. La troisième partie concerne la mise en œuvre effective de la séparation entre simulation et contrôle pédagogique préconisée plus haut. Nous proposons ARGOS, une architecture de communication entre simulations et outils de contrôle pédagogique. Un sous-ensemble d'ARGOS a servi à l'élaboration d'un prototype pour le contrôle pédagogique de simulations à distance.

A ce jour, les méthodes formelles ont montré qu'elles étaient applicables avec succès au développement de logiciels industriels. Pour maîtriser la complexité croissante de ces applications, la mise en oeuvre des paradigmes d'abstraction et de composition est incontournable. La méthode B permet d'assister le processus de développement des spécifications au code et offre une notion de modularité qui permet de composer à la fois les spécifications et les développements. La compositionnalité des preuves est assurée par des restrictions imposées par le langage, qui limitent les formes d'architectures autorisées. A la suite de nos précédents travaux, le manuscrit présenté ici explicite les principes de composition des spécifications et des développements, énonce les théorèmes sous-jacents à la composition des preuves et complète et valide les restrictions imposées par la méthode B. Bien que dédiés à la méthode B, les résultats présentés sont plus généraux : ils peuvent s'appliquer à d'autres approches formelles basées sur la notion d'état, comme les approches objet

Dans le cadre de la télécommunication, les entreprises développent des protocoles gérant le transfert de données entre machines. Ces protocoles fonctionnent sur le principe d'envoi de messages entre deux parties par l'intermédiaire de canaux non fiables. Pour s'assurer que tous les messages ont bien été reçus, les techniques employées consistent à réémettre les messages perdus et/ou à attendre un laps de temps déterminé avant de conclure à l'échec de la transmission. De plus, les systèmes sont souvent modélisés en fonction de paramètres. Nous avons travaillé sur un modèle mathématique permettant la vérification de spécifications (comportements attendus des systèmes) pour des protocoles manipulant à la fois des compteurs, des files d'attente ou des horloges, ainsi que des paramètres. Le but de l'analyse est de calculer l'ensemble des comportements possibles du système puis de vérifier qu'aucun d'eux ne viole une spécification attendue. Le problème ici est que cet ensemble est infini. En effet, un comportement est fonction des valeurs prises par les variables du système au cours de l'exécution et certaines sont définies sur un domaine infini. Il faut alors pouvoir représenter ces comportements de façon finie et aussi trouver des méthodes pour calculer en un temps fini un ensemble infini. Plus formellement, nous nous sommes placés dans le cadre de l'analyse automatique des systèmes (model-checking). La représentation choisie pour les modèles à compteurs et horloges paramétrés est une extension des matrices de bornes pour laquelle nous avons une méthode exacte d'accélération (calcul en un temps fini d'ensembles de comportements infinis). Du côté pratique, nous avons implanté ces méthodes dans un outil TReX qui est, à notre connaissance, le seul pouvant manipuler de manière exacte des compteurs, des horloges et des files d'attente. Nous avons pu vérifier des exemples conséquents tels que le protocole de retransmission bornée.

Cette thèse est une étude de méthodes permettant d'estimer des fonctions valeur avec des réseaux de neurones feedforward dans l'apprentissage par renforcement. Elle traite plus particulièrement de problèmes en temps et en espace continus, tels que les tâches de contrôle moteur. Dans ce travail, l'algorithme TD(lambda) continu est perfectionné pour traiter des situations avec des états et des commandes discontinus, et l'algorithme vario-eta est proposé pour effectuer la descente de gradient de manière efficace. Les contributions essentielles de cette thèse sont des succès expérimentaux qui indiquent clairement le potentiel des réseaux de neurones feedforward pour estimer des fonctions valeur en dimension élevée. Les approximateurs de fonctions linéaires sont souvent préférés dans l'apprentissage par renforcement, mais l'estimation de fonctions valeur dans les travaux précédents se limite à des systèmes mécaniques avec très peu de degrés de liberté. La méthode présentée dans cette thèse a été appliquée avec succès sur une tâche originale d'apprentissage de la natation par un robot articulé simulé, avec 4 variables de commande et 12 variables d'état indépendantes, ce qui est sensiblement plus complexe que les problèmes qui ont été résolus avec des approximateurs de fonction linéaires.

The foundation of term rewriting is equational logic but for the sake of efficiency, the equations are oriented and become the rules of a term rewriting system. Term rewriting form a model of computation on algebraic data structures (terms). Term rewriting systems play an important role in various domains of computer science such as automated theorem proving, functional programming, code generation, problem formalization (security of cryptographic protocols). Rewriting starts with a ground term, and consists of repeatedly replacing a redex (an instance of a left-hand side) by its contractum (the corresponding right-handside after applying the substitution). Rewriting may eventually yield a term in normal form which is a term containing no redex. Natural questions in term rewriting are: * is the system terminating" (i.e. there are no infinite rewrite sequences)? * "is the system confluent" (if a term rewrites independently to two terms t1 and t2 , there exists a term s such that both t1 and t2 rewrite to s)? We are interested in systems which can be used as programs so we want to allow non-terminating computations. Confluence implies unicity of normal forms but does not imply termination. Confluent systems form a good framework for deterministic programming. They have the power of Turing machines. However confluence is not a decidable property for term rewriting systems. Orthogonal systems (i.e. linear and non-overlapping left-hand sides) which are always confluent form the framework of all this work, although some results may apply to the more general class of left-linear systems (linear left-hand sides). The first point we want to address is "how to compute the normal form?" and not end up in an infinite computation when the normal form exists. The second is "how to do that efficiently?". The following theorem of Huet and Levy [HL91] forms the basis of all result on optimal normalizing rewrite strategies for orthogonal term rewrite systems: "Every reducible term contains a needed redex, i.e., a redex which is contracted in every rewrite sequence to normal form, and repeated contraction of needed redexes results in a normal form, if the term under consideration has a normal form". Unfortunately, needed redexes are not computable in general. Hence, in order to obtain a computable optimal rewrite strategy, we are left to find (1) decidable approximations of neededness and (2) decidable properties of rewrite systems which ensure that every reducible term has a needed redex identi-fied by (1). Starting with the seminal work of Huet and Levy [HL91] on strong sequentiality, these issues have been extensively investigated in the literature [Com00, Jac96b, JS95, KM91, NST95, Oya93, Toy92]. In all these works Huet and Levy's notions of index, omega-reduction, and sequentiality figure prominently. We present here our contributions to this domain.