Faire le point : Spécialité NSI, Terminale

b) Pour $B$, chaque doublement multiplie par $2$ : $12{,}3 \times 2 = 24{,}6$ ms à $16\,000$, puis $24{,}6 \times 2 \times 2 = 98{,}4$ ms à $64\,000$, deux doublements plus loin. Pour $C$, chaque doublement multiplie par $4$ : $1\,554 \times 4 = 6\,216$ ms à $16\,000$, puis $6\,216 \times 16 = 99\,456$ ms à $64\,000$, soit environ $99{,}5$ secondes. On passe donc de moins de deux secondes à plus d'une minute et demie pour huit fois plus de données. Le piège est de multiplier par $8$ au lieu de $4 \times 4$ : trois doublements se traduisent par $2^{3}$ pour un linéaire et par $4^{3}$ pour un quadratique, jamais par la même valeur.

L'exercice complet, avec toutes ses questions →

c) Oui, la table d'origine EST modifiée. list(table) construit bien une nouvelle liste, mais ses cases contiennent les MÊMES dictionnaires que l'original : on a copié le contenant, pas les contenus. copie[0] et table[0] désignent donc le même dictionnaire, et lui ajouter ou changer une clé se voit des deux côtés. C'est précisément le piège : le programmeur croit avoir protégé ses données parce qu'il a écrit une copie, alors qu'il n'a dupliqué qu'un niveau.

L'exercice complet, avec toutes ses questions →

b) Comme entier naturel, $11010011$ vaut $128 + 64 + 16 + 2 + 1 = 211$. Comme entier relatif en complément à deux, le bit de poids fort valant 1, le nombre est négatif : sa valeur est $211 - 256 = -45$. On peut aussi le retrouver en inversant tous les bits, ce qui donne 00101100 soit 44, puis en ajoutant 1 pour obtenir 45, et en mettant le signe moins. La même suite de huit bits vaut donc 211 ou moins 45 selon la seule convention retenue, et rien dans la mémoire ne dit laquelle est la bonne.

L'exercice complet, avec toutes ses questions →

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.

L'exercice complet, avec toutes ses questions →

c) La fonction taille : si l'arbre est vide, renvoyer 0 ; sinon renvoyer $1 + \text{taille}(\text{gauche}) + \text{taille}(\text{droit})$. Le cas de base est l'arbre vide, qui vaut 0. La fonction hauteur : si l'arbre est vide, renvoyer $-1$ ; sinon renvoyer $1 + \max(\text{hauteur}(\text{gauche}), \text{hauteur}(\text{droit}))$. Le cas de base est ici encore l'arbre vide, mais il vaut $-1$ et non 0, afin qu'un arbre réduit à sa racine ait la hauteur 0. Choisir 0 pour l'arbre vide donnerait la hauteur en nombre de NIVEAUX au lieu d'arêtes : les deux conventions existent, il faut annoncer celle qu'on emploie et s'y tenir, c'est la source d'erreur numéro un du chapitre.

L'exercice complet, avec toutes ses questions →

b) Dans la conception de droite, on modifie UNE ligne de la table des élèves, et c'est fini : les trois notes suivent automatiquement, puisqu'elles ne stockent que l'identifiant. Dans celle de gauche, il faut modifier les trois lignes concernées. Le risque propre à la première conception est l'ANOMALIE DE MISE À JOUR : si l'une des trois lignes est oubliée, la base affirme simultanément que Dupont est en 1G3 et en 1G4. Elle contient alors une contradiction, et aucune requête ne pourra plus trancher, puisque les deux réponses y sont écrites noir sur blanc.

L'exercice complet, avec toutes ses questions →

a) Le diagramme donne, dans l'ordre : A de 0 à 2, B de 2 à 4, C de 4 à 6, A de 6 à 8, B de 8 à 9, C de 9 à 11, A de 11 à 12. Le processus B s'achève à l'instant 9, C à l'instant 11 et A à l'instant 12. Cohérence : la somme des durées de calcul vaut $5 + 3 + 4 = 12$, et le processeur n'est jamais inoccupé, donc le dernier processus doit bien s'achever à l'instant 12.

L'exercice complet, avec toutes ses questions →

a) L'invariant : à l'entrée de chaque tour de boucle, la variable imax contient l'indice d'un plus grand élément parmi les éléments d'indices 0 à $i - 1$, c'est-à-dire parmi la zone déjà examinée de la figure, et c'est l'indice du premier d'entre eux en cas d'égalité. Formulé autrement, imax est la réponse correcte pour le préfixe examiné jusqu'ici. Le point de méthode : un invariant utile parle du travail DÉJÀ FAIT, jamais de ce qui reste, et c'est ce qui le rend vrai avant même le premier tour.

L'exercice complet, avec toutes ses questions →

a) 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$.

L'exercice complet, avec toutes ses questions →

b) Fenêtre $i = 0$ : elle couvre les indices $0$ à $3$, et la lettre alignée avec la fin du motif est texte[3], un espace. On compare l'espace au e du motif : échec, $1$ comparaison. L'espace n'est pas une clé, on avance de $4$. Fenêtre $i = 4$ : indices $4$ à $7$, la lettre lue est texte[7] = s, différente de e : $1$ comparaison, et d[s] = 1, donc $i = 5$. Remarquez que le décalage se lit sur la lettre du TEXTE, s, et non sur la lettre du motif qui lui fait face : c'est l'erreur qui fausse le plus de traces.

L'exercice complet, avec toutes ses questions →