Aux écrits d'informatique X-ENS, une fonction qui marche ne suffit pas : tu dois aussi justifier qu'elle s'arrête, que son résultat est juste, et ce qu'elle coûte. Pour l'exponentiation rapide détaillée plus bas : l'exposant restant diminue à chaque tour, la quantité $r \times b^k$ reste égale à $a^n$, et comme l'exposant est divisé par deux à chaque tour, il faut $O(\log n)$ multiplications.
Ce que le jury attend
À la session 2024, l'épreuve d'Informatique B de la filière MP durait 2 heures et se traitait en Python ; l'épreuve écrite d'informatique fondamentale des quatre ENS concernait les filières MP et MPI. En MPI, le programme d'informatique repose sur C et OCaml, plus SQL pour les bases de données.
En informatique fondamentale, le jury rappelle que « chaque affirmation doit être rigoureusement justifiée ». En Informatique B, le jury écrit : « L'absence de test sur le dépassement de bornes de listes est une erreur trop fréquente et systématiquement pénalisée. » Il souhaite aussi qu'une fonction longue soit expliquée en langage courant.
Piège classique : le coût d'une fonction inclut celui des fonctions qu'elle appelle. Une boucle de $n$ tours qui appelle à chaque tour une fonction en $O(n)$ coûte $O(n^2)$. En Python, x in L parcourt la liste L : c'est un coût caché en $O(n)$. Le rapport d'Informatique B 2024 relève cet oubli à deux questions.
Piège classique : en Python, b = a ne copie pas la liste a : modifier b modifie a. Une copie s'écrit a.copy(), et une liste de listes se copie ligne par ligne. Le même rapport relève cette lacune.
Prouver l'arrêt et la correction
Définition : un algorithme termine s'il s'arrête pour toute entrée. Il est partiellement correct si son résultat est juste quand il s'arrête, totalement correct s'il termine en plus. Un variant est une quantité entière naturelle qui diminue strictement à chaque tour de boucle. Un invariant est une propriété vraie avant le premier tour et conservée par chaque tour.
Le variant prouve l'arrêt : une suite d'entiers naturels ne peut pas décroître strictement sans fin. L'invariant prouve la correction en trois temps.
Initialisation : l'invariant est vrai avant le premier tour.
Conservation : s'il est vrai au début d'un tour, il l'est encore à la fin.
Conclusion : à la sortie, l'invariant joint à la condition d'arrêt donne le résultat voulu.
Voici l'exponentiation rapide, qui calcule $a^n$ pour un entier naturel $n$.
def puissance(a, n):
r, b, k = 1, a, n
while k > 0:
if k % 2 == 1:
r = r * b
b = b * b
k = k // 2
return rVariant : $k$, un entier naturel qui diminue strictement, car $\lfloor k/2 \rfloor < k$ pour $k \geqslant 1$.
Invariant : $r \times b^k = a^n$. Il est vrai au départ : $1 \times a^n = a^n$. Si $k = 2q$, la boucle remplace $b$ par $b^2$ et $k$ par $q$, et $r \times (b^2)^q = r \times b^{2q}$. Si $k = 2q + 1$, elle remplace en plus $r$ par $r \times b$, et $(r \times b) \times (b^2)^q = r \times b^{2q+1}$. À la sortie, $k = 0$, donc $r = a^n$.
Coût : $k$ est divisé par deux à chaque tour, donc pour $n \geqslant 1$ la boucle fait $\lfloor \log_2 n \rfloor + 1$ tours d'au plus deux multiplications : $O(\log n)$.
Le filtrage en OCaml
Une liste OCaml est soit vide, [], soit une tête suivie d'une queue, x :: q. Le filtrage (match ... with) suit cette définition : une ligne par forme possible.
let rec somme l = match l with
| [] -> 0
| x :: q -> x + somme qLa preuve suit les mêmes cas : tu montres la propriété pour [], puis pour x :: q en la supposant vraie pour q. C'est l'induction structurelle, qui généralise la récurrence. Ici, chaque appel porte sur une liste plus courte d'un élément : somme termine, en $n + 1$ appels de coût constant pour une liste de longueur $n$, soit $O(n)$.
Deux réflexes évitent des points perdus. Un filtrage complet d'abord : si une forme manque, le compilateur le signale, et l'exception Match_failure est levée si ce cas se présente. Ensuite, @ n'est pas gratuit : l1 @ l2 recopie toute la liste l1, en un temps proportionnel à sa longueur. Le programme demande de connaître ce coût ; l'exercice 2 montre ce qu'il change.
La programmation dynamique
Selon le jury d'informatique fondamentale 2024, « il semble que la quasi-totalité des étudiants ne maîtrise pas les principes de la programmation dynamique ». Ils tiennent pourtant en deux idées. Une solution optimale se construit à partir de solutions optimales de sous-problèmes plus petits (sous-structure optimale), et ces sous-problèmes reviennent plusieurs fois (chevauchement) : tu calcules chacun une seule fois et tu le ranges dans un tableau.
Exemple : payer la somme $s$ avec le moins de pièces possible, les pièces valant $p_1, \dots, p_k$, dont une vaut 1. Note $m(s)$ ce minimum. Une solution optimale pour $s$ a une dernière pièce $p_i$, et le reste paie $s - p_i$ de façon optimale, d'où :
$$m(0) = 0 \qquad \text{et, pour } s \geqslant 1, \quad m(s) = 1 + \min_{p_i \leqslant s} m(s - p_i)$$
En récursif naïf, cette formule recalcule les mêmes valeurs un nombre de fois qui explose avec $s$. De bas en haut, de $m(0)$ à $m(S)$, chacune n'est calculée qu'une fois :
def monnaie(pieces, S):
m = [0] * (S + 1)
for s in range(1, S + 1):
m[s] = 1 + min(m[s - p] for p in pieces if p <= s)
return mLe coût est $O(S \times k)$. La mémoïsation part du haut : la fonction récursive range chaque résultat dans un dictionnaire et le relit au lieu de le recalculer. Pour retrouver les pièces elles-mêmes, tu remontes le tableau, comme dans l'exercice 3.
Piège classique : rendre toujours la plus grosse pièce possible (algorithme glouton) ne donne pas toujours le minimum. Avec des pièces de 1, 3 et 4, le glouton paie 6 avec $4 + 1 + 1$, soit trois pièces, contre deux pour $3 + 3$. Un glouton ne s'utilise qu'avec une preuve de son optimalité.
Exercices corrigés
Du plus direct au niveau d'un écrit : rédige comme sur ta copie avant d'ouvrir la correction.
Exercice 1 : La fonction suivante reçoit deux entiers naturels $a$ et $b$, non tous les deux nuls. On admet que $\mathrm{pgcd}(a, b) = \mathrm{pgcd}(b, a \bmod b)$ quand $b > 0$, et que $\mathrm{pgcd}(a, 0) = a$. Montre qu'elle termine et qu'elle renvoie $\mathrm{pgcd}(a, b)$.
def pgcd(a, b):
while b != 0:
a, b = b, a % b
return aCorrection :
Terminaison : $b$ est un variant. C'est un entier naturel, remplacé à chaque tour par $a \bmod b$, et $0 \leqslant a \bmod b < b$ : il diminue strictement.
Correction : avec $a_0$ et $b_0$ les valeurs de départ, l'invariant est $\mathrm{pgcd}(a, b) = \mathrm{pgcd}(a_0, b_0)$. Vrai au départ, il est conservé grâce à l'égalité admise. À la sortie, $b = 0$, donc $\mathrm{pgcd}(a_0, b_0) = \mathrm{pgcd}(a, 0) = a$ : la fonction renvoie le bon résultat.
Exercice 2 : La fonction suivante renverse une liste.
let rec miroir l = match l with
| [] -> []
| x :: q -> miroir q @ [x]En comptant comme opération élémentaire la recopie d'un élément par @, combien d'opérations fait-elle sur une liste de longueur $n$ ? Écris une version de coût linéaire.
Correction :
Sur une liste de longueur $j \geqslant 1$, @ recopie miroir q, qui a $j - 1$ éléments. Les appels portent sur des longueurs $n, n - 1, \dots, 1$, d'où :
$$(n - 1) + (n - 2) + \dots + 1 + 0 = \frac{n(n - 1)}{2}$$
soit $O(n^2)$ : la fonction est quadratique, alors qu'un seul passage suffit.
La bonne version empile les éléments en tête d'un accumulateur, une liste passée en argument :
let miroir_lin l =
let rec aux acc l = match l with
| [] -> acc
| x :: q -> aux (x :: acc) q
in aux [] lIl y a $n + 1$ appels de coût constant : $O(n)$. Par induction sur l, aux acc l renvoie miroir l @ acc, donc aux [] l renvoie bien miroir l. L'appel récursif est la dernière opération de aux (récursivité terminale) : rien ne reste en attente sur la pile d'exécution, alors que la première version y garde $n$ appels.
Exercice 3 : Un distributeur de boissons rend la monnaie en pièces de 1, 3 et 4 unités, en quantité illimitée (système fictif). Calcule le nombre minimal $m(s)$ de pièces pour rendre $s$ unités, pour $s$ allant de 0 à 10. Donne une façon de rendre 10 unités avec $m(10)$ pièces, puis compare avec le glouton.
Correction :
Chaque valeur utilise $m(s - 1)$, $m(s - 3)$ et $m(s - 4)$ quand elles existent, par exemple $m(5) = 1 + \min(m(4), m(2), m(1)) = 2$. On obtient :
$m(0) = 0$, $m(1) = 1$, $m(2) = 2$, $m(3) = m(4) = 1$, $m(5) = m(6) = m(7) = m(8) = 2$, $m(9) = m(10) = 3$.
Reconstruction : $m(10) = 1 + m(7)$ avec une pièce de 3, $m(7) = 1 + m(4)$ avec une pièce de 3, et $m(4) = 1$ avec une pièce de 4. Le distributeur rend $3 + 3 + 4$, soit 3 pièces.
Le glouton rend $4 + 4 + 1 + 1$, soit 4 pièces : une de trop.
À retenir
À retenir :
- Une fonction se rend avec un variant (arrêt), un invariant (correction) et sa complexité.
- Invariant : initialisation, conservation, conclusion à la sortie.
- Une complexité inclut celle des fonctions appelées,
x in Let@compris. - En OCaml, un motif par forme de donnée, une preuve qui suit les mêmes cas.
- Programmation dynamique : sous-problème, récurrence, tableau rempli dans le bon ordre, reconstruction.
- Un glouton exige une preuve d'optimalité.
Sources
- Programme d'informatique de la filière MPI, ministère de l'Enseignement supérieur, 2021 : texte sur education.gouv.fr.
- Rapport du jury d'Informatique B, filière MP, concours 2024 : texte sur di.ens.fr.
- Rapport du jury de l'épreuve écrite d'informatique fondamentale, banques MP et MPI inter-ENS, session 2024 : texte sur di.ens.fr.