Algorithmique¶
Quoi ?¶
Un algorithme permet de décrire la solution d’un problème étape par étape, afin qu’elle soit intelligible par une machine. Pour résoudre un problème informatique, il faut commencer par le décomposer en sous‑problèmes. Et pour chacun de ces sous‑problèmes, il faut décrire précisément les opérations à réaliser pour le résoudre.
Il existe de nombreux algorithmes qui permettent de résoudre un problème, mais ils ne se valent pas tous. L’algorithmique étudie les propriétés des algorithmes, afin de nous aider à décider quel est le meilleur algorithme à utiliser.
Pourquoi ?¶
Les algorithmes sont partout. Ils analysent vos photos, vos déplacements et votre activité sur des plateformes informatiques. Ils vous proposent des contenus à regarder et composent votre fil d’actualité. Il est important de comprendre ce qu’il y a derrière.
Comment ?¶
Dans un premier temps nous allons nous intéresser à la notion même d’algorithme : comment décomposer la solution d’un problème en étapes ?
Dans un deuxième temps, nous allons aborder la notion de complexité qui permet de comparer différents algorithmes entre eux. Si plusieurs solutions existent, alors il faut choisir la plus rapide. Mais comment déterminer la vitesse d’un algorithme ? Et sera‑t‑elle la solution la plus rapide dans tous les cas ?
Finalement, si vous le souhaitez, vous pouvez ouvrir la porte merveilleuse de la récursivité, à la manière des Infinity Mirror Room de Yayoi Kusama.
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.
Pouvoir déterminer quelle est la meilleure solution pour un problème donné, en fonction de critères objectifs.
Comprendre pourquoi certains problème simples n’ont pas de solution exacte.
[Optionnel] Créer des fonctions récursives, qui s’appellent elles‑mêmes.
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.
Margaret Hamilton 🇺🇸
1902‑1985
L’informaticienne Margaret Hamilton a permis le succès de la mission Apollo 11, la première mission «humaine» sur la Lune. Elle a inventé le terme de software engineering (génie logiciel), qui vise à appliquer les principes de l’ingénierie à la création de logiciels.