Algorithmique et Python en Terminale STI2D

Algorithmique et Python en Terminale STI2D : cours complet

Rappels : fonctions, compteurs, accumulateurs

Méthode — Structure d'un programme. On découpe une tâche en fonctions courtes, chacune avec ses entrées (paramètres) et sa sortie (return). Un compteur part de $0$0 et augmente de $1$1 quand une condition est réalisée ; un accumulateur part de $0$0 (somme) ou de $1$1 (produit).

Exemple — Bernoulli et compteur.

from random import random

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

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

Sommes et notation $\sum$Σ

Définition — Notation $\sum$Σ. $\sum _{k=1}^n{u}_k=u_1+u_2+\dots +u_n$Σ_k=1ⁿ uₖ = u₁ + u₂ + … + uₙ. L'indice $k$k est le compteur de la boucle, $u_k$uₖ le terme ajouté à l'accumulateur, $1$1 et $n$n les bornes de la boucle.

Exemple.

def somme_carres(n):
    s = 0                    # initialisation de l'accumulateur
    for k in range(1, n + 1):    # k va de 1 à n
        s = s + k**2
    return s                 # sortie après la boucle

print(somme_carres(10))      # 385

On obtient de même $\sum _{k=1}^5{k}^3=225$Σ_k=1⁵ k³ = 225 (avec k**3) et $\sum _{k=1}^5\frac{1}{k}\approx 2,283$Σ_k=1⁵ 1/k ≈ 2,283 (avec 1/k).

Listes et données

Méthode — Rappels sur les listes. L = [3, 7, 2] (extension) ; L.append(x) (ajout) ; [k**2 for k in range(10) if k \% 2 == 1] (compréhension) ; L[0], L[-1], len(L) ; for x in L: (parcours).

Exemple — Sélection de données. Relevés de consommation (kWh) par mois, sous forme de liste de couples :

releves = [["jan", 412], ["fev", 380], ["mar", 305],
           ["avr", 260], ["mai", 198], ["juin", 150]]

def mois_au_dessus(donnees, seuil):
    return [m for (m, conso) in donnees if conso > seuil]

print(mois_au_dessus(releves, 300))   # ['jan', 'fev', 'mar']

Méthode de Monte-Carlo

Définition — Principe. La méthode de Monte-Carlo estime une grandeur (une aire, une probabilité) à l'aide d'un grand nombre de tirages aléatoires : la fréquence observée approche la probabilité, d'autant mieux que le nombre de tirages est grand.

Exemple — Estimer $\pi$π. On tire $n$n points au hasard dans le carré $[0;1]\times [0;1]$[0 ;1] × [0 ;1]. Un point est dans le quart de disque de centre $O$O et de rayon $1$1 si $x^2+y^2\le 1$x² + y² ≤ 1 ; la probabilité de cet événement est l'aire du quart de disque, $\frac{\pi }{4}$π/4.

from random import random

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

Une exécution avec $n=10000$n = 10 000 a donné $3,144$3,144.

Points tirés au hasard : en bleu ceux du quart de disque, en orange les autres.

Exemple — Aire sous une courbe. De même, la proportion de points du carré tels que $y\le x^2$y ≤ x² approche l'aire sous la parabole entre $0$0 et $1$1, qui vaut $\frac{1}{3}$1/3 (une simulation de $10000$10 000 points a donné $0,330$0,330).

Marches aléatoires

Définition — Marche aléatoire sur une droite. Un pion part de $0$0 ; à chaque étape, il avance de $+1$+1 ou recule de $-1$-1 avec la même probabilité $\frac{1}{2}$1/2, indépendamment des étapes précédentes. Sa position après $n$n étapes est aléatoire.

Exemple — Simulation.

def marche(n):
    x = 0
    for k in range(n):
        if random() < 0.5:
            x = x + 1
        else:
            x = x - 1
    return x

positions = [marche(100) for i in range(1000)]
proches = [x for x in positions if abs(x) <= 10]
print(len(proches) / 1000)

Sur $1000$1 000 marches de $100$100 étapes, une simulation a donné une distance moyenne à l'origine d'environ $8,1$8,1, et $70,6\%$70,6 % des marches finissant entre $-10$-10 et $10$10. La position finale est toujours paire : $100$100 pas de $\pm 1$± 1.

Erreurs classiques

Attention — À éviter.

• Décaler les bornes : range(1, n) s'arrête à $n-1$n - 1 ; pour aller jusqu'à $n$n, écrire range(1, n + 1).
• Réinitialiser l'accumulateur à l'intérieur de la boucle.
• Placer return dans la boucle : la fonction s'arrête au premier tour.
• Conclure à partir de trop peu de tirages : la méthode de Monte-Carlo demande un grand nombre de simulations.

Fiche de synthèse

Exercices d'application

Exercice 1 – Somme

Écrire une fonction somme_inverses(n) qui renvoie $\sum _{k=1}^n\frac{1}{k}$Σ_k=1ⁿ 1/k.

Exercice 2 – Lire un programme

Que renvoie f(4) ?

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

Exercice 3 – Monte-Carlo

Modifier estimation_pi pour estimer la probabilité qu'un point tiré au hasard dans le carré vérifie $y\le x$y ≤ x. Quelle valeur attend-on ?

Corrigés des exercices

Corrigé de l'exercice 1

Corrigé.

def somme_inverses(n):
    s = 0
    for k in range(1, n + 1):
        s = s + 1 / k
    return s

Corrigé de l'exercice 2

Corrigé. $p$p prend successivement les valeurs $1$1, $2$2, $6$6, $24$24 : f(4) renvoie $24=1\times 2\times 3\times 4$24 = 1 × 2 × 3 × 4.

Corrigé de l'exercice 3

Corrigé. On remplace la condition par if y <= x: et l'on renvoie c / n. Le triangle sous la diagonale a pour aire $\frac{1}{2}$1/2 : on attend une valeur proche de $0,5$0,5.