#Décomposition de problèmesCopier le lien

Découper un problème complexe en sous-problèmes simples, puis définir pour chacun une interface nette et des invariants vérifiables.

#PrérequisCopier le lien

Savoir lire un programme Python élémentaire (boucle, dictionnaire, comparaison). Le module programmation Python couvre ces bases.

#Objectifs d'apprentissageCopier le lien

• Découper un objectif en sous-problèmes ordonnés et indépendants.
• Écrire pour chaque sous-problème un contrat : entrée, sortie, garantie.
• Formaliser une décomposition récursive en définition inductive (base, règles) et vérifier qu'elle est non ambiguë.
• Énoncer un invariant de boucle et vérifier qu'il tient à chaque itération.
• Reconnaître quand une décomposition est terminée : chaque brique est testable isolément.

#Le fil rouge : statistiques de motsCopier le lien

Problème : à partir d'un texte, produire la liste des mots classés par fréquence décroissante. La décomposition naturelle donne cinq sous-problèmes : lire, nettoyer, découper, compter, trier. Chaque étape est volontairement écrite « à la main » pour se concentrer sur la logique plutôt que sur des fonctions toutes faites.

#Étape 1 : deux briques, un pipelineCopier le lien

Sortie exacte :

1[('bonjour', 2), ('le', 1), ('monde', 1)]

#Étape 2 : la version décomposéeCopier le lien

Le même comportement, mais chaque responsabilité a sa fonction et son contrat explicite :

Sorties exactes :

1['les', 'tudiants', 'posent', 'des', 'questions', 'posent', 'encore', 'des', 'questions']2[('des', 2), ('posent', 2), ('questions', 2), ('encore', 1), ('les', 1), ('tudiants', 1)]

#Le contrat de chaque briqueCopier le lien

Une bonne décomposition rend chaque brique remplaçable et testable. Voici les contrats de la version décomposée :

Ces contrats sont ce qui permet de remplacer le tri par sélection par sorted(tableau, key=lambda p: (-p[1], p[0])) sans toucher au reste : le consommateur de la sortie ne voit aucune différence.

#Invariants de boucleCopier le lien

Un invariant est une propriété qui reste vraie à chaque itération d'une boucle. C'est l'outil qui prouve qu'un algorithme fait ce qu'il prétend.

Dans le tri par sélection ci-dessus, l'invariant est : au début de l'itération i, la tranche tableau[:i] contient les i plus grandes paires du dictionnaire, dans l'ordre final.

• Avant la première itération (i = 0) : la tranche est vide, la propriété tient trivialement.
• Si elle tient à l'itération i : la boucle interne cherche le maximum de tableau[i:] selon le critère et l'amène en position i, donc elle tient encore à l'itération i + 1.
• À la sortie (i = len(tableau)) : la tranche est le tableau entier, trié selon le critère voulu.

Le même raisonnement s'applique au comptage : après traitement des k premiers mots, compteurs[mot] vaut le nombre d'occurrences de mot parmi ces k mots.

#Définition inductive : la décomposition formaliséeCopier le lien

Décomposer un problème récursif, c'est écrire une définition inductive. Le cours en donne la forme générale : se donner un sous-ensemble fini $B$ (la base) et un ensemble fini $K$ d'opérations $F$ d'arité $a(F)$ ; l'ensemble $X$ cherché est alors le plus petit ensemble vérifiant

$\text{(B) } B \subseteq X, \qquad \text{(I) } \forall F \in K,\ \forall x_1, \dots, x_{a(F)} \in X,\ F(x_1, \dots, x_{a(F)}) \in X.$

Deux exemples canoniques :

• sur $\mathbb{N}$ : $0 \in P$ et « si $n \in P$ alors $n + 2 \in P$ » définit l'ensemble des entiers pairs — le plus petit ensemble contenant 0 et clos par ajout de 2 ;
• sur l'alphabet $\{(,)\}$ : $\varepsilon \in D$ et « si $x, y \in D$ alors $(x) \in D$ et $xy \in D$ » définit le langage de Dyck, l'ensemble des mots bien parenthésés.

Le mot « plus petit » n'est pas décoratif : sans lui, $\mathbb{N}$ tout entier vérifierait la première définition. Une décomposition correcte est donc une base plus des règles de construction, et rien d'autre.

#L'ambiguïté, ou comment une décomposition correcte compte fauxCopier le lien

Une définition inductive est non ambiguë lorsque chaque élément admet une et une seule construction. Cette propriété n'est pas un luxe théorique : elle décide si la récurrence de comptage qu'on en déduit est juste.

Le cours donne l'exemple des « additions booléennes » sur l'alphabet $\{0,1,+\}$, avec la base $0 \in A$, $1 \in A$ et la règle « si $u, v \in A$ alors $u + v \in A$ ». Cette définition est ambiguë : le mot $0+1+0$ se construit de deux façons, en groupant à gauche ou à droite. La récurrence de comptage qu'on croit lire dans la définition,

$g(n) = \sum_{i} g(2i-1)\,g(n-2i),$

est alors fausse, parce qu'elle compte plusieurs fois les mêmes mots.

La définition corrigée est non ambiguë :

$\text{(B') } 0 \in A,\ 1 \in A; \qquad \text{(I') si } u \in A \text{ alors } u+0 \in A \text{ et } u+1 \in A.$

Elle donne immédiatement $g(0) = 0$, $g(1) = 2$, puis $g(n) = 2\,g(n-2)$ pour $n \gt 1$ : une suite géométrique, $g(n) = 2^{k+1}$ pour $n = 2k+1$. Le même ensemble, deux définitions, deux récurrences — une seule correcte. La leçon est nette : quand une décomposition admet plusieurs lectures d'un même objet, elle est à revoir avant d'être comptée.

#La décomposition détermine la récurrenceCopier le lien

Le lien entre décomposition et coût est direct. Considérons l'ensemble $E$ des mots sur $\{0,1\}$ sans deux 0 consécutifs, défini par $1 \in E$, $0 \in E$, et « si $m \in E$ alors $m1 \in E$ et $m10 \in E$ ». Cette définition est non ambiguë, et elle se lit comme un algorithme de construction : pour obtenir un mot de longueur $n \gt 2$, soit on ajoute un 1 à la fin d'un mot de longueur $n-1$, soit on ajoute 10 à la fin d'un mot de longueur $n-2$. Le nombre $f(n)$ de ces mots vérifie donc

$f(n) = f(n-1) + f(n-2), \qquad f(1) = 2, \quad f(2) = 3,$

c'est-à-dire $2, 3, 5, 8, 13, \dots$ : la suite de Fibonacci. Autrement dit, la décomposition choisie détermine l'équation de récurrence, donc le coût de l'algorithme récursif qui la suit. Changer de décomposition, c'est changer de coût — et c'est exactement le geste de conception que décrit ce chapitre.

#Stratégies de décompositionCopier le lien

#ÉtapesCopier le lien

1. Identifier le problème global : reformuler ce qui est demandé en une phrase avec entrée et sortie.
2. Diviser en sous-problèmes : chercher des étapes qui transforment les données de proche en proche.
3. Définir les interfaces : pour chaque étape, entrée, sortie et garantie.
4. Résoudre les sous-problèmes : implémenter chaque brique indépendamment.
5. Intégrer : assembler les briques et vérifier le comportement global sur des exemples.

#AvantagesCopier le lien

• Simplicité : chaque sous-problème tient dans la tête.
• Réutilisabilité : compter_occurrences sert pour tout comptage, pas seulement les mots.
• Testabilité : chaque brique se teste avec ses propres cas limites (texte vide, mot unique, égalités parfaites).
• Collaboration : plusieurs personnes travaillent sur des briques distinctes dès que les contrats sont fixés.

#Quand s'arrêter ?Copier le lien

Une décomposition est terminée quand chaque brique restante est triviale à écrire et à tester, et que ses entrées et sorties sont simples à décrire. Découper plus finement ajoute de l'indirection sans gain : une fonction incrementer_compteur(compteurs, mot) d'une ligne sous compter_occurrences n'apporterait rien.

#ExercicesCopier le lien

1. Décomposez « vérifier si une phrase est un palindrome » (en ignorant ponctuation, espaces et casse) en trois briques, et écrivez le contrat de chacune.
2. Énoncez l'invariant de boucle de compter_occurrences, puis montrez qu'il tient encore après avoir traité le mot suivant.
3. Remplacez le tri par sélection de l'étape 2 par un appel à sorted avec une clé adaptée, et vérifiez que la sortie est identique sur les deux exemples du chapitre.

#Éléments de correctionCopier le lien

1. Trois briques : normaliser(texte) (entrée : texte quelconque; sortie : uniquement des lettres minuscules; garantie : l'ordre des lettres conservées est inchangé), inverser(s) (entrée : chaîne; sortie : chaîne inversée; garantie : inverser(inverser(s)) == s), est_palindrome(texte) (entrée : texte quelconque; sortie : booléen; garantie : vrai si et seulement si la version normalisée est égale à son inverse). En Python l'inversion se fait par tranche s[::-1].
2. Invariant : après les k premiers mots traités, chaque clé de compteurs est un mot déjà vu et sa valeur est exactement son nombre d'apparitions parmi ces k mots. Le mot k+1 est soit nouveau (on crée la clé à 1, l'invariant passe à k+1 mots), soit déjà présent (on incrémente, la valeur redevient exacte). Dans les deux cas l'invariant est rétabli pour k+1.
3. sorted(compteurs.items(), key=lambda p: (-p[1], p[0])) : la fréquence décroissante s'obtient en niant le compte, l'ordre alphabétique croissant reste la clé secondaire. Sur les deux exemples du chapitre, la sortie est identique à celle du tri par sélection, caractère pour caractère.