50 clés pour comprendre les maths
60
chronologie
Vers 300 av. J.-C.
L’algorithme d’Euclide est publié
dans le Livre 7 des Éléments.
Vers l’an 300 ap. J.-C.
Sun Tzu découvre le théorème chinois.
D’abord, un algorithme est un programme. C’est une liste d’instructions du genre
« vous faites ceci et ensuite cela ». On voit pourquoi les ordinateurs aiment les algorithmes : ils sont doués pour suivre des instructions sans jamais s’en écarter. Certains
mathématiciens pensent que les algorithmes sont ennuyeux parce qu’ils sont répétitifs. Or, écrire un algorithme pour le traduire ensuite en un code informatique long de
plusieurs centaines de lignes comportant des instructions mathématiques est un véritable exploit. Le risque majeur, c’est que les choses tournent horriblement mal. Écrire
un algorithme est un défi créatif. Il y a souvent plusieurs méthodes possibles pour
exécuter la même tâche et il faut choisir la meilleure. Quelques algorithmes ne sont
parfois pas « à la hauteur » et d’autres sont parfois totalement inefficaces parce qu’ils
musardent ça et là. D’autres encore sont rapides mais donnent une réponse incorrecte.
C’est un peu comme la cuisine. Il doit y avoir des centaines de recettes (d’algorithmes)
pour cuisiner la dinde aux marrons, et nous ne voulons pas d’un mauvais algorithme
le seul jour de l’année où l’on en a réellement besoin. Nous avons donc les ingrédients
ainsi que les instructions. La recette (abrégée) pourrait commencer ainsi :
• Remplissez la dinde de farce.
• Beurrez la dinde généreusement.
• Salez, poivrez, et parsemez la dinde de thym.
• Faites rôtir à 240° C pendant 3 heures et demie.
• Laissez reposer la dinde
1
/ 2 heure.
Il suffit de suivre pas à pas l’ordre séquentiel des instructions de l’algorithme. La
seule chose d’ordinaire présente dans un algorithme mathématique mais qui fait
Al-Khwarizmi nous a donné le mot « algèbre », mais c’est dans son ouvrage
du ix
e siècle sur l’arithmétique que le mot « algorithme » apparut pour la première
fois. C’est un concept utile à la fois aux mathématiciens et aux informaticiens,
mais de quoi s’agit-il ? Si nous pouvons répondre à cette question, nous sommes
à deux doigts de comprendre l’algorithme d’Euclide.
L’algorithme
d’Euclide
15
60
chronologie
Vers 300 av. J.-C.
L’algorithme d’Euclide est publié
dans le Livre 7 des Éléments.
Vers l’an 300 ap. J.-C.
Sun Tzu découvre le théorème chinois.
D’abord, un algorithme est un programme. C’est une liste d’instructions du genre
« vous faites ceci et ensuite cela ». On voit pourquoi les ordinateurs aiment les algorithmes : ils sont doués pour suivre des instructions sans jamais s’en écarter. Certains
mathématiciens pensent que les algorithmes sont ennuyeux parce qu’ils sont répétitifs. Or, écrire un algorithme pour le traduire ensuite en un code informatique long de
plusieurs centaines de lignes comportant des instructions mathématiques est un véritable exploit. Le risque majeur, c’est que les choses tournent horriblement mal. Écrire
un algorithme est un défi créatif. Il y a souvent plusieurs méthodes possibles pour
exécuter la même tâche et il faut choisir la meilleure. Quelques algorithmes ne sont
parfois pas « à la hauteur » et d’autres sont parfois totalement inefficaces parce qu’ils
musardent ça et là. D’autres encore sont rapides mais donnent une réponse incorrecte.
C’est un peu comme la cuisine. Il doit y avoir des centaines de recettes (d’algorithmes)
pour cuisiner la dinde aux marrons, et nous ne voulons pas d’un mauvais algorithme
le seul jour de l’année où l’on en a réellement besoin. Nous avons donc les ingrédients
ainsi que les instructions. La recette (abrégée) pourrait commencer ainsi :
• Remplissez la dinde de farce.
• Beurrez la dinde généreusement.
• Salez, poivrez, et parsemez la dinde de thym.
• Faites rôtir à 240° C pendant 3 heures et demie.
• Laissez reposer la dinde
1
/ 2 heure.
Il suffit de suivre pas à pas l’ordre séquentiel des instructions de l’algorithme. La
seule chose d’ordinaire présente dans un algorithme mathématique mais qui fait
Al-Khwarizmi nous a donné le mot « algèbre », mais c’est dans son ouvrage
du ix
e siècle sur l’arithmétique que le mot « algorithme » apparut pour la première
fois. C’est un concept utile à la fois aux mathématiciens et aux informaticiens,
mais de quoi s’agit-il ? Si nous pouvons répondre à cette question, nous sommes
à deux doigts de comprendre l’algorithme d’Euclide.
L’algorithme
d’Euclide
15