Qu’est ce qu’un algorithme ?

Si je vous parle aujourd’hui des algorithmes, c’est qu’ils sont omniprésents dans l’informatique et les entreprises et que vous ne pourrez pas comprendre comment marche un programme informatique ou un site Internet sans avoir quelques notions d’algorithmique… Voyez-vous, les progrès liés à l’amélioration des algorithmes sont supérieurs aux progrès liés à la fameuse loi de Moore qui stipule que la puissance des ordinateurs double tous les 18 mois…

Soyons clairs, l’algorithmique est une discipline exigeante d’un point de vue scientifique et cet article ne fera qu’effleurer cette discipline et vous donner des ressources pour aller plus loin…

1. Définition

Schématiquement, un algorithme est une suite finie d’instructions non ambigües qui permet de résoudre un problème.

Les problèmes peuvent être très variés : trouver le site internet le plus pertinent par rapport à votre recherche, crypter un message, recommander un livre sur Amazon, trouver le chemin le plus court entre deux points, trier des choses, etc.

2. Pourquoi écrire des algorithmes ?

Tout le monde utilise des algorithmes même dans la vie de tous les jours

Les recettes de cuisine sont des algorithmes. Les tactiques d’attaque et de défense en sport sont aussi des algorithmes.

Dans son cours d’algorithmique de Stanford, Tim Roughgarden, commence par donner l’exemple d’un algorithme que tout le monde utilise : la multiplication de deux nombres. Souvenez-vous, en primaire, vous avez appris à « poser » une multiplication…

Les algorithmes comme gain de vitesse en informatique

Les ordinateurs sont limités par leur mémoire et leur puissance, les réseaux par la bande passante. Dans ce cadre, la recherche d’efficacité est primordiale.

Un algorithme peut toujours être amélioré. La méthode de multiplication a par exemple été améliorée en 1960 par le mathématicien soviétique Karatsuba ce qui permet de gagner un temps précieux, notamment sur les grands nombre.

Lorsqu’un informaticien crée un programme, il a toujours plusieurs moyens de procéder. Soit, il écrit bêtement un programme, sans se soucier de sa rapidité d’exécution. Si cela peut éventuellement faire l’affaire sur un programme de 20 lignes, lorsque ce dernier atteint 10 000, 100 000, 1 million ou plusieurs millions de lignes, il devient trop lent et inutilisable. Soit, il essaie d’optimiser son programme afin de minimiser le temps d’exécution. Il crée et réutilise alors un certain nombre d’algorithmes pour arriver à ses fins.

Les informaticiens de talent, en particulier avec un sens poussé de l’algorithmique, sont donc essentiels à la micro-informatique et à tout ce qui en découle (le web, le mobile, etc.). C’est pour cette raison que des entreprises comme Google, Facebook, Microsoft ou Apple cherchent à s’entourer des meilleurs informaticiens et qu’ils peuvent offrir un salaire annuel de plus de 100 000$ pour un jeune diplômé d’informatique (aux USA).

Les algorithmes révolutionnent votre quotidien

Si les algorithmes sont donc au coeur des programmes informatiques pour des raisons de performance, ils révolutionnent aussi votre quotidien.

L’exemple le plus connu est Google. Au départ, Google n’est rien d’autre qu’un algorithme qui permet, à partir d’une recherche, de trouver les pages web les plus pertinentes. Cet algorithme est nommé le « pagerank » (il a beaucoup évolué depuis et le moteur de recherche de Google se décompose maintenant en une myriade d’algorithmes…).

Le moteur qui permet à Amazon de vous suggérer des produits et vous faire acheter plus est aussi la résultante de plusieurs algorithmes.

La publicité sur internet est le fruit d’algorithmes complexes. Criteo, la société française qui fait ce que l’on appelle sur « retargeting publicitaire », qui s’est introduite en bourse à New York il y a quelques jours et qui est valorisée aux alentours de 1.5 milliards de dollars, vend des algorithmes à des annonceurs publicitaires.

Les applications sont de plus en plus nombreuses et sortent du strict cadre de l’informatique : biotechnologies, robotique, marketing, industrie, etc.

3. Pour aller plus loin

J’espère vous avoir convaincu de l’importance des algorithmes. Pour aller plus loin, si vous n’avez pas peur de la technique, je ne saurais que vous conseiller les quelques ressources suivantes (en anglais) :

  • Le livre de référence de Robert Sedgewick et Kevin Wayne: Algorithms (4th edition) et son cours partie 1 et partie 2 en anglais sur Coursera ainsi que le site du livre et du cours avec tous les codes. De nombreux exemples et exercices en Java.
  • Un autre livre incontournable : Introduction to Algorithms, Thomas H. Cormen & al. et le cours du MIT disponible ici.
  • Les 3 premiers volumes de The Art of Computer Programming (TAOCP) de Donald Knuth sont encore des références malgré leurs dates d’édition (1999). En revanche, ce livre est moins accessible : Bill Gates aurait dit de lui envoyer votre CV si vous comprenez ce bouquin en entier (plus d’infos ici)
  • Algorithms + Data Structures = Programs, de N. Wirth est moins complet que les précédents ouvrages mais peut s’avérer être une bonne introdution (366 pages).
  • Cours d’algorithmique de Stanford sur Coursera. Un peu moins appliqué que celui de Princeton.
  • Un site pour s’entraîner : Topcoder
  • How search works par Google
  • La liste des algorithmes connus sur Wikipédia
  • Le tri rapide (quicksort) : sans doute l’un des algorithmes les plus élégants qui existe.
  • Le cours de l’X sur Coursera. Je ne l’ai pas suivi mais il a l’air bien construit et est en Français. De nombreux exemples et exercices en Java.
Qu’est ce qu’un algorithme ?

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *