- Online algorithm
-
En informatique, un algorithme online (algorithme en-ligne) est un algorithme qui reçoit son entrée (son input) prédécoupée en petits morceaux, et qui commence à calculer dès le premier petit morceau reçu, puis continue à traiter, en série, les morceaux reçus ultérieurement. L'algorithme commence donc son travail sans avoir une vision globale de l'input qu'il va recevoir. À l'inverse, un algorithme offline connait lui l'ensemble de son input avant de commencer à traiter le problème correspondant. (Par exemple, le tri par sélection requiert que l'intégralité de la liste à trier soit fournie avant qu'il puisse commencer à la trier, tandis que le tri par insertion a plus de souplesse, et peut recevoir la liste à trier au compte-gouttes et néanmoins commencer à trier.)
Puisqu'il ne connait pas l'intégralité de son input, un algorithme online est forcé de faire des choix qui peuvent s'avérer au final non optimaux ; l'étude des algorithmes online a ainsi mis l'accent sur la qualité des choix possibles dans une telle configuration. L'analyse compétive formalise cette idée en comparant la performance, sur la même input, de l'algorithme online et offline. Pour d'autres points de vue sur les inputs online des algorithmes, voir les articles algorithme de fouille de flots de données (centré sur la quantité de mémoire nécessaire à représenté les inputs passées), dynamic algorithm (centré sur la complexité en temps pour manipuler les solutions à des problèmes à inputs online) et apprentissage en-ligne.
Un problème illustrant le concept d'algorithme online est celui du voyageur de commerce canadien. Le but de ce problème est de minimiser le coût d'atteinte d'un sommet dans graphe pondéré où certaines des arrêtes sont peu "fiables" car elles peuvent à tout moment être retirées du graphe. Cependant, si une arrête devient inutilisable, cela n'est révélé au "voyageur" uniquement lorsqu'il atteint l'un des sommets de cette arrête. Le pire cas de ce problème a lieu lorsque toutes les arrêtes peu fiables s'avèrent être inutilisables et le problème se réduit alors au problème du plus court chemin. Une analyse alternative du problème peut être effectuée à l'aide de l'analyse compétitive. Pour cette méthode d'analyse, l'algorithme offline connait en avance quelles arêtes vont être inutilisable et le but est de minimiser le rapport entre la performance de l'algorithme online et celle de l'algorithme offline. Ce problème est PSPACE-complet.
Sommaire
Liste d'algorithmes online
Voici quelques noms d'algorithmes online : K server, Balance2, Balance-Slack, Double Coverage, Equipoise, Handicap, Harmonic, Random-Slack, Tight Span Algorithm, Tree Algorithm, Work Function Algorithm.
Voir aussi
- algorithme glouton
- Adversary Model
- Job shop scheduling
- List update problem
- Metrical task systems
- Odds algorithm
- Paging Problem
- Real-time computing
- Secretary problem
- Ski rental problem
- Linear search problem
- Search games
- Algorithms for calculating variance
- Bandit problem
- algorithme d'Ukkonen
Références
- (en) Borodin, A., Online Computation and Competitive Analysis, Cambridge University Press, 1998 (ISBN 0-521-56392-5) [lire en ligne]
Lien externe
Wikimedia Foundation. 2010.
