Algorithme online

En informatique, un algorithme en ligne, parfois aussi appelé algorithme incrémental, est un algorithme qui reçoit un flux de données en entrée, et qui 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 à venir. Il s'oppose au concept d'algorithme hors ligne qui reçoit d'un seul coup les données qu'il a à considérer, et prend ses décisions en fonction de cette entrée.

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 d'algorithme de fouille de flots de données.

Principe

Définition

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

Exemple du tri

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.

Compétitivité

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

On dit qu'un algorithme en ligne est k-compétitif si la solution calculée n'est que k fois pire que l'optimal hors ligne^[1]. On remarque dans ce cas que ${\displaystyle k\geq 1}$ car dans le cas contraire il suffirait de considérer les données les unes après les autres dans l'algorithme hors ligne pour obtenir un meilleur algorithme, ce qui contredit son optimalité.