Pr. EL HADIQ Zouhair
Pour le rendu de monnaie, le sac à dos et Huffman : spécification, correction (invariant), terminaison (variant) et surtout la question propre aux gloutons — l'optimalité, qui se prouve par argument d'échange ou se réfute par un contre-exemple.
Comme pour tout algorithme :
\[ \text{Correction totale} \;=\; \text{Correction partielle} \;+\; \text{Terminaison} \]
Mais un glouton résout un problème d'optimisation : il ne suffit pas qu'il produise une solution valide (correction), il faut savoir si cette solution est optimale. C'est une propriété supplémentaire : un glouton peut être parfaitement correct (il termine et renvoie une solution réalisable) tout en n'étant pas optimal.
| Question | Outil |
|---|---|
| Correction (la sortie est-elle réalisable ?) | Invariant de boucle : initialisation + conservation + sortie |
| Terminaison (l'algorithme s'arrête-t-il ?) | Variant \(V \in \mathbb{N}\) strictement décroissant (Floyd) |
| Optimalité (la sortie est-elle la meilleure ?) | Propriété du choix glouton + sous-structure → preuve par échange ; sinon contre-exemple |
def rendu_monnaie(systeme, S): # systeme trie par ordre decroissant
rendu = []
for piece in systeme:
while S >= piece:
rendu.append(piece)
S = S - piece
return rendu
Précondition : systeme est une liste d'entiers strictement positifs, triée par ordre décroissant, contenant la pièce \(1\) ; \(S \in \mathbb{N}\). Postcondition : rendu est une liste de pièces de systeme dont la somme vaut \(S\).
Notons \(S_0\) la valeur initiale. À tout instant : \( \big(\sum \text{rendu}\big) + S = S_0 \) et \(S \ge 0\).
Initialisation : rendu est vide et \(S = S_0\), l'égalité tient. Conservation : chaque tour ajoute une pièce de valeur \(p\) à rendu et retranche \(p\) à \(S\) ; la somme \(\sum\text{rendu} + S\) est inchangée, et la garde \(S \ge p\) assure \(S \ge 0\) après. Sortie : à la fin, comme la pièce \(1\) divise tout entier et est présente, \(S\) a pu être ramené à \(0\), donc \(\sum \text{rendu} = S_0\).
On prend \(V = S\) (la somme restante). À chaque tour de la boucle while, \(S\) décroît de \(p \ge 1\), donc \(V\) est un entier naturel strictement décroissant : la boucle interne s'arrête. La boucle externe parcourt une liste finie. Par le théorème de Floyd (l'ordre \((\mathbb{N},<)\) est bien fondé), l'algorithme termine.
Pour le système de l'euro \((1,2,5,10,20,50,\dots)\), on démontre (argument d'échange) que le glouton renvoie le nombre minimal de pièces. Idée : si une solution optimale n'utilisait pas la plus grande pièce \(p \le S\), on pourrait remplacer un sous-ensemble de petites pièces sommant à \(p\) par cette pièce unique, sans augmenter le total — donc il existe une solution optimale qui fait le choix glouton.
Système \((4,3,1)\), \(S = 6\). Le glouton : \(6 \to 4\) (reste \(2\)) \(\to 1 \to 1\), soit \(\{4,1,1\}\), 3 pièces. L'optimum est \(\{3,3\}\), 2 pièces. Le choix glouton « prendre \(4\) » détruit l'optimalité : la propriété du choix glouton est fausse ici.
L'algorithme reste correct (il rend bien \(S\)) et termine dans tous les cas ; seule l'optimalité dépend du système. Pour un système quelconque, l'optimum se calcule par programmation dynamique : \( \text{opt}(m) = 1 + \min_{p \le m} \text{opt}(m-p) \), avec \(\text{opt}(0)=0\).
def sac_fractionnaire(objets, C): # objets : (valeur, poids)
objets = sorted(objets, key=lambda o: o[0]/o[1], reverse=True)
valeur = 0.0
for v, p in objets:
if C >= p:
valeur += v; C -= p
else:
valeur += v * (C / p); C = 0; break
return valeur
Pré : objets de poids \(p_i > 0\) et valeur \(v_i \ge 0\), capacité \(C \ge 0\). Post : valeur est la valeur maximale d'un remplissage de poids total \(\le C\), les objets étant divisibles.
La boucle for parcourt une liste finie d'objets ; le variant est le nombre d'objets non encore examinés, entier décroissant. L'instruction break ne fait qu'arrêter plus tôt. L'algorithme termine.
Trions par densité \(d_i = v_i/p_i\) décroissante. Soit une solution optimale \(x\) (proportion de chaque objet). Supposons qu'elle prenne une fraction d'un objet \(j\) moins rentable alors qu'un objet \(i\) plus rentable (\(d_i > d_j\)) n'est pas pris à fond. En transférant un poids \(\varepsilon\) de \(j\) vers \(i\), la valeur varie de \(\varepsilon(d_i - d_j) > 0\) : contradiction avec l'optimalité. Donc une solution optimale remplit d'abord les objets les plus denses — exactement le choix glouton. La sous-structure optimale (après avoir pris l'objet le plus dense, on résout le même problème sur la capacité restante) conclut.
\(A(60,10)\), \(B(100,20)\), \(C(120,30)\), capacité \(C = 50\). Densités \(6 > 5 > 4\). Le glouton prend \(A\) puis \(B\) : valeur \(160\), il reste \(20 < 30\), \(C\) refusé. Or \(B+C\) (poids \(50\)) vaut \(220 > 160\). L'indivisibilité détruit la propriété du choix glouton : prendre le plus dense « gaspille » de la capacité. Le sac 0/1 relève de la programmation dynamique.
import heapq
def huffman(freq):
tas = [[f, c, None, None] for c, f in freq.items()]
heapq.heapify(tas)
while len(tas) > 1:
g = heapq.heappop(tas) # plus petite frequence
d = heapq.heappop(tas) # deuxieme plus petite
heapq.heappush(tas, [g[0] + d[0], None, g, d])
return tas[0]
Pré : \(n \ge 1\) caractères de fréquences \(f_i > 0\). Post : un arbre binaire de code préfixe minimisant la longueur moyenne \( \sum_i f_i\,\ell_i \), où \(\ell_i\) est la profondeur (longueur du code) du caractère \(i\).
Variant \(V = |\text{tas}|\). Chaque tour retire deux arbres et en réinsère un : \(V\) décroît de \(1\) à chaque itération. Partant de \(n\), la boucle s'exécute \(n-1\) fois puis s'arrête (\(V=1\)). Avec un tas binaire, chaque opération coûte \(O(\log n)\), d'où une complexité \(O(n \log n)\).
Lemme. Soient \(x, y\) les deux caractères de plus faibles fréquences. Il existe un arbre optimal où \(x\) et \(y\) sont des feuilles sœurs de profondeur maximale. Preuve : dans un arbre optimal, échanger un caractère de profondeur maximale avec \(x\) (puis \(y\)) ne peut pas augmenter \(\sum f_i \ell_i\), car on déplace les plus petites fréquences vers le bas. On obtient un arbre optimal réalisant le choix glouton.
Sous-structure optimale. Fusionner \(x\) et \(y\) en un méta-caractère de fréquence \(f_x+f_y\) donne un problème à \(n-1\) caractères. Un arbre optimal du problème réduit, où l'on rouvre la feuille fusionnée en \((x,y)\), est optimal pour le problème initial. Par récurrence sur \(n\), Huffman est optimal.
| Algorithme | Termine ? | Correct ? | Optimal ? | Outil de preuve d'optimalité |
|---|---|---|---|---|
| Rendu (système euro) | Oui | Oui | Oui | Argument d'échange |
| Rendu (système 1,3,4) | Oui | Oui | Non | Contre-exemple \(6=3+3\) |
| Sac fractionnaire | Oui | Oui | Oui | Échange sur les densités |
| Sac à dos 0/1 | Oui | Oui | Non | Contre-exemple \(B+C\) |
| Huffman | Oui | Oui | Oui | Lemme d'échange + récurrence |
Pour un glouton : (1) prouver terminaison (variant) et correction (invariant : la solution construite reste réalisable) ; (2) pour l'optimalité, démontrer la propriété du choix glouton par échange — « il existe une solution optimale contenant le premier choix glouton » — puis conclure par sous-structure optimale et récurrence. Si la propriété du choix glouton est fausse, exhiber un contre-exemple suffit, et l'on bascule sur la programmation dynamique.
CPGE MP/PSI — Informatique · Analyse : algorithmes gloutons · Conforme au programme officiel 2023