Algorithmique et algorithmes

Il y a quelques temps, je vous présentais une initiation au codage à l’Epitech qui s’était déroulée en février dernier. Il s’agissait en fait de réaliser un jeu, classiquement proposé aux débutants : “Guess the number” (devinez le nombre). Le langage utilisé pour cette initiation était le Python. Sans que le mot ait jamais été prononcé ce jour là, ce qui se cachait derrière était en réalité une première approche de l’algorithmique.

Au sommaire :

• 1. Guess the number en Python
• 2. Guess the number en Javascript
• 3. L’algorithmique, kesako ?
  • 3.1. Comme une recette de cuisine
  • 3.2. Largement antérieure à l’informatique
• 4. L’algorithme de Guess the number
• 5. De l’algorithmique à la programmation
• Aller plus loin
• Lisez aussi

1. Guess the number en Python

Dans “Guess the number”, il s’agit en premier lieu de générer un nombre aléatoire, que le joueur va devoir deviner. A chaque essai, le programme aide ensuite le joueur en lui indiquant si le nombre est plus petit ou plus grand. On peut alors ajouter des variantes : un nombre limité d’essais, la possibilité de rejouer, etc.

En réalité, cette initiation aurait pu se faire dans n’importe quel langage informatique. En effet, la plupart des langages de programmation utilisent les mêmes concepts. Seule la syntaxe diffère d’un langage à l’autre. Ainsi, quand on connait un langage de programmation, il est assez facile d’en apprendre d’autres. C’est un peu comme avec les langues humaines : plus on connait de langues, plus il est facile d’en apprendre de nouvelles. Ainsi, ayant pratiqué le Pascal et le Visual basic il y a des années, et le PHP un peu plus tard, j’avais déjà écrit des algorithmes. Je n’ai donc pas été complètement perdu face au Python ce fameux après-midi de février 2020.

↑ — Revenir au sommaire

2. Guess the number en Javascript

La plupart des langages de programmation utilisent donc les mêmes concepts. Par exemple, voici ci-dessous le même jeu, « Guess the number », mais programmé en Javascript. Outre Python et Javascript, on pourrait tout aussi bien le réaliser en C++, C#, Java, PHP, Swift, ou tout autre langage. L’avantage avec Javascript par rapport à Python, c’est que le jeu peut fonctionner directement dans un navigateur web. En outre, l’association avec le HTML et le CSS rend l’interface plus conviviale et moins austère qu’avec le Python. Rendez vous donc sur cette simple page web pour voir le jeu en action : GuessNumberJS.htm

↑ — Revenir au sommaire

3. L’algorithmique, kesako ?

Variables, constantes, opérateurs, conditions, boucles, tableaux, fonctions… tous ces concepts sont communs à la plupart des langages informatiques. Ils sont en fait issus de l’algorithmique. Pour reprendre la métaphore des langues humaines, l’algorithmique, c’est un peu l’espéranto de l’informatique. Quand la presse parle des algorithmes des GAFA, c’est à cela qu’elle se réfère. Voici quelques algorithmes célèbres :

• Le PageRank de Google
• La Timeline de Facebook
• Les algorithmes de trading à haute fréquence
• L’algorithme de Round Robin
• Parcoursup

↑ — Revenir au sommaire

3.1. Comme une recette de cuisine

Pour expliquer ce qu’est un algorithme, on prend souvent l’analogie avec une recette de cuisine. On a des ingrédients avec lesquels on suit un processus étape par étape. Par exemple, pour confectionner une galette complète, on met d’abord le beurre sur la bilig, puis la pâte à galette qu’on étale et qu’on laisse légèrement cuire, puis le gruyère quand la galette est solidifiée, puis l’œuf dont on laisse cuire le blanc jusqu’à être « sur le plat », et enfin le jambon (agrémenté de champignons si c’est une complète champignons). Enfin, on sert la galette sur une assiette, avant de recommencer.

Voici une représentation schématique d’une recette de crêpes (et oui, avant d’étaler la pâte sur la bilig, il faut d’abord préparer celle-ci) :

↑ — Revenir au sommaire

3.2. L’algorithmique, très largement antérieure à l’informatique

Selon Wikipedia, un algorithme est un processus systématiques de résolution d’un problème, permettant de décrire précisément des étapes pour résoudre ce problème. L’algorithmique est donc l’étude et la production de règles et techniques qui sont impliquées dans la définition et la conception d’algorithmes.

Les premiers algorithmes dont on a retrouvé des descriptions datent des Babyloniens, au IIIe millénaire av. J.-C.. Ils décrivent des méthodes de calcul et des résolutions d’équations à l’aide d’exemples.

Le mot algorithme vient du nom d’un mathématicien perse du IXe siècle, Al-Khwârizmî (en arabe : الخوارزمي). Au XIIIe siècle, algorithme signifiait en Occident l’arithmétique avec les chiffres arabes.

L’algorithmique est donc très largement antérieure à l’informatique. Aujourd’hui, on utilise des algorithmes pour trouver l’amour, pour investir dans les meilleures actions, pour prédire le crime, pour organiser les résultats de recherche sur le web et pour des millions d’autres applications. Pourtant, les enquêtes d’opinion révèlent que si 80 % des Français considèrent que les algorithmes sont présents dans leur vie, 52% déclarent ne pas savoir précisément ce dont il s’agit. D’autre part, Même si la jeunesse est davantage connectée, il s’agit plus d’une génération d’utilisateurs que de codeurs.

• Le premier codeur était… une codeuse ! C’est en effet en 1842 qu’Ada Lovelace écrit le premier algorithme informatique, en travaillant sur la machine de Charles Babbage.
  La Conversation scientifique | Prénom de code : ADA – France Culture, 21/03/2020 (59 min)

↑ — Revenir au sommaire

4. L’algorithme de Guess the number

Guess the number est un jeu classiquement proposé aux débutants en programmation. Ce ne sont donc pas les tutos qui manquent sur Internet. Voici une vidéo qui explique les différentes instructions qu’il faudra prévoir pour implémenter le célèbre jeu. Dans ce cas, le nombre mystère est l’âge du capitaine, ce qui ne change rien de fondamental au processus.

Découvrez la playlist complète que Mathrix a consacré à l’algorithmique.

↑ — Revenir au sommaire

5. De l’algorithmique à la programmation

En informatique, l’algorithme est écrit dans un langage proche du langage humain. On parle alors d’un pseudo-langage. L’algorithme peut prendre différentes formes, et même être traduit en diagrammes. Voici par exemple un algorithme très simple, toujours dans la cuisine : celui qui permet au four de maintenir la bonne température :

Or, sachant qu’un ordinateur est (pour l’instant) incapable de comprendre le langage humain (ou le pseudo-langage des algorithmes), le développeur utilise un langage de programmation. Ce langage sert ainsi de passerelle entre le langage humain et le langage que la machine peut comprendre. Grâce à cet outil, le programmeur peut créer une série d’instructions que l’ordinateur peut ” comprendre “.

Voici donc la démarche complète :

1. D’abord, je définis mon problème : fabriquer un jeu Guess the number avec des règles précises, que ce soit un scénario « l’âge du capitaine » ou une possibilité de rejouer.
2. Puis, une fois les règles fixées, je réfléchis à toutes les instructions qu’il faudra donner à l’ordinateur : c’est mon algorithme.
3. Enfin, je n’ai plus qu’à traduire cet algorithme dans le langage informatique de mon choix. Au début de ce billet nous avions ainsi deux exemples, l’un en Python et l’autre en Javascript.

Les algorithmes sont au cœur de technologies émergentes révolutionnaires comme l’intelligence artificielle, les véhicules autonomes ou les assistants virtuels, le Machine Learning et le deep learning (algorithmes apprenants). Désormais les algorithmes sont capables de créer de l’intelligence, dite artificielle, et d’imiter le comportement humain. Que ce soit pour une opération chirurgicale délicate ou pour un voyage dans l’espace, des programmes sophistiqués permettent d’effectuer ces missions sans interventions humaines tout au long du processus. Dans le futur, nous continuerons à faire évoluer les algorithmes, en optimisant encore davantage leurs complexités, en accompagnant les transformations des machines, ou encore l’arrivée de nouvelles logiques telle que la logique quantique.

↑ — Revenir au sommaire

6. Aller plus loin

• Algorithmique (Wikipedia)
• Algorithme (Wikipedia)
• Qu’est ce qu’un algorithme ? Explication avec la recette des crêpes
• Algorithme : mais en fait, qu’est-ce que c’est et à quoi ça sert ?
• Top 10 des algorithmes que chaque programmeur devrait connaître
• Initiation à l’algorithmique
• Il était une fois les algorithmes
• La CNIL se prononce sur l’éthique des algorithmes et de l’intelligence artificielle
• Le virage de l’IA dans les RH
• Algorithmique répartie, à la recherche de l’universalité perdue (audio) – version vidéo
• Évolutions en cours et futures de l’informatique
• La programmation procédurale, fonctionnelle, orientée objet
• Algorithmique pour l’apprenti programmeur – OpenClassrooms

Une fois que le programmeur est convaincu que son algorithme est correct (il produit le résultat attendu, sans bug), il va essayer d’en évaluer l’efficacité. Pour obtenir un même résultat, il y a en effet plusieurs algorithmes possibles, mais d’efficacité variable. On parle de complexité algorithmique.

• Analyse de la complexité des algorithmes – Wikipedia
• Nos algorithmes pourraient-ils être plus rapides ? Video / Article – Sciences étonnantes
• P vs NP – Passe-science
• Problème P ≟ NP – Wikipedia

• Les gens voient les algorithmes comme des boites noires. Ils les utilisent ainsi sans savoir ce qu’il y a sous le capot. C’est également vrai avec les appareils numériques. En 1996, c’est pas sorcier consacrait un numéro au fonctionnement de l’ordinateur, à travers une visite du Computer Museum sur le campus du MIT à Boston. Même si les mémoires flash (clés USB, carte SD, disques SSD…) ont remplacé la disquette, les principes exposés restent valables : code binaire, portes logiques, transistors des puces, pixels, programmes, mémoire vive, mémoire morte, etc.
  Ordinateur tout un programme – C’est pas sorcier

↑ — Revenir au sommaire

Lisez aussi

• Promotion de la littératie : qui va s’en occuper?
• Du bon usage de l’Internet documentaire
• Les NTIC, des technologies pas si nouvelles que ça!
• Python, une initiation
• Quel langage informatique apprendre en 2020 ?
• Frameworks JavaScript
• Frameworks JS : une longue histoire
• Svelte, un framework JS à suivre
• JavaScript : un langage ou des langages?