Programmation modulaire

Cours complet · algorithmique et programmation (première), chapitre 5 · première, algorithmique et programmation

Comment écrire un programme de cinquante lignes sans s'y perdre ? En n'écrivant que des programmes de cinq lignes. La programmation modulaire — l'accent explicite du programme de première — consiste à découper une tâche complexe en tâches plus simples, chacune confiée à une fonction courte, testée, réutilisable. Ce chapitre en donne la méthode et l'applique à des mini-projets qui remobilisent tout le livre.

5.1 Le principe : découper

Définition 5.1Programmation modulaire

Programmer de façon modulaire, c'est organiser un programme en fonctions courtes, chacune réalisant une seule tâche clairement définie, et construire les tâches complexes en assemblant ces briques — comme une démonstration s'appuie sur des lemmes.

Une tâche complexe (bleu) se décompose en fonctions simples (vert) qui s'appellent entre elles : chaque flèche est un appel de fonction.

iRemarquePourquoi découper ?

Lisibilité : chaque fonction se lit et se comprend seule ;
tests : on vérifie chaque brique isolément — une erreur se localise vite ;
réutilisation : moyenne écrite au chapitre 4 ressert partout, sans retouche ;
travail d'équipe : chacun peut écrire sa brique, pourvu qu'on se soit accordé sur ce qu'elle reçoit et renvoie.

Méthode : Concevoir de façon modulaire

Décomposer la tâche en sous-tâches (au brouillon, en français) ;
pour chaque sous-tâche, préciser l'interface de la fonction : ses entrées (paramètres) et sa sortie (valeur renvoyée) ;
écrire et tester les briques une à une, en commençant par celles qui ne dépendent de rien ;
assembler : la fonction principale ne fait plus qu'appeler les briques.

5.2 Tester chaque brique

Le mot « brique » n'est pas une image gratuite : c'est parce que le programme est fait de briques qu'un défaut de l'une se manifeste ailleurs.

Méthode : Tests par `assert`

L'instruction assert condition ne fait rien si la condition est vraie, et arrête le programme sinon : c'est un filet de sécurité. On teste chaque fonction sur des cas dont on connaît la réponse — valeurs du cours, petits cas calculés à la main, cas limites :


def moyenne(L):
    return sum(L) / len(L)

assert moyenne([2, 4, 6]) == 4          # cas simple calculé de tête
assert moyenne([7]) == 7                # cas limite : un seul élément
assert abs(moyenne([0.1]*10) - 0.1) < 1e-9   # flottants : à epsilon près

Des tests qui passent ne prouvent pas la correction (chapitre logique : des exemples ne démontrent pas un « pour tout » !), mais un test qui échoue réfute — c'est le contre-exemple automatisé.

5.3 Mini-projet 1 : l'étude complète d'une suite

Objectif : une fonction etudier(f, u0, n) qui, pour une suite récurrente $u_{k + 1} = f (u_{k})$ , imprime un rapport — termes, nature conjecturée, limite éventuelle. Décomposition :


def termes(f, u0, n):
    L = [u0]
    for i in range(n - 1):
        L.append(f(L[-1]))
    return L

def differences(L):
    return [L[i+1] - L[i] for i in range(len(L) - 1)]

def quotients(L):
    return [L[i+1] / L[i] for i in range(len(L) - 1)]

def est_constante(L, eps=1e-9):
    # True si tous les éléments de L sont égaux (à eps près)
    return max(L) - min(L) < eps

def etudier(f, u0, n):
    L = termes(f, u0, n)
    print("Premiers termes :", L[:6])
    if est_constante(differences(L)):
        print("Conjecture : arithmétique de raison", differences(L)[0])
    elif est_constante(quotients(L)):
        print("Conjecture : géométrique de raison", quotients(L)[0])
    elif abs(L[-1] - L[-2]) < 1e-6:
        print("Conjecture : converge vers environ", round(L[-1], 4))
    else:
        print("Ni arithmétique, ni géométrique, pas de limite apparente")

etudier(lambda u: u + 3,        2, 30)  # arithmétique de raison 3
etudier(lambda u: 0.5 * u,      8, 60)  # géométrique de raison 0.5
etudier(lambda u: 0.8*u + 4,    5, 200) # converge vers environ 20.0
etudier(lambda u: 4*u*(1 - u), 0.2, 50) # ni l'un ni l'autre (logistique !)

iRemarque

Cinq briques de moins de six lignes, dont trois déjà écrites aux chapitres précédents : la modularité récompense le travail passé. Et la fonction est_constante est réutilisable telle quelle dans tout autre projet.

5.4 Mini-projet 2 : auditer un jeu d'argent

Objectif : décider si un jeu (loi de gain donnée par deux listes) est équitable, en croisant théorie et simulation — l'architecture du schéma d'ouverture :


from random import random

def esperance(valeurs, probas):
    return sum([probas[i] * valeurs[i] for i in range(len(valeurs))])

def simule(valeurs, probas):
    r, cumul = random(), 0
    for i in range(len(valeurs)):
        cumul += probas[i]
        if r < cumul:
            return valeurs[i]

def echantillon(valeurs, probas, n):
    return [simule(valeurs, probas) for k in range(n)]

def moyenne(L):
    return sum(L) / len(L)

def auditer(valeurs, probas, n=10**5):
    E = esperance(valeurs, probas)
    m = moyenne(echantillon(valeurs, probas, n))
    print("Espérance théorique :", E)
    print("Moyenne simulée     :", round(m, 4))
    if abs(E) < 1e-9:
        print("Jeu ÉQUITABLE")
    elif E > 0:
        print("Favorable au joueur")
    else:
        print("Défavorable au joueur :", -E, "perdu par partie en moyenne")

auditer([8, 0, -2], [0.1, 0.3, 0.6])
# Espérance théorique : -0.4
# Moyenne simulée     : -0.3982
# Défavorable au joueur : 0.4 perdu par partie en moyenne

iRemarque

La fonction principale auditer ne contient aucun calcul : elle orchestre. Si l'on veut changer la méthode de simulation, on ne touche qu'à simule ; le reste suit — c'est la force du découpage par interfaces.

5.5 Mini-projet 3 : quelle langue parle ce texte ?

Objectif : deviner la langue d'un texte en comparant son profil de fréquences de lettres (chapitre 4) aux profils de référence du français et de l'anglais. Il faut une notion de distance entre profils :


def distance(P, Q):
    # Somme des carrés des écarts entre deux profils de 26 fréquences
    return sum([(P[i] - Q[i])**2 for i in range(26)])

def quelle_langue(texte, profil_fr, profil_en):
    P = frequences_lettres(texte)          # brique du chapitre 4
    d_fr = distance(P, profil_fr)
    d_en = distance(P, profil_en)
    if d_fr < d_en:
        return "français"
    return "anglais"

Trois briques — frequences_lettres (déjà écrite), distance (quatre lignes), quelle_langue (l'assemblage) — suffisent pour un détecteur de langue fonctionnel. La même architecture identifie un auteur, décode une substitution, ou classe des documents : décomposer rend les idées transportables.

5.6 Exercices d'entraînement

Difficulté : ★ facile ★ moyen ★ plus difficile.

Exercice

Découper en fonctions (donner seulement les interfaces : nom, paramètres, valeur renvoyée) la tâche : « déterminer si l'équation $a x^{2} + b x + c = 0$ admet deux solutions de signes contraires ». Quel critère du cours de mathématiques la brique finale utilise-t-elle ?

Solution

Par exemple : discriminant(a, b, c) $\to$ réel ; produit_racines(a, c) $\to$ réel ( $= c / a$ ) ; signes_contraires(a, b, c) $\to$ booléen, qui renvoie discriminant(a,b,c) > 0 and produit_racines(a,c) < 0. Le critère : deux racines réelles de signes contraires $⟺ Δ > 0$ et produit $\frac{c}{a} < 0$ (somme et produit des racines, chapitre Second degré).

Exercice

Écrire trois assert pertinents pour la fonction mediane du chapitre 4 (au moins un cas pair, un cas impair, un cas limite).

Solution


assert mediane([3, 1, 2]) == 2            # impair : valeur centrale (et tri !)
assert mediane([4, 1, 3, 2]) == 2.5       # pair : moyenne des deux centrales
assert mediane([7]) == 7                  # limite : un seul élément

Le premier test vérifie aussi que la fonction trie bien (liste donnée en désordre) : un bon test contrôle plusieurs choses à la fois.

Exercice

Compléter le mini-projet 1 avec une brique seuil(f, u0, objectif) renvoyant le premier rang où la suite dépasse l'objectif, puis l'intégrer à etudier pour qu'elle affiche, dans le cas d'une conjecture de croissance vers l'infini, le rang de dépassement de $1 0^{6}$ .

Solution


def seuil(f, u0, objectif):
    u, n = u0, 0
    while u <= objectif:
        u = f(u)
        n += 1
    return n

# Dans etudier, brancher un cas supplémentaire :
#   elif L[-1] > L[0] and quotients(L) et croissance rapide...
# Version simple : si le dernier terme dépasse 10**6, afficher
#   print("Dépasse 10^6 au rang", seuil(f, u0, 10**6))

L'intérêt : seuil est autonome, testable seule (assert seuil(lambda u: 2*u, 1, 1000) == 10), et etudier ne grossit que d'un appel.

Exercice

Projet : simulateur de marche aléatoire. Écrire, en respectant la démarche modulaire :

pas() : renvoie $+ 1$ ou $- 1$ avec équiprobabilité ;
marche(n) : renvoie la liste des positions successives d'une marche de $n$ pas partant de $0$ ;
amplitude(L) : l'écart entre la position maximale et minimale atteintes ;
etude(N, n) : simule $N$ marches de $n$ pas et renvoie la moyenne des amplitudes.

Solution


from random import choice

def pas():
    return choice([-1, 1])

def marche(n):
    L = [0]
    for k in range(n):
        L.append(L[-1] + pas())
    return L

def amplitude(L):
    return max(L) - min(L)

def etude(N, n):
    return sum([amplitude(marche(n)) for k in range(N)]) / N

print(etude(2000, 100))   #   25 : l'amplitude croît comme rac(n),
print(etude(2000, 400))   #   50 : n x 4 -> amplitude x 2 !

Quatre briques de quatre lignes ; et l'expérience révèle la loi en $n$ des marches aléatoires — la même racine carrée que la fluctuation d'échantillonnage.

Exercice

Projet : dichotomie généraliste. Écrire dichotomie(f, a, b, eps) renvoyant une solution approchée de $f (x) = 0$ sur $[a; b]$ (avec $f (a)$ et $f (b)$ de signes contraires) à la précision eps, puis l'utiliser pour : (a) $10$ (via $x^{2} - 10$ ) ; (b) la solution de $e^{x} = 3$ (via une fonction utilisant exp du module math).

Solution


def dichotomie(f, a, b, eps):
    while b - a > eps:
        m = (a + b) / 2
        if f(a) * f(m) <= 0:
            b = m
        else:
            a = m
    return (a + b) / 2

print(dichotomie(lambda x: x**2 - 10, 3, 4, 1e-6))   # 3.1622776...

from math import exp
print(dichotomie(lambda x: exp(x) - 3, 0, 2, 1e-6))  # 1.0986122...

Une seule brique générique résout les deux problèmes : c'est le sommet de la modularité — la fonction reçoit une fonction en paramètre. (La solution de $e^{x} = 3$ est le $ln 3$ que la terminale nommera.)

Continuer sur Adloun : animation, QCM, fiches, exercices