T.11 · Compositions faibles, invariants de boucle et traçage de diagrammes de flux

Préparation GRE niveau universitaire. Objectifs locaux dans le périmètre ETS examiné ; il s'agit d'un enseignement original, pas d'un test officiel ni d'un prédicteur de score.

Prérequis : Coefficients binomiaux, compléments et traçage d'affectation.

• Compter des affectations indistinguables avec des contraintes positives ou strictement positives
• Tracer un organigramme dans l'ordre des instructions avec une remise à zéro correcte
• Utiliser un invariant de boucle et une mesure de progression pour justifier un algorithme

composition faible : Une affectation ordonnée d'un total en parties entières non négatives.

invariant de boucle : Une propriété préservée avant et après chaque itération d'une boucle.

Le nombre de solutions entières non négatives de x₁+⋯+x_k=n est C(n+k−1,k−1), pour n≥0 et k≥1. Représentez n étoiles identiques séparées en k boîtes nommées par k−1 barres ; des barres adjacentes et aux extrémités permettent des entrées nulles. Les boîtes sont distinguables, les objets ne le sont pas. Compter des jetons distincts attribuerait chacun indépendamment, donnant k^n avant autres contraintes. Choisissez le modèle selon ce que représentent les objets et les destinataires, et non selon la ressemblance d'un coefficient binomial familier.

Pour des affectations strictement positives x_i≥1, poser z_i=x_i−1 ; le total restant est n−k, donnant C(n−1,k−1) lorsque n≥k. Des bornes inférieures plus générales x_i≥a_i se traitent en soustrayant chaque a_i. Au moins un zéro est le complément de tous les termes positifs : soustraire C(n−1,k−1) du total non négatif. Les cas chevauchants, comme exactement deux boîtes vides, nécessitent un décompte différent ; soustraire chaque cas de boîte vide indépendamment double-compte leurs intersections.

Tracer un organigramme une instruction exécutée à la fois, en enregistrant les variables dans un tableau. Distinguer l'affectation d'un test d'égalité mathématique ; le côté droit d'une affectation utilise la valeur ancienne avant remplacement. Enregistrer quelle branche s'exécute ensuite et quelles variables sont remises à zéro. Un nouveau candidat de boucle extérieure peut remettre à zéro une somme intérieure sans remettre à zéro le candidat lui-même. Pour un processus qui ajoute 1,3,5,… à S depuis zéro, après m additions S=m² et le prochain addende est 2m+1.

Un invariant de boucle est vrai avant et après chaque itération. L'invariant de la somme de carrés vaut initialement à m=0 et est préservé car m²+(2m+1)=(m+1)². Un invariant seul ne prouve pas l'arrêt. Pour tester si un entier N≥0 est un carré en ajoutant des nombres impairs jusqu'à S≥N, S croît sans limite ; équivalentement, m augmente et doit atteindre une borne telle que N. À la sortie, l'égalité signifie carré et le dépassement signifie non-carré. Une valeur imprimée doit être atteinte sur un chemin d'exécution réel ; un motif numérique plausible seul ne constitue pas un traçage.

Distribuer 11 jetons identiques parmi 4 boîtes nommées. Les allocations non négatives comptent C(14,3)=364 ; les allocations strictement positives comptent C(10,3)=120. Par conséquent, 244 allocations ont au moins une boîte vide. Pour le test de somme impaire avec N=10, S progresse 0,1,4,9,16 ; il dépasse et rejette 10. Pour N=9, il sort à S=9 après trois additions. Les prochains addendes sont 1,3,5,7,9 ; les colonnes somme et prochain-addende ne doivent pas être confondues.

Les objets identiques et les objets distincts utilisent des modèles différents. Au moins une boîte vide n'est pas la même chose qu'une seule boîte occupée exactement. Dans un organigramme, préserver l'ordre des mises à jour et réinitialiser uniquement les variables que le chemin exécuté réinitialise réellement.

Compter les solutions non négatives de $a+b+c=8$ avec $a\ge2$. Combien ont aussi $b,c\ge1$ ? Combien de l'ensemble initial ont au moins un de b,c égal à zéro ?

Solution détaillée

Poser $u=a-2$. Alors $u+b+c=6$ a $\binom82=28$ solutions non négatives. Exiger b,c strictement positifs et soustraire un à chacun donne un total de quatre dans trois variables non négatives, compté par $\binom62=15$. Le décompte complémentaire est $28-15=13$. Directement b=0 donne sept, c=0 donne sept, et les deux zéros sont comptés deux fois, donnant $7+7-1=13$.

Tracer cet algorithme pour N=15 et N=16 : initialiser S=0, k=1 ; tant que S<N, exécuter S=S+k, puis k=k+2 ; rapporter si S=N. Énoncer un invariant, et justifier l'arrêt pour l'entier $N\ge0$.

Vérification après tentative

Après m itérations, $S=m^2$ et $k=2m+1$. Les paires de traçage (S,k) sont $(0,1),(1,3),(4,5),(9,7),(16,9)$. Ainsi 15 est rejeté par dépassement et 16 accepté. L'invariant vaut initialement et est préservé car $m^2+(2m+1)=(m+1)^2$. La somme croît sans limite, elle atteint donc finalement N ou la dépasse ; par exemple m=N suffit lorsque N est positif. Pour N=0, la boucle est sautée et l'égalité est vérifiée. Un invariant seul n'établirait pas l'arrêt.