Exercices corrigés de NSI : algorithmique, tris et complexité

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 l'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 mille : 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-1$ 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.