Math@mine / Terminale / Ch. 12 / Exercices

Exercices — Algorithmique et programmation

Terminale Spécialité · Chapitre 12

← Retour au cours
Ces exercices couvrent les méthodes algorithmiques principales du programme BO 2019 : recherche dichotomique, méthode de Newton/Héron, simulation Monte-Carlo et usage des dictionnaires. Astuce : ouvre JupyterHub pour tester tes solutions en Python.
Exo 1 Dichotomie — résoudre une équation

Écrire une fonction Python dichotomie(f, a, b, eps) qui approche une solution de f(x) = 0 sur [a, b] à eps près, en supposant que \(f(a)\) et \(f(b)\) sont de signes opposés.

  1. Vérifier au début de la fonction que \(f(a) \cdot f(b) \leq 0\) (sinon lever une ValueError).
  2. Tant que \(b - a > \varepsilon\), calculer \(m = (a+b)/2\) et réduire l'intervalle en gardant la moitié où \(f\) change de signe.
  3. Retourner \((a + b)/2\).
  4. Tester avec \(f(x) = x^3 - 2\) sur \([1\,;\,2]\) et une précision \(10^{-6}\). Tu dois trouver \(\sqrt[3]{2} \approx 1{,}2599\).
Voir la correction 
def dichotomie(f, a, b, eps):
    if f(a) * f(b) > 0:
        raise ValueError("f(a) et f(b) doivent être de signes opposés")
    while b - a > eps:
        m = (a + b) / 2
        if f(a) * f(m) <= 0:
            b = m
        else:
            a = m
    return (a + b) / 2

# Test
racine = dichotomie(lambda x: x**3 - 2, 1, 2, 1e-6)
print(racine)   # 1.25992...

Complexité : après \(n\) itérations, la largeur vaut \((b_0 - a_0)/2^n\). Pour une précision \(\varepsilon\), il faut \(n \approx \log_2((b-a)/\varepsilon)\) étapes — soit environ 20 pour passer d'une largeur 1 à \(10^{-6}\).

Exo 2 Méthode de Newton — racine carrée (méthode de Héron)

La méthode de Newton approche un zéro de \(f\) par la suite \(x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}.\) On veut approcher \(\sqrt{a}\) pour \(a > 0\), en appliquant Newton à \(f(x) = x^2 - a\).

  1. Montrer que la récurrence devient \(x_{n+1} = \dfrac{1}{2}\!\left(x_n + \dfrac{a}{x_n}\right)\). C'est la méthode de Héron, connue dès l'Antiquité.
  2. Écrire une fonction heron(a, eps) qui prend un nombre \(a > 0\) et un seuil \(\varepsilon\), démarre avec \(x_0 = a\), et retourne la première valeur \(x_n\) telle que \(|x_n^2 - a| < \varepsilon\).
  3. Tester avec \(a = 2\) et \(\varepsilon = 10^{-12}\). Compter le nombre d'itérations.
Voir la correction

1. \(f(x) = x^2 - a\), \(f'(x) = 2x\). Donc \(x_{n+1} = x_n - \dfrac{x_n^2 - a}{2x_n} = x_n - \dfrac{x_n}{2} + \dfrac{a}{2x_n} = \dfrac{1}{2}\!\left(x_n + \dfrac{a}{x_n}\right).\)

def heron(a, eps):
    x = a
    n = 0
    while abs(x*x - a) >= eps:
        x = 0.5 * (x + a/x)
        n += 1
    return x, n

racine, iters = heron(2, 1e-12)
print(f"√2 ≈ {racine} (en {iters} itérations)")
# √2 ≈ 1.4142135623730951 (en 5 itérations)

Performance : Newton est quadratiquement convergent : le nombre de décimales exactes double à chaque étape. C'est bien mieux que la dichotomie (qui gagne seulement 1 bit par itération, ≈ 3,3 décimales toutes les 11 étapes).

Exo 3 Simulation Monte-Carlo — estimer π

On tire un grand nombre de points \((x, y)\) uniformément dans le carré \([-1\,;\,1]^2\). La proportion de ceux qui tombent dans le disque unité (\(x^2 + y^2 \leq 1\)) approche \(\pi/4.\) On a donc \(\pi \approx 4 \cdot \dfrac{\text{points dans le disque}}{\text{total}}.\)

  1. Expliquer pourquoi la proportion tend vers \(\pi/4\) (loi faible des grands nombres, chapitre 11).
  2. Écrire une fonction pi_monte_carlo(n) qui estime \(\pi\) à partir de \(n\) tirages aléatoires.
  3. Tester avec \(n = 10^3\), \(10^5\), \(10^7\). Commenter la précision en fonction de \(n\).
Voir la correction

1. L'aire du carré vaut 4, celle du disque vaut \(\pi\). La probabilité qu'un point uniforme du carré tombe dans le disque est \(\pi/4.\) Par la loi faible des grands nombres (ch. 11, section 3), la fréquence observée converge vers cette probabilité.

import random

def pi_monte_carlo(n):
    dans = 0
    for _ in range(n):
        x = random.uniform(-1, 1)
        y = random.uniform(-1, 1)
        if x*x + y*y <= 1:
            dans += 1
    return 4 * dans / n

for n in [10**3, 10**5, 10**7]:
    print(f"n={n:>8}  π ≈ {pi_monte_carlo(n):.6f}")
# n=    1000  π ≈ 3.156000  (± 0.06)
# n=  100000  π ≈ 3.140720  (± 0.006)
# n=10000000  π ≈ 3.141563  (± 0.0006)

Remarque : la précision s'améliore en \(1/\sqrt{n}\) (décroissance lente : pour gagner une décimale il faut multiplier \(n\) par 100). Monte-Carlo est puissant pour les intégrations en grande dimension, pas pour approcher \(\pi\) — mais c'est une excellente illustration de la LGN.

Exo 4 Dictionnaire — comptage d'occurrences et histogramme

On dispose d'une liste de notes (entiers entre 0 et 20). On veut construire un dictionnaire qui associe à chaque note le nombre d'élèves l'ayant obtenue, puis afficher un histogramme ASCII.

  1. Écrire une fonction compter(notes) qui prend une liste et retourne le dictionnaire d'occurrences.
  2. Écrire une fonction histogramme(compteur) qui affiche, pour chaque note (triée croissant), une ligne note │ █████ (3) où la barre a une longueur égale au nombre d'occurrences.
  3. Tester avec la liste [15, 12, 8, 15, 17, 12, 10, 15, 12, 8, 14].
Voir la correction 
def compter(notes):
    compteur = {}
    for n in notes:
        compteur[n] = compteur.get(n, 0) + 1
    return compteur

def histogramme(compteur):
    for note in sorted(compteur.keys()):
        nb = compteur[note]
        barre = '█' * nb
        print(f"{note:2d} │ {barre} ({nb})")

notes = [15, 12, 8, 15, 17, 12, 10, 15, 12, 8, 14]
c = compter(notes)
histogramme(c)
#  8 │ ██ (2)
# 10 │ █ (1)
# 12 │ ███ (3)
# 14 │ █ (1)
# 15 │ ███ (3)
# 17 │ █ (1)

Variante Python pythonique : from collections import Counter; c = Counter(notes) fait exactement la même chose en une ligne.