Algorithme online

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Algorithme en ligne)
Aller à : navigation, rechercher

En informatique, un algorithme online ou algorithme en ligne est un algorithme qui reçoit son entrée non d'un seul coup mais comme un flux de données et doit prendre des décisions au fur et à mesure. Un cadre classique est celui dans lequel l'algorithme doit répondre à des requêtes les unes après les autres sans connaître les requêtes future.

Quand il est question d'apprentissage automatique on parle parfois d'algorithme d'apprentissage incrémental. Quand la mémoire est la contrainte importante, on parle plutôt de d'algorithme de fouille de flots de données (ou algorithme de streaming).

Principe[modifier | modifier le code]

Définition[modifier | modifier le code]

Il existe plusieurs modèles d'algorithmes online, mais ils ont tous en commun que l'algorithme doit prendre des décisions avant d'avoir toutes les données du problème.

Exemple du tri[modifier | modifier le code]

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. Il peut recevoir la liste à trier au compte-gouttes et néanmoins commencer à trier.

Online versus Offline et compétitivité[modifier | modifier le code]

Un algorithme online commence son travail sans avoir une vision globale sur la totalité des données qu'il va recevoir. À l'inverse, un algorithme hors ligne (offline), connait lui toutes les données avant de commencer à traiter le problème correspondant.

On dit qu'un algorithme online est k-compétitif si la solution calculée n'est que k fois pire que l'optimal offline[1].

Notes et références[modifier | modifier le code]

  1. Gilles Schaeffer, « Algorithme online », sur École polytechnique.

Liens externes[modifier | modifier le code]