Abonnez-vous

Les algorithmes en ligne
Prendre des décisions sans connaître l'avenir


Christian Laforest

Le don de deviner le futur serait évidemment un atout considérable. Qui n'en a jamais rêvé ? À défaut de boule de cristal, les mathématiques nous permettent de prendre des décisions peu pénalisantes, sans pour autant connaître l'avenir. Bienvenue dans le monde des algorithmes en ligne.


Faire des choix n’est pas toujours chose aisée. On peut se tromper du tout au tout ou, au contraire, prendre des décisions qui s’avéreront optimales par la suite. L’incertitude vient du fait qu’au moment où nous nous décidons, nous ne pouvons pas savoir ce que le futur nous réserve. Sur quelles bases faire des choix, sachant que l’avenir est totalement incertain ? Les algorithmes en ligne (ou online algorithms en anglais), peu connus, sont une piste de réflexion. De manière très simplifiée, ce sont des algorithmes qui doivent accomplir des tâches, prendre des décisions, à partir d’informations qu’ils ne connaissent pas intégralement dès le début, mais qui seront dévoilées au fil de l’eau. Un point commun unit de nombreuses variantes de ce contexte : lorsque l’algorithme reçoit un « bout » des données, il doit prendre une décision irrévocable (une fois un choix fait, l’algorithme ne peut plus revenir dessus). 

 

Louer ou acheter un vélo ?

M. Chronos est réparateur ambulant de montres et de pendules. Son atelier se trouve dans une camionnette, avec laquelle il se déplace. Un jour, il arrive en ville et installe son outil de travail sur la place du marché, sur laquelle il peut ... Lire la suite gratuitement