Synchronisation hypermédia et graphes série-parallèles

Les formats actuels permettant la diffusion de documents sur Internet apportent sans conteste de nouvelles possibilités par rapport au support papier grâce à leurs capacités d'interactivité et à leur intégration du multimédia. Mais les exigences deviennent toujours plus grandes et de nouveaux langages font régulièrement leur apparition pour tenter d'améliorer la structure et l'interactivité des documents. Parmi ces langages, certains comme SMIL (Synchronized Multimedia Integration Language) offrent la possibilité d'animer et synchroniser des composants multimédia dans les documents.

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.

Ce problème peut se modéliser, après quelques restrictions, comme un problème de tension de coût minimum dans un graphe. Pour le résoudre, nous avons étudié plusieurs méthodes dont nous proposons un récapitulatif et un comparatif sur les plans théorique et pratique. Cependant, les tests numériques ont été réalisés sur des graphes complètement aléatoires.

Les graphes représentant les contraintes temporelles sont en réalité très structurés et très proches de la classe des graphes appelés série-parallèles. Nous montrons tout d'abord, par des résultats numériques, que les méthodes déjà proposées ne sont pas toujours très efficaces. Nous présentons alors une méthode adaptée que nous appelons agrégation. Mais les graphes série-parallèles, bien que très proches de la réalité, restent encore une idéalisation. Nous terminons donc par la présentation de premiers résultats obtenus pour des graphes série-parallèles perturbés.