Aller au contenu
OptiTAB

Maths Première · Chapitre 3 · Algorithmique et programmation

Algorithmes du programme de Première

  • 8 parties
  • 6 schémas
  • Lecture ≈ 17 min
  • Conforme au programme
Objectifs

Écrire, lire et utiliser en Python les algorithmes du programme de Première : terme, somme et seuil d'une suite ; tableau de valeurs et balayage ; coefficients directeurs de sécantes ; méthode d'Euler et valeur approchée de e ; approximation de π ; simulation d'expériences aléatoires, fréquence et moyenne d'un échantillon.

Prérequis

Programme de Seconde : variables, fonctions def, instructions conditionnelles if, boucles for et while. Suites numériques, second degré, dérivation, fonction exponentielle et probabilités conditionnelles de Première.

ILes outils

Les algorithmes de ce chapitre n'utilisent que des outils vus en Seconde. Ils sont rappelés ici ; le reste du chapitre les applique aux notions de Première.

RappelRappel de Seconde
  • 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. range(a, b) donne les entiers de a à b−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, 1 pour un produit, 0 pour un compteur.
Type d'algorithmeBoucle utilisée
terme de rang n, somme, factorielle, méthode d'Eulerfor : nombre de tours connu
seuil, balayagewhile : on répète tant que le but n'est pas atteint
simulation de N expériencesfor et un compteur

IISuites numériques

1. Calculer un terme de rang donné

MéthodeTerme d'une suite définie par récurrence

Pour calculer un, on part de u0 et on applique n fois la relation de récurrence : c'est une boucle for de n tours. La variable k ne sert qu'à compter les tours.

Exempleu0=0 et un+1=0,5un+2
Python
def terme(n):
    u = 0
    for k in range(n):
        u = 0.5 * u + 2
    return u

for n in range(6):
    print(n, terme(n))
Affichage
0 0
1 2.0
2 3.0
3 3.5
4 3.75
5 3.875

Le tableau d'état de l'appel terme(3) donne la valeur de u à la fin de chaque tour :

Étapeku
avant la boucle—0
tour 100,5×0+2=2
tour 210,5×2+2=3
tour 320,5×3+2=3,5
RemarqueSuite définie de façon explicite

Si un=f(n), aucune boucle n'est nécessaire : pour un=3n2+1, la fonction contient la seule ligne return 3 * n**2 + 1.

2. Somme de termes et factorielle

MéthodeSomme u0+u1+⋯+un

On fait avancer ensemble l'accumulateur s et le terme u. De u0 à un, il y a n+1 termes : la boucle fait n+1 tours.

Exemple1+2+22+⋯+210

Ici u0=1 et uk+1=2uk.

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

print(somme(10))
Affichage
2047

On retrouve la formule de la somme des termes d'une suite géométrique :

1+2+⋯+210=211−12−1=2047
ExempleFactorielle

Pour n≥1, n!=1×2×⋯×n. Un produit s'initialise à 1.

Python
def factorielle(n):
    p = 1
    for k in range(1, n + 1):
        p = p * k
    return p

print(factorielle(10))
Affichage
3628800

3. Algorithme de seuil

MéthodePlus petit rang n tel que un>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 un>A, on répète donc tant que u≤A. À la sortie, n est le rang cherché.

Exempleu0=2, un+1=1,5un et le seuil A=50
Python
def seuil(A):
    n = 0
    u = 2
    while u <= A:
        u = 1.5 * u
        n = n + 1
    return n

print(seuil(50))
Affichage
8

En effet u7=2×1,57≈34,17≤50 et u8=2×1,58≈51,26>50.

Termes de la suite u_n = 2 × 1,5^n et seuil 50 : u_7 ≈ 34,17 est sous le seuil, u_8 ≈ 51,26 le dépasse
AttentionCondition du while

Écrire while u > A: est une erreur classique : comme u0=2≤50, la condition est fausse dès le départ, la boucle ne fait aucun tour et la fonction renvoie 0.

4. Une suite 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. Il faut le justifier avant de lancer le programme.

Exempleu0=0 et un+1=0,5un+2
Python
def seuil(A):
    n = 0
    u = 0
    while u <= A:
        u = 0.5 * u + 2
        n = n + 1
    return n

print(seuil(3.9))
Affichage
6

En revanche, l'appel seuil(5) ne se termine jamais. Posons vn=un−4 :

vn+1=un+1−4=0,5un−2=0,5(un−4)=0,5vn

La suite (vn) est géométrique de raison 0,5 et de premier terme v0=−4, donc un=4−4×0,5n. Ainsi un<4 pour tout n : la condition u <= 5 reste toujours vraie et la boucle est infinie.

Termes de la suite u_n = 4 − 4 × 0,5^n, tous inférieurs à 4 : le seuil 5 n'est jamais dépassé
ConseilUn garde-fou

On peut limiter le nombre de tours en prenant pour condition u <= A and n < 1000 ; après la boucle, on teste si le seuil a bien été dépassé avant de renvoyer n.

IIIFonctions : tableau de valeurs et balayage

1. Tableau de valeurs

Exemplef(x)=x2−4x+1 pour x entier de −1 à 5
Python
def f(x):
    return x**2 - 4*x + 1

for x in range(-1, 6):
    print(x, f(x))
Affichage
-1 6
0 1
1 -2
2 -3
3 -2
4 1
5 6

On lit le minimum f(2)=−3, qui est bien l'ordonnée du sommet car f(x)=(x−2)2−3. La fonction change de signe entre 0 et 1, puis entre 3 et 4 : chaque intervalle contient une solution de f(x)=0.

2. Balayage

MéthodeEncadrer une solution de f(x)=0

On part d'un nombre a et on avance de pas en pas tant que f garde le même signe. On obtient un encadrement d'amplitude pas de la solution.

ExempleSolution de f(x)=0 dans [0;1]

f est strictement décroissante sur [0;2], avec f(0)=1>0 et f(1)=−2<0.

Python
def balayage(a, pas):
    x = a
    while f(x + pas) > 0:
        x = x + pas
    x = round(x, 6)
    return x, round(x + pas, 6)

print(balayage(0, 0.1))
print(balayage(0, 0.01))
print(balayage(0, 0.001))
Affichage
(0.2, 0.3)
(0.26, 0.27)
(0.267, 0.268)

La fonction round(x, 6) arrondit à 10−6 : elle efface les erreurs d'arrondi des nombres décimaux en machine (sans elle, Python afficherait par exemple 0.30000000000000004).

Vérification : le discriminant de x2−4x+1 vaut Δ=12, d'où la solution x1=2−3≈0,2679, qui appartient bien à [0,267;0,268].

IVDérivation : coefficients directeurs des sécantes

Le coefficient directeur de la sécante qui passe par les points de la courbe d'abscisses x et x+h est le taux de variation

f(x+h)−f(x)h

Quand h tend vers 0, il tend vers le nombre dérivé f′(x).

ExempleListe des coefficients directeurs pour un pas donné

Pour f(x)=x2 et le pas h=0,1 :

Python
def f(x):
    return x**2

h = 0.1
for x in range(4):
    t = (f(x + h) - f(x)) / h
    print(x, round(t, 6))
Affichage
0 0.1
1 2.1
2 4.1
3 6.1

En effet

(x+h)2−x2h=2xh+h2h=2x+h

Chaque valeur dépasse f′(x)=2x de h=0,1 : plus le pas est petit, plus la liste est proche des nombres dérivés.

VFonction exponentielle

1. La méthode d'Euler

La fonction exponentielle est l'unique fonction f dérivable sur R telle que f′=f et f(0)=1. Pour h proche de 0, l'approximation affine f(x+h)≈f(x)+hf′(x) donne

f(x+h)≈f(x)+hf(x)=(1+h)f(x)
MéthodeMéthode d'Euler

On part du point (0;1) et, à chaque tour, on avance de h en abscisse et on multiplie l'ordonnée par 1+h :

xk+1=xk+hyk+1=yk+hyk

Les points (xk;yk) forment une ligne brisée proche de la courbe de la fonction exponentielle.

ExemplePas h=0,25 sur [0;2]
Python
h = 0.25
x = 0
y = 1
for k in range(8):
    x = x + h
    y = y + h * y
    print(x, round(y, 4))
Affichage
0.25 1.25
0.5 1.5625
0.75 1.9531
1.0 2.4414
1.25 3.0518
1.5 3.8147
1.75 4.7684
2.0 5.9605
Courbe de la fonction exponentielle sur [0 ; 2] et ligne brisée de la méthode d'Euler avec le pas 0,25, située sous la courbe
Remarque

La courbe de la fonction exponentielle est au-dessus de ses tangentes : la méthode d'Euler donne ici des valeurs par défaut (5,96<e2≈7,39). L'écart diminue quand on choisit un pas plus petit.

2. Valeur approchée de e

Avec n pas de longueur h=1n, on arrive en x=1 ; l'ordonnée y est multipliée n fois par 1+1n, donc elle vaut (1+1n)n, valeur approchée de e=exp⁡(1).

Python
for n in [10, 100, 1000, 10**6]:
    print(n, (1 + 1/n)**n)
Affichage
10 2.5937424601000023
100 2.7048138294215285
1000 2.7169239322355936
1000000 2.7182804690957534

On admet que ces valeurs se rapprochent de e≈2,71828, en restant inférieures à e.

AttentionLes parenthèses

(1 + 1/n)**n calcule (1+1n)n. Sans les parenthèses, 1 + 1/n**n calcule 1+1nn, qui est très proche de 1.

VITrigonométrie : approximation de π

Archimède encadre la longueur 2π d'un cercle de rayon 1 par les périmètres de polygones réguliers. On présente ici les polygones inscrits dans le cercle.

PropriétéPolygone inscrit

Soit cn la longueur d'un côté du polygone régulier à n côtés inscrit dans un cercle de rayon 1. Son demi-périmètre pn=ncn2 est inférieur à π, et

c2n=2−4−cn2
Hexagone régulier inscrit dans un cercle de centre O : sommets A et B, milieu I de [AB], point C du cercle sur [OI) et côtés [AC] et [CB] du polygone à 12 côtés
Démonstration

Soit A et B deux sommets consécutifs du polygone à n côtés, I le milieu de [AB] et C le point du cercle sur la demi-droite [OI) : [AC] est un côté du polygone à 2n côtés.

Dans le triangle OIA rectangle en I :

OI2=OA2−AI2=1−cn24

donc OI=4−cn22.

Dans le triangle AIC rectangle en I, avec IC=1−OI :

AC2=AI2+IC2=cn24+1−2OI+OI2=cn24+1−4−cn2+1−cn24=2−4−cn2
ExempleDe l'hexagone au polygone à 96 côtés

L'hexagone régulier inscrit est formé de 6 triangles équilatéraux : c6=1 et p6=3.

Python
from math import sqrt

n = 6
c = 1
for k in range(4):
    c = sqrt(2 - sqrt(4 - c**2))
    n = 2 * n
    print(n, n * c / 2)
Affichage
12 3.1058285412302498
24 3.132628613281237
48 3.139350203046872
96 3.14103195089053

Avec 96 côtés, Archimède obtenait ainsi 3,1410<π. En utilisant aussi les polygones circonscrits, il prouvait que 22371<π<227.

VIIProbabilités : simuler une expérience aléatoire

1. Les fonctions du module random

  • random() renvoie un nombre réel au hasard dans [0;1[ : le test random() < p est vrai avec la probabilité p.
  • randint(a, b) renvoie un entier au hasard entre a et b inclus : randint(1, 6) simule un dé équilibré.

Les résultats changent à chaque exécution ; les affichages de cette partie sont ceux d'une exécution.

2. Fréquence d'un événement

MéthodeCalculer une fréquence

On répète N fois l'expérience avec une boucle for, on compte avec un compteur c les fois où l'événement est réalisé, puis on renvoie cN.

ExempleSomme de deux dés égale à 7
Python
from random import randint

def frequence(N):
    c = 0
    for i in range(N):
        d1 = randint(1, 6)
        d2 = randint(1, 6)
        if d1 + d2 == 7:
            c = c + 1
    return c / N

print(frequence(10000))
Affichage
0.1642

Sur les 36 issues équiprobables, 6 donnent une somme égale à 7 : la probabilité vaut 636=16≈0,167. Pour N grand, la fréquence observée en est proche.

ExempleToutes les sommes : histogramme de 1000 lancers

La liste eff (voir la notion « Notion de liste ») compte les lancers de chaque somme s.

Python
from random import randint

N = 1000
eff = [0] * 13
for i in range(N):
    d1 = randint(1, 6)
    d2 = randint(1, 6)
    s = d1 + d2
    eff[s] = eff[s] + 1
for s in range(2, 13):
    print(s, eff[s])
Affichage
2 32
3 52
4 86
5 120
6 139
7 173
8 121
9 113
10 81
11 59
12 24
Histogramme des fréquences observées des sommes de deux dés sur 1000 lancers, comparées aux probabilités théoriques

3. Moyenne d'un échantillon

ExempleUn jeu de dé

On lance un dé équilibré : on gagne 4 € avec un 6, 1 € avec un 4 ou un 5, et on perd 1 € sinon. Le gain X a pour espérance

E(X)=4×16+1×26−1×36=36=0,5
Python
from random import randint

def gain():
    d = randint(1, 6)
    if d == 6:
        return 4
    elif d >= 4:
        return 1
    else:
        return -1

def moyenne(n):
    s = 0
    for i in range(n):
        s = s + gain()
    return s / n

print(moyenne(10000))
Affichage
0.4776

La moyenne d'un échantillon de grande taille est proche de l'espérance E(X)=0,5 ; elle change d'un échantillon à l'autre.

4. Succession de deux épreuves

ExempleDeux tirages sans remise

Une urne contient 3 boules rouges et 2 vertes. On tire une boule, on ne la remet pas, puis on en tire une seconde. La composition de l'urne au second tirage dépend du premier.

Arbre pondéré de deux tirages sans remise dans une urne de 3 boules rouges et 2 vertes, avec les probabilités des quatre issues

D'après l'arbre, la probabilité que les deux boules soient de la même couleur vaut

35×24+25×14=620+220=0,4

La fonction tirage(r, v) simule un tirage dans une urne de r boules rouges et v vertes ; experience() enchaîne les deux épreuves.

Python
from random import random

def tirage(r, v):
    if random() < r / (r + v):
        return "R"
    return "V"

def experience():
    t1 = tirage(3, 2)
    if t1 == "R":
        t2 = tirage(2, 2)
    else:
        t2 = tirage(3, 1)
    return t1 + t2

N = 10000
c = 0
for i in range(N):
    e = experience()
    if e == "RR" or e == "VV":
        c = c + 1
print(c / N)
Affichage
0.406

La fréquence observée est proche de la probabilité 0,4.

VIIIBilan

Partie du programmeAlgorithmeStructure
Suitesterme un, somme, factoriellefor
Suitesseuilwhile (condition contraire)
Second degré, fonctionstableau de valeurs, balayagefor, while
Dérivationcoefficients directeurs des sécantesfor
Exponentielleméthode d'Euler, valeur approchée de efor
Trigonométrieapproximation de π (Archimède)for
Probabilitésfréquence, moyenne, deux épreuvesfor et random
AttentionPièges fréquents
  • range(n) va de 0 à n−1 : la somme u0+⋯+un demande range(n + 1).
  • L'accumulateur s'initialise avant la boucle ; un produit commence à 1.
  • 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é, sinon la boucle est infinie.
  • Les nombres décimaux sont arrondis en machine : round rend l'affichage lisible.
  • randint(1, 6) inclut 6 ; une simulation donne un résultat différent à chaque exécution.
À retenir
  • Terme de rang n : n applications de la relation de récurrence (boucle for).
  • Seuil : boucle while et compteur, à condition que le seuil soit atteint.
  • Balayage : on avance de pas en pas tant que f garde le même signe.
  • Sécantes : f(x+h)−f(x)h tend vers f′(x) quand h tend vers 0.
  • Euler : y←y+hy ; (1+1n)n tend vers e.
  • Simulation : random() < p réalise un événement de probabilité p ; fréquence =cN.

Fiche de synthèse dans l'onglet Fiches !

Cours lu ? Continue avec :

Plateforme OptiTAB

S’entraîner jusqu’à maîtriser le programme de Première

Les 11 exercices corrigés de ce chapitre, le suivi de tes progrès et des révisions guidées.

Découvrir l’abonnement

Cours particuliers

Un prof de maths en Première, en ligne

Des séances individuelles avec un professeur, à distance, pour comprendre, combler ses lacunes et préparer les contrôles et le bac.

Réserver un cours particulier