Module L01 · Partie F · Coder comme un professionnel

Du code qui marche au code qui tient.

Au collège, un programme est fini quand il affiche la bonne réponse. À partir de maintenant, un programme est fini quand il est lisible, testé, documenté et qu’un autre humain (vous dans six mois) peut le modifier sans le casser.

Durée : 2 séances · Prérequis : le parcours collège (fonctions, listes, dictionnaires, classes de base). Objectifs : style PEP 8, annotations de types, docstrings, tests automatiques, gestion d’erreurs propre, journalisation, mesure de performance.

Ce que vous saurez faire à la fin

Relire un code et dire précisément ce qui le rend fragile.
Écrire une fonction avec sa signature typée, sa docstring et ses tests.
Concevoir des tests qui cassent le code avant l’utilisateur.
Profiler un programme et savoir où il perd son temps.

Références : PEP 8, PEP 484, The Pragmatic Programmer, cours CS50 (Harvard) et freeCodeCamp « Scientific Computing with Python ».

Fiche de cours · Définitions

Ce qu’il faut savoir définir précisément

Définition (spécification). Une fonction est spécifiée par sa précondition (ce que l’appelant garantit sur les entrées), sa postcondition (ce que la fonction garantit sur la sortie) et ses effets (ce qu’elle modifie). Un programme est correct s’il satisfait sa postcondition dès que la précondition est vraie.

Définition (invariant de boucle). Une propriété P est un invariant d’une boucle si (1) P est vraie avant la première itération (initialisation) et (2) si P est vraie avant une itération et que la condition de boucle est vraie, alors P est vraie après (conservation). À la sortie, on a P ∧ ¬condition (terminaison) — c’est de là qu’on tire la postcondition.

Définition (variant). Une quantité entière, positive ou nulle, qui décroît strictement à chaque itération. Son existence prouve la terminaison (une suite d’entiers naturels strictement décroissante est finie).

Définition (complexité asymptotique). f(n) = O(g(n)) s’il existe C > 0 et n₀ tels que f(n) ≤ C·g(n) pour tout n ≥ n₀. f = Ω(g) si g = O(f) ; f = Θ(g) si f = O(g) et f = Ω(g). La complexité temporelle compte les opérations élémentaires en fonction de la taille n de l’entrée, dans le pire cas sauf mention contraire.

Définition (mutabilité, aliasing). Un objet est mutable si son état peut changer après création (list, dict, set) ; immuable sinon (int, str, tuple, frozenset). Deux noms qui désignent le même objet sont des alias : modifier via l’un est visible via l’autre. C’est la source de bugs n°1 en Python.

Fiche de cours · Formules

Les ordres de grandeur à connaître par cœur

Formule	Ce qu’elle dit	Où elle apparaît
1 + 2 + … + n = n(n+1)/2 = Θ(n²)	Une boucle imbriquée triangulaire fait ~n²/2 tours	Tri par insertion, comparaison de toutes les paires
1 + 1/2 + … + 1/n = H_n ≈ ln n + 0,577	La série harmonique croît comme ln n	Analyse du tri rapide, du problème du collectionneur
1 + 2 + 4 + … + 2^k = 2^k+1 − 1	Une somme géométrique est dominée par son dernier terme	Tableau dynamique, arbres binaires complets
Nombre de divisions par 2 de n jusqu’à 1 : ⌊log₂ n⌋	« Couper en deux » coûte log n étapes	Dichotomie, tas, exponentiation rapide
n! ≈ √(2πn)·(n/e)ⁿ, log₂(n!) = Θ(n log n)	Formule de Stirling	Borne inférieure des tris par comparaison
Σ_k=0ⁿ C(n,k) = 2ⁿ	Nombre de sous-ensembles	Force brute sur les sous-ensembles (L04, L23)

log_b n = ln n / ln b donc O(log₂ n) = O(log₁₀ n) = O(ln n) : la base n’a pas d’importance dans un O

Hiérarchie : 1 ≺ log n ≺ √n ≺ n ≺ n log n ≺ n² ≺ n³ ≺ 2ⁿ ≺ n!. Pour n = 10⁶ et 10⁹ opérations par seconde : n log n ≈ 20 ms, n² ≈ 17 min, 2ⁿ ≈ jamais.

Fiche de cours · Théorèmes et démonstrations

Démonstrations à savoir refaire

Théorème 1 (correction de la recherche dichotomique). Soit L un tableau trié de n éléments et x une valeur. L’algorithme qui maintient bas ≤ haut avec m = ⌊(bas+haut)/2⌋ et remplace bas par m+1 si L[m] < x, haut par m−1 si L[m] > x, renvoie un indice i avec L[i] = x si x ∈ L, et « absent » sinon, en O(log n) comparaisons.

Invariant : « si x est dans L, alors x est dans L[bas..haut] ». Initialisation : bas = 0, haut = n−1, vrai. Conservation : si L[m] < x, comme L est trié, tous les L[j], j ≤ m, sont < x, donc x ne peut être qu’en m+1..haut ; symétriquement si L[m] > x. Terminaison : le variant haut − bas + 1 (taille de la zone) est divisé par 2 au moins à chaque tour (car m+1 > bas et m−1 < haut) donc la boucle s’arrête après au plus ⌊log₂ n⌋ + 1 tours. À la sortie : soit on a trouvé L[m] = x, soit bas > haut, la zone est vide, et l’invariant donne x ∉ L.

Théorème 2 (le tableau dynamique a un ajout en O(1) amorti). Une liste Python qui double sa capacité quand elle est pleine effectue n ajouts successifs en O(n) copies au total, soit O(1) par ajout en moyenne.

Les copies ont lieu aux tailles 1, 2, 4, …, 2^k avec 2^k ≤ n ; le nombre total d’éléments copiés est 1 + 2 + … + 2^k = 2^k+1 − 1 < 2n. Ajouté aux n écritures, le total est < 3n = O(n). (Argument « du banquier » : chaque ajout paie 3 unités — une pour lui, deux mises de côté pour financer sa future copie et celle d’un ancien élément.)

Théorème 3 (aliasing des arguments par défaut). En Python, l’expression d’un argument par défaut est évaluée une seule fois, à la définition de la fonction ; un défaut mutable est donc partagé entre tous les appels.

Ce n’est pas un théorème mathématique mais une règle du langage, vérifiable : def f(l=[]): l.append(1); return l puis f(); f() renvoie [1, 1]. Conséquence : écrire def f(l=None): if l is None: l = [].

Fiche de cours · Méthodes

Méthodes types et pièges

Méthode — prouver qu’une boucle est correcte. (1) Écrire la postcondition voulue. (2) Deviner l’invariant : souvent « la partie déjà traitée vérifie la postcondition » (ex. « L[0..i] est trié », « s = somme de L[0..i] »). (3) Vérifier initialisation et conservation. (4) Exhiber un variant. (5) Combiner invariant et négation de la condition pour obtenir la postcondition.

Méthode — trouver la complexité d’un programme. Boucles imbriquées indépendantes : multiplier. Boucle dont la borne dépend d’une autre : sommer (Σ i = n²/2). Division par 2 à chaque tour : log n. Appel récursif : écrire la récurrence T(n) et la résoudre (L04). Ne pas oublier le coût caché des opérations Python : x in liste est O(n), x in ensemble O(1), liste.insert(0, x) O(n), s += "a" dans une boucle O(n²) au total.

Méthode — tester. Un test par cas de la spécification : cas nominal, cas limites (vide, un élément, tous égaux, le plus grand possible), cas d’erreur (précondition violée → exception attendue). Puis des tests par propriétés : « trier puis inverser donne l’ordre décroissant », « len(trie) = len(L) », « trie est monotone ».

Pièges : comparer des flottants avec == (utiliser math.isclose) ; modifier une liste pendant qu’on l’itère ; confondre copie = l (alias) et copie = l[:] ; oublier que range(a, b) exclut b ; croire qu’une exception attrapée par except: nu est « gérée ».

Fiche de cours · Exercices corrigés

Exercices corrigés (rédaction attendue en prépa)

Exercice 1. On considère def s(L): t = 0 ; for x in L: t += x ; return t. Donner un invariant, prouver la correction et la complexité.

Correction. Invariant : après avoir traité les k premiers éléments, t = Σ_j<k L[j]. Initialisation : k = 0, t = 0 = somme vide. Conservation : si t = Σ_j<k L[j] et qu’on ajoute L[k], alors t = Σ_j<k+1 L[j]. Terminaison : k croît de 1 par tour jusqu’à n (variant n − k). Sortie : k = n, donc t = Σ_j<n L[j], la somme voulue. Chaque tour fait une addition : Θ(n).

Exercice 2. Quelle est la complexité de for i in range(n): for j in range(i): print(i, j) ? Et de while n > 1: n //= 2 ? Et de for i in range(n): if x in L: … où L est une liste de taille n ?

Correction. (a) Le tour i coûte i affichages : Σ_i=0ⁿ⁻¹ i = n(n−1)/2 = Θ(n²). (b) n est divisé par 2 à chaque tour : ⌊log₂ n⌋ tours, Θ(log n). (c) x in L parcourt L : O(n) par tour, n tours, O(n²). Avec S = set(L) construit une fois (O(n)) puis x in S en O(1) : O(n) au total.

Exercice 3. La fonction def f(L): return [x for x in L if x not in L[:L.index(x)]] supprime les doublons en gardant l’ordre. Est-elle correcte ? Quelle est sa complexité ? Proposer une version en O(n).

Correction. Correcte : x est gardé si et seulement s’il n’apparaît pas avant sa première occurrence, c’est-à-dire s’il s’agit de sa première occurrence. Mais L.index(x) est O(n), le tranchage O(n), le not in O(n) : O(n) par élément, O(n²) au total. Version linéaire : vus = set(); out = []; for x in L: if x not in vus: vus.add(x); out.append(x) — chaque opération sur l’ensemble est O(1) en moyenne, donc O(n). (Et, en une ligne, list(dict.fromkeys(L)) : les dict conservent l’ordre d’insertion.)

01 / Lisibilité

Le même programme, deux fois

Un nom de fonction doit dire ce qu’elle fait, pas comment. f, l, r ne disent rien ; carres_des_pairs, nombres disent tout. Le code est lu dix fois plus souvent qu’il n’est écrit.

PEP 8 en dix règles

Noms de variables et fonctions en minuscules_avec_underscores, classes en CamelCase, constantes en MAJUSCULES.
4 espaces d’indentation, jamais de tabulations.
Espaces autour des opérateurs (a + b), après les virgules, pas à l’intérieur des parenthèses.
Lignes de 79 caractères maximum (99 acceptés en pratique).
Deux lignes vides entre les fonctions de niveau module.
Imports en haut, un par ligne, ordre : bibliothèque standard, tiers, projet.
Pas de from module import *.
Comparer à None avec is, pas ==.
Une fonction fait une chose ; si vous mettez « et » dans son nom, coupez-la.
Les commentaires expliquent le pourquoi, jamais le quoi (le code dit déjà le quoi).

Outils : black (formatage automatique), ruff ou flake8 (vérification), mypy (types). Sur votre PC : pip install black ruff mypy.

01 / Lisibilité

Annotations de types : dire ce qu’on attend

Les types utiles

Annotation	Sens
`int, float, str, bool`	Types de base.
`list[int]`	Liste d’entiers (Python ≥ 3.9).
`dict[str, float]`	Dictionnaire clé texte → valeur flottante.
`tuple[float, float]`	Couple de flottants (par exemple une position).
`Optional[T]` ou `T \| None`	Soit un T, soit None.
`Callable[[int], str]`	Une fonction prenant un int et renvoyant un str.
`Iterable[T]`	Tout ce qu’on peut parcourir (liste, générateur…).

En C, OCaml, Rust ou Java, les types sont obligatoires et vérifiés par le compilateur : c’est l’un des grands sujets de la prépa MP2I. Prendre l’habitude en Python rend le passage naturel.

02 / Tests

Un test est un programme qui vérifie un programme

Sur un PC, on écrit ces tests dans test_texte.py et on lance pytest : il exécute toutes les fonctions test_*, affiche en vert ce qui passe, en rouge ce qui casse, avec la valeur exacte qui a échoué.

Comment choisir ses tests

Cas nominal : l’usage prévu (« kayak »).
Cas limites : vide, un seul élément, valeurs extrêmes, négatifs, zéro.
Cas d’erreur : que se passe-t-il avec une entrée invalide ? Le programme doit lever une exception claire, pas renvoyer n’importe quoi.
Cas trouvés par les bugs : chaque bug corrigé devient un test, pour qu’il ne revienne jamais (test de non-régression).

Règle d’or : un test doit échouer si on casse le code. Un test qui passe quoi qu’il arrive ne teste rien. Écrivez le test avant de corriger un bug : il doit d’abord être rouge, puis vert.

02 / Tests

Un mini-pytest dans la page

import traceback

def lancer_tests(*tests):
    """Exécute chaque fonction de test, résume les résultats comme pytest."""
    ok, ko = 0, 0
    for t in tests:
        try:
            t()
            print(f"PASSED  {t.__name__}")
            ok += 1
        except AssertionError as e:
            print(f"FAILED  {t.__name__}: {e or 'assertion fausse'}")
            ko += 1
        except Exception as e:
            print(f"ERROR   {t.__name__}: {type(e).__name__}: {e}")
            ko += 1
    print(f"===== {ok} passed, {ko} failed =====")

# Le code à tester (avec un bug volontaire)
def division_entiere(a: int, b: int) -> tuple[int, int]:
    """Renvoie (quotient, reste) de la division euclidienne de a par b > 0."""
    if b <= 0:
        raise ValueError("b doit être > 0")
    q = a // b
    r = a - q * b
    return q, r

def test_nominal():
    assert division_entiere(17, 5) == (3, 2)

def test_negatif():
    # Division euclidienne : le reste doit être dans [0, b[
    q, r = division_entiere(-17, 5)
    assert 0 <= r < 5, f"reste {r} hors de [0, 5["
    assert q * 5 + r == -17

def test_erreur():
    try:
        division_entiere(1, 0)
        assert False, "aucune exception levée"
    except ValueError:
        pass

lancer_tests(test_nominal, test_negatif, test_erreur)

Lire le résultat

Tout passe ? Regardez de près test_negatif : en Python, -17 // 5 = -4 et le reste vaut 3 — Python fait déjà la « bonne » division euclidienne (reste positif). En C, -17 / 5 = -3 et -17 % 5 = -2 ! Le même test, porté en C, échouerait. Les tests sur les cas limites révèlent les différences entre langages, et c’est précisément là que les bugs se cachent.

Avec le vrai pytest : pytest -v (verbeux), pytest -x (stop au premier échec), pytest --cov (couverture : quelles lignes n’ont jamais été exécutées par un test).

02 / Tests

Tests par propriétés : laisser la machine chercher le contre-exemple

import random

def tri_insertion(liste):
    resultat = list(liste)
    for i in range(1, len(resultat)):
        x = resultat[i]
        j = i - 1
        while j >= 0 and resultat[j] > x:
            resultat[j + 1] = resultat[j]
            j -= 1
        resultat[j + 1] = x
    return resultat

# Propriétés qu'un tri doit TOUJOURS vérifier, quelle que soit l'entrée
def proprietes_tri(tri, entree):
    sortie = tri(entree)
    assert len(sortie) == len(entree), "la longueur change"
    assert all(sortie[i] <= sortie[i + 1] for i in range(len(sortie) - 1)), "pas trié"
    assert sorted(entree) == sortie, "pas une permutation"
    assert tri(sortie) == sortie, "pas idempotent"

random.seed(1)
for essai in range(500):
    n = random.randint(0, 30)
    entree = [random.randint(-50, 50) for _ in range(n)]
    proprietes_tri(tri_insertion, entree)
print("500 entrées aléatoires : toutes les propriétés tiennent")

# Comparer à une référence : le tri de Python
for essai in range(500):
    entree = [random.random() for _ in range(random.randint(0, 20))]
    assert tri_insertion(entree) == sorted(entree)
print("500 comparaisons à sorted() : identiques")

Pourquoi c’est puissant

Écrire 5 tests à la main, c’est tester 5 cas. Énoncer une propriété (« la sortie est une permutation triée de l’entrée ») et la vérifier sur 500 entrées aléatoires, c’est tester une idée. La bibliothèque hypothesis automatise cela et, quand elle trouve un contre-exemple, le réduit au plus petit cas qui échoue. C’est la version pratique de « prouver que l’algorithme est correct » que vous verrez en module L09.

Exercice mental : quelle propriété distingue un tri stable ? (Deux éléments égaux gardent leur ordre relatif.) Comment la tester avec des couples (valeur, indice d’origine) ?

03 / Robustesse

Exceptions : échouer tôt, échouer clairement

class CapteurError(Exception):
    """Erreur propre au capteur (classe de base pour les nôtres)."""

class HorsPlage(CapteurError):
    def __init__(self, valeur, mini, maxi):
        super().__init__(f"valeur {valeur} hors de [{mini}, {maxi}]")
        self.valeur = valeur

def lire_temperature(brut: int) -> float:
    """Convertit une lecture 10 bits (0-1023) en °C. Lève HorsPlage sinon."""
    if not (0 <= brut <= 1023):
        raise HorsPlage(brut, 0, 1023)
    tension = brut * 5.0 / 1023
    return (tension - 0.5) * 100          # capteur TMP36

lectures = [512, 700, 2000, -3, 300]
temperatures = []
for brut in lectures:
    try:
        temperatures.append(lire_temperature(brut))
    except HorsPlage as e:
        print("lecture ignorée :", e)
    finally:
        pass                              # exécuté dans tous les cas (fermer un fichier, un port…)

print([round(t, 1) for t in temperatures])

# Ne JAMAIS faire ceci :
try:
    lire_temperature(5000)
except:                                   # attrape tout, même Ctrl+C et les fautes de frappe
    pass                                  # ... et se tait. Le bug est enterré vivant.
print("(le except nu a caché l'erreur — c'est le pire)")

Les règles

Attrapez l’exception la plus précise possible, jamais except: nu.
Une exception attrapée doit être traitée (valeur de repli, message, nouvel essai) ou relancée (raise). Jamais avalée en silence.
Créez vos propres classes d’exceptions pour que l’appelant puisse distinguer vos erreurs de celles de Python.
Vérifiez les préconditions en entrée de fonction (« échouer tôt ») : un bug détecté à 1 cm de sa cause se corrige en 1 minute ; à 1 km, en 1 journée.
finally ou, mieux, with pour libérer les ressources (fichiers, ports série, verrous).

03 / Robustesse

Journaliser plutôt qu’imprimer

print vs logging

print est pour l’utilisateur ; logging est pour le développeur et l’exploitant. Le logging a des niveaux (DEBUG < INFO < WARNING < ERROR < CRITICAL), une origine (le logger « robot.moteur »), un horodatage, et peut être redirigé vers un fichier, le réseau ou une console série sans toucher au code. Sur un robot, le journal est ce qui reste quand il a fini dans le mur : c’est votre boîte noire. Sur microcontrôleur, on fait la même chose à la main avec des niveaux et Serial.print.

04 / Performance

Mesurer avant d’optimiser

Les trois lois de l’optimisation

Ne le faites pas. Un code clair et correct d’abord.
Pas encore. Mesurez : dans 90 % des programmes, 90 % du temps est dans 10 % du code, et ce n’est presque jamais là où on croit.
Changez l’algorithme avant de bidouiller. Passer de O(n) à O(√n) par test (ci-dessus) gagne un facteur 100 ; réécrire les mêmes boucles « plus vite » gagne 20 %.

Outils : time.perf_counter() pour un chrono, timeit pour des micro-mesures répétées, cProfile pour la carte du temps, tracemalloc pour la mémoire. En C : perf, valgrind, gprof.

04 / Performance

Ce qui coûte vraiment en Python

Retenez : les compréhensions battent les boucles explicites ; join bat += ; un set ou un dict répond en O(1) là où une liste met O(n). Et NumPy (module L10) bat tout cela d’un facteur 10 à 100 dès qu’il s’agit de nombres.

Cours

Cours 1 — Qu’est-ce qu’un « bon » programme ? Les cinq critères

Critère	Définition	Comment on le vérifie
Correct	Fait ce que la spécification demande, pour toutes les entrées valides	Tests (cas nominaux, limites, erreurs), preuve (L09)
Lisible	Un lecteur comprend l’intention sans exécuter	Noms, découpage, docstrings ; relecture par un pair
Robuste	Échoue proprement sur les entrées invalides, ne cache pas d’erreur	Exceptions ciblées, validation en entrée, journal
Maintenable	Modifiable sans casser le reste	Tests de non-régression, faible couplage (L02)
Efficace	Assez rapide et économe pour l’usage	Mesure (profilage), complexité (L03-L04)

Définition. Une spécification est l’énoncé précis de ce qu’une fonction doit faire : ses entrées valides (précondition), sa sortie garantie (postcondition), ses effets (fichiers, réseau, état modifié). Sans spécification, aucun test n’a de sens : on ne peut pas dire qu’un programme est faux si on n’a pas dit ce qu’il devait faire.

Exemple travaillé. Spécifier moyenne(valeurs) : précondition « liste non vide de nombres » ; postcondition « renvoie Σ/n, un flottant » ; erreur « lève ValueError si vide ». Chaque clause devient un test : un cas nominal, le cas vide, et une propriété (la moyenne est comprise entre min et max).

Les erreurs de débutant, classées par gravité

Silencieuses (les pires) : except: pass, valeur de repli qui cache un bug, comparaison de flottants avec ==.
Fragiles : dépendre de l’ordre d’un dictionnaire ancien, de l’état global, du répertoire courant.
Illisibles : noms d’une lettre, fonctions de 200 lignes, commentaires qui répètent le code.
Lentes : O(n²) évitable, recalcul dans une boucle, += sur des chaînes. Elles ne sont graves que si mesurées.

Cours

Cours 2 — La pyramide des tests et le cycle rouge / vert / refactor

Test unitaire : une fonction, isolée, en millisecondes. Des centaines par projet.

Test d’intégration : plusieurs composants ensemble (le capteur simulé + le filtre + le journal). Des dizaines.

Test de bout en bout : le système complet (le robot fait un parcours). Quelques-uns ; lents et fragiles.

Test par propriétés : une invariance vérifiée sur des entrées aléatoires (L01 §02).

Test de non-régression : ajouté après chaque bug corrigé.

Le cycle TDD (test-driven development) :

Rouge : écrire un test qui échoue (la fonctionnalité n’existe pas encore).
Vert : écrire le code minimal qui le fait passer.
Refactor : nettoyer sans changer le comportement ; les tests le garantissent.

Ce cycle force à spécifier avant de coder, produit une suite de tests complète sans effort séparé, et garde le code simple. Ce n’est pas obligatoire partout, mais pour un algorithme délicat, c’est la méthode la plus sûre.

Cours

Cours 3 — Lire un profil et une trace d’erreur

Traceback (most recent call last):
  File "robot.py", line 42, in <module>
    mission.demarrer()
  File "robot.py", line 30, in demarrer
    self.capteurs[0].lire()
IndexError: list index out of range

Une trace se lit de bas en haut : la dernière ligne dit quoi (IndexError : indice hors limites), la ligne juste au-dessus dit où (ligne 30, self.capteurs[0]), les lignes du dessus disent comment on est arrivé là (appelé depuis demarrer, depuis la ligne 42). Question à se poser : « pourquoi capteurs est-il vide à ce moment ? » — pas « comment éviter l’exception ». Le bug est en amont, là où la liste aurait dû être remplie.

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1000    2.310    0.002    2.310    0.002 robot.py:55(lire_capteur)
        1    0.004    0.004    2.402    2.402 robot.py:40(boucle)
    50000    0.080    0.000    0.080    0.000 {method 'append' of 'list' objects}

Un profil (cProfile) se lit par cumtime décroissant : ici 96 % du temps est dans lire_capteur, appelée 1000 fois à 2,3 ms. Deux leviers : appeler moins (cache, cadence) ou rendre chaque appel moins cher. Les 50 000 append ne pèsent rien : les optimiser serait une perte de temps. C’est ce que « mesurer avant d’optimiser » veut dire concrètement.

TP guidé

TP — Mettre en place l’atelier du professionnel (sur votre PC, 45 min)

Créer le projet et l’environnement.

mkdir tp-pro && cd tp-pro
python -m venv .venv
source .venv/bin/activate        # Windows : .venv\Scripts\activate
pip install pytest hypothesis ruff black mypy
python -c "import pytest, hypothesis; print('ok')"

Attendu : ok. Si python est introuvable, essayez python3 ou py.

Écrire le module. Fichier stats.py :

"""Statistiques élémentaires sur des listes de nombres."""

def moyenne(valeurs: list[float]) -> float:
    """Moyenne arithmétique ; ValueError si la liste est vide."""
    if not valeurs:
        raise ValueError("moyenne d'une liste vide")
    return sum(valeurs) / len(valeurs)

def mediane(valeurs: list[float]) -> float:
    """Valeur centrale (moyenne des deux centrales si n pair)."""
    if not valeurs:
        raise ValueError("médiane d'une liste vide")
    t = sorted(valeurs); n = len(t)
    return t[n // 2] if n % 2 else (t[n // 2 - 1] + t[n // 2]) / 2

Écrire les tests. Fichier test_stats.py :

import pytest
from hypothesis import given, strategies as st
from stats import moyenne, mediane

def test_moyenne_nominal():
    assert moyenne([1, 2, 3]) == 2

def test_moyenne_vide():
    with pytest.raises(ValueError):
        moyenne([])

@given(st.lists(st.floats(-1e6, 1e6), min_size=1))
def test_moyenne_entre_min_et_max(v):
    assert min(v) - 1e-6 <= moyenne(v) <= max(v) + 1e-6

@given(st.lists(st.integers(), min_size=1))
def test_mediane_partage(v):
    m = mediane(v)
    assert sum(x <= m for x in v) >= len(v) / 2 and sum(x >= m for x in v) >= len(v) / 2

Lancer.
```
pytest -v
```
Attendu : 4 tests PASSED. Hypothesis a exécuté 100 listes aléatoires par test de propriété. Cassez volontairement mediane (retirez le sorted) : quel test devient rouge, et quel contre-exemple minimal Hypothesis affiche-t-il ?
Style et types.
```
ruff check .
black --check .
mypy stats.py
```
Attendu : aucun message (ou corrigez ce qui est signalé : imports inutilisés, lignes trop longues, annotation manquante).
Profiler.
```
python -c "import cProfile, random, stats; v=[random.random() for _ in range(200000)]; cProfile.run('for _ in range(20): stats.mediane(v)', sort='cumtime')"
```
Lisez la ligne de sorted : c’est là que passe le temps. Comment obtenir la médiane sans trier complètement ? (Indice : statistics.median, ou l’algorithme quickselect, O(n) en moyenne — défi ★★ du module L04.)
Livrable. Un dossier avec stats.py, test_stats.py, et la sortie de pytest -v copiée dans un fichier RESULTATS.md. Vous réutiliserez cette structure dans tous les TP suivants.

Exercices

Exercices auto-corrigés — complétez, exécutez, les tests disent si c’est juste

Exercice 1 — Spécifier et implémenter

Complétez normaliser : reçoit une liste de nombres, renvoie la liste ramenée dans [0, 1] par (x − min)/(max − min). Si tous les éléments sont égaux, renvoyer une liste de 0. Liste vide → liste vide. Ne modifiez pas les tests.

Correction

def normaliser(valeurs):
    if not valeurs: return []
    lo, hi = min(valeurs), max(valeurs)
    if hi == lo: return [0] * len(valeurs)
    return [(x - lo) / (hi - lo) for x in valeurs]

Exercice 2 — Exceptions propres

Écrivez lire_config(texte) qui transforme des lignes cle=valeur en dictionnaire (valeurs converties en int si possible, sinon chaîne), ignore les lignes vides et les commentaires #, et lève ValueError avec le numéro de ligne pour une ligne sans =.

Correction

def lire_config(texte):
    conf = {}
    for num, ligne in enumerate(texte.splitlines(), 1):
        l = ligne.strip()
        if not l or l.startswith("#"): continue
        if "=" not in l: raise ValueError(f"ligne {num} : '=' attendu")
        k, v = (s.strip() for s in l.split("=", 1))
        try: conf[k] = int(v)
        except ValueError: conf[k] = v
    return conf

Exercices

Exercices auto-corrigés — tests et mesure

Exercice 3 — Écrire les tests qui trouvent le bug

chercher_max contient un bug. Écrivez au moins trois assert dont un qui échoue avec la version actuelle ; puis corrigez la fonction pour que tout passe.

Correction

assert chercher_max([4, 9, 9]) == 1 échoue (renvoie 2) : le >= doit être > pour garder le premier maximum. Autres tests utiles : [7] → 0, [9, 1, 2] → 0, [-3, -1, -2] → 1.

Exercice 4 — Mesurer et choisir

Deux fonctions calculent les doublons d’une liste. Mesurez-les sur 20 000 éléments avec time.perf_counter, puis complétez la phrase imprimée avec la bonne complexité (« n² » ou « n »).

05 / Défis

Défi ★ — Refactoriser

Consigne

Réécrivez ce code selon les règles du module : noms, types, docstring, découpage en fonctions, un test par fonction. Il doit produire exactement les mêmes résultats.

Correction

def statistiques(valeurs: list[float]) -> dict[str, float]:
    """Maximum, minimum, moyenne et étendue d'une liste non vide."""
    if not valeurs:
        raise ValueError("liste vide")
    maxi, mini = max(valeurs), min(valeurs)
    return {"max": maxi, "min": mini,
            "moyenne": sum(valeurs) / len(valeurs), "etendue": maxi - mini}

def test_statistiques():
    s = statistiques([4, 8, 15, 16, 23, 42])
    assert s["max"] == 42 and s["min"] == 4
    assert abs(s["moyenne"] - 18) < 1e-9 and s["etendue"] == 38
    assert statistiques([7]) == {"max": 7, "min": 7, "moyenne": 7, "etendue": 0}
    try:
        statistiques([]); assert False
    except ValueError:
        pass

Un dictionnaire nommé vaut mieux qu’une liste de 4 valeurs dont il faut se rappeler l’ordre. Les fonctions intégrées max, min, sum remplacent trois boucles. Le cas de la liste vide devient une erreur explicite au lieu d’un IndexError mystérieux.

05 / Défis

Défi ★★ — Trouver le bug par les tests

Consigne

Cette fonction est censée renvoyer l’indice de x dans la liste triée L (ou −1) par dichotomie. Elle a un bug. Écrivez des tests par propriétés (comparaison à L.index(x) sur des listes aléatoires) qui le révèlent, trouvez le plus petit contre-exemple, corrigez.

Correction

Contre-exemple minimal : dichotomie([1, 2], 2) boucle sans fin (bas = 0, haut = 2, m = 0, L[0] < 2 donc bas = 0 : rien ne change). Le bug : bas = m au lieu de bas = m + 1. Quand L[m] < x, on sait que m n’est pas la réponse : on doit l’exclure. Avec l’invariant « la réponse, si elle existe, est dans [bas, haut[ », chaque tour doit strictement réduire l’intervalle, sinon la terminaison n’est pas garantie.

import random
def test_dichotomie():
    for _ in range(2000):
        L = sorted(random.sample(range(100), random.randint(0, 20)))
        x = random.randint(0, 100)
        attendu = L.index(x) if x in L else -1
        assert dichotomie(L, x) == attendu, (L, x)

Pour détecter une boucle infinie dans un test, ajoutez un compteur de tours et une assertion tours <= 2 * len(L).bit_length() + 2. Le module L09 montre comment prouver la terminaison plutôt que l’espérer.

05 / Défis

Défi ★★★ — Esprit prépa : une bibliothèque de fractions testée

Consigne

Écrivez une classe Fraction (numérateur, dénominateur, toujours réduite, dénominateur > 0) avec + − × ÷, comparaison, __repr__, conversion en float, et une batterie de tests par propriétés : commutativité, associativité, élément neutre, inverse, cohérence avec fractions.Fraction de la bibliothèque standard sur 1000 tirages. Le tout doit tenir en moins de 80 lignes, sans un seul print hors des tests.

Correction

from math import gcd
from functools import total_ordering
import random
from fractions import Fraction as Ref

@total_ordering
class Fraction:
    __slots__ = ("num", "den")
    def __init__(self, num: int, den: int = 1):
        if den == 0:
            raise ZeroDivisionError("dénominateur nul")
        if den < 0:
            num, den = -num, -den
        g = gcd(num, den) or 1
        self.num, self.den = num // g, den // g
    def __add__(self, o):  return Fraction(self.num * o.den + o.num * self.den, self.den * o.den)
    def __sub__(self, o):  return Fraction(self.num * o.den - o.num * self.den, self.den * o.den)
    def __mul__(self, o):  return Fraction(self.num * o.num, self.den * o.den)
    def __truediv__(self, o): return Fraction(self.num * o.den, self.den * o.num)
    def __neg__(self):     return Fraction(-self.num, self.den)
    def __eq__(self, o):   return (self.num, self.den) == (o.num, o.den)
    def __lt__(self, o):   return self.num * o.den < o.num * self.den
    def __float__(self):   return self.num / self.den
    def __repr__(self):    return f"{self.num}/{self.den}" if self.den != 1 else str(self.num)

def alea():
    return Fraction(random.randint(-20, 20), random.randint(1, 20))

def test_proprietes():
    zero, un = Fraction(0), Fraction(1)
    for _ in range(1000):
        a, b, c = alea(), alea(), alea()
        assert a + b == b + a and a * b == b * a
        assert (a + b) + c == a + (b + c)
        assert a + zero == a and a * un == a
        assert a + (-a) == zero
        assert a * (b + c) == a * b + a * c
        if a != zero:
            assert a / a == un
        ra, rb = Ref(a.num, a.den), Ref(b.num, b.den)
        s = a + b
        assert Ref(s.num, s.den) == ra + rb
        assert (a < b) == (ra < rb)
test_proprietes()

@total_ordering déduit <=, >, >= de == et <. __slots__ fixe les attributs (moins de mémoire, pas de faute de frappe silencieuse). La comparaison à la bibliothèque standard est un oracle : quand il existe une implémentation de référence, testez contre elle. Ouverture : et pour des fractions de polynômes ? La même structure fonctionne dès qu’on a un PGCD (anneau euclidien) — c’est un thème de l’algèbre de prépa.

06 / Vérification

Lequel de ces tests est inutile ?

Deux questions supplémentaires

1. Pourquoi except Exception vaut-il mieux que except: ? Le second attrape aussi KeyboardInterrupt et SystemExit : le programme devient impossible à arrêter proprement.

2. Quel est l’intérêt d’un test qui échoue avant la correction d’un bug ? Prouver que le test détecte bien le bug. Un test écrit après coup, qui n’a jamais été rouge, peut ne rien tester du tout.

Référence

Les mots à retenir

Mot	Définition
PEP 8	Le guide de style officiel de Python.
Annotation de type	Indication `x: int` lue par les outils (mypy), pas vérifiée par Python.
Docstring	Chaîne sous la signature qui documente la fonction ; lue par `help()`.
Test unitaire	Fonction qui vérifie un comportement précis avec `assert`.
Test par propriétés	Vérifier une invariance sur des entrées aléatoires.
Non-régression	Test ajouté après un bug pour qu’il ne revienne pas.
Oracle	Implémentation de référence à laquelle on compare.
Profilage	Mesurer où passe le temps, fonction par fonction.
Refactoriser	Améliorer la structure du code sans changer son comportement (les tests le garantissent).

Pour continuer

Vous écrivez du code qu’on peut relire

Module suivant : la programmation orientée objet en profondeur — encapsulation, héritage, polymorphisme, et les patrons de conception qu’utilisent les vrais logiciels.

À faire chez soi

Installer sur PC : pip install black ruff mypy pytest hypothesis. Passer black et ruff sur un ancien programme du parcours collège.
Reprendre le projet « Mission Mars » (séance 10) : le découper en fonctions typées et documentées, écrire 10 tests.
Lire le chapitre « Clean Code » de Robert Martin sur les noms, ou le cours CS50 semaine 1 (« Don’t repeat yourself »).

Sommaire L02 : Programmation orientée objet →