Algorithme online

En informatique, un algorithme incrémental, parfois aussi appelé algorithme en ligne (ou algorithme online), 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. Un algorithme online s'oppose aux algorithmes offline qui prend tout l'entrée d'un seul coup, et qui prend ses décisions en fonction de toute l'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 (ou d'algorithme de streaming).

PrincipeModifier

DéfinitionModifier

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 triModifier

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

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érencesModifier

Liens externesModifier

Articles connexesModifier