Optimisation de la présentation d'un document hypermédia

Tout le monde connaît maintenant le HTML qui est le langage favori pour la diffusion de documents sur Internet. Il apporte de nouvelles possibilités par rapport au support papier grâce à ses capacités d'interactivité et à son intégration du multimédia. Mais comme toujours, les besoins augmentent et de nouveaux langages sont développés pour améliorer la structure et l'interactivité des documents. Notamment le langage SMIL (Synchronized Multimedia Integration Language), basé sur XML (futur standard pour la diffusion de documents sur Internet), a fait son apparition. Il offre une nouvelle dynamique aux documents hypermédia, et en particulier la possibilité d'y animer et synchroniser des composants multimédia.

La variété des composants qui forment un document (audio, vidéo, texte, image...) fait de l'animation un problème compliqué. L'auteur d'un document synchronisé fournit une liste de contraintes temporelles sur les composants de manière à décrire le déroulement de la présentation. Ces composants ont chacun une durée de présentation qui est flexible dans une certaine limite. Tout le problème consiste à trouver un bon ajustement des durées pour que la présentation se déroule au plus proche de ce que souhaite l'auteur tout en évitant les pauses (les moments où il ne se passe rien). Cet ajustement doit être planifié avant la présentation du document, mais peut être modifié ensuite au cours de la présentation, à cause de l'interaction avec l'utilisateur ou des retards éventuels liés aux transferts sur le réseau.

Nous collaborons avec une équipe de recherche brésilienne qui développe des outils pour concevoir et présenter de tels documents. Nous contribuons à ce travail en fournissant des algorithmes rapides pour répondre à quelques uns des différents problèmes exposés précédemment. Nous expliquons ici comment modéliser ces problèmes avec des graphes et quelles sont les possibilités pour estimer la qualité d'une présentation. Nous nous concentrons ensuite plus particulièrement sur l'un de ces problèmes qui peut être modélisé comme un problème de tension de coût minimum dans un graphe. Pour le résoudre, nous proposons une adaptation de l'algorithme de mise à conformité (out-of-kilter) dans le cas de coûts linéaires par morceaux et dans le cas de coûts non linéaires convexes. Des tests numériques montrent l'intérêt de cette modélisation pour l'optimisation de la qualité de présentation de documents hypermédia. Nous terminons avec la présentation d'une classe de contraintes très particulières, modélisées par des graphes série-parallèles, qui représentent une idéalisation du problème.