Éducation Nationale Française · Seconde
Algorithmique : les classiques
I
Le balayage
Décrire un algorithme, l'exécuter à la main et le vérifier sont déjà acquis. Tout cela s'applique aux algorithmes dont les mathématiques se servent depuis des siècles : encadrer un nombre sans écriture décimale exacte, trouver le plus grand commun diviseur de deux nombres, dire si un système de deux équations a une seule solution, estimer une probabilité en lançant des dés. Chacun se rencontre dans un chapitre de mathématiques pour ce à quoi il sert ; ici il se rencontre pour ce qu'il est : une suite d'étapes qui se trace, dont la terminaison se justifie et dont le coût se compte. Compter ce coût est ce qui s'y ajoute, et le balayage et la dichotomie existent pour être comparés.
Définition — Encadrer
Encadrer un nombre, c'est donner deux nombres entre lesquels il se trouve, et la différence des deux est l'amplitude de l'encadrement. Un nombre sans écriture décimale exacte, comme le côté d'un carré d'aire \(2\), se connaît par des encadrements d'amplitude de plus en plus petite : chaque nouvelle décimale de son écriture est un encadrement dix fois plus fin. Un algorithme qui encadre ne donne pas le nombre ; il donne deux nombres et la promesse que la réponse est entre eux. Définition — Le balayage
Le balayage avance d'un point de départ vers la réponse, par pas de taille fixée, et s'arrête au premier point où un test change de réponse. Il s'emploie sous une hypothèse, sans laquelle il ne conclut rien : la grandeur testée varie toujours dans le même sens, si bien que le test change de réponse une seule fois sur l'intervalle parcouru. Sous cette hypothèse la réponse cherchée est entre le dernier point d'avant le changement et le premier d'après, donc l'encadrement obtenu a l'amplitude d'un pas. Rien n'est deviné : l'algorithme ne fait que marcher et tester. Méthode — Encadrer par balayage
- Nommer le test qui change de réponse au nombre cherché, et un point de départ où il répond d'une façon.
- Choisir le pas : c'est l'amplitude de l'encadrement obtenu, donc un pas de \(0{,}1\) donne une décimale, un pas de \(0{,}01\) en donne deux.
- Avancer pas à pas tant que le test garde sa première réponse.
- Lire l'encadrement : le premier point où le test a changé, et celui d'avant.
- Balayer avec des entiers quand le pas est décimal : compter les pas dans un compteur entier et diviser une seule fois à la fin, jamais ajouter le pas à lui-même.
Exemple
Le nombre \(\sqrt{2}\) est entre \(1\) et \(2\). Exécuter à la main l'algorithme ci-dessous et donner ce qu'il affiche. Le compteur k compte des dixièmes, donc le test k \(\times\) k < 200 demande si le carré de k dixièmes est inférieur à \(2\). k ← 10
Tant que k × k < 200
k ← k + 1
Fin Tant que
Afficher k - 1
Afficher k| Instruction | \(k\) | \(k \times k < 200\) | Affichage |
| départ | \(10\) | ||
| tour 1 | \(11\) | \(100 < 200\) vrai | |
| tour 2 | \(12\) | \(121 < 200\) vrai | |
| tour 3 | \(13\) | \(144 < 200\) vrai | |
| tour 4 | \(14\) | \(169 < 200\) vrai | |
| tour 5 | \(15\) | \(196 < 200\) vrai | |
| fin | \(15\) | \(225 < 200\) faux | |
| Afficher \(k - 1\) | \(15\) | \(14\) | |
| Afficher \(k\) | \(15\) | \(15\) |
14 puis 15, qui lus comme des dixièmes donnent \(1{,}4 < \sqrt{2} < 1{,}5\). Cinq tours, un par dixième parcouru de \(1\) à \(1{,}5\). La boucle se termine pour la raison que toute boucle doit nommer : le variant est le nombre entier k, qui croît de un à chaque tour pendant que la condition maintient son carré sous \(200\), et un nombre entier ne peut pas croître indéfiniment sous une borne. L'encadrement a l'amplitude d'un pas, un dixième, soit exactement une décimale de \(\sqrt{2}\). Exemple
Qu'affiche le programme suivant ? k = 10
while k * k < 200:
k = k + 1
print((k - 1) / 10)
print(k / 10)1.4
1.5Définition — Le coût d'un balayage
Le coût d'un algorithme est le nombre d'opérations qu'il fait, compté en fonction de ce qu'il reçoit. Une opération est ici une opération arithmétique ou un test ; nommer une valeur ne coûte rien. Le compte se fait sur l'algorithme, jamais en mesurant une exécution. Un balayage de pas \(p\) sur un intervalle de longueur \(L\) fait au plus autant de tours qu'il y a de pas dans l'intervalle, c'est-à-dire \(L \div p\) quand la division tombe juste et l'entier au-dessus sinon, puisque chaque tour avance de \(p\) et que la marche ne peut pas sortir de l'intervalle. Pour encadrer à \(n\) décimales sur un intervalle de longueur \(1\), le pas vaut \(10^{-n}\) et le coût est d'au plus \(10^n\) tours : c'est le pire cas, atteint quand la réponse est à l'autre bout, et une décimale de plus le multiplie par dix. Méthode — Compter les tours d'une boucle
- Dire ce qu'avance un tour : un pas, une unité d'un compteur, une division de l'amplitude par deux.
- Dire ce qui arrête la boucle : la borne que teste sa condition.
- Compter combien d'avancées tiennent entre le départ et cette borne, sous la forme d'un nombre écrit avec ce que reçoit l'algorithme.
- Vérifier le compte sur une trace déjà écrite, sur un petit cas, où les tours se comptent à la main.
- Ne jamais mesurer une exécution : le compte est une propriété de l'algorithme, et une machine deux fois plus rapide n'y change rien.
Ce que suppose le balayage
Le balayage trouve le premier point où le test change, et rien de plus. Si le test change deux fois à l'intérieur d'un pas, la marche passe par-dessus les deux changements sans les voir, et l'encadrement obtenu est faux. L'algorithme s'emploie donc là où la grandeur testée varie toujours dans le même sens, c'est-à-dire là où elle est monotone.
Ajouter dix fois un dixième
Une machine écrit les décimaux en base deux, où un dixième n'a pas d'écriture exacte, si bien qu'ajouter
0.1 à lui-même accumule une minuscule erreur à chaque tour. Le programme ci-dessous le montre. x = 0
for k in range(10):
x = x + 0.1
print(x)
print(x == 1)0.9999999999999999
FalseCompétences à pratiquer
- Prédire
- Balayer à la main
- Traduire
- Compter les tours
II
La dichotomie
Le balayage marche vers la réponse. Il y a une autre façon d'y arriver : couper l'intervalle en deux, regarder quelle moitié contient la réponse, la garder, et recommencer. Rien n'est parcouru ; à chaque tour la moitié de ce qui restait est jetée. Les deux algorithmes répondent à la même question et sont tous deux justes, donc la seule chose qui les sépare est ce qu'ils coûtent, et c'est ce coût que la comparaison tranche enfin.
Définition — La dichotomie
La dichotomie part d'un encadrement [a ; b] dont on sait qu'il contient la réponse, prend son milieu m, et garde la moitié qui la contient encore : [a ; m] ou [m ; b], selon le même test qu'employait le balayage. Elle repose sur la même hypothèse : la grandeur testée varie toujours dans le même sens, si bien que le test dit quelle moitié contient encore la réponse (si la réponse est le milieu lui-même, les deux moitiés la contiennent). Chaque tour divise l'amplitude par deux, et l'algorithme s'arrête quand l'amplitude est inférieure à la précision voulue.
Ce qui est vrai à chaque tour
La phrase la réponse est entre
a et b est vraie avant le premier tour, parce que l'encadrement de départ a été choisi ainsi, et chaque tour la garde vraie, parce que la moitié jetée est celle dont le test dit que la réponse n'y est pas. Elle est donc vraie quand la boucle s'arrête, et c'est elle qui fait du dernier encadrement une réponse plutôt que deux nombres. Une phrase de cette sorte, vraie à chaque tour d'une boucle, est ce qui rend un algorithme juste pour toutes ses entrées, là où une trace ne le montre juste que pour une.
Méthode — Encadrer par dichotomie
- Partir d'un encadrement qui contient la réponse, et nommer le test qui distingue les deux moitiés.
- Prendre le milieu de l'encadrement courant.
- Garder la moitié où le test change encore de réponse, et jeter l'autre.
- Répéter tant que l'amplitude est supérieure à la précision voulue.
- Lire l'encadrement, et dire la phrase restée vraie à chaque tour.
Exemple
Exécuter à la main l'algorithme ci-dessous et donner ce qu'il affiche. Il encadre \(\sqrt{2}\) à partir de l'encadrement [1 ; 2] jusqu'à une amplitude d'au plus un dixième. a ← 1
b ← 2
Tant que b - a > 0.1
m ← (a + b) ÷ 2
Si m × m < 2 alors
a ← m
Sinon
b ← m
Fin Si
Fin Tant que
Afficher a
Afficher b| Instruction | \(a\) | \(b\) | \(b - a\) | \(b - a > 0{,}1\) | Affichage |
| départ | \(1\) | \(2\) | \(1\) | ||
| tour 1 : \(m = 1{,}5\), \(b \leftarrow m\) | \(1\) | \(1{,}5\) | \(0{,}5\) | vrai | |
| tour 2 : \(m = 1{,}25\), \(a \leftarrow m\) | \(1{,}25\) | \(1{,}5\) | \(0{,}25\) | vrai | |
| tour 3 : \(m = 1{,}375\), \(a \leftarrow m\) | \(1{,}375\) | \(1{,}5\) | \(0{,}125\) | vrai | |
| tour 4 : \(m = 1{,}4375\), \(b \leftarrow m\) | \(1{,}375\) | \(1{,}4375\) | \(0{,}0625\) | vrai | |
| fin | \(1{,}375\) | \(1{,}4375\) | \(0{,}0625\) | faux | |
| Afficher \(a\) | \(1{,}375\) | \(1{,}4375\) | \(0{,}0625\) | \(1{,}375\) | |
| Afficher \(b\) | \(1{,}375\) | \(1{,}4375\) | \(0{,}0625\) | \(1{,}4375\) |
a et b est vraie à chaque ligne, ce qui permet de lire la dernière comme une réponse. Exemple
Qu'affiche le programme suivant ? a = 1
b = 2
while b - a > 0.1:
m = (a + b) / 2
if m * m < 2:
a = m
else:
b = m
print(a)
print(b)1.375
1.4375Définition — Le coût d'une dichotomie
Chaque tour divise l'amplitude par deux, donc après \(t\) tours une amplitude de départ \(L\) est devenue \(L \div 2^t\). Atteindre une amplitude d'au plus \(p\) demande donc le premier nombre de tours \(t\) pour lequel \(2^t\) atteint \(L \div p\) : le coût croît comme le nombre de fois que \(2\) doit être multiplié par lui-même pour atteindre ce quotient, et non comme le quotient lui-même. En décimales, gagner une décimale de plus coûte entre trois et quatre tours, puisque \(2^3 = 8\) et \(2^4 = 16\) encadrent \(10\).
Le premier contraste de coûts
Les deux algorithmes encadrent le même nombre et sont tous deux justes. Pour une décimale sur tout un intervalle de longueur un, le balayage fait dix tours au pire et la dichotomie quatre, comme le montre sa propre trace ; l'exemple du balayage en faisait cinq, parce que la réponse était rencontrée à mi-chemin. Pour six décimales le balayage en fait un million et la dichotomie une vingtaine. L'écart ne vient pas de l'écriture, plus courte pour le balayage, mais de ce que chaque tour jette : le balayage élimine un pas, la dichotomie élimine la moitié de ce qui reste. Comparer deux algorithmes justes, c'est comparer cela, et rien d'autre.
Ce que suppose la dichotomie
La dichotomie a besoin d'un encadrement de départ qui contienne vraiment la réponse, et d'un test qui réponde d'une façon à une extrémité et de l'autre à l'autre. Sans ce premier encadrement elle n'a rien à couper ; avec une grandeur qui change deux fois de réponse dans l'intervalle, elle garde une moitié où la réponse peut ne pas être, et sa promesse tombe avec. Ces deux hypothèses s'établissent d'abord ; l'algorithme ne fait que s'y appuyer.
Compétences à pratiquer
- Prédire
- Dichotomiser à la main
- Justifier et comparer
III
Les nombres entiers
Les deux sections précédentes cherchaient un nombre sans écriture décimale exacte. Celle-ci pose sur les entiers des questions à réponse exacte : combien de diviseurs a un nombre, quel est le plus grand diviseur que deux nombres partagent. Les algorithmes sont anciens et courts, et chacun porte les trois mêmes questions que les autres : se termine-t-il, est-il juste, que coûte-t-il. La dernière réserve ici une surprise : l'un des algorithmes coûte bien moins que son écriture évidente, pour une raison qui est un fait d'arithmétique et non de programmation.
Définition — Compter les diviseurs
Un entier k divise n, ou est un diviseur de n, quand le reste de n par k est nul. Pour un entier n valant au moins \(1\), l'algorithme évident teste tous les k de 1 à n et compte ceux qui divisent : il est juste, il se termine après n tours, et il coûte n tests. Pour un nombre de dix chiffres, cela fait de l'ordre du milliard de tests, et pour un nombre de vingt chiffres dix milliards de fois plus, qu'aucune machine ne fera jamais. Méthode — S'arrêter à la racine carrée
- Apparier les diviseurs : si
kdivisen, alors le quotient denparkdivisenaussi, et les deux se multiplient pour donnern. - Remarquer que l'un des deux est petit : dans un couple dont le produit vaut
n, les deux ne peuvent pas être au-dessus de la racine carrée den, sans quoi leur produit dépasseraitn. - Ne tester que les petits, c'est-à-dire les
ktels quek \(\times\) k \(\leqslant\) n, et compter chaque couple trouvé pour deux diviseurs. - Compter une seule fois le
kdont le compagnon est lui-même, c'est-à-dire quandk \(\times\) k = n.
k \(\times\) k \(\leqslant\) n est ce qui remplace ici une racine carrée : il pose la même question avec une multiplication, exacte sur les entiers là où une racine carrée ne le serait pas. Exemple
Exécuter à la main l'algorithme ci-dessous pour n égal à \(36\) et donner la valeur qu'il affiche. c ← 0
k ← 1
Tant que k × k ≤ 36
Si reste de 36 par k = 0 alors
Si k × k = 36 alors
c ← c + 1
Sinon
c ← c + 2
Fin Si
Fin Si
k ← k + 1
Fin Tant que
Afficher c| Instruction | \(k\) | \(c\) | \(k \times k \leqslant 36\) | trouvé | Affichage |
| départ | \(1\) | \(0\) | |||
| tour \(k = 1\) | \(2\) | \(2\) | vrai | couple \((1 ; 36)\) | |
| tour \(k = 2\) | \(3\) | \(4\) | vrai | couple \((2 ; 18)\) | |
| tour \(k = 3\) | \(4\) | \(6\) | vrai | couple \((3 ; 12)\) | |
| tour \(k = 4\) | \(5\) | \(8\) | vrai | couple \((4 ; 9)\) | |
| tour \(k = 5\) | \(6\) | \(8\) | vrai | rien | |
| tour \(k = 6\) | \(7\) | \(9\) | vrai | \(6 \times 6 = 36\) | |
| fin | \(7\) | \(9\) | faux | ||
| Afficher \(c\) | \(7\) | \(9\) | \(9\) |
9. Six tours au lieu de trente-six, et tout diviseur est compté : les quatre couples en donnent huit, et \(6\), dont le compagnon est lui-même, donne le neuvième. La colonne de la condition montre où la boucle s'arrête, à \(k = 7\), puisque \(49\) dépasse \(36\). La boucle se termine pour la raison habituelle : le variant est le nombre entier k, qui croît de un à chaque tour pendant que la condition maintient son carré à au plus \(36\), et un entier ne peut pas croître indéfiniment sous une borne. L'algorithme ne regarde jamais au-dessus de la racine carrée, et il n'en a pas besoin. Définition — L'algorithme d'Euclide
Le plus grand commun diviseur de deux entiers naturels est le plus grand nombre qui les divise tous les deux. L'algorithme d'Euclide le calcule par les restes : tant que le second nombre n'est pas nul, remplacer le couple (a ; b) par le couple (b ; r), où r est le reste de a par b ; quand le second devient nul, le premier est la réponse. Les deux nombres sont des entiers naturels et l'un au moins n'est pas nul, puisqu'un couple de deux zéros n'a pas de plus grand commun diviseur : tout entier divise zéro. Méthode — Justifier l'algorithme d'Euclide
- Terminaison : le second nombre du couple est un entier naturel, et à chaque tour il devient le reste de la division de
aparb, donc il est strictement plus petit que lebqu'il remplace, et un reste n'est jamais négatif. Un entier naturel ne peut pas décroître indéfiniment au-dessus de zéro, donc le second nombre atteint zéro. - Correction : écrire la division sous la forme \(a = q \times b + r\). Un nombre qui divise
aetbdivise \(a - q \times b\), c'est-à-direr; et un nombre qui divisebetrdivise \(q \times b + r\), c'est-à-direa. Les deux couples ont donc exactement les mêmes diviseurs communs, et le plus grand d'entre eux voyage inchangé de tour en tour. - Lecture de la réponse : quand le second est nul, les diviseurs communs du couple sont les diviseurs du premier, dont le plus grand est le premier lui-même.
- Désigner la colonne du tableau d'états qui porte l'argument : le second nombre, strictement décroissant, est le variant ; le plus grand commun diviseur, inchangé, est ce qui reste vrai à chaque tour.
Exemple
Exécuter à la main l'algorithme d'Euclide sur \(1071\) et \(462\), et donner la valeur qu'il affiche. a ← 1071
b ← 462
Tant que b ≠ 0
r ← reste de a par b
a ← b
b ← r
Fin Tant que
Afficher a| Instruction | \(a\) | \(b\) | \(r\) | \(b \neq 0\) | Affichage |
| départ | \(1071\) | \(462\) | |||
| tour 1 | \(462\) | \(147\) | \(147\) | vrai | |
| tour 2 | \(147\) | \(21\) | \(21\) | vrai | |
| tour 3 | \(21\) | \(0\) | \(0\) | vrai | |
| fin | \(21\) | \(0\) | \(0\) | faux | |
| Afficher \(a\) | \(21\) | \(0\) | \(0\) | \(21\) |
21. Trois tours, et la colonne \(b\) porte les deux arguments à la fois : elle vaut \(462\), \(147\), \(21\), \(0\), strictement décroissante, ce pourquoi la boucle se termine ; et le plus grand commun diviseur du couple de chaque ligne vaut \(21\) à toutes, ce pourquoi la dernière ligne se lit comme la réponse. Écrits comme des divisions, les trois tours sont \(1071 = 2 \times 462 + 147\), puis \(462 = 3 \times 147 + 21\), puis \(147 = 7 \times 21 + 0\) : l'algorithme est la chaîne de ces divisions, et rien d'autre.
Trois coûts rencontrés jusqu'ici
Le balayage coûte autant de tours qu'il y a de pas à parcourir, au plus \(10^n\) pour \(n\) décimales. La dichotomie coûte le nombre de fois que deux doit être multiplié par lui-même pour atteindre la même précision, entre trois et quatre tours par décimale. Le test des diviseurs coûte autant de tours qu'il y a d'entiers jusqu'à la racine carrée de
n. Trois croissances, trois algorithmes, et la même façon de mesurer : compter les tours en fonction de ce que l'algorithme reçoit, sur l'algorithme lui-même, sans l'exécuter.
Compétences à pratiquer
- Prédire
- Compter les diviseurs et appliquer l'algorithme d'Euclide
IV
Décider et simuler
Tout algorithme ne répète pas. Certains répondent à une question en calculant un nombre et en le regardant : un système de deux équations a-t-il une seule solution. Leur coût est le même quoi qu'ils reçoivent, et toute leur difficulté est dans le nombre calculé, qui vient des mathématiques et non de l'algorithme. D'autres répètent un très grand nombre de fois exprès, parce que ce qui est voulu n'est pas une réponse mais une proportion : lancer mille fois un dé pour voir combien de fois sort un six. Les deux sortes se placent côte à côte, et la comparaison se clôt sur ce qu'une fréquence simulée dit et ne dit pas.
Définition — Décider par un calcul
Certaines questions se répondent sans aucune répétition : un nombre est calculé à partir de ce qui est donné, et la réponse se lit sur ce nombre, le plus souvent sur sa nullité. Un tel algorithme n'a pas de boucle, donc rien à justifier quant à sa terminaison, et son coût est un nombre fixe d'opérations, compté comme pour tout autre algorithme. Deux entrées peuvent prendre deux branches de longueurs différentes, mais aucune de ces longueurs ne croît avec les nombres reçus. Il lui faut seulement un résultat mathématique disant quel nombre calculer et comment le lire. Méthode — Décider si trois points sont alignés
- Construire les deux vecteurs qui partent du même point : de \(A\) vers \(B\), et de \(A\) vers \(C\).
- Calculer le nombre \(x \times y_2 - y \times x_2\) à partir de leurs coordonnées \((x ; y)\) et \((x_2 ; y_2)\), le nombre appelé leur déterminant.
- Lire la réponse : les trois points sont alignés exactement quand ce nombre est nul.
- Remarquer que rien ne se répète : cinq soustractions et deux multiplications, quels que soient les points.
Exemple
Exécuter à la main l'algorithme ci-dessous pour \(A(1 ; 2)\), \(B(4 ; 3)\) et \(C(7 ; 5)\), et donner ce qu'il affiche. x ← xB - xA
y ← yB - yA
x2 ← xC - xA
y2 ← yC - yA
d ← x × y2 - y × x2
Si d = 0 alors
Afficher "aligned"
Sinon
Afficher "not aligned"
Fin Si| Instruction | \(x\) | \(y\) | \(x_2\) | \(y_2\) | \(d\) | \(d = 0\) | Affichage |
| \(x \leftarrow x_B - x_A\) | \(3\) | ||||||
| \(y \leftarrow y_B - y_A\) | \(3\) | \(1\) | |||||
| \(x_2 \leftarrow x_C - x_A\) | \(3\) | \(1\) | \(6\) | ||||
| \(y_2 \leftarrow y_C - y_A\) | \(3\) | \(1\) | \(6\) | \(3\) | |||
| \(d \leftarrow x \times y_2 - y \times x_2\) | \(3\) | \(1\) | \(6\) | \(3\) | \(3\) | ||
| Si \(d = 0\) | \(3\) | \(1\) | \(6\) | \(3\) | \(3\) | faux | |
| Afficher | \(3\) | \(1\) | \(6\) | \(3\) | \(3\) | not aligned |
not aligned. Le déterminant vaut \(3 \times 3 - 1 \times 6 = 3\), qui n'est pas nul. Avec \(C(7 ; 4)\) à la place, le second vecteur serait \((6 ; 2)\) et le déterminant \(3 \times 2 - 1 \times 6 = 0\) : les trois points seraient alignés. Sept opérations dans les deux cas, cinq soustractions et deux multiplications, et aucune boucle — la trace porte une ligne par instruction et s'arrête là, puisque rien n'est répété. Méthode — Résoudre un système de deux équations par son déterminant
Le système est \(a_1x + b_1y = c_1\) et \(a_2x + b_2y = c_2\). Multiplier la première équation par \(b_2\), la seconde par \(b_1\), puis soustraire la seconde de la première élimine \(y\) : \((a_1b_2 - b_1a_2)x = c_1b_2 - b_1c_2\). Le nombre \(d = a_1b_2 - b_1a_2\) s'appelle le déterminant du système. Quand \(d\) n'est pas nul, diviser par lui donne \(x = (c_1b_2 - b_1c_2) \div d\), et éliminer \(x\) de la même façon donne \(y = (a_1c_2 - c_1a_2) \div d\). - Calculer le déterminant \(d = a_1b_2 - b_1a_2\) à partir des quatre coefficients des inconnues.
- Y lire le cas : quand \(d\) est nul le système n'a pas de solution unique, et l'algorithme le dit au lieu de calculer.
- Sinon appliquer les deux quotients qui résolvent le système, et les afficher.
- Compter ce qu'il coûte : aucune boucle, donc les mêmes opérations pour tout système, et la branche est la seule chose qui varie.
d ← a1 × b2 - b1 × a2
Si d = 0 alors
Afficher "no single solution"
Sinon
x ← (c1 × b2 - b1 × c2) ÷ d
y ← (a1 × c2 - c1 × a2) ÷ d
Afficher x
Afficher y
Fin SiExemple
Exécuter à la main l'algorithme de la Méthode sur le système \(2x + 3y = 8\) et \(5x - y = 3\), dont les coefficients sont \(a_1 = 2\), \(b_1 = 3\), \(c_1 = 8\), \(a_2 = 5\), \(b_2 = -1\), \(c_2 = 3\), et donner ce qu'il affiche. | Instruction | \(d\) | \(x\) | \(y\) | \(d = 0\) | Affichage |
| départ | |||||
| \(d \leftarrow a_1b_2 - b_1a_2\) | \(-17\) | ||||
| Si \(d = 0\) | \(-17\) | faux | |||
| \(x \leftarrow (c_1b_2 - b_1c_2) \div d\) | \(-17\) | \(1\) | |||
| \(y \leftarrow (a_1c_2 - c_1a_2) \div d\) | \(-17\) | \(1\) | \(2\) | ||
| Afficher \(x\) | \(-17\) | \(1\) | \(2\) | \(1\) | |
| Afficher \(y\) | \(-17\) | \(1\) | \(2\) | \(2\) |
Définition — Simuler
Simuler une expérience, c'est faire tirer au hasard par une machine ce que le hasard aurait donné, un grand nombre de fois, et compter. La fréquence d'une issue est le nombre de fois où elle est sortie divisé par le nombre de tirages. Simuler donne une estimation et non une valeur : deux exécutions du même programme donnent le plus souvent deux fréquences différentes. C'est ce que l'on fait quand aucun calcul exact n'est à portée, et c'est aussi une façon de voir une probabilité déjà connue exactement. Méthode — Estimer une fréquence par simulation
- Nommer l'issue comptée, et le nombre de tirages.
- Créer le compteur à
0avant la boucle, comme pour tout accumulateur. - Répéter le tirage le nombre de fois choisi, et compter les tirages qui donnent l'issue.
- Diviser le compteur par le nombre de tirages, après la boucle.
- Dire ce que vaut le résultat : c'est une fréquence, non une probabilité. Avec beaucoup de tirages elle est le plus souvent proche de la probabilité ; il peut arriver qu'elle tombe exactement dessus, et c'est encore le hasard, non un calcul.
Exemple
Exécuter à la main l'algorithme ci-dessous. Les nombres lus sont, dans l'ordre, \(6\), \(2\), \(6\), \(4\), \(1\) et \(5\). c ← 0
Pour i allant de 1 à 6
Lire d
Si d = 6 alors
c ← c + 1
Fin Si
Fin Pour
Afficher c| Instruction | \(d\) | \(c\) | \(d = 6\) | Affichage |
| départ | \(0\) | |||
| tour 1 | \(6\) | \(1\) | vrai | |
| tour 2 | \(2\) | \(1\) | faux | |
| tour 3 | \(6\) | \(2\) | vrai | |
| tour 4 | \(4\) | \(2\) | faux | |
| tour 5 | \(1\) | \(2\) | faux | |
| tour 6 | \(5\) | \(2\) | faux | |
| Afficher \(c\) | \(5\) | \(2\) | \(2\) |
2, donc la fréquence du six sur ces six tirages vaut \(\frac{2}{6}\), c'est-à-dire \(\frac{1}{3}\) — le double de la probabilité, ce que valent six tirages. L'algorithme est un accumulateur dans une boucle bornée, et son coût se lit sur les bornes sans rien exécuter : exactement un tour par tirage, donc n tours pour n tirages. C'est le seul coût que choisit celui qui écrit l'algorithme. Exemple
Le programme ci-dessous lance mille fois un dé et affiche la fréquence du six. Que peut-on dire du nombre qu'il affiche ? import random
c = 0
for i in range(1000):
d = random.randint(1, 6)
if d == 6:
c = c + 1
print(c / 1000)
Un nombre le plus souvent proche de \(0{,}167\), et le plus souvent différent à chaque exécution : \(0{,}158\), puis \(0{,}174\), puis \(0{,}165\). Rien de certain ne peut être dit à l'avance, et c'est là le point. La probabilité du six vaut \(\frac{1}{6}\), nombre que la mathématique du hasard donne exactement ; la fréquence affichée est ce que mille tirages ont donné, et il n'y a aucune raison qu'elle vaille ce nombre — une fraction \(\frac{c}{1000}\) ne peut jamais valoir exactement \(\frac{1}{6}\), mais elle peut tomber tout près (\(0{,}167\) pour \(c = 167\)). Multiplier les tirages par cent rend les grands écarts bien moins probables sans les rendre impossibles : une simulation estime, elle ne calcule pas.
Une fréquence n'est pas une probabilité
Les deux se distinguent par ce dont elles dépendent : une probabilité est fixée par l'expérience, une fréquence par les tirages qui ont eu lieu. Exécuter deux fois le programme le montre le plus souvent, puisque les deux exécutions diffèrent le plus souvent — et si elles se trouvent coïncider, cela ne change rien : une fréquence peut changer d'une exécution à l'autre, une probabilité ne le peut pas. C'est pourquoi une réponse qui dit la probabilité vaut \(0{,}158\) est fausse même si le nombre est proche : ce que donne la simulation est une estimation, et le dire fait partie de la réponse. La théorie des probabilités dit quelle est la valeur exacte et pourquoi les fréquences se rassemblent autour d'elle ; l'algorithme ne fait que les produire.
Les coûts des algorithmes classiques
Six coûts se comparent. Un algorithme sans boucle coûte la même chose pour toute entrée. La dichotomie coûte un nombre de tours qui croît comme le nombre de fois que deux doit être multiplié par lui-même. L'algorithme d'Euclide s'observe très peu coûteux même sur de grands nombres — trois tours sur \(1071\) et \(462\) — et pourquoi il en est toujours ainsi est un résultat que le compte des tours n'établit pas. Le test des diviseurs coûte les entiers jusqu'à la racine carrée. La simulation coûte exactement le nombre de tirages demandé. Le balayage coûte dix fois plus par décimale gagnée. Compter les tours, sur l'algorithme et sans l'exécuter, précède le fait de nommer ces croissances.
Compétences à pratiquer
- Prédire
- Décider par un calcul
- Simuler
V
Pour aller plus loin
Compétences à pratiquer
- Problèmes
- Chercher des régularités dans les algorithmes
- Quiz
Aller à la section