Exercices corrigés de NSI : diviser pour régner, programmation dynamique et graphes

La précondition est que le tableau soit TRIÉ par ordre croissant. Sans elle, la comparaison t[m] < v ne permet plus de conclure dans quelle moitié chercher, et la fonction renvoie un résultat arbitraire sans jamais signaler d'erreur. Si la valeur est absente, la boucle se termine lorsque g dépasse d, et la fonction renvoie $-1$.

Le tableau a 10 éléments, d'indices 0 à 9. Tour 1 : $g = 0$, $d = 9$, $m = 4$, $t[4] = 16 < 23$, donc $g$ devient 5. Tour 2 : $g = 5$, $d = 9$, $m = 7$, $t[7] = 56 > 23$, donc $d$ devient 6. Tour 3 : $g = 5$, $d = 6$, $m = 5$, $t[5] = 23$, trouvé : la fonction renvoie 5. Trois tours.

Pour la valeur 40. Tour 1 : $g = 0$, $d = 9$, $m = 4$, $16 < 40$, $g$ devient 5. Tour 2 : $g = 5$, $d = 9$, $m = 7$, $56 > 40$, $d$ devient 6. Tour 3 : $g = 5$, $d = 6$, $m = 5$, $23 < 40$, $g$ devient 6. Tour 4 : $g = 6$, $d = 6$, $m = 6$, $t[6] = 38 < 40$, $g$ devient 7. La condition $g \le d$ est alors fausse et la boucle s'arrête : la fonction renvoie $-1$. Quatre tours. On retient que l'échec coûte à peine plus cher que le succès, contrairement à la recherche séquentielle où l'échec coûte le maximum.

Chaque tour divise par deux la taille de la zone restante, donc le nombre de tours est au plus $\lfloor \log_{2} n \rfloor + 1$. Pour $n = 1\ 000$ : $\log_{2}(1\ 000) \approx 9{,}97$, donc au plus 10 comparaisons. Pour $n = 10^{6}$ : $\log_{2}(10^{6}) \approx 19{,}93$, donc au plus 20 comparaisons. Une recherche séquentielle en demanderait respectivement 1 000 et 1 000 000. Le rapport vaut donc 100 dans le premier cas et 50 000 dans le second : c'est le propre d'un gain logarithmique, il grandit avec la taille du problème.

Avec une division non entière, m devient un FLOTTANT, par exemple $4{,}5$. L'accès t[4.5] lève un TypeError, car un indice de liste doit être entier. L'erreur est donc immédiate et bruyante, ce qui est une chance. Avec g = m au lieu de m + 1, la boucle peut ne plus PROGRESSER : quand il ne reste qu'un élément, $g = d = m$, la valeur n'est pas trouvée et g reste égal à m, si bien que le tour suivant recalcule exactement le même m. La boucle est infinie, et cette fois rien ne le signale : le programme se fige. Le remède est de vérifier, comme on l'a fait pour un variant, que la quantité $d - g$ décroît STRICTEMENT à chaque tour, ce que garantit le passage à $m + 1$ et $m - 1$.

Au niveau le plus bas, les quatre tableaux d'un élément sont 38, 27, 43 et 3. Première fusion : 38 et 27 donnent 27, 38 ; 43 et 3 donnent 3, 43. Seconde fusion : on fusionne 27, 38 avec 3, 43. On compare 27 et 3, on prend 3 ; on compare 27 et 43, on prend 27 ; on compare 38 et 43, on prend 38 ; il ne reste que 43, on le prend. Le tableau final est 3, 27, 38, 43.

L'algorithme : on place un indice au début de chacun des deux tableaux et l'on crée un tableau résultat vide. Tant que les deux indices sont valides, on compare les deux éléments pointés, on ajoute le plus petit au résultat et on avance l'indice correspondant. Quand l'un des deux tableaux est épuisé, on recopie tout ce qui reste de l'autre. Le coût est de $p + q$ opérations au plus, car chaque élément est examiné et recopié exactement une fois : la fusion est LINÉAIRE, et c'est cette propriété qui fait tout l'intérêt de la méthode.

Chaque niveau divise par deux la taille des tableaux, donc l'arbre compte $\log_{2} n$ niveaux de découpage, plus le niveau des feuilles, soit $\log_{2} n + 1$ niveaux. À chaque niveau, les fusions portent au total sur les $n$ éléments du tableau, quel que soit le nombre de tableaux à ce niveau : deux fusions de $n/2$ éléments coûtent autant qu'une fusion de $n$. Le travail par niveau vaut donc $n$, et le coût total vaut $n \log_{2} n$. C'est le raisonnement le plus important du chapitre : on ne compte pas les appels, on compte le travail PAR NIVEAU et on multiplie par le nombre de niveaux.

La récurrence : $C(n) = 2 C(n/2) + n$, avec $C(1) = 0$, puisqu'un tableau d'un élément est trié sans travail. Vérification avec $C(n) = n \log_{2} n$ : le membre de droite vaut $2 \times (n/2) \log_{2}(n/2) + n = n (\log_{2} n - 1) + n = n \log_{2} n - n + n = n \log_{2} n$, qui est bien le membre de gauche. Et $C(1) = 1 \times \log_{2} 1 = 0$, ce qui vérifie le cas de base.

Le tri fusion est STABLE, à condition que la comparaison de la fusion prenne l'élément du tableau de GAUCHE en cas d'égalité : deux éléments égaux conservent alors leur ordre initial. Il demande une mémoire supplémentaire de l'ordre de $n$, pour le tableau résultat de chaque fusion, ce qui est son principal défaut. Comparaison avec le tri par insertion : celui-ci est également stable, ne demande AUCUNE mémoire supplémentaire, et coûte $n^{2}/4$ en moyenne. Pour $n = 10\ 000$, l'insertion demande environ $2{,}5 \times 10^{7}$ opérations contre $1{,}3 \times 10^{5}$ pour la fusion, soit 188 fois plus. On garde donc l'insertion pour les très petits tableaux, où sa simplicité l'emporte, et la fusion au-delà : les bibliothèques réelles combinent d'ailleurs les deux, en basculant sur l'insertion sous une trentaine d'éléments.

La partition garantit que tous les éléments à gauche du pivot lui sont inférieurs ou égaux, et tous ceux à sa droite supérieurs. Le pivot EST à sa place définitive : dans le tableau trié, il occupera exactement cette position, puisque le nombre d'éléments qui lui sont inférieurs ne changera plus. Les deux zones, en revanche, ne sont PAS triées : sur la figure, la zone gauche vaut 3, 2, 1, 4 et la droite 8, 7, 6, ni l'une ni l'autre n'étant en ordre. C'est précisément ce qui reste à faire, et c'est l'objet des appels récursifs.

L'algorithme : si le tableau a moins de deux éléments, il est trié, on s'arrête ; sinon on partitionne autour d'un pivot, ce qui donne sa position définitive ; puis on trie récursivement la zone de gauche et la zone de droite. Par rapport au tri fusion, le travail est situé AVANT les appels récursifs, dans la partition, alors que le tri fusion travaille APRÈS, dans la fusion. Le tri fusion découpe sans réfléchir et recombine intelligemment ; le tri rapide découpe intelligemment et recombine sans rien faire. Les deux stratégies sont symétriques, et c'est ce qui explique leurs profils d'erreur opposés.

Sur un tableau déjà trié avec le premier élément comme pivot, la partition ne trouve AUCUN élément plus petit : la zone gauche est vide et la zone droite contient les $n - 1$ éléments restants. Le découpage est donc totalement déséquilibré, un contre $n - 1$ à chaque étape, et la profondeur de récursion vaut $n$ au lieu de $\log_{2} n$. Le coût total vaut $(n-1) + (n-2) + \dots + 1 = n(n-1)/2$, c'est-à-dire QUADRATIQUE. Le paradoxe mérite d'être noté : l'entrée la plus favorable pour un humain est la pire pour cet algorithme, et c'est aussi l'entrée la plus fréquente en pratique, puisque les données arrivent souvent déjà classées.

Meilleur cas, partition équilibrée : $C(n) = 2 C(n/2) + n$, d'où $C(n) = n \log_{2} n$, exactement comme le tri fusion. Pire cas, partition dégénérée : $C(n) = C(n-1) + n$, d'où $C(n) = n(n+1)/2$, quadratique. Pour $n = 10\ 000$ : le meilleur cas donne environ $1{,}33 \times 10^{5}$ opérations, le pire environ $5{,}00 \times 10^{7}$. Le rapport vaut environ 376 : c'est la différence entre un tri instantané et un tri qu'on voit passer.

Première stratégie, le PIVOT ALÉATOIRE : on tire au hasard l'indice du pivot. Elle fonctionne parce que le pire cas ne dépend plus des données mais du tirage : aucune entrée particulière ne peut le provoquer systématiquement, et la probabilité d'obtenir plusieurs partitions très déséquilibrées de suite décroît exponentiellement. On démontre que le coût moyen reste $O(n \log n)$ quelle que soit l'entrée. Seconde stratégie, la MÉDIANE DE TROIS : on prend la médiane du premier, du dernier et de l'élément central. Elle fonctionne parce qu'elle traite exactement les cas problématiques réels, tableau trié ou trié à l'envers, pour lesquels elle choisit l'élément central, donc une partition parfaitement équilibrée. Elle ne protège pas contre une entrée construite exprès pour la mettre en échec, ce que le pivot aléatoire, lui, garantit.

Première récurrence, $C(n) = C(n/2) + 1$ : un seul sous-problème de taille moitié et un travail constant. C'est la recherche DICHOTOMIQUE, de coût $\log_{2} n$. Deuxième, $C(n) = 2C(n/2) + n$ : deux sous-problèmes de taille moitié et un travail linéaire. C'est le TRI FUSION, de coût $n \log_{2} n$. Troisième, $C(n) = C(n-1) + n$ : un sous-problème à peine plus petit et un travail linéaire. C'est le tri rapide dans son PIRE CAS, ou le tri par sélection, de coût $n^{2}/2$.

La méthode générale, dite de l'arbre de récursion. On se demande d'abord combien de sous-problèmes chaque appel engendre, appelons ce nombre $a$, et de quelle taille, disons $n/b$. Au niveau $k$, il y a donc $a^{k}$ sous-problèmes de taille $n/b^{k}$. On se demande ensuite quel travail chacun effectue en dehors des appels récursifs, et l'on multiplie par $a^{k}$ pour obtenir le travail du niveau. Enfin, le nombre de niveaux est le nombre de divisions nécessaires pour atteindre la taille 1, soit $\log_{b} n$. Le coût total est la somme des travaux de tous les niveaux, et le résultat dépend de qui l'emporte : si tous les niveaux coûtent autant, on multiplie ; si le travail décroît, le premier niveau domine ; s'il croît, le dernier domine.

Pour $C(n) = 2C(n/2) + 1$ : il y a $2^{k}$ sous-problèmes au niveau $k$, chacun coûtant 1, donc le niveau $k$ coûte $2^{k}$. Le travail CROÎT avec la profondeur, et le dernier niveau, celui des feuilles, en compte $2^{\log_{2} n} = n$. La somme $1 + 2 + 4 + \dots + n$ vaut $2n - 1$ : le coût est LINÉAIRE, et le dernier niveau porte à lui seul la moitié du total. Le profil correspond au parcours complet d'un arbre binaire équilibré, ou au calcul du maximum d'un tableau par découpage en deux.

Pour $C(n) = 4C(n/2) + n$ : au niveau $k$ il y a $4^{k}$ sous-problèmes de taille $n/2^{k}$, chacun coûtant $n/2^{k}$, donc le niveau coûte $4^{k} \times n / 2^{k} = n \times 2^{k}$. Le travail DOUBLE à chaque niveau : c'est donc le DERNIER qui domine. Le nombre de niveaux vaut $\log_{2} n$, donc le dernier niveau coûte $n \times 2^{\log_{2} n} = n \times n = n^{2}$, et la somme géométrique vaut environ $2n^{2}$. Le coût est quadratique. C'est exactement le profil de la multiplication de matrices par blocs naïve, que l'algorithme de Strassen améliore en ramenant les 4 sous-problèmes à 7 sur des blocs deux fois plus petits.

On cherche $n$ tel que $n \log_{2} n > 100 n$, c'est-à-dire $\log_{2} n > 100$, donc $n > 2^{100} \approx 1{,}27 \times 10^{30}$. Autrement dit, JAMAIS en pratique : aucun jeu de données réel n'atteint cette taille. Il faut en conclure qu'un ordre de grandeur ne dit rien sur les tailles utiles s'il est pris seul. La constante multiplicative compte, et un algorithme asymptotiquement meilleur peut être plus lent sur toutes les entrées qu'on rencontrera. On compare donc les ordres de grandeur pour choisir une STRUCTURE d'algorithme, et l'on mesure pour trancher entre deux implémentations de même ordre.

Système 1, 2, 5, 10, somme 38. On prend trois pièces de 10, il reste 8 ; une pièce de 5, il reste 3 ; une pièce de 2, il reste 1 ; une pièce de 1. Total : $3 + 1 + 1 + 1 = 6$ pièces. Ce résultat est bien optimal, et l'on démontre que la méthode gloutonne l'est toujours pour ce système, ce qui explique pourquoi personne ne s'en méfie au quotidien.

Système 1, 3, 4, somme 6. La méthode gloutonne prend une pièce de 4, il reste 2 ; puis deux pièces de 1 : total 3 pièces. La solution optimale est deux pièces de 3, soit 2 pièces. La conclusion est que la méthode gloutonne N'EST PAS optimale en général : elle l'est pour certains systèmes de pièces, dits canoniques, et fausse pour d'autres. Une méthode gloutonne doit donc toujours être justifiée, jamais supposée ; et le contre-exemple, ici, tient en une ligne.

La relation : $m(0) = 0$, car rendre zéro ne demande aucune pièce ; et pour $s > 0$, $m(s) = 1 + \min\{m(s - c)\}$, le minimum étant pris sur toutes les pièces $c$ du système telles que $c \le s$. La lecture est directe : quelle que soit la solution optimale, elle utilise au moins une pièce ; si l'on connaissait laquelle, le reste serait une solution optimale pour $s - c$. Comme on ne le sait pas, on essaie toutes les pièces et l'on garde la meilleure. C'est le principe d'optimalité, qui fonde toute la programmation dynamique.

Système 1, 3, 4. $m(0) = 0$. $m(1) = 1 + m(0) = 1$, seule la pièce de 1 est utilisable. $m(2) = 1 + m(1) = 2$. $m(3) = 1 + \min(m(2), m(0)) = 1 + \min(2, 0) = 1$, en prenant la pièce de 3. $m(4) = 1 + \min(m(3), m(1), m(0)) = 1 + \min(1, 1, 0) = 1$, en prenant la pièce de 4. $m(5) = 1 + \min(m(4), m(2), m(1)) = 1 + \min(1, 2, 1) = 2$. $m(6) = 1 + \min(m(5), m(3), m(2)) = 1 + \min(2, 1, 2) = 2$, en prenant une pièce de 3 puis $m(3) = 1$. Le tableau est donc 0, 1, 2, 1, 1, 2, 2 pour $s$ de 0 à 6, ce qui confirme le résultat de la question b.

L'algorithme : on crée un tableau de taille $s + 1$, on met $m[0]$ à 0 et toutes les autres cases à une valeur très grande ; puis, pour $k$ allant de 1 à $s$, et pour chaque pièce $c$ inférieure ou égale à $k$, on remplace $m[k]$ par $1 + m[k - c]$ si c'est plus petit ; on renvoie $m[s]$. Le coût est de $s \times p$ opérations, puisque chaque case examine chaque pièce : il est donc PSEUDO-POLYNOMIAL, linéaire en la somme et en le nombre de pièces. Il est préférable à la version récursive naïve pour la raison vue avec Fibonacci : celle-ci recalcule les mêmes sous-sommes un nombre exponentiel de fois, alors que le remplissage de bas en haut calcule chaque valeur exactement une fois et la conserve. On peut aussi mémoriser la pièce choisie dans un second tableau, ce qui permet de reconstituer la liste des pièces et pas seulement leur nombre.

La case de la ligne $i$ et de la colonne $c$ contient la valeur maximale que l'on peut emporter en n'ayant le droit d'utiliser que les $i$ premiers objets et en ne dépassant pas la capacité $c$. La ligne 0 est remplie de zéros parce qu'avec zéro objet disponible, on n'emporte rien, quelle que soit la capacité offerte. C'est le cas de base, et il est indispensable : c'est sur lui que s'appuient toutes les autres cases.

Notons $p_{i}$ et $v_{i}$ le poids et la valeur du $i$-ième objet, et $V(i, c)$ la case cherchée. Premier cas, si $p_{i} > c$ : l'objet ne rentre pas, donc $V(i, c) = V(i-1, c)$. Second cas, si $p_{i} \le c$ : on a le choix entre le laisser, ce qui donne $V(i-1, c)$, et le prendre, ce qui donne $v_{i} + V(i-1, c - p_{i})$ ; on garde le maximum des deux. La subtilité est le $c - p_{i}$ : en prenant l'objet, on ne dispose plus que de la capacité restante pour les objets précédents.

Ligne 2, l'objet 2 pesant 3 et valant 4. Colonne 3 : l'objet rentre, on compare $V(1, 3) = 3$ à $4 + V(1, 0) = 4 + 0 = 4$ ; le maximum est 4, ce qui correspond à la table. Colonne 4 : on compare $V(1, 4) = 3$ à $4 + V(1, 1) = 4 + 0 = 4$ ; le maximum est 4, conforme. Colonne 5 : on compare $V(1, 5) = 3$ à $4 + V(1, 2) = 4 + 3 = 7$ ; le maximum est 7, conforme. Cette dernière case est la seule où les deux premiers objets tiennent ensemble, $2 + 3 = 5$, exactement la capacité.

La réponse au problème est la case de la dernière ligne et de la dernière colonne, soit $V(4, 5) = 7$. Remontée. En $(4, 5)$, la valeur 7 est égale à $V(3, 5) = 7$ : l'objet 4 n'a donc pas été pris, on remonte en $(3, 5)$. En $(3, 5)$, la valeur 7 est égale à $V(2, 5) = 7$ : l'objet 3 n'a pas été pris, on remonte en $(2, 5)$. En $(2, 5)$, la valeur 7 diffère de $V(1, 5) = 3$ : l'objet 2 A été pris, on retire son poids et l'on va en $(1, 5 - 3) = (1, 2)$. En $(1, 2)$, la valeur 3 diffère de $V(0, 2) = 0$ : l'objet 1 a été pris, on va en $(0, 0)$ et l'on s'arrête. Le sac contient donc les objets 1 et 2, de poids total $2 + 3 = 5$ et de valeur $3 + 4 = 7$. La règle de la remontée : si la valeur est identique à celle de la ligne du dessus, l'objet n'a pas été pris ; sinon il l'a été.

Le coût en temps est de $n \times C$ opérations, une par case, chacune valant un maximum de deux termes. Le coût en mémoire est également de $n \times C$ cases. On ne dit pas que le problème est résolu en temps polynomial parce que la taille de l'ENTRÉE n'est pas $C$ mais le nombre de chiffres nécessaires pour écrire $C$, soit environ $\log_{2} C$ bits : le coût $nC$ est donc exponentiel en la taille de l'écriture de la capacité. On parle de coût PSEUDO-POLYNOMIAL, et le problème du sac à dos reste effectivement dans la classe des problèmes réputés difficiles. Pour réduire la mémoire, on remarque que le calcul d'une ligne n'utilise que la précédente : il suffit donc de conserver DEUX lignes, ce qui ramène la mémoire à $2C$ cases. On peut même n'en garder qu'une seule en parcourant les capacités par valeurs DÉCROISSANTES, mais on perd alors la possibilité de reconstituer le contenu du sac, qui exige toute la table.

Le squelette : créer une structure et y placer le sommet de départ, en le marquant visité. Tant que la structure n'est pas vide : en retirer un sommet ; le traiter ; puis, pour chacun de ses voisins non encore visités, le marquer visité et l'ajouter à la structure. Le choix de la structure intervient à la troisième ligne, celle du retrait : avec une PILE, on retire le dernier ajouté et l'on obtient un parcours en profondeur ; avec une FILE, on retire le premier ajouté et l'on obtient un parcours en largeur. Tout le reste est identique, mot pour mot.

Il faut marquer AVANT l'ajout parce qu'un même sommet peut être voisin de plusieurs sommets traités successivement. Si l'on ne marque qu'au retrait, il sera ajouté une fois par voisin qui le découvre, et se retrouvera plusieurs fois dans la structure. Les conséquences : la structure enfle jusqu'à contenir de l'ordre du nombre d'arêtes au lieu du nombre de sommets, chaque sommet est traité plusieurs fois, et surtout, pour un parcours en largeur, la distance calculée peut être fausse puisqu'un sommet risque d'être atteint par un chemin plus long après l'avoir été par un plus court. Le programme donne encore un résultat, ce qui rend l'erreur difficile à voir : c'est le coût qui explose d'abord.

Avec des LISTES D'ADJACENCE : chaque sommet est retiré une fois de la structure et chacune de ses arêtes est examinée une fois depuis chaque extrémité, soit un coût de l'ordre de $n + 2m$ pour un graphe non orienté, c'est-à-dire $O(n + m)$, linéaire. Avec une MATRICE D'ADJACENCE : pour chaque sommet retiré, il faut parcourir sa ligne entière pour trouver ses voisins, soit $n$ cases, d'où un coût de $O(n^{2})$ quel que soit le nombre d'arêtes. Sur un graphe creux, la différence est considérable : pour $n = 40\ 000$ et $m = 90\ 000$, on passe d'environ $2{,}2 \times 10^{5}$ opérations à $1{,}6 \times 10^{9}$, soit plus de sept mille fois plus.

Détecter un CYCLE : parcours en profondeur, car un cycle se révèle par une arête qui ramène sur un sommet encore présent dans la descente en cours, information que la pile de récursion fournit naturellement. PLUS COURT CHEMIN en nombre d'arêtes : parcours en largeur, seul à découvrir les sommets par distance croissante. COMPOSANTES CONNEXES : l'un ou l'autre indifféremment, puisqu'on ne s'intéresse qu'à l'ensemble des sommets atteints ; on relance un parcours depuis chaque sommet non visité et l'on compte les relances. Tester si un graphe est BIPARTI : parcours en largeur, car il suffit de colorier chaque sommet selon la parité de sa distance à la source et de vérifier qu'aucune arête ne relie deux sommets de même couleur. Sortir d'un LABYRINTHE sans se soucier de la longueur : parcours en profondeur, qui trouve une sortie plus vite en moyenne et consomme beaucoup moins de mémoire, puisqu'il ne mémorise qu'un chemin au lieu d'un front d'onde entier.

La pile explicite est remplacée par la PILE D'APPELS du langage : chaque appel récursif empile un cadre, exactement comme au chapitre de la récursivité. La limite introduite est la profondeur maximale de récursion, de l'ordre de mille en Python par défaut. Sur un graphe de un million de sommets, un chemin long suffit à la dépasser : un simple chemin de mille sommets provoque une RecursionError, alors que la version itérative avec une pile explicite traiterait un million de sommets sans difficulté, la pile étant alors une structure ordinaire logée dans le tas. C'est la raison pour laquelle tout parcours destiné à de grands graphes s'écrit itérativement, malgré l'élégance de la version récursive.

FAUX. Elle exige que le tableau soit TRIÉ : c'est sur cette hypothèse que repose la conclusion « si l'élément du milieu est plus petit, la valeur cherchée est dans la moitié droite ». Sur un tableau non trié, la fonction renvoie un résultat arbitraire sans signaler d'erreur. Énoncé correct : la recherche dichotomique exige un tableau trié, et sa précondition doit être documentée, faute de quoi elle produit des faux négatifs silencieux.

FAUX en général. Les deux coûtent $n \log_{2} n$ en moyenne, mais le tri rapide dégénère en $n^{2}$ dans son pire cas, notamment sur un tableau déjà trié avec un pivot mal choisi, alors que le tri fusion garantit $n \log_{2} n$ dans TOUS les cas. Énoncé correct : le tri rapide est souvent plus rapide en pratique, grâce à de meilleures constantes et à un usage du cache favorable, mais il n'offre aucune garantie ; le tri fusion en offre une, au prix d'une mémoire supplémentaire linéaire.

FAUX. Avec le système 1, 3, 4 et la somme 6, la méthode gloutonne donne 3 pièces, $4 + 1 + 1$, alors que l'optimum en demande 2, $3 + 3$. Énoncé correct : la méthode gloutonne n'est optimale que pour certains systèmes de pièces ; elle doit être démontrée pour le système considéré, et la programmation dynamique donne l'optimum quel que soit le système.

FAUX, au sens strict. Le coût $nC$ est linéaire en la CAPACITÉ, mais la capacité s'écrit avec environ $\log_{2} C$ chiffres : rapporté à la taille de l'entrée, le coût est exponentiel. Énoncé correct : la programmation dynamique résout le sac à dos en temps PSEUDO-POLYNOMIAL ; le problème reste dans la classe des problèmes réputés difficiles, et l'algorithme devient impraticable dès que la capacité est un grand nombre.

FAUX. On a $n \log_{2} n < 100 n$ tant que $\log_{2} n < 100$, c'est-à-dire pour tout $n$ inférieur à $2^{100}$, soit $1{,}27 \times 10^{30}$ : aucun jeu de données réel n'atteint ce seuil, donc l'algorithme en $n \log_{2} n$ est le plus rapide sur toutes les entrées qu'on rencontrera jamais. Énoncé correct : un ordre de grandeur ignore les constantes, donc il ne permet de comparer deux algorithmes que sur les grandes tailles ; sur les tailles réelles, seules une analyse fine et une mesure tranchent.

L'algorithme. Un, attribuer la distance 0 à la source et l'infini à tous les autres sommets, et placer tous les sommets dans une file de priorité. Deux, tant que la file n'est pas vide, en extraire le sommet de distance provisoire MINIMALE. Trois, sa distance est alors définitive. Quatre, pour chacun de ses voisins encore dans la file, calculer la distance obtenue en passant par lui, et la remplacer si elle est meilleure que la distance provisoire connue : c'est le relâchement. Cinq, recommencer. Le critère de sélection est le point décisif : on choisit toujours le plus proche non encore traité, jamais le voisin le plus proche du dernier traité.

Étape 1 : on sélectionne A, distance définitive 0. Relâchements : B passe à 4 par A, C passe à 2 par A. Étape 2 : le minimum provisoire est C à 2, on le sélectionne, distance définitive 2. Relâchements : B passe de 4 à $2 + 1 = 3$ par C, D passe à $2 + 8 = 10$, E passe à $2 + 10 = 12$. Étape 3 : le minimum est B à 3, sélectionné, définitif. Relâchement : D passe de 10 à $3 + 5 = 8$. Étape 4 : le minimum est D à 8, sélectionné, définitif. Relâchements : E passe de 12 à $8 + 2 = 10$, F passe à $8 + 6 = 14$. Étape 5 : le minimum est E à 10, sélectionné, définitif. Relâchement : F passe de 14 à $10 + 3 = 13$. Étape 6 : F à 13, sélectionné, définitif. Distances finales : A 0, B 3, C 2, D 8, E 10, F 13.

Le plus court chemin de A à F est A, C, B, D, E, F, de coût $2 + 1 + 5 + 2 + 3 = 13$. On le reconstitue en remontant les prédécesseurs enregistrés à chaque relâchement retenu. Le nombre de chemins simples de A à F est bien plus grand : on en compte plusieurs dizaines dans ce petit graphe, et ce nombre croît de façon combinatoire avec la taille. L'algorithme n'en a examiné qu'une petite partie parce qu'il n'énumère aucun chemin : il ne fait que relâcher des arêtes, chacune au plus une fois, et la garantie de la question d lui permet de ne jamais revenir sur une décision.

La propriété : au moment où un sommet est extrait avec la plus petite distance provisoire, cette distance est la distance définitive. Justification : supposons qu'il existe un chemin plus court vers ce sommet. Ce chemin devrait passer par au moins un sommet encore dans la file ; or tous ceux-là ont une distance provisoire supérieure ou égale à celle du sommet extrait, puisque c'est le minimum. Le chemin en question aurait donc déjà une longueur supérieure ou égale avant même d'atteindre sa destination, et il ne pourrait que s'allonger ensuite : il ne peut pas être plus court. C'est là qu'intervient l'hypothèse des POIDS POSITIFS, dans le mot « s'allonger » : si des arêtes pouvaient être négatives, la suite du chemin pourrait au contraire raccourcir le total, et le raisonnement s'effondre.

Prenons trois sommets et trois arcs : A vers B de coût 2, A vers C de coût 1, B vers C de coût $-3$. L'algorithme sélectionne A à 0 et relâche B à 2 et C à 1. Il sélectionne ensuite C, le plus proche, et déclare sa distance 1 DÉFINITIVE. Il sélectionne enfin B à 2 et découvre que le chemin A, B, C coûte $2 - 3 = -1$, moins que 1 : mais C est déjà sorti de la file, et la distance fausse reste. L'erreur tient exactement à l'argument de la question d : la fin du chemin, par l'arc négatif, a raccourci le total au lieu de l'allonger. La méthode à employer en présence de poids négatifs est l'algorithme de Bellman-Ford, qui relâche toutes les arêtes $n - 1$ fois au lieu de figer les sommets un par un, et qui détecte au passage les cycles de poids négatif, cas où la notion même de plus court chemin perd son sens.

C'est un problème de SAC À DOS : une capacité, ici 12 heures, des objets indivisibles avec un poids et une valeur, et une valeur totale à maximiser. La méthode gloutonne qui vient à l'esprit consiste à classer les chapitres par RENDEMENT, c'est-à-dire par points par heure, et à prendre dans cet ordre tant que le temps le permet. Rendements : A vaut 2, B environ $1{,}67$, C vaut 2, D vaut $1{,}8$, E vaut 2, F environ $1{,}83$. Ordre décroissant : A, C et E à 2, puis F à $1{,}83$, puis D à $1{,}8$, puis B à $1{,}67$. On prend A, 2 h et 4 points, il reste 10 h ; C, 4 h et 8 points, il reste 6 h ; E, 1 h et 2 points, il reste 5 h ; F demande 6 h, refusé ; D demande 5 h, accepté, 9 points, il reste 0 h. Total : $2 + 4 + 1 + 5 = 12$ heures et $4 + 8 + 2 + 9 = 23$ points.

Ici la méthode gloutonne tombe juste, mais rien ne le garantissait. Vérifions qu'aucune combinaison ne fait mieux : le total des gains de tous les chapitres vaut 39 points pour 21 heures, et l'on ne peut en retenir que 12. En essayant les regroupements à 12 heures exactement, on trouve A, C, E, D à 23 points ; A, C, F à 23 points également ; B, C, E, A à 19 ; D, F à 20 ; C, F à 19 plus E, soit 21. Le maximum est donc 23, atteint par deux combinaisons différentes. La conclusion est que le glouton était optimal sur CETTE instance, ce qui ne prouve rien : il suffirait de remplacer F par un chapitre de 7 heures rapportant 15 points pour qu'il échoue : le glouton prend ce chapitre, de meilleur rendement, puis A et E, pour 21 points, alors que C, E et ce chapitre en rapportent 25 en 12 heures.

La table a $7$ lignes, de 0 à 6 chapitres considérés, et $13$ colonnes, de 0 à 12 heures. La case de la ligne $i$ et de la colonne $t$ contient le gain maximal atteignable en n'utilisant que les $i$ premiers chapitres et au plus $t$ heures. La récurrence : si le temps du chapitre $i$ dépasse $t$, la case vaut celle du dessus, $V(i-1, t)$ ; sinon elle vaut le maximum entre $V(i-1, t)$, on ne le révise pas, et $g_{i} + V(i-1, t - h_{i})$, on le révise. La ligne 0 est nulle partout, et la réponse se lit en bas à droite.

Il y a $7 \times 13 = 91$ cases, chacune demandant une comparaison de deux termes, soit un coût de l'ordre de 91 opérations, disons quelques centaines en comptant tout. Une recherche exhaustive devrait examiner tous les sous-ensembles de 6 chapitres, soit $2^{6} = 64$ combinaisons, ce qui est ici du même ordre. L'écart n'apparaît qu'en grandissant : avec 40 chapitres et 200 heures, la table compte $41 \times 201 = 8\ 241$ cases alors que la recherche exhaustive devrait examiner $2^{40} \approx 1{,}10 \times 10^{12}$ combinaisons, soit environ 133 millions de fois plus. C'est exactement le passage de l'exponentiel au pseudo-polynomial.

Si les chapitres deviennent divisibles, le problème devient le sac à dos FRACTIONNAIRE, et la méthode GLOUTONNE par rendement décroissant devient optimale. La raison est qu'on n'a plus jamais à refuser un objet faute de place : on en prend la fraction qui tient, si bien que la capacité est toujours remplie exactement, et qu'aucune heure n'est occupée par un chapitre de rendement inférieur à un autre encore disponible. Un échange local ne peut donc qu'aggraver le total, ce qui est la démonstration standard d'optimalité d'un glouton. Solution : on prend A, C et E, de rendement 2, soit $2 + 4 + 1 = 7$ heures et $4 + 8 + 2 = 14$ points ; il reste 5 heures. On prend ensuite F, de rendement $1{,}83$, mais il demande 6 heures : on en prend les cinq sixièmes, ce qui donne $5$ heures et $11 \times 5 / 6 \approx 9{,}17$ points. Le total vaut environ $14 + 9{,}17 = 23{,}17$ points, légèrement supérieur aux 23 du problème indivisible, ce qui est normal : relâcher une contrainte ne peut qu'améliorer l'optimum.

$D(0, j) = j$ : pour passer du mot vide aux $j$ premières lettres du second, il faut exactement $j$ insertions. De même $D(i, 0) = i$ : passer des $i$ premières lettres au mot vide demande $i$ suppressions. Ce sont les cas de base, la première ligne et la première colonne du tableau.

$D(i, j) = \min\big(D(i-1, j) + 1,\ D(i, j-1) + 1,\ D(i-1, j-1) + \delta\big)$, où $\delta$ vaut 0 si la $i$-ième lettre du premier mot est égale à la $j$-ième du second, et 1 sinon. Le premier terme correspond à SUPPRIMER la dernière lettre du premier mot, le deuxième à INSÉRER la dernière lettre du second, le troisième à faire correspondre les deux dernières lettres, gratuitement si elles sont égales, par un REMPLACEMENT sinon. Une solution optimale se termine forcément par l'un de ces trois cas, et l'on garde le meilleur : c'est le principe d'optimalité de l'exercice 5.

Première ligne, mot vide : 0, 1, 2, 3, 4, 5. Ligne C : 1, 0, 1, 2, 3, 4. Ligne H : 2, 1, 0, 1, 2, 3. Ligne A : 3, 2, 1, 1, 2, 3. Ligne T : 4, 3, 2, 2, 2, 3. Par exemple, la case de la ligne A et de la colonne I vaut $\min(0 + 1, 1 + 1, 0 + 1) = 1$ : on remplace A par I après avoir fait correspondre CH et CH.

La distance est la dernière case, $D(4, 5) = 3$. Une suite d'opérations : garder C et H ; remplacer A par I ; remplacer T par E ; insérer N. On obtient CHIEN en trois opérations, et le tableau prouve qu'on ne peut pas faire moins.

Le tableau compte $(m + 1)(n + 1)$ cases, chacune calculée en temps constant : coût $O(m\,n)$. Une fonction récursive directe relancerait trois appels à chaque étape et recalculerait les mêmes sous-problèmes un nombre exponentiel de fois, exactement comme Fibonacci naïf. Pour le correcteur : environ $9 \times 9 = 81$ cases par comparaison, donc $300\ 000 \times 81 \approx 2{,}4 \times 10^{7}$ cases, soit une fraction de seconde. Les vrais correcteurs réduisent encore ce nombre en ne comparant que des mots de longueur voisine.

Chacun des 2 chiffres du premier nombre est multiplié par chacun des 2 chiffres du second : 4 multiplications. Pour $n$ chiffres : $n^{2}$ multiplications, un coût quadratique.

$x_{1} = 4$, $x_{0} = 7$, $y_{1} = 8$, $y_{0} = 3$. $a = 4 \times 8 = 32$, $d = 7 \times 3 = 21$, $e = (4 + 7)(8 + 3) = 11 \times 11 = 121$. Puis $e - a - d = 121 - 32 - 21 = 68$. Le produit vaut $100 \times 32 + 10 \times 68 + 21 = 3\ 200 + 680 + 21 = 3\ 901$, et l'on vérifie que $47 \times 83 = 3\ 901$. Trois multiplications au lieu de quatre.

$x\,y = (10\,x_{1} + x_{0})(10\,y_{1} + y_{0}) = 100\,x_{1} y_{1} + 10\,(x_{1} y_{0} + x_{0} y_{1}) + x_{0} y_{0}$. Or $e = (x_{1} + x_{0})(y_{1} + y_{0}) = x_{1} y_{1} + x_{1} y_{0} + x_{0} y_{1} + x_{0} y_{0} = a + (x_{1} y_{0} + x_{0} y_{1}) + d$, donc $x_{1} y_{0} + x_{0} y_{1} = e - a - d$. En remplaçant, $x\,y = 100\,a + 10\,(e - a - d) + d$. Toute l'astuce est là : le terme du milieu, qui semblait exiger deux produits, s'obtient à partir d'un seul produit supplémentaire et de soustractions, beaucoup moins coûteuses.

Chaque multiplication de nombres de $n$ chiffres se ramène à 3 multiplications de nombres de $n/2$ chiffres : $M(n) = 3\,M(n/2)$, avec $M(1) = 1$. Pour $n = 2^{k}$, on déroule : $M(2^{k}) = 3\,M(2^{k-1}) = \dots = 3^{k}$. Pour $n = 1\ 024 = 2^{10}$ : $M = 3^{10} = 59\ 049$, contre $1\ 024^{2} = 1\ 048\ 576$ pour la méthode de l'école, soit environ 18 fois moins. On a négligé les additions, dont le coût est linéaire à chaque niveau.

$3^{k} = (2^{\log_{2} 3})^{k} = (2^{k})^{\log_{2} 3} = n^{\log_{2} 3}$, avec $\log_{2} 3 \approx 1{,}585$. Le coût passe donc de $n^{2}$ à environ $n^{1{,}585}$, un gain qui grandit sans limite avec $n$. Pour les petits nombres, la méthode récursive paie des additions, des soustractions et des découpages supplémentaires, dont le coût constant dépasse le gain : les bibliothèques basculent donc sur la méthode de l'école en dessous d'un seuil de quelques dizaines de chiffres, comme le tri fusion bascule sur le tri par insertion pour les petits tableaux.

Le graphe a 8 arêtes, une par paire en conflit. Degrés : M 2, P 3, S 3, H 3, A 3, F 2. On vérifie que la somme des degrés, 16, vaut bien deux fois le nombre d'arêtes.

M reçoit 1. P, voisin de M, reçoit 2. S, voisin de M et P, reçoit 3. H, dont seul le voisin S est déjà colorié, reçoit 1. A, voisin de P de couleur 2 et de H de couleur 1, reçoit 3. F, voisin de A de couleur 3 et de H de couleur 1, reçoit 2. On utilise 3 créneaux : M et H ensemble, P et F ensemble, S et A ensemble.

M, P et S sont deux à deux en conflit : ils forment un TRIANGLE, et leurs trois couleurs doivent être différentes. Il faut donc au moins 3 couleurs, et la coloration de la question b en utilise 3 : elle est optimale.

M reçoit 1, P reçoit 2, S reçoit 3. A, dont seul P est colorié parmi ses voisins, reçoit 1. F, voisin de A, reçoit 2. H est voisin de S de couleur 3, de A de couleur 1 et de F de couleur 2 : il reçoit 4. On obtient 4 créneaux. L'algorithme glouton n'est donc PAS optimal : son résultat dépend de l'ordre de traitement des sommets, et un mauvais ordre peut coûter une couleur de plus sur le même graphe.

Quand l'algorithme traite un sommet, celui-ci a au plus $\Delta$ voisins, donc au plus $\Delta$ couleurs sont interdites : parmi les couleurs 1 à $\Delta + 1$, l'une au moins est libre. Ici $\Delta = 3$, donc au plus 4 couleurs, ce qui est exactement ce qu'a produit le mauvais ordre. Déterminer le nombre MINIMAL de couleurs d'un graphe quelconque est un problème difficile : on ne connaît aucun algorithme efficace dans tous les cas, et l'on se contente en pratique d'heuristiques gloutonnes, par exemple traiter d'abord les sommets de plus fort degré.

À chacun des 3 passages d'un étage au suivant, on a 2 choix : $2^{3} = 8$ chemins. Pour $n$ étages, $2^{n-1}$ chemins. Pour 100 étages : $2^{99} \approx 6{,}3 \times 10^{29}$ chemins, bien au-delà de ce qu'aucun ordinateur pourra jamais parcourir.

Depuis 4, on choisit 8 plutôt que 5 ; depuis 8, on choisit 3 plutôt que 1 ; depuis 3, on choisit 7 plutôt que 2. Chemin 4, 8, 3, 7, de somme 22.

Cas de base, la dernière ligne : $S(3, j) = t[3][j]$. Relation : $S(i, j) = t[i][j] + \max\big(S(i+1, j),\ S(i+1, j+1)\big)$. Étage 3 : 6, 2, 7, 8. Étage 2 : $1 + \max(6, 2) = 7$ ; $3 + \max(2, 7) = 10$ ; $9 + \max(7, 8) = 17$. Étage 1 : $8 + \max(7, 10) = 18$ ; $5 + \max(10, 17) = 22$. Étage 0 : $4 + \max(18, 22) = 26$.