# Algorithmes du programme de Terminale : maths Terminale

Chapitre 4 du programme de mathématiques de Terminale (thème : Algorithmique et programmation). Ressource gratuite OptiTAB.

- Cours : https://www.optitab.net/ressources-gratuites/maths/terminale/algorithmes-du-programme-de-terminale/
- Fiche de révision : https://www.optitab.net/ressources-gratuites/maths/terminale/algorithmes-du-programme-de-terminale/fiche/
- Exercices corrigés : https://www.optitab.net/ressources-gratuites/maths/terminale/algorithmes-du-programme-de-terminale/exercices/

## Cours

**Objectifs : Écrire, lire et utiliser en Python les algorithmes cités par le programme de Terminale : terme, somme et seuil d'une suite ; méthode de dichotomie et méthode de Newton ; méthode des rectangles ; seuils avec l'exponentielle et le logarithme ; simulation d'un schéma de Bernoulli, d'une loi binomiale et d'échantillons ; génération de listes en dénombrement.**

**Prerequis : Programmes de Seconde et de Première : variables, fonctions `def`, instructions `if`, boucles `for` et `while`, listes (voir la notion « Notion de liste »). Terminale : suites et limites, continuité, logarithme, calcul intégral, loi binomiale, loi des grands nombres, dénombrement.**

## I. Les outils

Le programme de Terminale n'introduit aucune instruction nouvelle : il applique les outils de Seconde et de Première à chaque partie du cours.

**Rappel : Rappel de Seconde et de Première**
- `def f(x):` puis `return …` définit une fonction qui renvoie un résultat.
- `if condition:` … `else:` … exécute un bloc ou l'autre.
- `for k in range(n):` répète un bloc $n$ fois ; `k` prend les valeurs $0$, $1$, …, $n-1$.
- `while condition:` répète un bloc **tant que** la condition est vraie.
- Un **accumulateur** s'initialise **avant** la boucle : $0$ pour une somme ou un compteur, $1$ pour un produit.
- `L.append(x)` ajoute `x` à la fin de la liste `L`.

| Algorithme | Boucle utilisée |
|---|---|
| terme $u_n$, somme, rectangles | `for` : nombre de tours connu |
| seuil, dichotomie | `while` : tant que le but n'est pas atteint |
| simulation de $N$ expériences | `for` et un compteur |

**Remarque : Simulations : la graine**
Le module `random` produit des nombres **pseudo-aléatoires** : ils sont calculés à partir d'un point de départ, la **graine**. L'instruction `seed(2026)` fixe cette graine : le programme donne alors toujours le même affichage, et c'est celui que l'on imprime ici. Sans `seed`, ou avec une autre graine, on obtient d'autres résultats, de même allure.

## II. Suites numériques

### 1. Terme de rang $n$ et somme de termes

La suite $(u_n)$ est définie par $u_0 = 1$ et, pour tout entier naturel $n$, $u_{n+1} = 0{,}8\,u_n + 2$.

**Méthode : Terme et somme**
- **Terme $u_n$** : on part de $u_0$ et on applique $n$ fois la relation de récurrence (boucle `for` de $n$ tours).
- **Somme $u_0 + \dots + u_n$** : un accumulateur `s` et le terme `u` avancent **ensemble** ; il y a $n + 1$ termes, donc $n + 1$ tours.

```python
def terme(n):
    u = 1
    for k in range(n):
        u = 0.8 * u + 2
    return u

def somme(n):
    s = 0
    u = 1
    for k in range(n + 1):
        s = s + u
        u = 0.8 * u + 2
    return s

print(round(terme(3), 4))
print(round(somme(3), 4))
```

```console
5.392
13.432
```

On vérifie : $u_1 = 2{,}8$, $u_2 = 4{,}24$, $u_3 = 5{,}392$ et

$$
\begin{aligned}
&u_0 + u_1 + u_2 + u_3 \\
&= 1 + 2{,}8 + 4{,}24 + 5{,}392 \\
&= 13{,}432
\end{aligned}
$$

**Remarque : La forme explicite**
La suite définie par $v_n = u_n - 10$ vérifie

$$
\begin{aligned}
v_{n+1} &= 0{,}8\,u_n + 2 - 10 \\
&= 0{,}8\,(u_n - 10) = 0{,}8\,v_n
\end{aligned}
$$

Elle est géométrique de raison $0{,}8$ et $v_0 = -9$. Donc $u_n = 10 - 9 \times 0{,}8^n$, et $(u_n)$ converge vers $10$ car $-1 \lt 0{,}8 \lt 1$.

### 2. Algorithme de seuil

**Méthode : Plus petit rang $n$ tel que $u_n \gt A$**
On calcule les termes un par un **tant que** le seuil n'est pas dépassé, en comptant les tours. La condition du `while` est le **contraire** de la condition cherchée : on veut $u_n \gt A$, on répète donc tant que $u \le A$. À la sortie, `n` est le rang cherché.

```python
def seuil(A):
    n = 0
    u = 1
    while u <= A:
        u = 0.8 * u + 2
        n = n + 1
    return n

print(seuil(9))
```

```console
10
```

![Termes de la suite u(n+1) = 0,8 u(n) + 2 avec u0 = 1 : ils dépassent le seuil 9 à partir de u10 ≈ 9,03 et restent sous la droite y = 10, jamais atteinte](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n100_co104_1_suite_seuil.png)

**Point : Vérification par le logarithme**
$$
\begin{aligned}
u_n \gt 9 &\iff 10 - 9 \times 0{,}8^n \gt 9 \\
&\iff 0{,}8^n \lt \frac{1}{9} \\
&\iff n \ln(0{,}8) \lt -\ln(9) \\
&\iff n \gt \frac{\ln(9)}{-\ln(0{,}8)}
\end{aligned}
$$

On a divisé par $\ln(0{,}8) \lt 0$, ce qui change le sens de l'inégalité. Comme $\dfrac{\ln(9)}{-\ln(0{,}8)} \approx 9{,}85$, le plus petit entier est bien $n = 10$.

### 3. Une suite majorée qui ne dépasse jamais le seuil

Un algorithme de seuil ne s'arrête que si le seuil est **réellement dépassé** à partir d'un certain rang. Ici, l'appel `seuil(10)` ne se termine jamais.

**Démonstration : Pour tout $n$, $u_n \lt 10$**
Par récurrence. **Initialisation** : $u_0 = 1 \lt 10$. **Hérédité** : si $u_n \lt 10$, alors $0{,}8\,u_n \lt 8$, donc $u_{n+1} = 0{,}8\,u_n + 2 \lt 10$. La propriété est vraie pour tout entier naturel $n$.
**La : condition `u <= 10` reste donc toujours vraie : la boucle est **infinie**. La suite converge vers $10$ sans jamais l'atteindre.**

**Conseil : Un garde-fou**
On limite le nombre de tours avec un second paramètre `nmax`, puis on teste si le seuil a bien été dépassé. La fonction renvoie `None` (« rien ») sinon.

```python
def seuil2(A, nmax):
    n = 0
    u = 1
    while u <= A and n < nmax:
        u = 0.8 * u + 2
        n = n + 1
    if u > A:
        return n
    return None

print(seuil2(9, 1000))
print(seuil2(10, 1000))
```

```console
10
None
```

## III. Continuité : résoudre $f(x) = 0$

La fonction $f : x \mapsto x^3 + x - 1$ est continue et strictement croissante sur $[0\,;1]$ (car $f'(x) = 3x^2 + 1 \gt 0$), avec $f(0) = -1 \lt 0$ et $f(1) = 1 \gt 0$. D'après le corollaire du théorème des valeurs intermédiaires, l'équation $f(x) = 0$ admet une **unique** solution $\alpha$ dans $[0\,;1]$.

### 1. La méthode de dichotomie

**Méthode : Dichotomie**
On part d'un intervalle $[a\,;b]$ qui contient $\alpha$. À chaque tour, on calcule le milieu $m = \dfrac{a + b}{2}$ :
- si $f(a)$ et $f(m)$ sont de signes contraires, c'est-à-dire $f(a) \times f(m) \le 0$, la solution est dans $[a\,;m]$ : on remplace $b$ par $m$ ;
- sinon, elle est dans $[m\,;b]$ : on remplace $a$ par $m$.

On s'arrête quand l'amplitude $b - a$ est inférieure ou égale à la précision $e$.

```python
def f(x):
    return x**3 + x - 1

def dichotomie(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

print(dichotomie(0, 1, 0.01))
```

```console
(0.6796875, 0.6875)
```

| Tour | $m$ | signe de $f(m)$ | nouvel intervalle |
|---|---|---|---|
| 1 | $0{,}5$ | $-$ | $[0{,}5\,;1]$ |
| 2 | $0{,}75$ | $+$ | $[0{,}5\,;0{,}75]$ |
| 3 | $0{,}625$ | $-$ | $[0{,}625\,;0{,}75]$ |
| 4 | $0{,}6875$ | $+$ | $[0{,}625\,;0{,}6875]$ |

![Courbe de y = x³ + x − 1 sur 0 ; 1 coupant l'axe des abscisses en alpha, et intervalles successifs de la dichotomie aux tours 0 à 4 : 0 ; 1, 0,5 ; 1, 0,5 ; 0,75, 0,625 ; 0,75 et 0,625 ; 0,6875](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n100_co104_2_dichotomie.png)

L'amplitude est divisée par $2$ à chaque tour : après $n$ tours, elle vaut $\dfrac{1}{2^n}$. Comme $\dfrac{1}{2^6} \gt 0{,}01$ et $\dfrac{1}{2^7} = \dfrac{1}{128} \le 0{,}01$, la boucle fait $7$ tours : $0{,}6796 \lt \alpha \lt 0{,}6875$.

### 2. La méthode de Newton

**Méthode : Méthode de Newton**
On part d'une valeur $x_0$ proche de $\alpha$. La tangente à la courbe au point d'abscisse $x_n$ coupe l'axe des abscisses en $x_{n+1}$ :
$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$
Dans les cas favorables (comme ici), la suite $(x_n)$ converge très vite vers $\alpha$.

**Démonstration : D'où vient la formule**
La tangente au point d'abscisse $x_n$ a pour équation $y = f'(x_n)(x - x_n) + f(x_n)$. Elle coupe l'axe des abscisses quand $y = 0$, c'est-à-dire, si $f'(x_n) \neq 0$, pour $x = x_n - \dfrac{f(x_n)}{f'(x_n)}$.

![Méthode de Newton pour y = x³ + x − 1 : la tangente au point d'abscisse x0 = 1 coupe l'axe en x1 = 0,75, la tangente au point d'abscisse x1 le coupe en x2, très proche de la solution](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n100_co104_3_newton.png)

```python
def fp(x):
    return 3 * x**2 + 1

x = 1
for k in range(4):
    x = x - f(x) / fp(x)
    print(k + 1, x)
```

```console
1 0.75
2 0.686046511627907
3 0.6823395825973142
4 0.6823278039465127
```

Après $4$ tours, $x_4 \approx 0{,}682\,327\,804$ : ses neuf premières décimales sont celles de $\alpha$ (au tour suivant, Python affiche `0.6823278038280194`). La dichotomie, elle, gagne environ une décimale tous les $3$ ou $4$ tours.

**Attention : Les limites de la méthode de Newton**
Il faut connaître la dérivée $f'$, et la méthode échoue si $f'(x_n) = 0$ ; si l'on part d'une valeur trop éloignée de $\alpha$, la suite peut même s'en écarter. La dichotomie est lente mais toujours sûre ; la méthode de Newton est rapide quand on part près de la solution.

## IV. Calcul intégral : la méthode des rectangles

Soit $f$ continue et positive sur $[a\,;b]$. On partage $[a\,;b]$ en $n$ intervalles de même largeur $h = \dfrac{b - a}{n}$, d'extrémités $x_k = a + kh$. Sur chaque petit intervalle, on remplace l'aire sous la courbe par l'aire d'un rectangle de largeur $h$.

**Méthode : Rectangles à gauche, rectangles à droite**
- À gauche, les hauteurs sont $f(x_0)$, …, $f(x_{n-1})$ ;
- à droite, les hauteurs sont $f(x_1)$, …, $f(x_n)$.

$$
\begin{aligned}
S &= h \sum_{k=0}^{n-1} f(x_k) \quad \text{(à gauche)} \\
s &= h \sum_{k=1}^{n} f(x_k) \quad \text{(à droite)}
\end{aligned}
$$

Si $f$ est **décroissante**, $s \le \displaystyle\int_a^b f(x)\,\mathrm{d}x \le S$ (inégalités inversées si $f$ est croissante).

**Exemple : Encadrer $\ln(2) = \displaystyle\int_1^2 \frac{1}{x}\,\mathrm{d}x$**
La fonction inverse est décroissante sur $[1\,;2]$ : les rectangles à droite donnent une valeur approchée par défaut $s$, les rectangles à gauche une valeur approchée par excès $S$.

```python
def f(x):
    return 1 / x

def gauche(a, b, n):
    h = (b - a) / n
    S = 0
    for k in range(n):
        S = S + h * f(a + k*h)
    return S

def droite(a, b, n):
    h = (b - a) / n
    s = 0
    for k in range(1, n + 1):
        s = s + h * f(a + k*h)
    return s

for n in [4, 10, 100]:
    s = round(droite(1, 2, n), 4)
    S = round(gauche(1, 2, n), 4)
    print(n, s, S)
```

```console
4 0.6345 0.7595
10 0.6688 0.7188
100 0.6907 0.6957
```

![Courbe de y = 1/x sur 1 ; 2 avec 4 rectangles à gauche, au-dessus de la courbe (somme S), et 4 rectangles à droite, sous la courbe (somme s)](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n100_co104_4_rectangles.png)

Avec $n = 100$ : $0{,}6907 \le \ln(2) \le 0{,}6957$, et en effet $\ln(2) \approx 0{,}6931$. Les termes communs se simplifient : $S - s = h\,\big(f(1) - f(2)\big) = \dfrac{1}{2n}$, qui tend vers $0$ quand $n$ augmente.

## V. Exponentielle et logarithme : seuils

**Méthode : Deux façons de trouver un seuil**
- **Par un algorithme** : on teste $n = 0$, $1$, $2$, … avec une boucle `while` ; on obtient le plus petit entier qui convient.
- **Par le calcul** : on résout l'inéquation avec la fonction $\ln$ (croissante) ou la fonction $\exp$. C'est le calcul qui **démontre** le résultat.

**Exemple : Un capital placé à $3\,\%$ par an**
Un capital de $1\,000$ € augmente de $3\,\%$ par an : au bout de $n$ années, il vaut $1\,000 \times 1{,}03^n$. Au bout de combien d'années aura-t-il doublé ?

```python
n = 0
c = 1000
while c <= 2000:
    c = c * 1.03
    n = n + 1
print(n, round(c, 2))
```

```console
24 2032.79
```

Par le calcul, comme $\ln(1{,}03) \gt 0$ :

$$
\begin{aligned}
1{,}03^n \gt 2 &\iff n \ln(1{,}03) \gt \ln(2) \\
&\iff n \gt \frac{\ln(2)}{\ln(1{,}03)} \approx 23{,}45
\end{aligned}
$$

Le capital a doublé au bout de $24$ ans.

**Exemple : Une décroissance exponentielle**
La masse d'un produit radioactif vaut $m(t) = 100\,e^{-0{,}3t}$ grammes au bout de $t$ jours. On cherche à partir de quand elle est inférieure à $1$ gramme.

```python
from math import exp

t = 0
while 100 * exp(-0.3*t) >= 1:
    t = t + 1
print(t)
```

```console
16
```

Par le calcul :

$$
\begin{aligned}
100\,e^{-0{,}3t} \lt 1 &\iff e^{-0{,}3t} \lt 0{,}01 \\
&\iff -0{,}3t \lt \ln(0{,}01) \\
&\iff t \gt \frac{\ln(100)}{0{,}3} \approx 15{,}35
\end{aligned}
$$

On a divisé par $-0{,}3 \lt 0$ et utilisé $-\ln(0{,}01) = \ln(100)$. Le premier nombre entier de jours est bien $16$.

**Remarque : Un pas plus fin**
En remplaçant `t = t + 1` par `t = round(t + 0.01, 2)`, la même boucle avance de $0{,}01$ en $0{,}01$ et affiche `15.36` : c'est une valeur approchée par excès, au centième, de $\dfrac{\ln(100)}{0{,}3}$. La fonction `round` efface les erreurs d'arrondi des décimaux en machine.

## VI. Probabilités : simuler

### 1. Schéma de Bernoulli et loi binomiale

`random()` renvoie un nombre au hasard dans $[0\,;1[$ : le test `random() < p` est vrai avec la probabilité $p$. La fonction `bernoulli(p)` simule donc une épreuve de Bernoulli de paramètre $p$ (elle renvoie $1$ pour un succès, $0$ pour un échec). La somme de $n$ épreuves indépendantes suit la loi binomiale $\mathcal{B}(n\,;p)$.

```python
from random import random, seed

def bernoulli(p):
    if random() < p:
        return 1
    return 0

def binomiale(n, p):
    x = 0
    for k in range(n):
        x = x + bernoulli(p)
    return x

seed(2026)
R = []
for k in range(10):
    R.append(bernoulli(0.3))
print(R)
print(binomiale(10, 0.3))
```

```console
[1, 0, 0, 0, 1, 1, 0, 0, 0, 0]
2
```

La liste `R` contient les résultats de $10$ épreuves : $3$ succès ici. Le dernier appel simule une valeur de $X \sim \mathcal{B}(10\,;0{,}3)$ : on a obtenu $2$ succès sur $10$.

### 2. Fréquences observées et probabilités

On simule $N = 1\,000$ valeurs de $X$, qui suit $\mathcal{B}(10\,;0{,}3)$. La liste `E` compte combien de fois chaque valeur $k$ est obtenue : `E[k]` est l'effectif de $k$.

```python
seed(2026)
N = 1000
E = [0] * 11
for i in range(N):
    x = binomiale(10, 0.3)
    E[x] = E[x] + 1
for k in range(11):
    print(k, E[k])
```

```console
0 32
1 123
2 219
3 265
4 198
5 110
6 40
7 10
8 2
9 1
10 0
```

On compare les fréquences $\dfrac{E[k]}{N}$ aux probabilités $P(X = k) = \dbinom{10}{k}\,0{,}3^k\,0{,}7^{10-k}$, calculées avec la fonction `comb` du module `math`.

```python
from math import comb

def p_binom(n, p, k):
    q = 1 - p
    c = comb(n, k)
    return c * p**k * q**(n - k)

for k in range(6):
    pk = p_binom(10, 0.3, k)
    f = E[k] / N
    print(k, f, round(pk, 3))
```

```console
0 0.032 0.028
1 0.123 0.121
2 0.219 0.233
3 0.265 0.267
4 0.198 0.2
5 0.11 0.103
```

![Diagramme en barres des fréquences observées sur 1000 simulations de la loi binomiale B(10 ; 0,3), comparées aux probabilités P(X = k)](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n100_co104_5_histo_binom.png)

### 3. Calculer un seuil pour une loi binomiale

**Méthode : Plus petit $k$ tel que $P(X \le k) \ge a$**
On ajoute les probabilités $P(X = 0)$, $P(X = 1)$, … **tant que** leur somme est inférieure à $a$. On utilise la fonction `p_binom` ci-dessus.

```python
def seuil_binom(n, p, a):
    k = 0
    s = p_binom(n, p, 0)
    while s < a:
        k = k + 1
        s = s + p_binom(n, p, k)
    return k, round(s, 4)

print(seuil_binom(10, 0.3, 0.95))
```

```console
(5, 0.9527)
```

Pour $X \sim \mathcal{B}(10\,;0{,}3)$ : $P(X \le 4) \approx 0{,}8497 \lt 0{,}95$ et $P(X \le 5) \approx 0{,}9527 \ge 0{,}95$, donc $k = 5$. Ce type de calcul sert aussi à résoudre un problème de surréservation.

### 4. Échantillons et loi des grands nombres

La fréquence des succès dans un échantillon de taille $n$ est la moyenne de $n$ variables de Bernoulli indépendantes. D'après la loi des grands nombres, elle se rapproche de $p$ quand $n$ devient grand.

```python
seed(2026)
for n in [10, 100, 1000, 10000]:
    s = 0
    for i in range(n):
        s = s + bernoulli(0.3)
    print(n, s / n)
```

```console
10 0.3
100 0.21
1000 0.285
10000 0.308
```

Les fréquences fluctuent beaucoup pour de petits échantillons, puis se stabilisent autour de $p = 0{,}3$.

## VII. Dénombrement : générer des listes

### 1. Le triangle de Pascal

**Méthode : Relation de Pascal**
Pour $1 \le k \le n$ : $\dbinom{n+1}{k} = \dbinom{n}{k-1} + \dbinom{n}{k}$. Chaque ligne du triangle se déduit de la précédente : elle commence et finit par $1$, et chaque autre nombre est la somme des **deux nombres voisins** de la ligne du dessus.

![Triangle de Pascal des lignes 0 à 5 : les nombres 4 et 6 de la ligne 4 s'additionnent pour donner 10 sur la ligne 5](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n100_co104_6_pascal_cours.png)

```python
def suivante(L):
    M = [1]
    for k in range(len(L) - 1):
        M.append(L[k] + L[k + 1])
    M.append(1)
    return M

L = [1]
for n in range(6):
    print(L)
    L = suivante(L)
```

```console
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
```

La ligne $n$ contient les coefficients $\dbinom{n}{0}$, $\dbinom{n}{1}$, …, $\dbinom{n}{n}$ : par exemple $\dbinom{5}{2} = 10$.

### 2. Les parties à $2$ éléments d'un ensemble

**Exemple : Parties à $2$ éléments de $\{a, b, c, d\}$**
Deux boucles imbriquées : pour chaque indice `i`, l'indice `j` parcourt les indices **suivants** ; chaque partie est ainsi obtenue une seule fois.

```python
E = ["a", "b", "c", "d"]
P = []
for i in range(len(E)):
    for j in range(i + 1, len(E)):
        P.append([E[i], E[j]])
for c in P:
    print(c)
print(len(P))
```

```console
['a', 'b']
['a', 'c']
['a', 'd']
['b', 'c']
['b', 'd']
['c', 'd']
6
```

On retrouve $\dbinom{4}{2} = \dfrac{4 \times 3}{2} = 6$. La même liste s'écrit aussi en compréhension : voir la notion « Notion de liste ».

## VIII. Bilan

| Partie du programme | Algorithmes |
|---|---|
| Suites | terme $u_n$, somme (`for`) ; seuil, suite majorée (`while`) |
| Continuité | dichotomie (`while`, `if`) ; méthode de Newton |
| Calcul intégral | rectangles (`for`, accumulateur) |
| Exp et ln | seuils (`while`, puis $\ln$) |
| Probabilités | Bernoulli, binomiale, échantillons (`random`, compteur) |
| Dénombrement | triangle de Pascal, parties (listes) |

**Remarque : Autres exemples cités par le programme**
Méthode de la sécante, algorithme de Briggs (logarithme), méthode d'Euler pour $y' = ay + b$, méthodes des milieux et des trapèzes, méthode de Monte-Carlo, planche de Galton, marche aléatoire : ils utilisent les mêmes outils.

**Attention : Pièges fréquents**
- Dans un algorithme de seuil, la condition du `while` est le **contraire** de la condition cherchée.
- Avant de chercher un seuil, on vérifie qu'il sera dépassé (suite majorée : boucle infinie).
- Diviser une inégalité par $\ln(q) \lt 0$ (quand $0 \lt q \lt 1$) change son sens.
- Dichotomie : on garde la moitié où $f$ **change de signe**, et on s'arrête sur l'amplitude $b - a$, pas sur $f(m)$.
- Rectangles : `range(n)` pour les rectangles à gauche ($x_0$ à $x_{n-1}$), `range(1, n + 1)` à droite.
- Une simulation sans `seed` donne un résultat différent à chaque exécution.

**À retenir : - Seuil : `while u <= A:` et un compteur, puis vérification par le logarithme.**
- Dichotomie : l'amplitude est divisée par $2$ à chaque tour.
- Newton : $x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}$.
- Rectangles : $h \times$ (somme des hauteurs), avec $h = \dfrac{b - a}{n}$.
- Bernoulli : `random() < p` ; binomiale : somme de $n$ Bernoulli ; la fréquence tend vers $p$.
- Pascal : chaque coefficient est la somme des deux nombres voisins de la ligne du dessus.

Fiche de synthèse dans l'onglet Fiches !

## Fiche de révision

**Objectifs : L'essentiel des algorithmes du programme de Terminale : suites, dichotomie, Newton, rectangles, seuils, simulations, dénombrement.**

## I. Suites : terme, somme, seuil

| Objectif | Structure |
|---|---|
| terme $u_n$ | `for` : $n$ applications de la récurrence |
| somme $u_0 + \dots + u_n$ | `for` de $n + 1$ tours, accumulateur à $0$ |
| plus petit $n$ tel que $u_n \gt A$ | `while u <= A:` et un compteur |

```python
def seuil(A):
    n = 0
    u = 1
    while u <= A:
        u = 0.8 * u + 2
        n = n + 1
    return n

print(seuil(9))
```

```console
10
```

![Termes de la suite u(n+1) = 0,8 u(n) + 2 : le seuil 9 est dépassé à partir de n = 10, la droite y = 10 n'est jamais atteinte](https://optitab-media.s3.eu-north-1.amazonaws.com/synthesis_images/v1_n100_fi36_1_suite_seuil.png)

**Attention : Suite majorée**
Ici $u_n \lt 10$ pour tout $n$ (récurrence) : `seuil(10)` ne s'arrête jamais. On vérifie toujours que le seuil sera dépassé.

## II. Résoudre $f(x) = 0$

**Méthode : Dichotomie**
Tant que $b - a \gt e$ : $m = \dfrac{a + b}{2}$ ; si $f(a) \times f(m) \le 0$, alors $b \leftarrow m$, sinon $a \leftarrow m$. Après $n$ tours, l'amplitude est $\dfrac{b - a}{2^n}$.

**Formule : $$\text{Newton :}\quad x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$**
**Newton : converge beaucoup plus vite, à condition de partir près de la solution et que $f'(x_n) \neq 0$.**

## III. Intégrale : méthode des rectangles

Avec $h = \dfrac{b - a}{n}$ et $x_k = a + kh$ :

$$
\begin{aligned}
S &= h \sum_{k=0}^{n-1} f(x_k) \quad \text{(à gauche)} \\
s &= h \sum_{k=1}^{n} f(x_k) \quad \text{(à droite)}
\end{aligned}
$$

![Rectangles à gauche au-dessus et rectangles à droite au-dessous de la courbe décroissante y = 1/x sur 1 ; 2](https://optitab-media.s3.eu-north-1.amazonaws.com/synthesis_images/v1_n100_fi36_2_rectangles.png)

Si $f$ est décroissante : $s \le \displaystyle\int_a^b f(x)\,\mathrm{d}x \le S$ ; inversé si $f$ est croissante.

## IV. Seuils : algorithme puis logarithme

- L'algorithme donne le plus petit entier qui convient ; le calcul le démontre.
- $q^n \lt \varepsilon$ avec $0 \lt q \lt 1$ : $n \gt \dfrac{\ln(\varepsilon)}{\ln(q)}$ (le sens change, car $\ln(q) \lt 0$).

## V. Probabilités

- Succès de probabilité $p$ : le test `random() < p`.
- Loi $\mathcal{B}(n\,;p)$ : somme de $n$ épreuves de Bernoulli indépendantes.
- $P(X = k) = \dbinom{n}{k}\,p^k\,(1 - p)^{n-k}$, avec `comb(n, k)` pour $\dbinom{n}{k}$.
- Fréquence : un compteur divisé par le nombre $N$ d'expériences.
- `seed(2026)` fixe la graine : la simulation donne toujours le même résultat.
- Loi des grands nombres : la fréquence d'un échantillon se rapproche de $p$ quand sa taille augmente.

## VI. Dénombrement

- Triangle de Pascal : chaque ligne commence et finit par $1$ ; les autres nombres sont `L[k] + L[k + 1]`, la somme de deux voisins de la ligne précédente.
- Parties à $2$ éléments : deux boucles, `j` allant de `i + 1` à `len(E) - 1` ; il y en a $\dbinom{n}{2}$.

**Attention : Les pièges**
1. Condition du `while` : le **contraire** de la condition cherchée.
2. Diviser par $\ln(q) \lt 0$ change le sens de l'inégalité.
3. Dichotomie : on garde la moitié où $f$ change de signe.
4. Rectangles : `range(n)` à gauche, `range(1, n + 1)` à droite.
5. Sans `seed`, une simulation change à chaque exécution.

## Exercices corrigés

### Exercice 1 : Terme et somme d'une suite récurrente

La suite $(u_n)$ est définie par $u_0 = 5$ et, pour tout entier naturel $n$, $u_{n+1} = 0{,}5\,u_n + 1$.

1. Calculer $u_1$, $u_2$ et $u_3$.
2. Compléter la fonction suivante pour qu'elle renvoie $u_n$.

```python
def terme(n):
    u = …
    for k in range(…):
        u = …
    return u
```

3. On considère la fonction suivante. Qu'affiche l'instruction `print(somme(3))` ? Que calcule cette fonction ?

```python
def somme(n):
    s = 0
    u = 5
    for k in range(n + 1):
        s = s + u
        u = 0.5 * u + 1
    return s
```

4. On pose $v_n = u_n - 2$. Montrer que la suite $(v_n)$ est géométrique, en déduire l'expression de $u_n$ en fonction de $n$, puis la limite de la suite $(u_n)$.

#### Correction détaillée

## Question 1 : Premiers termes

**Méthode : On applique la relation de récurrence avec $n = 0$, puis $n = 1$, puis $n = 2$.**

**Etape : Calculs**
$$
\begin{aligned}
u_1 &= 0{,}5 \times 5 + 1 = 3{,}5 \\
u_2 &= 0{,}5 \times 3{,}5 + 1 = 2{,}75 \\
u_3 &= 0{,}5 \times 2{,}75 + 1 = 2{,}375
\end{aligned}
$$

**Resultat : $u_1 = 3{,}5$, $u_2 = 2{,}75$ et $u_3 = 2{,}375$.**

## Question 2 : La fonction `terme`

**Méthode : On part de $u_0 = 5$ et on applique $n$ fois la relation de récurrence : la boucle fait $n$ tours.**

**Etape : Fonction complète**
```python
def terme(n):
    u = 5
    for k in range(n):
        u = 0.5 * u + 1
    return u

print(terme(3))
```

```console
2.375
```

**Etape : Tableau d'état de `terme(3)`**
| Étape | `u` |
|---|---|
| avant la boucle | $5$ |
| tour 1 ($k = 0$) | $3{,}5$ |
| tour 2 ($k = 1$) | $2{,}75$ |
| tour 3 ($k = 2$) | $2{,}375$ |

**Resultat : Les trous sont `5`, `n` et `0.5 * u + 1`.**

## Question 3 : La fonction `somme`

**Méthode : On suit les variables `s` et `u` tour par tour : `s` reçoit le terme courant **avant** que `u` passe au terme suivant.**

**Etape : Tableau d'état de `somme(3)`**
| Tour | `s` à la fin du tour | `u` à la fin du tour |
|---|---|---|
| 1 | $5$ | $3{,}5$ |
| 2 | $8{,}5$ | $2{,}75$ |
| 3 | $11{,}25$ | $2{,}375$ |
| 4 | $13{,}625$ | $2{,}1875$ |

**Etape : Vérification par l'exécution**
```python
print(somme(3))
```

```console
13.625
```

**Attention : `range(n + 1)` fait $n + 1$ tours : de $u_0$ à $u_n$, il y a $n + 1$ termes. Avec `range(n)`, on oublierait $u_n$.**

**Resultat : `somme(3)` affiche `13.625` : la fonction renvoie $u_0 + u_1 + \dots + u_n$, ici $5 + 3{,}5 + 2{,}75 + 2{,}375 = 13{,}625$.**

## Question 4 : Expression de $u_n$ et limite

**Méthode : On exprime $v_{n+1}$ en fonction de $v_n$ ; une suite géométrique de raison $q$ avec $-1 \lt q \lt 1$ converge vers $0$.**

**Etape : La suite $(v_n)$ est géométrique**
$$
\begin{aligned}
v_{n+1} &= u_{n+1} - 2 \\
&= 0{,}5\,u_n + 1 - 2 \\
&= 0{,}5\,(u_n - 2) \\
&= 0{,}5\,v_n
\end{aligned}
$$

$(v_n)$ est géométrique de raison $0{,}5$ et de premier terme $v_0 = 5 - 2 = 3$.

**Etape : Expression de $u_n$**
$v_n = 3 \times 0{,}5^n$, donc $u_n = v_n + 2 = 2 + 3 \times 0{,}5^n$. Vérification : $u_3 = 2 + 3 \times 0{,}125 = 2{,}375$.

**Etape : Limite**
Comme $-1 \lt 0{,}5 \lt 1$, $\lim\limits_{n \to +\infty} 0{,}5^n = 0$, donc $\lim\limits_{n \to +\infty} u_n = 2$.

![Termes de la suite u(n+1) = 0,5 u(n) + 1 avec u0 = 5 : ils décroissent et se rapprochent de la droite y = 2](https://optitab-media.s3.eu-north-1.amazonaws.com/exercice_images/v1_n100_ex832_1_e832_limite.png)

**Resultat : $u_n = 2 + 3 \times 0{,}5^n$ et la suite $(u_n)$ converge vers $2$.**

#### Réponses

1. $u_1 = 3{,}5$, $u_2 = 2{,}75$, $u_3 = 2{,}375$.
2. `u = 5`, `range(n)`, `u = 0.5 * u + 1`.
3. `somme(3)` affiche `13.625` ; la fonction renvoie $u_0 + u_1 + \dots + u_n$.
4. $v_{n+1} = 0{,}5\,v_n$, $v_0 = 3$ ; $u_n = 2 + 3 \times 0{,}5^n$ ; $(u_n)$ converge vers $2$.

### Exercice 2 : Une suite majorée qui ne dépasse jamais un seuil

On reprend la situation d'un médicament dont l'organisme élimine $30\,\%$ chaque heure, mais on réinjecte $2$ mg au patient à la fin de chaque heure. On note $u_n$ la quantité (en mg) présente au bout de $n$ heures : $u_0 = 2$ et $u_{n+1} = 0{,}7\,u_n + 2$.

![Nuage des points (n ; u_n) de la suite u(n+1) = 0,7 u(n) + 2 avec u0 = 2, pour n de 0 à 15](https://optitab-media.s3.eu-north-1.amazonaws.com/exercice_images/v1_n100_ex835_1_e835_enonce.png)

1. Calculer $u_1$ et $u_2$.
2. Démontrer par récurrence que, pour tout entier naturel $n$, $0 \lt u_n \lt u_{n+1} \lt \dfrac{20}{3}$.
3. En déduire que la suite $(u_n)$ converge, puis déterminer sa limite.
4. On considère la fonction ci-dessous. Que renvoie `seuil(6)` ? Le vérifier par le calcul, sachant que $u_n = \dfrac{20}{3} - \dfrac{14}{3} \times 0{,}7^n$.

```python
def seuil(A):
    n = 0
    u = 2
    while u <= A:
        u = 0.7 * u + 2
        n = n + 1
    return n
```

5. Expliquer pourquoi l'appel `seuil(7)` ne se termine jamais. Modifier la fonction pour qu'elle s'arrête après au plus `N` tours et renvoie `None` si le seuil n'est pas dépassé.

#### Correction détaillée

## Question 1 : Premiers termes

**Etape : Calculs**
$$
\begin{aligned}
u_1 &= 0{,}7 \times 2 + 2 = 3{,}4 \\
u_2 &= 0{,}7 \times 3{,}4 + 2 = 4{,}38
\end{aligned}
$$

**Resultat : $u_1 = 3{,}4$ et $u_2 = 4{,}38$.**

## Question 2 : Démonstration par récurrence

**Méthode : On note $P(n)$ la propriété « $0 \lt u_n \lt u_{n+1} \lt \frac{20}{3}$ ». On l'initialise, puis on montre qu'elle est héréditaire en appliquant la fonction croissante $x \mapsto 0{,}7x + 2$.**

**Etape : Initialisation**
$u_0 = 2$ et $u_1 = 3{,}4$ : on a bien $0 \lt 2 \lt 3{,}4 \lt \dfrac{20}{3} \approx 6{,}67$. $P(0)$ est vraie.

**Etape : Hérédité**
On suppose $0 \lt u_n \lt u_{n+1} \lt \dfrac{20}{3}$. On multiplie par $0{,}7 \gt 0$, puis on ajoute $2$ :
$$
\begin{aligned}
0{,}7 \times 0 + 2 &\lt 0{,}7\,u_n + 2 \\
&\lt 0{,}7\,u_{n+1} + 2 \\
&\lt 0{,}7 \times \frac{20}{3} + 2
\end{aligned}
$$

soit $2 \lt u_{n+1} \lt u_{n+2} \lt \dfrac{14}{3} + 2 = \dfrac{20}{3}$. Donc $P(n+1)$ est vraie.

**Resultat : Pour tout entier naturel $n$, $0 \lt u_n \lt u_{n+1} \lt \dfrac{20}{3}$ : la suite est croissante et majorée par $\dfrac{20}{3}$.**

## Question 3 : Convergence et limite

**Méthode : Une suite croissante et majorée converge. Sa limite $\ell$ vérifie $\ell = 0{,}7\,\ell + 2$, car $x \mapsto 0{,}7x + 2$ est continue.**

**Etape : Calcul de la limite**
$$\ell = 0{,}7\,\ell + 2 \iff 0{,}3\,\ell = 2 \iff \ell = \frac{20}{3}$$

**Resultat : La suite $(u_n)$ converge vers $\dfrac{20}{3} \approx 6{,}67$ mg.**

## Question 4 : La valeur de `seuil(6)`

**Méthode : On exécute la fonction, puis on résout $u_n \gt 6$ avec le logarithme.**

**Etape : Exécution**
```python
print(seuil(6))
```

```console
6
```

**Etape : Par le calcul**
$$
\begin{aligned}
u_n \gt 6 &\iff \frac{14}{3} \times 0{,}7^n \lt \frac{2}{3} \\
&\iff 0{,}7^n \lt \frac{1}{7} \\
&\iff n \gt \frac{\ln(7)}{-\ln(0{,}7)}
\end{aligned}
$$

et $\dfrac{\ln(7)}{-\ln(0{,}7)} \approx 5{,}46$.

![Termes de la suite avec la droite y = 20/3 en vert, le seuil 6 dépassé dès n = 6 et le seuil 7 jamais dépassé](https://optitab-media.s3.eu-north-1.amazonaws.com/exercice_images/v1_n100_ex835_2_e835_corrige.png)

**Resultat : `seuil(6)` renvoie $6$ : la quantité dépasse $6$ mg à partir de $6$ heures ($u_5 \approx 5{,}88$ et $u_6 \approx 6{,}12$).**

## Question 5 : Le seuil $7$ et le garde-fou

**Méthode : D'après la question 2, $u_n \lt \dfrac{20}{3} \lt 7$ pour tout $n$ : la condition `u <= 7` n'est jamais fausse.**

**Etape : Pourquoi la boucle est infinie**
La boucle `while` ne s'arrête que lorsque $u \gt 7$. Or tous les termes sont inférieurs à $\dfrac{20}{3} \approx 6{,}67$ : la condition reste vraie à chaque tour et la boucle ne s'arrête jamais.

**Etape : Fonction avec garde-fou**
```python
def seuil2(A, N):
    n = 0
    u = 2
    while u <= A and n < N:
        u = 0.7 * u + 2
        n = n + 1
    if u > A:
        return n
    return None

print(seuil2(6, 1000))
print(seuil2(7, 1000))
```

```console
6
None
```

**Attention : Un algorithme de seuil ne doit être lancé que si l'on sait que le seuil sera dépassé. Ici, tout seuil supérieur ou égal à $\dfrac{20}{3}$ n'est jamais dépassé.**

**Resultat : `seuil(7)` boucle sans fin car $u_n \lt \dfrac{20}{3} \lt 7$ ; la fonction `seuil2` s'arrête après au plus `N` tours et renvoie `None`.**

#### Réponses

1. $u_1 = 3{,}4$ et $u_2 = 4{,}38$.
2. Initialisation : $0 \lt 2 \lt 3{,}4 \lt \frac{20}{3}$ ; hérédité en multipliant par $0{,}7$ puis en ajoutant $2$.
3. Croissante et majorée, la suite converge ; $\ell = 0{,}7\,\ell + 2$ donne $\ell = \frac{20}{3}$.
4. `seuil(6)` renvoie $6$ ; $n \gt \frac{\ln(7)}{-\ln(0{,}7)} \approx 5{,}46$.
5. $u_n \lt \frac{20}{3} \lt 7$ : la condition `u <= 7` reste vraie, la boucle est infinie ; garde-fou `while u <= A and n < N:` puis `return None` si `u <= A`.

### Exercice 3 : Surréservation et loi binomiale

Un avion compte $200$ places. Chaque passager ayant réservé se présente à l'embarquement avec la probabilité $0{,}92$, indépendamment des autres. La compagnie vend $n$ billets ($n \ge 200$) ; on note $X_n$ le nombre de passagers qui se présentent. Il y a **surréservation** quand $X_n \gt 200$.

![Diagramme en barres de la loi binomiale B(210 ; 0,92) pour k de 178 à 210, avec la limite des 200 places](https://optitab-media.s3.eu-north-1.amazonaws.com/exercice_images/v1_n100_ex5543_1_surbook_enonce.png)

1. Quelle est la loi de $X_n$ ? Calculer l'espérance de $X_{210}$.
2. La fonction `pb(n, k)` renvoie $P(X_n = k)$. Compléter la fonction `p_sur(n)`, qui renvoie $P(X_n \gt 200)$.

```python
from math import comb

def pb(n, k):
    c = comb(n, k)
    q = 0.08**(n - k)
    return c * 0.92**k * q
```

```python
def p_sur(n):
    s = 0
    for k in range(…, …):
        s = s + pb(n, k)
    return s
```

3. La compagnie vend $210$ billets. Calculer la probabilité de surréservation.
4. La compagnie accepte un risque de surréservation d'au plus $5\,\%$. Écrire un programme qui détermine le nombre maximal de billets qu'elle peut vendre.
5. Pour $210$ billets vendus, déterminer le plus petit entier $k$ tel que $P(X_{210} \gt k) \le 0{,}05$. Interpréter.

#### Correction détaillée

## Question 1 : Loi et espérance

**Méthode : On reconnaît $n$ épreuves de Bernoulli identiques et indépendantes, de succès « le passager se présente ».**

**Etape : Loi de $X_n$**
$X_n$ compte les succès parmi $n$ épreuves indépendantes de probabilité de succès $0{,}92$ : $X_n$ suit la loi $\mathcal{B}(n\,;0{,}92)$.

**Etape : Espérance**
$E(X_{210}) = 210 \times 0{,}92 = 193{,}2$.

**Resultat : $X_n \sim \mathcal{B}(n\,;0{,}92)$ et $E(X_{210}) = 193{,}2$ passagers en moyenne.**

## Question 2 : La fonction `p_sur`

**Méthode : On additionne les probabilités $P(X_n = k)$ pour $k$ allant de $201$ à $n$ : la boucle utilise donc `range(201, n + 1)`.**

**Etape : Fonction complète**
```python
def p_sur(n):
    s = 0
    for k in range(201, n+1):
        s = s + pb(n, k)
    return s
```

**Resultat : La boucle s'écrit `for k in range(201, n + 1):`.**

## Question 3 : Risque pour $210$ billets

**Etape : Exécution**
```python
print(round(p_sur(210), 4))
```

```console
0.0244
```

![Loi B(210 ; 0,92) : les barres k = 201 à 210, en vert, représentent la surréservation, de probabilité environ 0,024](https://optitab-media.s3.eu-north-1.amazonaws.com/exercice_images/v1_n100_ex5543_2_surbook_corrige.png)

**Resultat : $P(X_{210} \gt 200) \approx 0{,}024$ : le risque de surréservation est d'environ $2{,}4\,\%$.**

## Question 4 : Nombre maximal de billets

**Méthode : On augmente $n$ à partir de $200$ **tant que** le risque reste inférieur ou égal à $0{,}05$ ; à la sortie, `n` est le premier nombre qui dépasse le risque, et la réponse est `n - 1`.**

**Etape : Programme**
```python
n = 200
while p_sur(n) <= 0.05:
    n = n + 1
print(n - 1)
print(round(p_sur(n - 1), 4))
print(round(p_sur(n), 4))
```

```console
211
0.0453
0.0774
```

**Resultat : La compagnie peut vendre au plus $211$ billets : $P(X_{211} \gt 200) \approx 0{,}045 \le 0{,}05$, alors que $P(X_{212} \gt 200) \approx 0{,}077$.**

## Question 5 : Plus petit $k$ tel que $P(X_{210} \gt k) \le 0{,}05$

**Méthode : $P(X \gt k) = 1 - P(X \le k)$ : on cumule $P(X = 0)$, …, $P(X = k)$ tant que $1 - P(X \le k) \gt 0{,}05$.**

**Etape : Programme**
```python
k = 0
c = pb(210, 0)
while 1 - c > 0.05:
    k = k + 1
    c = c + pb(210, k)
print(k, round(1 - c, 4))
```

```console
199 0.0471
```

**Resultat : $k = 199$ : avec $210$ billets vendus, il y a plus de $199$ passagers dans moins de $5\,\%$ des cas. Un avion de $199$ places suffirait avec un risque de surréservation d'au plus $5\,\%$.**

#### Réponses

1. $X_n \sim \mathcal{B}(n\,;0{,}92)$ ; $E(X_{210}) = 193{,}2$.
2. `for k in range(201, n + 1):`.
3. $P(X_{210} \gt 200) \approx 0{,}024$.
4. $211$ billets au plus ($0{,}045 \le 0{,}05 \lt 0{,}077$).
5. $k = 199$.
