Quatre algorithmes Python à maîtriser : seuil, dichotomie, Euler et simulation

Ta calculatrice affiche ln(2) ≈ 0,693147 en un éclair, un logiciel de banque t'annonce l'année où ton livret dépassera 2 000 €, un simulateur prévoit la trajectoire d'une fusée. Pas de magie là-dedans : des boucles qui répètent un calcul simple jusqu'à atteindre la précision voulue. Au bac, quatre algorithmes reviennent sans cesse ; tu dois savoir les lire, les compléter et les écrire.

1. L'algorithme de seuil

La suite définie par u₀ = 100 et uₙ₊₁ = 0,9uₙ + 30 est croissante et converge vers 300. À partir de quel rang dépasse-t-elle 290 ?

def seuil(s):
 n = 0
 u = 100
 while u <= s:
 u = 0.9 * u + 30
 n = n + 1
 return n

seuil(290) renvoie 29. La boucle while tourne tant que sa condition est vraie : on y écrit la négation de ce que l'on cherche (u ≤ 290 tant que le seuil n'est pas dépassé). Attention : si la suite n'atteint jamais le seuil, comme avec seuil(300), la boucle ne s'arrête pas.

Vérification par le calcul. On montre que uₙ = 300 − 200 × 0,9ⁿ. Alors uₙ > 290 équivaut à 0,9ⁿ < 0,05, soit n × ln(0,9) < ln(0,05), donc n > ln(0,05)ln(0,9) ≈ 28,4 (on change le sens de l'inégalité car ln(0,9) < 0). Le premier rang est bien 29.

2. La dichotomie

Si f est continue sur [a ; b] et si f(a) et f(b) sont de signes contraires, le théorème des valeurs intermédiaires assure que f s'annule sur [a ; b]. On coupe l'intervalle en deux, on garde la moitié où le signe change, et on recommence.

def dichotomie(f, a, b, e):
 while b - a > e:
 m = (a + b) / 2
 if f(a) * f(m) <= 0:
 b = m
 else:
 a = m
 return a, b

Exemple. Pour f(x) = x³ + x − 1 sur [0 ; 1], f(0) = −1 < 0 et f(1) = 1 > 0. dichotomie(f, 0, 1, 0.001) renvoie (0.681640625, 0.6826171875) : la solution α vérifie 0,6816 ≤ α ≤ 0,6827. Chaque tour divise la longueur par 2 : après k tours, elle vaut b − a2ᵏ. Il a fallu 10 tours, car 2⁹ = 512 < 1 000 ≤ 2¹⁰ = 1 024.

3. La méthode d'Euler

Pour h petit, la tangente donne f(t + h) ≈ f(t) + h × f'(t). Pour approcher la solution de y' = y avec y(0) = 1 (la fonction exponentielle), on avance pas à pas : yₖ₊₁ = yₖ + h × yₖ.

def euler(n):
 h = 1 / n
 y = 1
 for k in range(n):
 y = y + h * y
 return y

euler(n) fait n pas de longueur h = 1n entre 0 et 1, donc approche e ≈ 2,71828. On obtient euler(10) ≈ 2,5937 (c'est 1,1¹⁰) et euler(1000) ≈ 2,7169 : plus le pas est petit, meilleure est l'approximation, mais plus le calcul est long. Pour y' = ay + b, seule la mise à jour change : yₖ₊₁ = yₖ + h × (ayₖ + b).

4. Simuler des échantillons

from random import random

def echantillon(n, p):
 succes = 0
 for i in range(n):
 if random() < p:
 succes = succes + 1
 return succes / n

def proportion_proches(N, n, p):
 bons = 0
 for j in range(N):
 f = echantillon(n, p)
 if abs(f - p) <= 1 / n ** 0.5:
 bons = bons + 1
 return bons / N

random() renvoie un nombre au hasard dans [0 ; 1[, donc random() < p est vrai avec la probabilité p : echantillon(n, p) simule n épreuves de Bernoulli indépendantes et renvoie la fréquence des succès. proportion_proches(1000, 100, 0.5) simule 1 000 échantillons de taille 100 et renvoie la proportion de ceux dont la fréquence est à au plus 1√100 = 0,1 de p. On obtient environ 0,96, une valeur qui change un peu à chaque appel. L'inégalité de Bienaymé-Tchebychev ne garantit que 1 − 0,25100 × 0,01 = 0,75 : elle est sûre, mais prudente.

À retenir

• Seuil : une boucle while dont la condition est la négation du but ; elle ne s'arrête que si le seuil est atteint.
• Dichotomie : f continue et changement de signe ; après k tours, l'intervalle mesure b − a2ᵏ.
• Euler : pour y' = ay + b, yₖ₊₁ = yₖ + h × (ayₖ + b) ; plus h est petit, meilleure est l'approximation.
• Simulation : random() < p simule un succès de probabilité p ; on répète pour former un échantillon, puis on répète les échantillons pour étudier la fluctuation.

★ Pour aller plus loin

La dichotomie gagne environ trois décimales tous les 10 tours, car 2¹⁰ = 1 024 ≈ 10³. La méthode de Newton, qui suit les tangentes, double à peu près le nombre de décimales exactes à chaque étape : appliquée à x² = 2, c'est la méthode qu'Héron d'Alexandrie décrivait déjà au Iᵉʳ siècle de notre ère.

L'erreur de la méthode d'Euler est à peu près proportionnelle au pas h : on dit qu'elle est d'ordre 1. Les méthodes de Runge-Kutta, mises au point par Carl Runge (1895) et Martin Kutta (1901), sont bien plus précises et tournent dans les simulateurs de vol et de météo. Dans le film « Les Figures de l'ombre » (2016), la mathématicienne Katherine Johnson recourt à la méthode d'Euler pour calculer le retour sur Terre de l'astronaute John Glenn.

Le langage Python a été créé par Guido van Rossum, qui en a publié la première version en 1991 ; son nom est un clin d'œil aux humoristes britanniques des Monty Python.

Sources pour creuser

• Livres : Gérard Swinnen, « Apprendre à programmer avec Python 3 » (Eyrolles, version libre en ligne) ; Mickaël Launay, « Le grand roman des maths » (Flammarion).
• Vidéos : chaîne YouTube « Yvan Monka » (cherche « algorithme de seuil Python Monka », « méthode de dichotomie Monka » et « méthode d'Euler Monka ») ; chaîne « Les Bons Profs » (cherche « algorithme de seuil suite »).
• Institutionnel et pratique : docs.python.org/fr/3/ (documentation officielle en français) ; france-ioi.org (exercices d'algorithmique progressifs) ; eduscol.education.fr (programme de spécialité de Terminale).