Exercices corrigés de NSI : algorithmique, récursivité et complexité (Terminale)

a) recherche(t, 4) renvoie 3, car t[3] vaut 4. recherche(t, 5) renvoie -1 : la valeur est absente. On choisit -1 parce que c'est un indice IMPOSSIBLE en parcours normal, ce qui permet à l'appelant de distinguer sans ambiguïté l'échec du succès. Renvoyer 0 serait une faute grave, puisque 0 est un indice valide.

b) Pour 7 : une seule comparaison, il est en tête. Pour 3 : sept comparaisons, il est en dernière position. Pour une valeur absente : sept comparaisons également, la boucle va jusqu'au bout.

c) Meilleur cas : 1 comparaison, l'élément est en première position. Pire cas : $n$ comparaisons, l'élément est en dernier ou absent. En moyenne, si la valeur est présente et que toutes les positions sont équiprobables, on effectue $\dfrac{1+2+\cdots+n}{n}=\dfrac{n+1}{2}$ comparaisons, soit environ la moitié du tableau. Dans les trois cas le coût est proportionnel à $n$ : la recherche séquentielle est de complexité linéaire, $O(n)$.

d) Il faut supprimer le return anticipé et accumuler les indices, donc parcourir tout le tableau. Le coût devient exactement $n$ comparaisons dans TOUS les cas, y compris le meilleur : on perd la possibilité de s'arrêter tôt. C'est le prix à payer pour une réponse exhaustive.

e) Parce que le tableau n'est pas trié. La dichotomie repose entièrement sur le fait que comparer la valeur cherchée à l'élément du milieu permet d'éliminer une moitié entière ; si le tableau est en désordre, cette comparaison n'apprend rien sur la position des autres éléments. Trier d'abord coûte plus cher qu'une seule recherche séquentielle : cela ne vaut la peine que si l'on prévoit de nombreuses recherches sur le même tableau.

def tous_les_indices(t, x):
    resultat = []
    for i in range(len(t)):
        if t[i] == x:
            resultat.append(i)
    return resultat        # cout : n comparaisons, toujours

a) Tour i = 0 : le minimum du tableau entier est 1, en position 4 ; on l'échange avec 7, ce qui donne [1, 2, 9, 4, 7, 8, 3]. Tour i = 1 : le minimum de la fin est 2, déjà en place, le tableau est inchangé, [1, 2, 9, 4, 7, 8, 3]. Tour i = 2 : le minimum de la fin est 3, en position 6 ; on l'échange avec 9, ce qui donne [1, 2, 3, 4, 7, 8, 9].

b) Le tableau final est [1, 2, 3, 4, 7, 8, 9]. Il se trouve qu'ici il est déjà entièrement trié après trois tours, mais l'algorithme continue quand même : il ne le sait pas.

c) Au tour $i$, la boucle interne parcourt les indices de $i+1$ à $n-1$, soit $n-1-i$ comparaisons. Le total est $\sum_{i=0}^{n-1}(n-1-i)$, c'est-à-dire $(n-1)+(n-2)+\cdots+1+0$, dont la valeur est $\frac{n(n-1)}{2}$. Pour $n=7$ cela fait $\dfrac{7\times 6}{2}=21$ comparaisons.

d) Non, il n'en dépend pas du tout. Les deux boucles sont des for dont les bornes ne dépendent que de $n$, et aucun test ne peut les interrompre. Un tableau déjà trié coûte exactement les mêmes 21 comparaisons qu'un tableau en désordre complet. C'est la signature du tri par sélection : son coût est le même dans le meilleur et dans le pire cas, ce qui le rend prévisible mais l'empêche de profiter d'un tableau presque trié. La complexité est $O(n^{2})$ dans tous les cas.

e) L'algorithme effectue exactement $n$ échanges, un par tour de boucle externe (dont certains sont l'échange d'un élément avec lui-même). C'est très peu : là où le tri par insertion peut effectuer de l'ordre de $n^{2}$ déplacements, le tri par sélection en fait $n$. Si un élément est coûteux à déplacer, par exemple un gros enregistrement, minimiser les écritures devient plus important que minimiser les comparaisons, et le tri par sélection redevient intéressant.

a) Départ [5, 3, 8, 1]. Tour i = 1 : on insère 3, qui remonte devant 5, ce qui donne [3, 5, 8, 1]. Tour i = 2 : on insère 8, qui est déjà plus grand que 5, une seule comparaison et rien ne bouge, [3, 5, 8, 1]. Tour i = 3 : on insère 1, qui traverse 8, 5 et 3, ce qui donne [1, 3, 5, 8].

b) Si le tableau est déjà trié, la condition t[j] > valeur est fausse dès la première comparaison à chaque tour : la boucle while s'arrête immédiatement. Cela fait exactement une comparaison par tour, soit $n-1$ comparaisons au total, et aucun déplacement. Le coût au mieux est donc LINÉAIRE, $O(n)$.

c) Si le tableau est trié à l'envers, chaque nouvel élément doit traverser toute la partie déjà triée : $i$ comparaisons au tour $i$. Le total est $1+2+\cdots+(n-1)=\dfrac{n(n-1)}{2}$, soit $O(n^{2})$, exactement comme le tri par sélection.

d) Coût au mieux : insertion $n-1$, sélection $\frac{n(n-1)}{2}$, l'insertion gagne largement. Coût au pire : les deux valent $\frac{n(n-1)}{2}$, égalité. Déplacements : sélection $n$ échanges seulement, insertion jusqu'à $\frac{n(n-1)}{2}$ décalages, la sélection gagne. Aucun des deux ne domine l'autre : le choix dépend des données et du coût d'un déplacement.

e) Le tri par insertion, sans hésiter. Un tableau presque trié est précisément son meilleur terrain : chaque élément déjà bien placé coûte une seule comparaison, et seuls les 5 intrus provoquent de vrais décalages. Le coût sera de l'ordre de 10 000 opérations. Le tri par sélection, lui, effectuerait ses $\frac{10000\times 9999}{2}\approx 50$ millions de comparaisons, indifférent au fait que le travail soit presque fait. C'est le seul des deux capable de profiter de l'ordre déjà présent.

a) Départ g = 0, d = 6, donc m = 3 et t[3] = 4, inférieur à 8 : on va à droite, g devient 4. Tour 2 : g = 4, d = 6, m = 5 et t[5] = 8 : trouvé, on renvoie 5. Il aura fallu 2 tours.

b) Départ g = 0, d = 6, m = 3, t[3] = 4 < 5 donc g = 4. Tour 2 : g = 4, d = 6, m = 5, t[5] = 8 > 5 donc d = 4. Tour 3 : g = 4, d = 4, m = 4, t[4] = 7 > 5 donc d = 3. Maintenant g = 4 > d = 3, la boucle s'arrête et la fonction renvoie -1. Trois tours ont suffi pour éliminer les 7 cases.

c) Chaque tour divise par deux le nombre de cases restantes : 7, puis 3, puis 1, puis 0. Il faut donc au plus 3 tours pour 7 éléments. En général le nombre de tours est de l'ordre de $\log_{2}n$, plus précisément $\lfloor\log_{2}n\rfloor+1$ au pire.

d) Pour $n=1\ 000$ : la recherche séquentielle fait jusqu'à 1 000 comparaisons, la dichotomie environ 10, puisque $2^{10}=1024$. Pour $n=1\ 000\ 000$ : séquentielle 1 000 000, dichotomie environ 20, puisque $2^{20}\approx 10^{6}$. Multiplier la taille des données par mille n'ajoute que dix tours à la dichotomie. C'est la différence entre un coût linéaire et un coût logarithmique, et c'est ce qui rend la dichotomie irremplaçable sur de grandes données.

e) Le variant est $d-g+1$, le nombre de cases encore candidates. C'est un entier, il reste positif tant que la boucle tourne (la condition d'entrée est $g\leq d$), et chaque tour le fait décroître strictement : dans les deux branches on déplace $g$ ou $d$ strictement au-delà de $m$, ce qui retire au moins la case du milieu. Un entier positif qui décroît strictement ne peut pas décroître indéfiniment : la boucle se termine.

a) Pour factorielle : cas de base $n\leq 1$, qui renvoie 1 sans nouvel appel ; cas récursif $n\times$ factorielle$(n-1)$. Pour fibonacci : cas de base $n<2$, qui renvoie $n$ ; cas récursif, la somme des deux appels précédents. Sans cas de base, la récursion ne s'arrêterait jamais et provoquerait une RecursionError.

b) La descente empile factorielle(5), qui appelle factorielle(4), puis (3), (2) et enfin (1). Ce dernier renvoie 1 sans rappel. La remontée donne alors $2\times 1=2$, puis $3\times 2=6$, puis $4\times 6=24$, puis $5\times 24=120$. Le résultat est 120. Rien n'est calculé pendant la descente : tout le travail se fait à la remontée.

c) Avec if n == 1, l'appel factorielle(0) ne rencontrerait jamais son cas de base : il appellerait factorielle(-1), puis (-2), et ainsi de suite indéfiniment, jusqu'à l'erreur de dépassement de pile. C'est pourquoi on écrit $n\leq 1$ et non $n=1$ : le cas de base doit couvrir TOUTES les entrées qui ne relancent pas la récursion. Mathématiquement $0!=1$, la version correcte donne donc aussi la bonne valeur.

d) fibonacci(0) à fibonacci(9) valent 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. Et fibonacci(10) vaut 55.

e) La version itérative accumule le produit dans une variable.

def factorielle_iterative(n):
    resultat = 1
    for i in range(2, n + 1):
        resultat = resultat * i
    return resultat

# factorielle_iterative(5) vaut 120, comme la version recursive

a) A : $O(n)$, une boucle simple. B : $O(n^{2})$, deux boucles imbriquées de $n$ tours. C : $O(n^{2})$ également. D : $O(\log n)$, la variable est divisée par deux à chaque tour. E : $O(n\log n)$, une boucle de $n$ tours contenant chacune une boucle logarithmique.

b) La boucle interne fait 0 tour pour $i=0$, 1 tour pour $i=1$, et ainsi de suite, soit au total $0+1+\cdots+(n-1)=\dfrac{n(n-1)}{2}$ tours. C'est bien environ la moitié des $n^{2}$ tours du fragment B. Mais la notation $O$ ignore les facteurs constants : $\dfrac{n^{2}-n}{2}$ et $n^{2}$ ont le même ordre de grandeur, car leur rapport tend vers la constante $\frac{1}{2}$. Ce qu'on retient, c'est la façon dont le coût GRANDIT quand $n$ double, et dans les deux cas il est multiplié par quatre.

c) Du moins au plus coûteux : $O(1)$, $O(\log n)$, $O(n)$, $O(n\log n)$, $O(n^{2})$, $O(2^{n})$.

d) En $O(n^{2})$, multiplier $n$ par 10 multiplie le temps par $10^{2}=100$. Pour 10 000 éléments : environ 100 secondes, soit près de 2 minutes. Pour 100 000 : environ 10 000 secondes, soit près de 3 heures. C'est le passage à l'échelle qui tue les algorithmes quadratiques, pas leur vitesse sur les petits jeux de données.

e) Le second est plus lent au départ mais grandit beaucoup moins vite : il finit forcément par gagner, et le point de bascule se situe pour un $n$ assez petit. Vérification à $n=100\ 000$ : le quadratique met environ 10 000 s. Pour le second, le coût passe de $1000\times\log_{2}1000\approx 10^{4}$ à $100\ 000\times\log_{2}100\ 000\approx 1{,}66\times 10^{6}$, soit environ 167 fois plus, donc $2\times 167\approx 333$ secondes. Il est alors exactement trente fois plus rapide que le premier. Un mauvais algorithme rapide perd toujours contre un bon algorithme lent, dès que les données grossissent.

a) L'invariant est : au début de chaque tour, s contient la somme des i premiers éléments du tableau, c'est-à-dire $s=\sum_{k=0}^{i-1}t[k]$, avec $0\leq i\leq \text{len}(t)$.

b) Initialisation : avant la boucle, $i=0$ et $s=0$ ; la somme des 0 premiers éléments est bien la somme vide, qui vaut 0. L'invariant est vrai. Conservation : supposons-le vrai en début de tour, donc $s=\sum_{k=0}^{i-1}t[k]$. Le tour ajoute $t[i]$ à s puis incrémente i. En fin de tour, s vaut $\sum_{k=0}^{i}t[k]$ et l'indice vaut $i+1$ : c'est exactement l'invariant écrit pour la nouvelle valeur de i. Terminaison de la preuve : à la sortie, la condition de boucle est fausse, donc $i=\text{len}(t)$, et l'invariant donne $s=\sum_{k=0}^{\text{len}(t)-1}t[k]$, la somme de tous les éléments. C'est bien ce qu'on voulait démontrer.

c) Le variant est $\text{len}(t)-i$. C'est un entier, positif tant que la boucle tourne puisque la condition est $i<\text{len}(t)$, et chaque tour le diminue exactement de 1 car i augmente de 1 et len(t) ne change pas. Une suite d'entiers positifs strictement décroissante est finie : la boucle se termine.

d) En incrémentant i avant de l'utiliser, on saute t[0] et on tente de lire t[len(t)], qui n'existe pas : le programme lève une IndexError. L'erreur se manifeste dès le premier tableau non vide, y compris un tableau à un seul élément : i passe à 1 puis on lit t[1] hors bornes. C'est le décalage d'indice classique, et c'est précisément l'invariant qui permet de le repérer sans exécuter le code, car il n'est plus préservé par le tour.

e) L'invariant est : au début de chaque tour, imax est l'indice du plus grand élément parmi les i premiers, et c'est le plus petit indice où ce maximum est atteint. Initialisation avec imax = 0 et i = 1 : le maximum du seul élément t[0] est bien atteint en 0. Conservation : le tour remplace imax seulement si t[i] est STRICTEMENT plus grand, ce qui préserve à la fois la maximalité et le choix de la première occurrence. À la sortie, i vaut len(t) et l'invariant porte alors sur le tableau entier.

a) L'appel fibonacci(5) déclenche fibonacci(4) et fibonacci(3) ; fibonacci(4) déclenche à son tour fibonacci(3) et fibonacci(2), et ainsi de suite. En développant tout l'arbre, fibonacci(2) est appelé 3 fois. Le point important est qu'il est recalculé intégralement à chaque fois, sans que rien ne soit conservé d'un appel à l'autre.

b) Il faut 177 appels de fonction pour produire le nombre 55. Autrement dit, on effectue plus de trois fois plus de travail que la valeur du résultat lui-même. Presque tout ce travail est du recalcul pur : dans cet arbre, fibonacci(3) est évalué 21 fois, toujours pour obtenir 2.

c) Chaque appel non terminal en engendre deux, donc le nombre d'appels double approximativement quand $n$ augmente de 1. On obtient un arbre binaire de profondeur $n$, dont le nombre de nœuds croît comme $2^{n}$ (plus précisément comme $\varphi^{n}$, avec $\varphi$ le nombre d'or). Passer de $n=40$ à $n=50$ multiplie le temps par environ $\varphi^{10} \approx 123$ : c'est ce qui rend cette version inutilisable, alors même qu'elle est parfaitement correcte. Correction et efficacité sont deux propriétés indépendantes.

d) Il suffit de garder les deux derniers termes et d'avancer. La boucle fait $n$ tours et chaque tour coûte une addition : la complexité est LINÉAIRE, $O(n)$. On passe de $2^{n}$ à $n$, ce qui rend fibonacci(1000) instantané.

e) La mémoïsation consiste à ranger chaque résultat dans un dictionnaire dès qu'il est calculé, et à consulter ce dictionnaire avant de relancer un appel. Chaque valeur fibonacci(k) n'est alors calculée qu'une seule fois, pour $k$ de 0 à $n$ : la complexité tombe à $O(n)$ également, au prix d'un espace mémoire $O(n)$. C'est la même idée que la version itérative, obtenue sans renoncer à l'écriture récursive.

def fibonacci_iteratif(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a                      # O(n)

def fibonacci_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]                # O(n) aussi

a) On prend d'abord la plus grosse pièce possible : 100 (reste 78), puis 50 (reste 28), puis 20 (reste 8), puis 5 (reste 3), puis 2 (reste 1), puis 1 (reste 0). La liste rendue est [100, 50, 20, 5, 2, 1], soit 6 pièces. Aucune pièce de 200 n'est prise puisque 200 dépasse 178.

b) Parce que le principe même du glouton est de prendre le meilleur choix local, et « meilleur » signifie ici « la plus grosse pièce qui rentre ». Si la liste n'était pas triée, la boucle épuiserait d'abord des petites pièces et rendrait une solution médiocre, par exemple 178 pièces de 1 centime en commençant par 1. Le tri fait partie de l'algorithme, pas de la préparation des données.

c) Avec [4, 3, 1] et la somme 6 : le glouton prend 4 (reste 2), puis ne peut pas prendre 3, prend 1 (reste 1), puis 1 (reste 0). Il rend [4, 1, 1], soit 3 pièces.

d) La solution optimale est [3, 3], soit 2 pièces seulement. L'algorithme glouton n'est donc PAS optimal en général : en prenant la pièce de 4 il s'est interdit la bonne combinaison, et comme il ne revient jamais en arrière, il ne peut plus se rattraper. Il se trouve que le système européen est, lui, canonique, ce qui rend le glouton optimal dans ce cas particulier, mais c'est une propriété du système de pièces, pas de l'algorithme. Pour un système quelconque, il faut la programmation dynamique.

e) Sa rapidité et sa simplicité. Le glouton ne teste qu'une seule combinaison, celle qu'il construit, là où une recherche exhaustive en examinerait un nombre exponentiel. Quand la solution optimale n'est pas indispensable, ou quand on sait démontrer que le glouton est optimal sur le problème traité, c'est de loin la meilleure approche. Beaucoup d'algorithmes classiques sont gloutons et prouvés optimaux, comme celui de Dijkstra pour les plus courts chemins.

a) Recherche dichotomique, puisque le tableau est trié : environ $\log_{2}(500\ 000)\approx 19$ comparaisons. C'est immédiat, même sur un demi-million d'entrées. Faire une recherche séquentielle ici serait gaspiller l'information précieuse que constitue le tri.

b) Pour UNE seule recherche, la recherche séquentielle gagne largement. Elle coûte au pire $n=500\ 000$ comparaisons. Trier d'abord coûterait de l'ordre de $n\log_{2}n\approx 500\ 000\times 19\approx 9{,}5$ millions d'opérations, soit près de vingt fois plus, avant même d'avoir commencé à chercher. On ne trie jamais pour une seule requête.

c) Oui, la réponse s'inverse. Il faut comparer $k$ recherches séquentielles, soit $k\times n$, au coût du tri suivi de $k$ dichotomies, soit $n\log_{2}n+k\log_{2}n$. Avec $k=10\ 000$ : à gauche $10\ 000\times 500\ 000=5$ milliards d'opérations ; à droite environ $9{,}5$ millions pour le tri plus $10\ 000\times 19\approx 190\ 000$, soit moins de 10 millions. Le tri est amorti dès quelques dizaines de recherches : c'est tout l'intérêt d'organiser les données une fois pour les interroger souvent.

d) Non, trier les 500 000 ouvrages pour n'en garder que 10 est un gaspillage. Il suffit de parcourir le catalogue une seule fois en maintenant les 10 meilleurs vus jusqu'ici : pour chaque ouvrage, on le compare au plus faible des 10 retenus et on l'insère si nécessaire. Le coût est $O(n\times 10)$, donc linéaire en $n$, contre $O(n\log n)$ pour un tri complet. Sur un demi-million d'entrées, cela fait environ $10n=5$ millions d'opérations contre $n\log_{2}n\approx 9{,}5$ millions, soit deux fois moins dans le pire des cas. En pratique l'écart est bien plus grand : la quasi-totalité des ouvrages est éliminée dès la première comparaison avec le dixième meilleur, si bien que le coût réel avoisine $n$ et non $10n$.

e) Méthode naïve : comparer chaque titre à tous les autres, soit $\dfrac{n(n-1)}{2}$ comparaisons, environ $1{,}25\times 10^{11}$ ici, ce qui est hors de portée. Méthode efficace : trier les titres, puis parcourir la liste triée une fois en comparant chaque titre à son voisin immédiat, car deux titres identiques sont forcément côte à côte après tri. Le coût tombe à $O(n\log n)$ pour le tri plus $O(n)$ pour le parcours. Encore mieux, on peut utiliser un dictionnaire ou un ensemble et détecter un doublon en un seul parcours, en $O(n)$ en moyenne.

a) Le motif apparaît en position 0, abra au début, et en position 7, abra à la fin : la fonction renvoie [0, 7]. Les deux occurrences ne se chevauchent pas ici, mais l'algorithme trouverait aussi des occurrences qui se chevauchent, puisqu'il teste chaque position indépendamment des autres.

b) $n = 11$ et $m = 4$, donc i prend les valeurs 0 à 7 : 8 positions. Au-delà de $n - m$, le motif dépasserait la fin du texte et la lecture de texte[i + j] sortirait des bornes ; la borne $n - m + 1$ du range garantit que la dernière position testée place la dernière lettre du motif sur la dernière lettre du texte.

c) Position 0 : abra est trouvé, 4 comparaisons. Position 1 : b contre a, 1 comparaison, de même aux positions 2, 4 et 6, où les lettres r, c et d diffèrent de a. Position 3 : a correspond, puis c contre b échoue, 2 comparaisons ; même chose en position 5 avec d. Position 7 : abra est trouvé, 4 comparaisons. Total : $4 + 1 + 1 + 2 + 1 + 2 + 1 + 4 = 16$ comparaisons.

d) À chaque position, les neuf a du motif correspondent et seul le b échoue : 10 comparaisons par position, pour $1\ 000 - 10 + 1 = 991$ positions, soit $9\ 910$ comparaisons. Dans le pire cas, l'algorithme fait $m$ comparaisons à chacune des $n - m + 1$ positions : sa complexité est $O(n \times m)$.

e) Pour 'xyz', il y a $11 - 3 + 1 = 9$ positions, et la première comparaison échoue à chacune : 9 comparaisons. Dans un texte ordinaire, la première lettre du motif diffère presque toujours de la lettre du texte, si bien que l'on fait environ une comparaison par position et un coût proche de $n$. Le pire cas exige un texte et un motif très répétitifs, fréquents dans un génome, rares dans un roman. L'exercice 14 montre comment faire mieux que $n$ comparaisons.

a) Distance à A : $\sqrt{3{,}4^{2} + 1{,}4^{2}} = \sqrt{13{,}52} \approx 3{,}68$. À B : $\sqrt{3{,}3^{2} + 1{,}3^{2}} = \sqrt{12{,}58} \approx 3{,}55$. À C : $\sqrt{0{,}3^{2} + 0{,}1^{2}} = \sqrt{0{,}10} \approx 0{,}32$. À D : $\sqrt{0{,}8^{2} + 0{,}4^{2}} = \sqrt{0{,}80} \approx 0{,}89$. À E : $\sqrt{0{,}7^{2} + 0{,}5^{2}} = \sqrt{0{,}74} \approx 0{,}86$. À F : $\sqrt{0{,}2^{2} + 0{,}2^{2}} = \sqrt{0{,}08} \approx 0{,}28$.

b) Ordre croissant : F $0{,}28$, C $0{,}32$, E $0{,}86$, D $0{,}89$, B $3{,}55$, A $3{,}68$. Pour $k = 1$, le plus proche voisin est F : prédiction virginica. Pour $k = 3$, les voisins sont F, C et E, soit deux virginica contre une versicolor : prédiction virginica.

c) Pour $k = 5$, les voisins sont F, C, E, D et B : deux virginica, deux versicolor et une setosa. Il y a ÉGALITÉ, et l'algorithme ne sait pas conclure. Choisir $k$ impair ne suffit pas quand il y a plus de deux classes. Remèdes : pondérer chaque voisin par l'inverse de sa distance, ce qui donne $\frac{1}{0{,}28} + \frac{1}{0{,}86} \approx 4{,}7$ pour virginica contre $\frac{1}{0{,}32} + \frac{1}{0{,}89} \approx 4{,}3$ pour versicolor, donc virginica ; ou départager par le plus proche des voisins à égalité ; ou revenir à une valeur de $k$ plus petite.

d) Il faut calculer les $n$ distances, puis extraire les $k$ plus petites : $O(n)$ pour les distances, et $O(n \log n)$ si l'on trie tout, $O(n\,k)$ si l'on maintient seulement les $k$ meilleures. L'algorithme n'a pas de phase d'apprentissage parce qu'il ne construit aucun modèle : il conserve la table entière et fait tout le travail au moment de la prédiction. Le prix est double : la table doit rester en mémoire, et chaque prédiction coûte un parcours complet, ce qui devient lourd pour des millions d'exemples et des milliers de prédictions.

e) Les écarts de masse, de l'ordre de dizaines ou de centaines, écraseraient les écarts de pétales, de l'ordre du centimètre : la distance ne dépendrait presque plus que de la masse, et la forme des pétales serait ignorée, sans que rien ne le signale. Le remède est de NORMALISER chaque caractéristique avant de calculer les distances, par exemple en la ramenant entre 0 et 1 à l'aide de son minimum et de son maximum dans la table, afin que chacune pèse d'un poids comparable.

a) Les appels successifs portent sur $n = 10$, pair, puis 5, impair, puis 4, pair, puis 2, pair, puis 1, impair, puis 0, cas de base. En remontant : $2^{0} = 1$, $2^{1} = 2 \times 1 = 2$, $2^{2} = 2 \times 2 = 4$, $2^{4} = 4 \times 4 = 16$, $2^{5} = 2 \times 16 = 32$, $2^{10} = 32 \times 32 = 1\ 024$.

b) Chaque appel autre que le cas de base effectue exactement une multiplication, y * y ou x * puissance(x, n - 1) : pour $n$ valant 10, 5, 4, 2 et 1, cela fait 5 multiplications. La méthode naïve en ferait 10. Le gain paraît modeste ici ; il devient spectaculaire dès que $n$ grandit.

c) Suite : 1000, 500, 250, 125, 124, 62, 31, 30, 15, 14, 7, 6, 3, 2, 1, 0, soit 15 multiplications au lieu de $1\ 000$. Chaque appel pair divise $n$ par deux ; un appel impair le rend pair et est donc suivi d'une division. Il y a donc au plus deux appels par division par deux, et le nombre de divisions nécessaires pour ramener $n$ à 1 vaut $\lfloor \log_{2} n \rfloor$ : au total au plus $2 \log_{2} n$ multiplications, soit $O(\log n)$. Pour $n = 1\ 000$, $\lfloor \log_{2} 1\ 000 \rfloor = 9$ divisions et 6 appels impairs donnent bien 15.

d) Le résultat est correct, mais le calcul de $x^{n/2}$ est fait DEUX fois au lieu d'une. Pour $n = 8$, la version rapide fait les appels 8, 4, 2, 1, soit 4 multiplications. La version modifiée vérifie $T(8) = 2\,T(4) + 1$, $T(4) = 2\,T(2) + 1$, $T(2) = 2\,T(1) + 1$ et $T(1) = 1$, d'où $T(2) = 3$, $T(4) = 7$ et $T(8) = 15$ : plus que les 8 multiplications de la méthode naïve. Dédoubler l'appel annule tout le bénéfice : c'est le même piège que la récursivité naïve de Fibonacci, où l'on recalcule ce qu'on vient de calculer.

e) Le nombre de chiffres d'un entier $N \geq 1$ vaut $\lfloor \log_{10} N \rfloor + 1$. Ici $\log_{10} 2^{1000} = 1\ 000 \times 0{,}30103 = 301{,}03$, donc $2^{1000}$ possède 302 chiffres. L'exponentiation rapide le calcule en 15 multiplications d'entiers, là où la méthode naïve en demanderait mille.

a) Pour chaque lettre du motif sauf la dernière, le décalage est la distance entre sa dernière occurrence et la fin du motif : c vaut $4 - 1 - 0 = 3$, h vaut $4 - 1 - 1 = 2$, a vaut $4 - 1 - 2 = 1$. Une lettre absente de la table, t compris, donne un décalage égal à la longueur du motif, 4 : aucune position intermédiaire ne peut aligner cette lettre avec une lettre égale du motif.

b) i = 0 : la lettre alignée est c, qui diffère de t, 1 comparaison, décalage 3. i = 3 : t correspond, puis a, h et c, 4 comparaisons, occurrence trouvée, décalage de t, 4. i = 7 : r, 1 comparaison, décalage 4. i = 11 : u, 1 comparaison, décalage 4. i = 15 : e, 1 comparaison, décalage 4. i = 19 : a, 1 comparaison, décalage 1. i = 20 : t, a, h, c correspondent, 4 comparaisons, occurrence trouvée, décalage 4. i = 24 : i, 1 comparaison, décalage 4, et $28 > 29 - 4$ arrête la boucle.

c) Positions renvoyées : 3 et 20. Total : $1 + 4 + 1 + 1 + 1 + 1 + 4 + 1 = 14$ comparaisons, contre 32 pour l'algorithme naïf, qui teste les 26 positions. Horspool n'a examiné que 8 positions : la plupart des lettres du texte ne figurent pas dans le motif et font sauter 4 cases d'un coup. Plus le motif est long, plus les sauts sont grands, ce qui fait de cet algorithme, paradoxalement, un algorithme d'autant plus rapide que le motif cherché est long.

d) Le décalage doit amener sous la lettre lue du texte une occurrence PLUS À GAUCHE de cette lettre dans le motif. Si la dernière lettre était incluse, elle recevrait le décalage 0 et l'algorithme ne progresserait plus. Pour 'toit', la table donne t : 3, o : 2, i : 1 ; le t final est exclu, et le décalage de t vient du t initial, 3. C'est exactement ce qu'il faut : après un échec sur une fenêtre terminée par t, on aligne le t initial du motif sous ce t du texte.

e) À chaque position, la lettre alignée avec la fin du motif ne figure pas dans le motif : une comparaison, puis un décalage de 10. On teste donc environ $\frac{1\ 000\ 000}{10} = 100\ 000$ positions, avec $100\ 000$ comparaisons. L'algorithme naïf teste les $999\ 991$ positions, avec au moins une comparaison chacune, soit environ un million : dix fois plus. Le gain croît avec la longueur du motif.

a) L'activité qui commence le plus tôt est C, de 0 h à 6 h. Parmi celles qui commencent à 6 h ou après, la première est G, de 6 h à 10 h. Parmi celles qui commencent à 10 h ou après, il ne reste que K, de 12 h à 16 h. On obtient C, G et K : 3 activités. Commencer tôt ne dit rien de la place qu'on occupe : C bloque à elle seule six heures.

b) L'activité qui se termine le plus tôt est A, de 1 h à 4 h. Les activités compatibles qui se terminent ensuite le plus tôt sont D, de 5 h à 7 h, puis H, de 8 h à 11 h, puis K, de 12 h à 16 h ; toutes les autres chevauchent une activité déjà choisie. On obtient A, D, H et K : 4 activités, soit une de plus que la stratégie 1.

c) La plus courte est celle de 4 h à 6 h, qui dure 2 heures. Une fois choisie, elle chevauche les deux autres, qui sont éliminées : la stratégie 3 accepte 1 activité. Or les activités de 0 h à 5 h et de 5 h à 10 h sont compatibles entre elles : l'optimum vaut 2. Un seul contre-exemple suffit à réfuter une stratégie gloutonne.

d) Soit une solution optimale, rangée par heures de fin, et $a$ l'activité qui se termine le plus tôt de toutes. La première activité $o$ de la solution optimale se termine au plus tôt comme $a$, par définition de $a$. Remplacer $o$ par $a$ ne crée aucun conflit : $a$ se termine avant ou en même temps que $o$, donc avant le début de la deuxième activité de la solution. On obtient une solution de même taille, donc encore optimale, qui commence par le choix glouton. En répétant l'argument sur les activités restantes, on montre que toute la solution gloutonne est optimale.

e) Il faut trier les activités par heure de fin, en $O(n \log n)$, puis les parcourir une fois en ne retenant que celles qui commencent après la fin de la dernière choisie, en $O(n)$ : coût total $O(n \log n)$. Une recherche exhaustive examinerait les $2^{50} \approx 1{,}1 \times 10^{15}$ sous-ensembles de 50 activités. À un milliard de sous-ensembles par seconde, il faudrait près de deux semaines, là où le glouton répond instantanément.