1. Introduction¶
Quoi ?¶
Il y a de fortes chances que vous ayez déjà entendu parler d’algorithmes dans les médias. Il y a aussi de fortes chances que ce mot évoque pour vous des notions bien différentes de celles de votre voisin. L’objectif de ce chapitre est de vous éclairer sur la notion d’algorithme et la distinction avec la notion de programme informatique.
Pourquoi ?¶
Les algorithmes existent depuis des millénaires. On doit le nom d’algorithme à Al-Khwârizmî, mathématicien perse né en l’an 780 dont les ouvrages ont contribué à la popularisation des chiffres arabes en Europe, ainsi que la classification de plusieurs algorithmes connus à ce moment. D’ailleurs l’algorithme le plus connu, l’algorithme d’Euclide, date environ de l’an 300 av J.-C. et permet de calculer le plus grand diviseur commun de deux nombres. Si Euclide a bien laissé des traces écrites de cet algorithme, il est vraisemblable qu’il ait puisé cette connaissance auprès de disciples de Pythagore lui-même.
Les algorithmes sont devenus très populaires aujourd’hui grâce à la machine qui a permis de les automatiser. Que ce soit dans votre smartphone, sur un ordinateur ou dans un système embarqué, ils permettent de résoudre une quantité de problèmes, facilement et avec une rapidité impressionnante.
Comment ?¶
Dans un premier temps nous allons nous intéresser à la notion même d’algorithme : qu’est-ce qui caractérise un algorithme et comment le faire exécuter par une machine ? Nous allons voir que pour un problème donné il existe de nombreuses solutions, mais que toutes ces solutions ne sont pas de bonnes solutions, selon le contexte dans lequel on tente de résoudre le problème. Dans un deuxième temps nous chercherons à départager ces différentes solutions.