Introduction¶
Quoi ?¶
Nous avons tous entendu parler des algorithmes dans les médias. Normal, c’est le mot à la mode et que tout le monde utilise sans vraiment le comprendre. Ils sont partout, ils font toutes sortes de choses, même nous manipuler. Pourquoi en parle‑t‑on de la même manière que des extraterrestres ? Dans ce cours, nous allons tenter de revenir sur terre, parce que les algorithmes ce n’est pas si compliqué que ça. On apprendra à les définir, à les faire marcher et surtout à reconnaître la différence entre un programme et un algorithme, ainsi qu’entre un « bon » et un « mauvais » algorithme.
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.
Objectifs d’apprentissage¶
À la fin de ce chapitre, vous saurez ce qu’est un algorithme et vous serez capable de transcrire des algorithmes en programmes. Vous saurez résoudre des problèmes, en décomposant leur solution en étapes à suivre. Vous verrez également que pour un même problème, on peut avoir plusieurs solutions avec des propriétés, avantages et désavantages différents.
Se familiariser avec la notion d’algorithme.
Savoir résoudre des problèmes, en décomposant leur solution en étapes à suivre.
Savoir que pour un même problème, on peut avoir plusieurs solutions avec différents propriétés, avantages et désavantages.
Être capable de transcrire un algorithme dans un programme.
Bienvenue dans le monde fascinant des algorithmes.
Personnages‑clés¶
Al‑Khwârizmî 🇺🇿
780‑850
Considéré comme le père de l’algèbre Al‑Khwârizmî a vécu au VIII\(^{e}\) siècle dans le Moyen‑Orient. Il est l’auteur de plusieurs ouvrages de mathématiques, d’astronomie et de géographie. Son nom est à l’origine du mot algorithme.
Edsger Dijkstra 🇳🇱
1930‑2002
Edsger Wybe Dijkstra est un mathématicien et informaticien néerlandais du XX\(^{e}\) siècle. Il reçoit en 1972 le prix Turing pour ses contributions sur la science et l’art des langages de programmation et au langage Algol. Il est le concepteur de l’algorithme éponyme de recherche du plus court chemin.