Cours et exercices corrigés de terminale : Algorithmique et programmation en Python : listes, seuils, dichotomie et méthode de Monte-Carlo

1. Listes et fonctions : rappels et compléments

• Création en compréhension avec filtre : [k for k in range(1, 50) if k % 7 == 3] donne [3, 10, 17, 24, 31, 38, 45].
• Fonctions prédéfinies : len(L), sum(L), max(L), min(L) ; L.append(x) ajoute un élément ; L[-1] est le dernier élément.
• Une fonction peut renvoyer une liste, ou s'interrompre dès qu'un résultat est trouvé :

def position(L, v):
    for i in range(len(L)):
        if L[i] == v:
            return i      # sortie immédiate
    return -1             # v absent de L

• Affectation simultanée : dans a, b = b, a + b, le membre de droite est entièrement calculé avant les affectations (suite de Fibonacci).

2. Suites et algorithmes de seuil

• Si $(u_n)$ tend vers $+\infty$, la boucle while u < A: se termine et fournit le plus petit $n$ tel que $u_n \ge A$.
• Si $(u_n)$ converge vers $\ell$, on peut chercher un rang à partir duquel $u_n$ approche $\ell$ à $10^{-p}$ près :

u = 10
n = 0
while abs(u - 6) > 0.001:
    u = 0.5 * u + 3
    n = n + 1
print(n)      # affiche 12

Ici $u_n - 6 = 4 \times 0{,}5^n$ : on cherche le premier $n$ tel que $4 \times 0{,}5^n \le 0{,}001$, soit $2^n \ge 4000$, d'où $n = 12$. (Voir aussi le chapitre TA2.)

• Une boucle while doit se terminer : si la suite ne dépasse jamais le seuil, le programme tourne indéfiniment.

3. Méthode de dichotomie

Soit $f$ continue et strictement monotone sur $[a ; b]$ avec $f(a)$ et $f(b)$ de signes contraires : l'équation $f(x) = 0$ a une unique solution $\alpha$ dans $[a ; b]$ (corollaire du théorème des valeurs intermédiaires, chapitre TA3).
À chaque étape, on calcule le milieu $m$ et on garde la moitié qui contient $\alpha$ :

• si $f(a) \times f(m) \le 0$, $\alpha \in [a ; m]$ : on remplace $b$ par $m$ ;
• sinon, $\alpha \in [m ; b]$ : on remplace $a$ par $m$.

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

On passe la fonction f en paramètre (en Python, une fonction est une valeur comme une autre).

4. Précision et nombre d'étapes d'une dichotomie

À chaque étape, la longueur de l'intervalle est divisée par 2. Partant de $[a ; b]$, après $n$ étapes, elle vaut $\frac{b - a}{2^n}$.
Pour obtenir une précision $e$, il faut le plus petit $n$ tel que $\frac{b - a}{2^n} \le e$, c'est-à-dire $2^n \ge \frac{b - a}{e}$, soit $n \ge \frac{\ln\left(\frac{b - a}{e}\right)}{\ln 2}$.
Exemple : sur $[1 ; 2]$, pour $e = 0{,}01$, il faut $2^n \ge 100$, donc $n = 7$ étapes ($2^7 = 128$). Chaque étape fait gagner environ « un tiers de chiffre décimal » : $10$ étapes divisent la longueur par $2^{10} = 1024 \approx 10^3$.

5. Méthode de Monte-Carlo

On tire au hasard $n$ points $(x ; y)$ uniformément dans un rectangle $R$ d'aire $\mathcal{A}_R$ et on compte le nombre $c$ de points qui tombent dans un domaine $D \subset R$. D'après la loi des grands nombres :
$$\frac{c}{n} \approx \frac{\text{aire}(D)}{\mathcal{A}_R}$$
Estimation de $\pi$ : avec $x$ et $y$ dans $[0 ; 1[$, la condition $x^2 + y^2 \le 1$ décrit un quart de disque d'aire $\frac{\pi}{4}$.

from random import random

def estimation_pi(n):
    c = 0
    for i in range(n):
        x = random()
        y = random()
        if x ** 2 + y ** 2 <= 1:
            c = c + 1
    return 4 * c / n

Estimation d'une intégrale : si $0 \le f \le M$ sur $[0 ; A]$, avec x = A * random() et y = M * random(), la quantité $A \times M \times \frac{c}{n}$ (où $c$ compte les points tels que $y \le f(x)$) estime $\int_0^A f(x)\,\mathrm{d}x$.

6. Pour aller plus loin : autres méthodes numériques

• Méthode d'Euler (chapitre 1A4) : pour approcher la solution de $y' = y$, $y(0) = 1$, on itère $y \leftarrow y + h \times y$ avec un petit pas $h$.
• Méthode des rectangles (chapitre TA7) : approximation déterministe d'une intégrale par une somme d'aires de rectangles.
• Méthode de Newton : on remplace la courbe par sa tangente, $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$ ; la convergence est en général beaucoup plus rapide que la dichotomie, mais elle n'est pas garantie.
• Comparaison : la dichotomie gagne un facteur $2$ par étape, la méthode de Monte-Carlo a une précision de l'ordre de $\frac{1}{\sqrt{n}}$ : pour gagner un chiffre, il faut 100 fois plus de points.