Aller au contenu Maths PDF : cours, exercices, QCM, géométrie et calcul, du CM1 à la terminale
Maths PDF Accueil

Terminale · fiche 12 sur 12

Algorithmique et programmation en Python

Trois algorithmes reviennent au bac : la recherche de seuil, la dichotomie pour approcher une solution, et la simulation d'une loi.

L'essentiel en trois points

  1. Une recherche de seuil s'écrit avec une boucle while et un compteur.
  2. La dichotomie divise l'intervalle par deux à chaque étape.
  3. Après $n$ étapes de dichotomie, l'amplitude est divisée par $2^n$.

Recherche de seuil

Comment faire — le schéma

u = 1
n = 0
while u < 10**6:
    u = 1.5 * u
    n = n + 1
print(n)

La condition du while est celle sous laquelle on continue.

Astuce

Ce programme renvoie le premier rang où le seuil est dépassé. Vérifiez ce que demande l'énoncé : premier rang au-dessus, ou dernier en dessous.

La dichotomie

Comment faire — approcher une solution

Sur $[a\ ;\ b]$ où $f$ est continue, strictement monotone et change de signe :

while b - a > 0.001:
    m = (a + b) / 2
    if f(a) * f(m) < 0:
        b = m
    else:
        a = m

À savoir — nombre d'étapes

Chaque tour divise l'amplitude par $2$ : après $n$ étapes, elle vaut $\dfrac{b-a}{2^n}$. Pour une précision de $10^{-3}$ sur un intervalle de longueur $1$, il faut $n \ge 10$.

Piège à éviter

Le test porte sur le signe du produit $f(a)\times f(m)$, pas sur la valeur de $f(m)$ seule.

Sommes et listes

Comment faire — accumuler

s = 0
for k in range(1, n+1):
    s = s + k**2

Ou, avec une liste : sum([k**2 for k in range(1, n+1)]).

Simuler une loi binomiale

Comment faire — compter les succès

from random import random
def simule(n, p):
    s = 0
    for i in range(n):
        if random() < p:
            s = s + 1
    return s

Astuce

En répétant cette simulation un grand nombre de fois, la moyenne des résultats approche $np$ : c'est la loi des grands nombres à l'œuvre.

Vérifiez que vous savez faire

  • écrire une recherche de seuil avec une boucle while
  • programmer une dichotomie
  • déterminer le nombre d'étapes nécessaires à une précision donnée
  • calculer une somme par accumulation
  • simuler une loi binomiale et interpréter le résultat

On nous pose souvent ces questions

Comment fonctionne la méthode de dichotomie ?

On coupe l'intervalle en deux à chaque étape et l'on conserve la moitié où la fonction change de signe, jusqu'à atteindre la précision voulue.

Combien d'étapes de dichotomie faut-il ?

Chaque étape divise l'amplitude par deux. Pour passer d'un intervalle de longueur 1 à une précision de un millième, il en faut dix.

Sur quoi porte le test dans une dichotomie ?

Sur le signe du produit des images des deux bornes concernées, et non sur la valeur de la fonction au milieu prise isolément.

Travailler ce chapitre plus loin

Cette fiche donne l'essentiel. Pour approfondir, voici le même chapitre traité en entier sur Maths PDF.

Télécharger cette fiche en PDFVersion imprimable, sans la figure interactive.