Algorithmique et Python — cours de Terminale

Variables, types et affectation, Conditions, Boucles bornées et non bornées, Fonctions et spécification Lecture ≈ 5 min.

S'entraîner Quiz du chapitre

1. Variables, types et affectation

Notions de base

Un algorithme est une suite finie et non ambiguë d'instructions. En Python, = effectue une affectation et == teste une égalité. Les principaux types sont int (entier), float (décimal approché), bool (booléen), str (texte) et list (liste).

Exemple

x = 3
x = x + 2       # x vaut désormais 5
test = (x == 5) # test vaut True

L'instruction x = x + 2 n'est pas une égalité mathématique : elle remplace la valeur de x par l'ancienne valeur augmentée de 2.

2. Conditions

Structure conditionnelle

if condition:
    instructions_si_vraie
elif autre_condition:
    autres_instructions
else:
    instructions_si_fausse

L'indentation délimite les blocs. Les comparaisons sont <, <=, >, >=, ==, !=. On combine avec and, or, not.

Exemple

def signe(x):
    if x > 0:
        return 1
    elif x < 0:
        return -1
    else:
        return 0

3. Boucles bornées et non bornées

DéfinitionBoucle for

for k in range(n): fait prendre à k les valeurs 0, 1, ..., n-1. range(a,b) va de a inclus à b exclu.

DéfinitionBoucle while

Une boucle while condition: se répète tant que la condition reste vraie. Il faut vérifier qu'une variable évolue vers la sortie, sinon la boucle peut être infinie.

Somme et produit

def somme_carres(n):
    s = 0
    for k in range(1, n + 1):
        s = s + k**2
    return s

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

4. Fonctions et spécification

Écrire une fonction fiable

Préciser les entrées, leurs types et leurs conditions.
Préciser la sortie attendue.
Traiter les cas limites.
Tester sur des cas simples calculables à la main.
Distinguer return, qui renvoie une valeur, de print, qui l'affiche seulement.

Coefficient binomial

def coefficient_binomial(n, k):
    if k < 0 or k > n:
        return 0
    k = min(k, n - k)
    resultat = 1
    for i in range(1, k + 1):
        resultat = resultat * (n - i + 1) // i
    return resultat

La symétrie C(n,k) = C(n,n − k) réduit le nombre d'itérations. La division entière // est exacte à chaque étape dans cet algorithme.

5. Suites et recherche de seuil

Calculer un terme récurrent

def terme_suite(n):
    u = 1
    for k in range(n):
        u = 0.8 * u + 6
    return u

Avant la première itération, u vaut u₀. Après k itérations, il vaut u_k : c'est l'invariant de boucle.

Premier rang dépassant un seuil

def premier_rang(seuil):
    n = 0
    u = 1
    while u < seuil:
        u = 0.8 * u + 6
        n = n + 1
    return n, u

Cette fonction n'a de sens que pour un seuil effectivement atteignable. Ici la suite tend vers 30 en restant inférieure à 30 : un seuil supérieur ou égal à 30 provoquerait une boucle qui ne s'arrête pas. Ajouter un contrôle est prudent.

6. Dichotomie robuste

Version avec précondition

def dichotomie(f, a, b, epsilon):
    if epsilon <= 0:
        raise ValueError("epsilon doit être positif")
    if f(a) * f(b) > 0:
        raise ValueError("pas de changement de signe")
    while b - a > epsilon:
        m = (a + b) / 2
        if f(a) * f(m) <= 0:
            b = m
        else:
            a = m
    return a, b

Si f est continue et possède une unique racine sur l'intervalle, l'invariant est : « la racine appartient à [a ; b] ». La longueur est divisée par deux à chaque tour, ce qui assure la terminaison.

7. Simulation probabiliste

Simuler une loi binomiale

from random import random

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

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

def estimation(n, p, repetitions, k):
    favorables = 0
    for _ in range(repetitions):
        if binomiale(n, p) == k:
            favorables += 1
    return favorables / repetitions

Le résultat fluctue d'une exécution à l'autre. Augmenter repetitions améliore en général l'estimation, mais une simulation ne remplace pas une valeur exacte accessible par la formule binomiale.

8. Méthode de Monte-Carlo

Estimer π

from random import random

def estime_pi(n):
    dedans = 0
    for _ in range(n):
        x = random()
        y = random()
        if x*x + y*y <= 1:
            dedans += 1
    return 4 * dedans / n

Le point (x ; y) est uniforme dans le carré [0 ; 1]². La proportion attendue dans le quart de disque unité est son aire π4. La fréquence fournit donc une estimation de π4, multipliée par 4.

9. Intégration numérique

Rectangles et trapèzes

def trapezes(f, a, b, n):
    h = (b - a) / n
    somme = (f(a) + f(b)) / 2
    for k in range(1, n):
        somme += f(a + k*h)
    return h * somme

La méthode des trapèzes remplace la courbe par des segments. Pour une fonction régulière, elle est souvent plus précise que les rectangles à nombre de subdivisions égal. Comparer avec une intégrale exacte sur une fonction simple permet de valider le programme.

10. Listes et compréhensions

Liste

Une liste stocke plusieurs valeurs ordonnées. Les indices commencent à 0. Une compréhension permet de construire une liste : [f(k) for k in range(n)].

Table de valeurs

from math import exp

abscisses = [k / 10 for k in range(-20, 21)]
ordonnees = [x * exp(-x) for x in abscisses]

Les deux listes ont la même longueur ; abscisses[i] et ordonnees[i] décrivent un point de la courbe.

11. Valeurs approchées et flottants

Précision numérique

Un nombre de type float est stocké avec une précision finie. Ainsi, certains décimaux ne sont pas représentés exactement et 0.1 + 0.2 == 0.3 peut être faux. Pour comparer deux résultats approchés, tester plutôt abs(a-b) < epsilon.

Bonnes pratiques

Ne pas arrondir les valeurs intermédiaires inutilement.
Choisir un critère d'arrêt explicite.
Prévoir les domaines interdits (division par zéro, logarithme d'un nombre non positif).
Tester les bornes et les cas dégénérés.
Commenter l'idée mathématique, pas chaque symbole évident.

Erreurs fréquentes

Confondre = et ==.
Oublier que la borne droite de range est exclue.
Modifier une variable dans le mauvais ordre au sein d'une boucle.
Employer une boucle while sans preuve ou garantie de terminaison.
Présenter un résultat simulé comme une preuve exacte.

Fiche résumé Exercices corrigés → Passer le quiz