INTRODUCTION
 

Grâce à la puissance des ordinateurs et au débit des communications actuels, il est possible de combiner différents médias (son, vidéo, texte, images, animations, applets...) pour produire des documents plus sophistiqués, que l'on peut diffuser aussi bien sur support fixe (CD, DVD...) qu'à travers un réseau. Cependant, malgré ces progrès, les documents hypermédia rencontrés notamment sur Internet possèdent une organisation très proche des supports papiers. Ils possèdent en effet une structure logique (décomposition en parties, chapitres, sections...) et une structure spatiale (placement précis des objets à l'écran). En revanche, ils sont très peu organisés au niveau temporel, alors que des documents par exemple éducatifs (encyclopédie, atlas, cours...) nécessitent des scénarios très planifiés prenant en compte des interactions avec l'utilisateur.

Des outils sont élaborés, à l'image de ceux permettant la structuration logique et spatiale d'un document, afin d'assister les auteurs dans la création de documents hypermédia synchronisés. Produire de tels documents consiste avant tout à spécifier les relations temporelles entre les divers objets multimédia, chacun ayant une durée fixée dite idéale que l'auteur accepte de modifier éventuellement dans un certain intervalle. Cela signifie qu'un objet multimédia trop long pour satisfaire les contraintes imposées peut être raccourci dans certaines limites. La seconde étape consiste alors à déterminer une planification du scénario qui soit en adéquation avec les contraintes exprimées par l'auteur, autrement dit, il faut trouver la durée de chaque objet multimédia telle qu'il n'y ait pas de temps mort dans la présentation. Au moment de la présentation du document, la planification est suivie au mieux, mais des aléas comme un retard dans le téléchargement des médias, ou bien une action de l'utilisateur, peuvent perturber la planification. Il faut alors un moyen de réajuster en temps réel cette planification.

En adoptant un modèle de graphe pour représenter les relations temporelles entre les objets multimédia, les problèmes de synchronisation adressés précédemment peuvent se traduire par des problèmes de tension dans un graphe: la recherche d'une tension compatible qui reflète la recherche d'une planification possible pour un scénario, et la recherche d'une tension de coût minimal qui modélise la recherche de la meilleure planification possible. La notion de tension dans un graphe est beaucoup moins répandue que celle de flot, peut-être plus intuitive, et permettant de modéliser de nombreux problèmes. Néanmoins, la relation de dualité qu'il existe entre le flot et la tension suggère deux stratégies pour résoudre les problèmes de tension: s'inspirer des algorithmes de flot pour élaborer des méthodes pour les problèmes de tension, ou bien transformer via la dualité un problème de tension en un problème de flot.

Nous proposons plusieurs méthodes de résolution qui tentent de prendre en compte les différentes contraintes pratiques liées à la synchronisation hypermédia. La qualité d'une planification d'un scénario est difficile à mesurer. Parmi les approches proposées, nous avons retenu celle qui attribue à chaque objet une pénalité en fonction de l'écart entre sa durée planifiée et sa durée idéale, ce coût étant naturellement une fonction convexe. Cependant la forme précise de la fonction est une question ouverte, il est nécessaire de proposer une approche suffisamment flexible pour permettre l'expérimentation de différents types de coût convexe (linéaire par morceaux, dérivable). Un autre aspect important concerne la réaction en temps réel des méthodes, il est nécessaire de proposer des méthodes qui puissent réajuster instantanément une planification qui n'est plus possible à la suite d'anomalies (retards sur le réseau, intervention de l'utilisateur...), afin de rendre la planification à nouveau réalisable et même mieux optimale. Ces besoins en flexibilité et en efficacité restreignent forcément les approches que l'on peut envisager. Les algorithmes proposés dans ce mémoire sont polynômiaux ou pseudo-polynômiaux avec une efficacité pratique établie.

Notre objectif étant de proposer des solutions pratiques pour le domaine de l'hypermédia, il nous a semblé important de fournir une implémentation des méthodes que nous proposons. Cela nous a conduit à réfléchir au projet plus ambitieux de développer des composants logiciels réutilisables pour la recherche opérationnelle, et plus spécifiquement pour les problèmes de graphes, l'objectif étant que des personnes connaissant la recherche opérationnelle puissent réutiliser et étendre les composants pour développer leurs propres solutions, et que des personnes peut-être moins averties puissent utiliser les composants comme des "boîtes noires" et les assembler pour obtenir un produit fini.

Mais la recherche opérationnelle, contrairement à d'autres domaines, ne peut pas suivre les règles classiques de développement du génie logiciel centrées sur la modélisation des données plutôt que celle des algorithmes. Outre les enjeux que suscite le développement de composants logiciels réutilisables pour les problèmes de graphes et les différences avec une conception logicielle classique, nous montrons le potentiel (et les concepts tentants à éviter) du paradigme objet pour élaborer des composants de recherche opérationnelle. Nous présentons finalement différentes techniques de conception qui permettent d'aboutir à des composants génériques réutilisables, portables, robustes et efficaces.

Ce mémoire est décomposé en trois parties. La première, formée des deux premiers chapitres, présente le domaine de la synchronisation hypermédia et comment modéliser certains de ses problèmes sous la forme de problèmes de tension dans un graphe. La seconde partie, composée des chapitres 3 à 5, propose plusieurs algorithmes pour résoudre des problèmes de tension. La dernière partie, formée des trois chapitres restants, présente les enjeux, les moyens et les solutions les mieux adaptées à l'élaboration de composants logiciels réutilisables pour la recherche opérationnelle. Voici maintenant un résumé très bref de chacun de ces chapitres.

Le présente plus en détails la problématique de la synchronisation hypermédia et les nombreux besoins des concepteurs d'outils de création et de présentation de documents hypermédia, notamment les différents types de relations temporelles à exprimer entre les objets multimédia et les possibilités de mesure de la qualité d'une planification.

Le introduit la notion de graphe et plus particulièrement celle de graphe temporel, qui permet de modéliser des contraintes temporelles entre des objets multimédia. Nous montrons que certains problèmes de synchronisation hypermédia peuvent alors être étudiés comme des problèmes de tension, en particulier ceux de la tension compatible et de la tension de coût minimal.

Le est consacré au problème de la tension compatible, pour lequel nous étudions deux approches, l'une basée sur une recherche de cocycles augmentants, l'autre sur une recherche de plus courts chemins, les deux méthodes étant fortement polynômiales.

Le se penche sur le problème de la tension de coût minimal, considérant tout d'abord des coûts convexes linéaires par morceaux, et ensuite de manière plus générale des coûts convexes dérivables. Pour le premier type de coût, deux approches sont étudiées, l'une basée sur une recherche de cocycles augmentants, elle est pseudo-polynômiale, et l'autre consistant en une transformation du problème en un problème de flot de coût minimal, elle est polynômiale. La première méthode est ensuite adaptée à des coûts convexes dérivables quelconques.

Le s'intéresse à une classe particulière de graphes, les graphes série-parallèles, qui représentent des cas idéaux de synchronisation hypermédia. Une méthode fortement polynômiale est alors proposée. Cette méthode est ensuite exploitée pour résoudre des cas plus réalistes modélisés par des graphes presque série-parallèles, la méthode est alors pseudo-polynômiale.

Le explique les enjeux de la réutilisabilité logicielle et son rôle dans le développement de logiciels de qualité, les particularités liées à la recherche opérationnelle sont évoquées.

Le présente le paradigme objet, l'une des approches les plus évoluées du génie logiciel, en expliquant en détail les forces et les faiblesses des différents concepts face à la réutilisabilité et aussi à l'efficacité qu'ils entraînent pour la recherche opérationnelle.

Le présente des techniques de conception pour élaborer des composants génériques, c'est-à-dire indépendants des structures de données qu'ils manipulent et des algorithmes qu'ils emploient, tout en étant suffisamment extensibles pour être réutilisés dans différentes situations. Enfin, nous présentons succinctement la bibliothèque que nous avons développée, en précisant quelques aspects plus pratiques tels que la portabilité, et les extensions que nous envisageons par la suite.

 
 
Copyright (c) 1999-2016 - Bruno Bachelet - bruno@nawouak.net - http://www.nawouak.net
La permission est accordée de copier, distribuer et/ou modifier ce document sous les termes de la licence GNU Free Documentation License, Version 1.1 ou toute version ultérieure publiée par la fondation Free Software Foundation. Voir cette licence pour plus de détails (http://www.gnu.org).