ƒFiches Maths Soutien
Accueil›Terminale spécialité›Fiche 18

Algorithmique et Python

Écrire, lire et expliquer des programmes liés aux notions de Terminale.

Télécharger le PDF
Un mot d’encouragement, si tu en as besoin

Tu peux avancer à ton rythme. Une difficulté ne définit pas ce dont tu es capable.

Trouver du soutien
Avant de commencer5 questions pour vérifier tes bases
1. Après « x = 3 », puis « x = x + 2 », quelle valeur contient x ?
2. Dans une fonction Python, à quoi sert « return resultat » ?
3. S part de 0. Une boucle ajoute successivement 1, puis 2, puis 3 à S. Que vaut S à la fin ?
4. Avec randint du module random, randint(1, 6) renvoie un entier aléatoire. Quelles valeurs sont possibles ?
5. Une simulation réalise 1 000 essais indépendants d’une même expérience et observe 230 succès. Que fournit 230/1000 ?

Comprendre ce que fait un programme

Un algorithme décrit une suite d'instructions. Python permet de l'exécuter, mais l'ordinateur ne connaît ni la question du cours ni les hypothèses d'un théorème. Un nombre affiché ne dit pas, à lui seul, si c'est une valeur exacte, une approximation contrôlée ou une simulation.

Python : des instructions que l'on peut suivre

Affectation : lire la droite avant de changer la gauche

x = 3
y = x + 2
x = 10
y = y + x
print(x, y)
Instruction exécutéexy
\(\texttt{x = 3}\)3non défini
\(\texttt{y = x + 2}\)35
\(\texttt{x = 10}\)105
\(\texttt{y = y + x}\)1015

y ne reste pas une formule liée à x : son calcul a déjà eu lieu. L'affichage est donc 10 15.

Types, calculs et nombres approchés

intEntier, par exemple -3 ou 1000. Les opérations entières usuelles sont exactes, dans les limites de mémoire.
floatNombre à virgule flottante, par exemple 0.1. C'est une approximation binaire de précision finie, pas un réel exact quelconque.
boolTrue ou False, résultat d'un test.
strTexte, par exemple "bonjour".
listListe ordonnée de valeurs, par exemple [2, 5, 8].
print(7 / 2)       # 3.5 : quotient
print(7 // 2)      # 3 : quotient entier arrondi vers le bas
print(7 % 2)       # 1 : reste
print(-7 // 2)     # -4, car -7 = 2*(-4) + 1
print(2**3)        # 8 : puissance, pas 2^3
print(0.1 + 0.2)   # 0.30000000000000004

Entrées, affichages, imports et exécution

Dans un environnement Python, on peut exécuter des instructions dans une console ou enregistrer un script. Les blocs ci-dessous se lisent de haut en bas. Une fonction définie dans le cours doit être exécutée avant les exemples qui l'appellent ; les imports indiqués doivent aussi avoir été exécutés. Les blocs sont des exemples distincts, pas un unique script à lancer aveuglément.

texte = input("Entier positif ou nul : ")
n = int(texte)
print("Son carré vaut", n**2)

from math import sqrt, exp, log, sin, cos, pi
print(sqrt(2))
print(log(exp(1)))

input renvoie un texte ; int le convertit si son écriture représente un entier. Un texte comme "trois" produit une erreur de conversion. Les fonctions mathématiques gardent leurs domaines : log(x) exige \(x>0\), sqrt(x) exige \(x\geqslant0\) pour un résultat réel. Les angles de sin et cos sont en radians.

Tests et choix : comprendre quelle branche est exécutée

temperature = 0
if temperature < 0:
    print("Température négative")
elif temperature == 0:
    print("Température nulle")
else:
    print("Température positive")

Une chaîne if/elif/else n'exécute qu'une branche : la première dont le test est vrai, ou le else si aucune ne convient. Les deux-points ouvrent un bloc. L'indentation en délimite les instructions ; utiliser quatre espaces par niveau et éviter de mélanger tabulations et espaces.

Boucle for : parcourir sans oublier la borne exclue

print(list(range(2, 7, 2)))   # [2, 4, 6]
print(list(range(5, 0, -2)))  # [5, 3, 1]
S = 0
for k in range(1, 5):
    S = S + k**2
print(S)                    # 30

La boucle additionne quatre termes. L'accumulateur part de 0, élément neutre de l'addition. Après \(k=1,2,3,4\), ses valeurs sont respectivement \(1,5,14,30\). Déplacer S = 0 dans la boucle effacerait les sommes précédentes.

Fonctions : séparer le calcul de son affichage

def carre(x):
    resultat = x**2
    return resultat

y = carre(3) + 1
print(y)                    # 10

Exécuter def définit la fonction et son nom. Son corps s'exécute lorsqu'on l'appelle, ici avec \(x=3\). return renvoie une valeur à l'appelant et quitte la fonction. print affiche, sans fournir à sa place une valeur numérique réutilisable. Une fonction qui termine sans return renvoie None.

def pente_secante(f, x, h):
    if h == 0:
        raise ValueError("h doit être non nul")
    return (f(x + h) - f(x)) / h

Cette fonction prend elle-même une fonction en argument. Il faut que \(x\) et \(x+h\) appartiennent à son domaine. Pour \(f(x)=x^2\), \(x=2\) et \(h=0{,}1\), le résultat mathématique vaut

\[\frac{(2+0{,}1)^2-2^2}{0{,}1}=4{,}1,\]

à comparer à \(f'(2)=4\). Un \(h\) excessivement petit peut amplifier les erreurs d'arrondi lors de la soustraction : « plus petit » n'est pas une garantie universelle.

Listes : une suite de cases, indexées à partir de zéro

L = [4, 7, 9]
print(L[0], L[-1], len(L))  # 4 9 3
L[1] = 8                   # modification : [4, 8, 9]
L.append(12)               # extension : [4, 8, 9, 12]
dernier = L.pop()           # renvoie 12 et le supprime
del L[0]                   # suppression par indice : [8, 9]
carres = [k**2 for k in range(5)]
positifs = [x for x in [-2, 0, 3, 5] if x > 0]
for valeur in carres:
    print(valeur)
for indice in range(len(carres)):
    print(indice, carres[indice])

Pour une liste de longueur \(m\), les indices positifs autorisés sont \(0\) à \(m-1\). L[m] est en dehors de la liste. append ajoute une case à la fin ; la compréhension [k**2 for k in range(5)] construit \([0,1,4,9,16]\). La liste positifs vaut \([3,5]\) : le test placé après if filtre les éléments, sans modifier la liste parcourue. Remplacer \(>\) par \(\geqslant\) inclurait aussi 0.

Boucle while : prévoir pourquoi elle s'arrête

u = 100
n = 0
while u <= 200:
    u = 1.05 * u
    n = n + 1
print(n)                    # 15

Le test a lieu avant chaque passage. La boucle continue tant que \(u\leqslant200\) ; elle s'arrête au premier \(u>200\). Après \(n\) passages, \(u=100\times1{,}05^n\). Cette suite tend vers \(+\infty\), donc elle finit par franchir 200. On obtient \(n=15\) ; \(100\times1{,}05^{14}<200\) et \(100\times1{,}05^{15}>200\).

Petits outils réutilisables et tests pertinents

Les fonctions numériques suivantes utilisent un contrôle commun pour leurs nombres d'étapes. raise ValueError signale une entrée qui ne respecte pas le contrat ; ce n'est pas un résultat mathématique.

from math import isfinite

def entier_naturel(n, minimum=0):
    if type(n) is not int or n < minimum:
        raise ValueError("entier hors du domaine demandé")

def probabilite(p):
    if not 0 <= p <= 1:
        raise ValueError("p doit appartenir à [0, 1]")

Le programme peut vérifier un entier, un signe ou une borne. Il ne peut pas déduire d'un simple test que les tirages de ton modèle sont indépendants, ni qu'une fonction est continue sur tout un intervalle. Ces hypothèses restent à établir dans le raisonnement. Dans les programmes suivants, isfinite(x) vérifie que le nombre flottant n'est ni infini ni indéterminé ; all(liste) renvoie vrai si tous les tests de la liste sont vrais. Par exemple all([True, False]) vaut False. La compréhension [isfinite(x) for x in [a,b]] produit un test pour chaque borne. Tester un cas connu, un cas frontière et un contre-exemple ciblé est plus instructif que lancer seulement un gros calcul. Une série finie de tests ne prouve pas un énoncé « pour tout entier » ; un seul résultat contraire suffit toutefois à le réfuter.

Dichotomie : garder une solution entre deux bornes

Le dessin avant le programme

Pour \(f(x)=x^2-2\) sur \([1,2]\), les signes sont \(-\) puis \(+\). Au milieu \(1{,}5\), \(f(1{,}5)=0{,}25>0\) : on garde \([1,1{,}5]\). Le milieu suivant est \(1{,}25\) ; son image vaut \(-0{,}4375\), donc on garde \([1{,}25,1{,}5]\).

Schéma : Le dessin avant le programme

Un intervalle en sortie, puis un centre

Le contrat demande \(\varepsilon>0\), des bornes finies et les hypothèses précédentes. Les valeurs calculées de \(f\) doivent être finies. Le contrôle de signe évite de multiplier deux valeurs flottantes potentiellement très grandes ou très petites.

def dichotomie_intervalle(f, a, b, eps):
    if not all([isfinite(x) for x in [a, b, eps]]):
        raise ValueError("bornes et tolérance finies")
    if not a < b or eps <= 0:
        raise ValueError("a < b et eps > 0 requis")
    fa, fb = f(a), f(b)
    if not isfinite(fa) or not isfinite(fb):
        raise ValueError("images non finies")
    if fa == 0:
        return [a, a]
    if fb == 0:
        return [b, b]
    if (fa < 0) == (fb < 0):
        raise ValueError("signes opposés requis")
    while b - a > eps:
        m = a / 2 + b / 2
        if m == a or m == b:
            raise ArithmeticError("précision flottante atteinte")
        fm = f(m)
        if not isfinite(fm):
            raise ValueError("image non finie")
        if fm == 0:
            return [m, m]
        if (fa < 0) == (fm < 0):
            a, fa = m, fm
        else:
            b = m
    return [a, b]

Chaque branche conserve des signes opposés : si le milieu a le même signe que la borne gauche, on déplace cette borne gauche. Sinon on déplace la droite. La valeur de fa doit suivre celle de a.

def dichotomie(f, a, b, eps):
    bornes = dichotomie_intervalle(f, a, b, eps)
    return bornes[0] / 2 + bornes[1] / 2

def carre_moins_deux(x):
    return x**2 - 2

print(dichotomie_intervalle(carre_moins_deux, 1, 2, 0.01))

En arithmétique exacte, la largeur finale est au plus eps et l'erreur du centre au plus eps/2. En flottants, les signes évalués et les milieux subissent des arrondis : le programme signale une stagnation, mais ne constitue pas un calcul certifié par arithmétique d'intervalles. Aux précisions usuelles, contrôler aussi la cohérence du résultat avec le graphe et l'étude de \(f\).

Euler : avancer avec la pente actuelle

De la tangente à une suite de points

Pour

\[y'=y,\]
\[y(0)=1,\]
\[h=0{,}5\]
\[\begin{aligned}y_1 &= 1+0{,}5\times1\\[.35em]&= 1{,}5,\\[.35em]y_2 &= 1{,}5+0{,}5\times1{,}5\\[.35em]&= 2{,}25.\end{aligned}\]

La valeur exacte en \(t=1\) est \(\e\approx2{,}71828\). En quatre pas de \(0{,}25\), Euler donne \(1{,}25^4=2{,}44140625\), ici plus proche.

Schéma : De la tangente à une suite de points

Les segments relient les points calculés. Ils montrent la construction polygonale d'Euler ; seule la courbe verte représente la solution exacte de cet exemple.

Programmer et interpréter le pas

def euler(f, t0, y0, h, n):
    entier_naturel(n)
    if not all([isfinite(x) for x in [t0, y0, h]]) or h <= 0:
        raise ValueError("données finies et h > 0 requis")
    T, Y = [t0], [y0]
    t, y = t0, y0
    for k in range(n):
        pente = f(t, y)
        y = y + h * pente
        t = t0 + (k + 1) * h
        if not isfinite(t) or not isfinite(y):
            raise ArithmeticError("calcul non fini")
        T.append(t)
        Y.append(y)
    return [T, Y]

Les listes ont \(n+1\) valeurs car elles incluent le point initial. La pente utilise l'ancien couple \((t,y)\) ; on ne met pas à jour le temps avant de la calculer. Pour \(n=0\), on renvoie seulement les données initiales.

Intégrer avec des rectangles

Choisir la hauteur et conserver le signe

On suppose \(f\) continue sur \([a,b]\), \(a<b\), et \(n\geqslant1\) entier. Posons \(h=(b-a)/n\) et \(x_k=a+kh\). Les trois sommes suivantes choisissent la hauteur au bord gauche, au bord droit ou au milieu de chaque intervalle :

\[\begin{aligned}L_n&=h\sum_{k=0}^{n-1}f(x_k),\\[.35em]R_n&=h\sum_{k=0}^{n-1}f(x_{k+1}),\\[.35em]M_n&=h\sum_{k=0}^{n-1}f(x_k+h/2).\end{aligned}\]

Les trois convergent vers \(\int_a^b f(x)\,\mathrm dx\) quand \(n\to+\infty\). Une hauteur négative fournit une contribution négative : l'intégrale est une aire algébrique, pas toujours une aire positive.

Schéma : Choisir la hauteur et conserver le signe

Ici \(f(x)=x^2\), \([a,b]=[0,1]\), \(n=4\). Le premier rectangle a une hauteur nulle. La somme gauche vaut

\[\begin{aligned}L_4 &= 7/32\\[.35em]&= 0{,}21875\end{aligned}\]

et la somme droite

\[\begin{aligned}R_4 &= 15/32\\[.35em]&= 0{,}46875.\end{aligned}\]

La fonction étant croissante, elles encadrent l'intégrale \(1/3\).

Une fonction commune pour éviter trois copies presque identiques

def riemann(f, a, b, n, position):
    entier_naturel(n, 1)
    if not all([isfinite(x) for x in [a, b]]) or not a < b:
        raise ValueError("bornes finies et a < b requis")
    if position not in [0, 0.5, 1]:
        raise ValueError("position : 0, 0.5 ou 1")
    h = (b - a) / n
    S = 0
    for k in range(n):
        x = a + (k + position) * h
        valeur = f(x)
        if not isfinite(valeur):
            raise ValueError("image non finie")
        S = S + valeur
    return h * S

def riemann_gauche(f, a, b, n):
    return riemann(f, a, b, n, 0)

def riemann_droite(f, a, b, n):
    return riemann(f, a, b, n, 1)

def riemann_milieu(f, a, b, n):
    return riemann(f, a, b, n, 0.5)

Le paramètre position déplace le point d'évaluation à l'intérieur de chaque intervalle. Les trois fonctions courtes expriment l'intention et réutilisent le même calcul. Cette organisation en petites fonctions est la programmation modulaire.

Simuler : prévoir ce qui change et ce qui reste fixe

Une épreuve, un échantillon, plusieurs échantillons

random() produit un nombre pseudo-aléatoire dans \([0,1[\). Dans le modèle continu idéal uniforme, la proportion de cet intervalle située sous \(p\) est \(p\). Le test random() < p permet ainsi de simuler une Bernoulli de paramètre \(p\). Les appels successifs servent à modéliser des essais indépendants ; répéter un résultat déjà tiré ne simule pas de nouveaux essais.

from random import random, randint, choice

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

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

def frequence(n, p):
    entier_naturel(n, 1)
    return binomiale(n, p) / n

def echantillons(N, n, p):
    entier_naturel(N, 1)
    entier_naturel(n, 1)
    probabilite(p)
    return [frequence(n, p) for _ in range(N)]

binomiale(0,p) vaut 0 ; une fréquence sur zéro essai n'est pas définie. Pour \(p=0\), tous les résultats valent 0 ; pour \(p=1\), ils valent 1. Le caractère _ est ici un nom de boucle dont la valeur n'est pas utilisée. echantillons(100,20,0.3) renvoie 100 fréquences, calculées chacune sur 20 essais. Les nombres \(N\) et \(n\) n'ont pas le même rôle.

Voir une trajectoire, puis comparer des dispersions

def frequences_cumulees(n, p):
    entier_naturel(n, 1)
    probabilite(p)
    S = 0
    valeurs = []
    for k in range(1, n + 1):
        S = S + bernoulli(p)
        valeurs.append(S / k)
    return valeurs

La liste commence par la fréquence après un essai. Le graphique doit donc utiliser les abscisses de 1 à \(n\), et non de 0 à \(n-1\).

# Affichage facultatif : nécessite matplotlib.
import matplotlib.pyplot as plt
n, p = 200, 0.5
valeurs = frequences_cumulees(n, p)
plt.plot(range(1, n + 1), valeurs)
plt.axhline(p, color="black", linestyle="--")
plt.xlabel("Nombre d'essais")
plt.ylabel("Fréquence observée")
plt.show()

La fréquence peut s'éloigner de \(p\) à l'étape suivante. La loi des grands nombres décrit un risque d'écart pour une taille croissante, pas une obligation de rapprochement à chaque tirage.

La fiche 17 complète ce travail : simuler \(N\) échantillons de taille \(n\), comparer leur écart-type observé à \(\sqrt{p(1-p)/n}\), puis compter les fréquences à moins de un, deux et trois écarts-types théoriques de \(p\). Comparer plusieurs tailles et répéter avec un nouveau lot. Cela explore la variabilité ; un lot simulé ne démontre pas une borne de probabilité.

Suites, seuils et recherche sur une grille

Stocker les termes : le rang zéro compte aussi

def termes_suite(f, u0, n):
    entier_naturel(n)
    termes = [u0]
    u = u0
    for k in range(n):
        u = f(u)
        termes.append(u)
    return termes

Le contrat demande que \(f\) soit définie sur tous les termes rencontrés. La liste contient \(u_0\) à \(u_n\), donc \(n+1\) termes. Pour obtenir les vingt premiers termes, on demande \(n=19\). Le rang d'une case coïncide ici avec celui de la suite : termes[k] vaut \(u_k\).

Limiter la recherche sans inventer une conclusion

def seuil_borne(f, u0, M, max_iter=10000):
    entier_naturel(max_iter)
    if not isfinite(u0) or not isfinite(M):
        raise ValueError("valeurs finies requises")
    u = u0
    for n in range(max_iter + 1):
        if u > M:
            return n
        if n < max_iter:
            u = f(u)
            if not isfinite(u):
                raise ArithmeticError("terme non fini")
    return None

Si un rang est renvoyé, tous les rangs précédents ont été testés et ont échoué : c'est le premier franchissement strict dans la plage explorée. None signifie « aucun franchissement trouvé jusqu'à max_iter », pas « aucun franchissement n'existe ». Si \(u_0>M\), le résultat est 0, même avec zéro mise à jour autorisée. Une preuve de limite peut établir à part qu'un seuil sera finalement franchi.

Un maximum calculé sur des points, pas automatiquement sur tout un intervalle

def maximum_balayage(f, a, b, n):
    entier_naturel(n, 1)
    if not all([isfinite(x) for x in [a, b]]) or not a < b:
        raise ValueError("bornes finies et a < b requis")
    x_max, y_max = a, f(a)
    if not isfinite(y_max):
        raise ValueError("image non finie")
    for k in range(1, n + 1):
        x = a + (b - a) * k / n
        y = f(x)
        if not isfinite(y):
            raise ValueError("image non finie")
        if y > y_max:
            x_max, y_max = x, y
    return [x_max, y_max]

Il y a \(n+1\) points, bornes incluses. On initialise le maximum à \(f(a)\), ce qui fonctionne aussi si toutes les valeurs sont négatives. Avec le test strict, la première abscisse rencontrée est conservée en cas d'égalité.

Triangle de Pascal : utiliser la ligne précédente

def pascal(n):
    entier_naturel(n)
    lignes = [[1]]
    for k in range(1, n + 1):
        precedente = lignes[-1]
        ligne = [1]
        for j in range(1, k):
            ligne.append(precedente[j - 1] + precedente[j])
        ligne.append(1)
        lignes.append(ligne)
    return lignes

La ligne 0 est \([1]\), les suivantes \([1,1]\), \([1,2,1]\), \([1,3,3,1]\). Le coefficient lignes[k][j] vaut \(\binom{k}{j}\). La formule de Pascal additionne deux cases de la ligne précédente ; une nouvelle liste est créée à chaque tour.

Choisir, expliquer, vérifier

Approfondissement : la méthode de Newton

Soit \(f\) dérivable sur un intervalle, et \(\alpha\) un zéro recherché. Dans les questions qui utilisent Taylor, on suppose de plus \(f\) de classe \(C^2\) près de \(\alpha\) et \(f'(\alpha)\ne0\).

Partie A : La construction géométrique

  1. Écrire la tangente au point d'abscisse \(x_n\).

  2. Si \(f'(x_n)\ne0\), déterminer l'abscisse \(x_{n+1}\) où elle coupe l'axe horizontal. Retrouver \(x_{n+1}=x_n-f(x_n)/f'(x_n)\).

  3. Pour \(f(x)=x^2-2\) et \(x_0=1\), placer la première tangente et sa rencontre avec l'axe. Cette rencontre est-elle déjà le zéro de \(f\) ?

Partie B : Programmer et définir l'arrêt

  1. Écrire newton(f, df, x0, eps, max_iter). On exige \(\varepsilon>0\) et on accepte un résultat seulement si \(|f(x)|<\varepsilon\). Signaler un échec si la dérivée est nulle hors d'un zéro ou si le nombre maximal de mises à jour est atteint.

  2. Appliquer à \(x^2-2\) avec \(x_0=1\) et \(\varepsilon=10^{-15}\). Comparer le résidu \(|f(x)|\) à l'erreur \(|x-\sqrt2|\) : ce sont deux nombres différents.

  3. Combien de divisions par deux suffisent pour qu'un intervalle initial \([1,2]\) ait une largeur au plus \(10^{-15}\) ? Comparer des nombres d'étapes permet-il, seul, de comparer les temps de calcul ?

Partie C : Comprendre la convergence locale

  1. Sous les hypothèses \(C^2\) et zéro simple, utiliser Taylor entre \(x_n\) et \(\alpha\) pour relier \(e_{n+1}=x_{n+1}-\alpha\) à \(e_n^2\).

  2. Expliquer ce que signifie une borne \(|e_{n+1}|\leqslant C|e_n|^2\) près du zéro. Pourquoi ne garantit-elle pas un doublement exact des décimales à toutes les étapes ni en précision flottante limitée ?

  3. Dans le cas \(x^2-2\), calculer \(x_1\) à \(x_4\). Justifier l'identité exacte \(e_{n+1}=e_n^2/(2x_n)\) pour \(x_n>0\).

Partie D : Comprendre les échecs et conserver un intervalle

  1. Examiner \(f(x)=x^3-1\) avec \(x_0=0\). Comparer avec \(f(x)=x^2\) et \(x_0=0\) : la dérivée est nulle dans les deux cas, mais les situations sont-elles identiques ?

  2. Calculer deux étapes pour \(f(x)=x^3-2x+2\) avec \(x_0=0\). Que constate-t-on ?

  3. Proposer une méthode hybride qui conserve des signes opposés : accepter une proposition de Newton seulement si elle appartient à la moitié centrale de l'intervalle courant ; sinon choisir le milieu. Expliquer pourquoi la largeur se réduit alors d'un facteur au plus \(3/4\) à chaque étape sans zéro exact.

Fiche mémoire

Revois une base utile ou prolonge ce chapitre.