CONCLUSION

Plusieurs travaux proposaient une représentation sous forme de graphe des contraintes temporelles d'un document hypermédia synchronisé. Nous avons montré que cette modélisation permet de considérer les problèmes de synchronisation hypermédia comme des problèmes de tension dans un graphe et donc de profiter de la théorie des graphes pour résoudre certains de ces problèmes.

Dans un premier temps, nous nous sommes intéressés à la recherche d'une tension compatible dans un graphe, traduisant la recherche d'une planification possible pour un scénario. Les méthodes étudiées sont suffisamment efficaces pour envisager leur usage en temps réel, il est tout à fait concevable de les relancer au cours de la présentation du document hypermédia afin d'ajuster la planification après une anomalie. En outre, la méthode basée sur le plus court chemin est tout à fait adaptée à l'aspect incrémental de la création d'un document. La non réalisabilité d'un ensemble de contraintes se traduit par la détection d'un circuit de longueur négative, il est alors possible d'indiquer à l'utilisateur où se situe le problème: il suffit d'exhiber les objets qui se trouvent sur ce circuit.

Pour le problème de la tension optimale, qui reflète le problème de déterminer la meilleure planification d'un scénario, nous proposons plusieurs méthodes, chacune adaptée à des phases différentes de la création et de la présentation du document synchronisé. Avec des coûts linéaires sur les objets multimédia pour mesurer la qualité de la synchronisation, la méthode de la mise à l'échelle du dual est la plus efficace et peut être envisagée non seulement pour le formatage final du document, mais également pour les prévisualisations. La méthode de la mise à conformité, certes moins performante sur des graphes quelconques, semble plus efficace sur des graphes plus structurés, une étude sur des cas réels est nécessaire pour identifier la méthode la mieux adaptée aux instances de synchronisation hypermédia.

La méthode de la mise à conformité nous semble néanmoins très importante dans l'aspect temps réel, puisque son approche pour optimiser la planification est distribuée sur le graphe (comme le montre d'ailleurs la méthode de reconstruction). En effet, si la tension est modifiée localement, ce serait le cas après un retard par exemple dans la présentation du document, alors il suffit de rendre à nouveau conformes les quelques arcs qui ne le sont plus pour conserver une planification optimale. Pour chaque arc, cette méthode nécessite opérations, ce qui est tout à fait acceptable pour un usage temps réel.

Nous avons également proposé d'adapter la mise à conformité à des coûts convexes quelconques pour mesurer la qualité d'une planification. L'intérêt de cette approche est de permettre aux personnes qui élaborent les outils de conception de documents hypermédia synchronisés d'expérimenter différents types de coûts, dans un premier temps sans se préoccuper de la manière d'optimiser la planification. Comme l'explique par exemple [Kim95], il peut être intéressant d'employer des coûts quadratiques plutôt que des coûts linéaires, afin d'obtenir une meilleure répartition des déformations entre les objets multimédia.

Nos travaux sur les problèmes de tension se terminent dans ce mémoire par l'étude d'une classe particulière de graphes, les graphes série-parallèles, qui semblent présenter une structure très proche de celle des graphes issus de synchronisation hypermédia. Nous avons proposé une méthode d'agrégation efficace, opérations, pour résoudre ces cas idéaux. Les bonnes performances de cette méthode ont ensuite été exploitées pour élaborer la première ébauche d'une méthode de reconstruction de la tension optimale d'un graphe quelconque à partir d'une décomposition le représentant en composantes série-parallèles.

Des résultats numériques montrent le potentiel de cette approche, dont nous n'avons pas réussi pour l'instant à profiter pleinement. Néanmoins, nous avons proposé deux variantes qui s'avèrent efficaces pour des graphes presque série-parallèles avec une SP-perturbation d'au plus . Les tests ont révélé que la méthode peut être performante jusqu'à de SP-perturbation, ce qui permettrait de résoudre très certainement encore plus efficacement les problèmes pratiques. Un point intéressant de cette étude sur les graphes presque série-parallèles est d'avoir permis de mettre en évidence l'intérêt des différentes méthodes en fonction de la structure du graphe: les graphes série-parallèles sont traités avec la méthode d'agrégation, les graphes presque série-parallèles avec la méthode de reconstruction ou la mise à conformité simple, et enfin les graphes quelconques avec la méthode de mise à l'échelle du dual.

Une partie de ce mémoire a été consacrée à des réflexions sur la manière de concevoir des composants réutilisables pour la recherche opérationnelle. Il nous a semblé important d'en discuter ici, puisque les problèmes de tension ont été traités dans l'objectif de répondre à des besoins dans le domaine de l'hypermédia. Il était inconcevable pour nous de fournir simplement comme réponse des algorithmes sous une forme trop abstraite. Il nous semblait important de produire des algorithmes implémentés tout à fait opérationnels pour qui voudrait les utiliser. Cela nous a amené à une réflexion plus large sur la manière de mener à la fois une recherche efficace, c'est-à-dire pouvoir expérimenter rapidement une nouvelle méthode, et en même temps fournir des implémentations réutilisables par une majorité de personnes, à savoir des initiés en recherche opérationnelle, mais également des novices ayant identifié leur problème et désirant une implémentation rapide. Une autre motivation importante était de pouvoir évaluer les performances pratiques de différents algorithmes, il est en effet très délicat de comparer des implémentations si elles n'ont pas été développées sur le même modèle. Le fait de fournir un environnement réutilisable où finalement tous les algorithmes utilisent les mêmes "briques" de base facilite forcément cette comparaison.

Nous espérons dans cette dernière partie avoir convaincu de l'intérêt de proposer un environnement réutilisable de développement pour les problèmes de graphes, les enjeux étant d'accélérer l'implémentation de nouveaux algorithmes et de permettre plus aisément de fournir des produits finis. Les problèmes et les besoins de la recherche opérationnelle sont différents de ceux d'autres domaines de l'informatique, il est donc hors de question de suivre les schémas classiques proposés par le génie logiciel pour conduire le développement d'un système logiciel vaste pour la recherche opérationnelle. Nous avons donc tenté dans notre présentation du paradigme objet de montrer en quoi cette approche pouvait être bénéfique pour la recherche opérationnelle, comme elle l'a été pour de nombreux autres domaines, à condition d'éviter certaines tentations durant la phase de développement: des possibilités au premier abord alléchantes en termes de réutilisabilité et d'extensibilité peuvent conduire à une inefficacité catastrophique. A partir de notre expérience et de nos réflexions, nous avons discuté plusieurs techniques de conception qui permettent de développer des composants génériques, c'est-à-dire indépendants des structures de données qu'ils manipulent et des sous-algorithmes qu'ils emploient, tout en étant fortement extensibles, et cela avec une perte d'efficacité minimale.

Nos diverses implémentations nous ont menés progressivement au développement d'une bibliothèque assez vaste comprenant des modules pour différents problèmes de recherche opérationnelle sur les graphes (concernant surtout la tension, mais aussi les flots, les plus court chemins...), l'enjeu étant qu'elle puisse être utilisée ou réutilisée par une majorité de personnes, ce qui signifie une bonne réutilisabilité, une portabilité éprouvée et une efficacité honorable. Nous envisageons d'intégrer cette bibliothèque dans un environnement de développement pour les problèmes de graphes qui assisterait les personnes dans leurs implémentations, dans un processus d'expérimentation de nouvelles méthodes ou dans l'élaboration d'un produit fini. Notre première étape est actuellement l'élaboration d'une interface graphique permettant non seulement de manipuler des graphes, mais également de construire plus aisément des algorithmes à partir des "briques" de la bibliothèque.

Notre ligne de conduite tout au long de l'étude a été de fournir pour les problèmes de tension des algorithmes et des résultats théoriques, des implémentations informatiques réutilisables (documentées, portables, efficaces, robustes...) et des jeux d'essais (génération aléatoire). Le but d'un environnement de développement serait de pouvoir mieux intégrer toutes ces phases et de faciliter ainsi le passage d'une idée à sa réalisation, ce qui ne peut que dynamiser la recherche d'algorithmes pour les problèmes de graphes.