Algorithmique

Algorithmique et Python

Listes, boucles, fonctions et les algorithmes qui tombent au bac

Tout est gratuit et lisible sans compte. Crée ton compte gratuit pour garder ta progression.

Ce que tu dois savoir faire

Lire, compléter et écrire une fonction Python avec def, return, if, for et while
Créer une liste en extension ou en compréhension, y ajouter ou retirer des éléments, la parcourir
Calculer les termes d'une suite et programmer une recherche de seuil
Programmer la dichotomie, la méthode d'Euler et la méthode des rectangles
Simuler une expérience aléatoire, un échantillon, et estimer une probabilité par une fréquence

1. Les bases à maîtriser

Au bac, l'algorithmique n'est pas une épreuve séparée : elle apparaît dans les exercices (suites, fonctions, probabilités). On te demande le plus souvent de compléter une fonction, de dire ce qu'elle renvoie, ou d'en interpréter le résultat. Il faut donc savoir lire du Python sans hésiter.

L’essentiel de la syntaxe

instruction	rôle	exemple
`x = 3`	affectation : $x$ reçoit la valeur $3$	`n = n + 1` augmente $n$ de $1$
`x == 3`	test d'égalité (vrai ou faux)	`if x == 3:`
`**` , `%` , `//`	puissance, reste, quotient entier	`2**3` vaut $8$ , `17 % 5` vaut $2$
`def f(x): … return …`	définir une fonction qui renvoie un résultat	`return x**2`
`for k in range(n):`	répéter $n$ fois, $k$ allant de $0$ à $n - 1$	`range(2, 8, 2)` donne $2, 4, 6$
`while condition:`	répéter tant que la condition est vraie	`while u < 100:`

Méthode — Trois structures, un exemple chacune

def f(x):
    return x**2 - 3*x + 1      # une fonction mathématique

print(f(2))                     # affiche -1

n = 0
while 2**n < 1000:              # tant que la condition est vraie…
    n = n + 1                   # …on recommence
print(n)                        # 10, car 2**9 = 512 et 2**10 = 1024

for k in range(5):              # k prend les valeurs 0, 1, 2, 3, 4
    if k % 2 == 0:              # k % 2 est le reste de la division par 2
        print(k, "est pair")
    else:
        print(k, "est impair")

Piège fréquent

range(n) s'arrête avant $n$ : range(5) donne $0, 1, 2, 3, 4$ (cinq valeurs). Et l'indentation (le décalage du début de ligne) fait partie du langage : c'est elle qui indique ce qui est à l'intérieur d'une boucle ou d'un if.

Conseil bac

Pour comprendre un programme, fais-le « tourner à la main » : un tableau avec une colonne par variable et une ligne par passage dans la boucle. C'est exactement ce qu'attend le correcteur quand on te demande « quelle valeur renvoie… ».

2. Les listes

Définition — Liste

Une liste est une suite ordonnée de valeurs, écrite entre crochets : L = [3, 1, 4, 1, 5]. Chaque élément est repéré par son indice, qui commence à $0$ . len(L) est le nombre d'éléments.

Indices d’une liste

L[0] est le premier élément, L[-1] le dernier. L[5] provoque une erreur : il n'y a pas d'élément d'indice $5$ .

Opérations sur les listes

écriture	effet
`[]`	liste vide
`L.append(x)`	ajoute $x$ à la fin de la liste
`L.pop()`	retire (et renvoie) le dernier élément
`L.remove(x)`	retire la première occurrence de $x$
`L[i] = x`	remplace l'élément d'indice $i$
`[expr for k in range(n)]`	liste en compréhension
`[expr for k in range(n) if cond]`	en compréhension, avec un filtre
`sum(L)`, `max(L)`, `min(L)`	somme, maximum, minimum (listes de nombres)

Méthode — Créer et modifier une liste

L = [3, 1, 4, 1, 5]        # liste définie en extension
L.append(9)                # ajoute 9 à la fin : [3, 1, 4, 1, 5, 9]
print(len(L), L[0], L[-1]) # 6 3 9
L.pop()                    # retire le dernier élément : [3, 1, 4, 1, 5]
L.remove(1)                # retire le PREMIER 1 rencontré : [3, 4, 1, 5]
L[0] = 7                   # modifie un élément : [7, 4, 1, 5]

carres = [k**2 for k in range(6)]             # en compréhension : [0, 1, 4, 9, 16, 25]
pairs = [k for k in range(20) if k % 2 == 0]  # avec une condition : [0, 2, 4, ..., 18]

Méthode — Parcourir une liste

On peut parcourir les éléments (for x in L) ou les indices (for i in range(len(L))), quand on a besoin de la position.

def moyenne(L):
    s = 0
    for x in L:            # parcours par les éléments
        s = s + x
    return s / len(L)

def maximum(L):
    m = L[0]
    for i in range(1, len(L)):   # parcours par les indices
        if L[i] > m:
            m = L[i]
    return m

print(moyenne([12, 15, 9]), maximum([12, 15, 9]))   # 12.0 15

3. Suites : termes et seuils

Méthode — Calculer les termes d’une suite récurrente

Une seule variable u suffit : à chaque tour de boucle, on la remplace par le terme suivant. Pour garder tous les termes, on les ajoute à une liste avec append.

def termes(n):
    """Liste des termes u0, ..., un de la suite u0 = 2, u(k+1) = 0.5 u(k) + 3."""
    u = 2
    L = [u]
    for k in range(n):
        u = 0.5 * u + 3
        L.append(u)
    return L

print(termes(5))   # [2, 4.0, 5.0, 5.5, 5.75, 5.875] : la suite semble tendre vers 6

Les termes calculés par termes(10) : la suite croît et se rapproche de $6$ (on peut montrer que $u_{n} = 6 - 4 \times 0, 5^{n}$ ).

Méthode — L’algorithme de seuil

Pour trouver le premier rang $n$ à partir duquel une condition est vérifiée, on utilise une boucle while dont la condition est le contraire de celle qu'on cherche : on continue tant qu'on n'y est pas.

def seuil(s):
    """Premier n tel que 100 * 0.8**n < s (médicament éliminé de 20 % par heure)."""
    n = 0
    u = 100
    while u >= s:          # condition CONTRAIRE de celle qu'on cherche
        u = 0.8 * u
        n = n + 1
    return n

print(seuil(5))   # 14

Piège fréquent

Si la suite ne dépasse jamais le seuil, la boucle while ne s'arrête pas ! Avant d'utiliser un algorithme de seuil, il faut savoir (par la limite) que le seuil sera atteint. Exemple : chercher le premier $n$ tel que $u_{n} > 7$ pour la suite précédente, qui reste sous $6$ , ferait tourner le programme indéfiniment.

4. Analyse : dichotomie, Euler, aires

Méthode — La dichotomie

Si $f$ est continue sur $[a; b]$ et change de signe, l'équation $f (x) = 0$ a une solution dans $[a; b]$ (théorème des valeurs intermédiaires). On coupe l'intervalle en deux, on garde la moitié où $f$ change de signe, et on recommence : la longueur est divisée par $2$ à chaque étape.

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

def dichotomie(a, b, precision):
    """f change de signe sur [a ; b] : on encadre la solution de f(x) = 0."""
    while b - a > precision:
        m = (a + b) / 2
        if f(a) * f(m) <= 0:   # changement de signe entre a et m
            b = m
        else:                  # sinon, il est entre m et b
            a = m
    return a, b

print(dichotomie(1, 2, 0.001))   # (1.4140625, 1.4150390625) : encadrement de racine de 2

Les intervalles successifs : $[1; 2]$ , $[1; 1, 5]$ , $[1, 25; 1, 5]$ , $[1, 375; 1, 5]$ … ils emprisonnent $2$ . Après $10$ étapes, la longueur est $\frac{1}{2 ^{10}} < 0, 001$ .

Méthode — La méthode d’Euler

Pour approcher la solution de $y^{'} = a y + b$ avec $y (0) = y_{0}$ : on avance pas à pas en suivant la tangente, $y (t + h) \approx y (t) + h y^{'} (t)$ .

def euler(a, b, y0, h, n):
    """Points approchés de la solution de y' = a y + b, y(0) = y0, avec n pas de longueur h."""
    t = 0
    y = y0
    points = [(t, y)]
    for k in range(n):
        y = y + h * (a * y + b)    # y(t + h) ≈ y(t) + h y'(t)
        t = t + h
        points.append((t, y))
    return points

print(euler(-0.2, 4, 0, 1, 3))   # [(0, 0), (1, 4.0), (2, 7.2), (3, 9.76)]

Avec un pas $h = 1$ , l'approximation est grossière : la vraie valeur en $t = 3$ est $20 - 20 e^{- 0, 6} \approx 9, 02$ . Avec $h = 0, 01$ (et $n = 300$ ), on trouve $9, 03$ .

Méthode — Monte-Carlo : une aire par le hasard

On tire des points au hasard dans un carré ; la proportion de points sous une courbe approche l'aire (en proportion du carré). C'est une autre façon d'approcher une intégrale, comme la méthode des rectangles.

from random import random

def monte_carlo(n):
    """Approche pi : proportion de points du carré [0;1]² tombant sous le quart de cercle."""
    dedans = 0
    for i in range(n):
        x = random()
        y = random()
        if x**2 + y**2 <= 1:
            dedans = dedans + 1
    return 4 * dedans / n

print(monte_carlo(100000))   # environ 3.14 (le résultat change à chaque exécution)

5. Probabilités : simuler et compter

Méthode — Simuler une loi de Bernoulli, une loi binomiale, un échantillon

random() renvoie un nombre au hasard dans $[0; 1 [$ ; le test random() < p est donc vrai avec la probabilité $p$ . C'est la brique de toutes les simulations.

from random import random

def bernoulli(p):
    """Renvoie 1 avec la probabilité p, 0 sinon."""
    if random() < p:
        return 1
    else:
        return 0

def binomiale(n, p):
    """Simule une variable de loi B(n, p) : nombre de succès en n épreuves."""
    X = 0
    for i in range(n):
        X = X + bernoulli(p)
    return X

echantillon = [binomiale(20, 0.8) for j in range(1000)]   # 1000 simulations
print(sum(echantillon) / len(echantillon))                # proche de E(X) = 16

Propriété — Fréquence et probabilité

D'après la loi des grands nombres, sur un grand nombre de simulations, la fréquence d'un événement est proche de sa probabilité, et la moyenne des valeurs simulées est proche de l'espérance. Une simulation donne une estimation, jamais une valeur exacte : deux exécutions donnent des résultats différents.

Méthode — Les coefficients binomiaux par la relation de Pascal

La relation de Pascal $(k + 1 n + 1) = (k n) + (k + 1 n)$ permet de construire chaque ligne du triangle à partir de la précédente : chaque coefficient intérieur est la somme des deux coefficients situés au-dessus.

def ligne_pascal(n):
    """Ligne n du triangle de Pascal : les coefficients binomiaux (n parmi k)."""
    L = [1]
    for k in range(n):
        L = [1] + [L[i] + L[i + 1] for i in range(len(L) - 1)] + [1]
    return L

print(ligne_pascal(5))   # [1, 5, 10, 10, 5, 1]

Conseil bac

Pour calculer directement un coefficient binomial ou une probabilité binomiale, from math import comb donne comb(n, k). Mais au bac, on te demandera plutôt de comprendre une simulation : repère la variable qui compte (elle augmente de $1$ quand un événement se produit) et la division finale qui transforme un effectif en fréquence.

L’essentiel à retenir

= affecte, == teste ; l'indentation délimite les blocs ; range(n) va de $0$ à $n - 1$ .
Les indices d'une liste commencent à $0$ ; L[-1] est le dernier élément ; len(L) donne la taille.
L.append(x) ajoute à la fin, L.pop() retire le dernier, L.remove(x) retire la première occurrence de $x$ .
Liste en compréhension : [k**2 for k in range(10) if k % 2 == 0].
Seuil : boucle while avec la condition contraire de celle cherchée ; on renvoie le compteur $n$ .
Dichotomie : la longueur de l'intervalle est divisée par $2$ à chaque étape.
Euler : y = y + h * (a * y + b) ; plus $h$ est petit, meilleure est l'approximation.
random() < p simule un succès de probabilité $p$ ; une fréquence simulée estime une probabilité.

Et pour t’entraîner : 10 QCM corrigés et 4 exercices type bac, avec indices et corrections rédigées.