Exercices corrigés de NSI : les structures de données

a) Les quatre opérations. Créer une pile vide, qui n'attend rien et renvoie la structure. Tester si elle est vide, qui n'attend rien et renvoie un booléen. Empiler, qui attend une valeur et ne renvoie rien mais modifie la pile. Dépiler, qui n'attend rien, retire l'élément du sommet et le renvoie. On y ajoute souvent une cinquième opération, lire le sommet sans le retirer. LIFO signifie « dernier entré, premier sorti » : l'élément rendu par un dépilement est toujours le plus récemment empilé.

b) Après avoir empilé 3, 7 puis 2, la pile contient 3, 7, 2 du fond vers le sommet. Le premier dépilement renvoie 2, le second renvoie 7 : la pile ne contient plus que 3. On empile ensuite 5, donc la pile contient 3, 5 du fond vers le sommet. Les valeurs renvoyées sont donc 2 puis 7, dans cet ordre, ce qui est bien l'inverse de leur ordre d'arrivée.

c) Sur une pile vide, l'appel à pop sur une liste vide lève une exception IndexError, dont le message parle d'une liste alors que l'utilisateur croyait manipuler une pile : la fuite d'implémentation est déjà un défaut en soi. Deux conceptions possibles. La première est DÉFENSIVE : depiler teste est_vide et lève une exception explicite, du genre « dépilement d'une pile vide », ce qui interrompt le programme au bon endroit avec le bon message. La seconde est CONTRACTUELLE : on documente que dépiler une pile vide est interdit, et c'est à l'appelant de tester avant. La première est plus sûre, la seconde est plus rapide ; le choix se justifie, il ne se devine pas.

d) Non, le programme utilisateur n'a pas à être modifié, à condition qu'il n'ait jamais accédé à l'attribut contenu. C'est le principe d'ENCAPSULATION, ou de séparation entre interface et implémentation : l'utilisateur programme contre le contrat, jamais contre la réalisation. Ce principe est ce qui permet d'optimiser une structure sans réécrire les programmes qui s'en servent, et c'est aussi pourquoi accéder directement à contenu depuis l'extérieur est une faute, même quand le langage l'autorise.

e) Avec pop(0), on retire l'élément d'INDICE 0, c'est-à-dire le plus anciennement empilé : l'objet obtenu se comporte comme une file, pas comme une pile. Il ne respecte donc plus le contrat. Le second problème, plus insidieux, est le COÛT : retirer le premier élément d'une liste Python oblige à décaler tous les autres, donc l'opération est linéaire en la taille au lieu d'être constante. Une boucle qui vide la structure passe ainsi d'un coût linéaire à un coût quadratique, sans qu'aucun test fonctionnel ne le signale, puisque le résultat, lui, serait correct si l'on voulait une file.

a) Jeton 3 : la pile contient 3. Jeton 4 : elle contient 3, 4. Jeton + : on dépile 4 puis 3, on empile $3 + 4 = 7$, la pile contient 7. Jeton 5 : elle contient 7, 5. Jeton * : on dépile 5 puis 7, on empile $7 \times 5 = 35$. Le résultat renvoyé est 35.

b) Jeton 7 : pile 7. Jeton 2 : pile 7, 2. Jeton 3 : pile 7, 2, 3. Jeton * : on dépile 3 puis 2, on empile $2 \times 3 = 6$, pile 7, 6. Jeton - : on dépile 6 dans b puis 7 dans a, on empile $a - b = 7 - 6 = 1$. Le résultat est 1. L'ordre des dépilements est décisif : le premier dépilé est le SECOND opérande, puisque la pile rend les éléments dans l'ordre inverse de leur arrivée. Écrire a = p.depiler() avant b donnerait $6 - 7 = -1$. Pour l'addition et la multiplication, qui sont commutatives, l'erreur passerait inaperçue, ce qui la rend d'autant plus dangereuse : elle ne se révèle qu'à la première soustraction.

c) $(2 + 3) \times (8 - 5)$ s'écrit 2 3 + 8 5 - *, et $2 + 3 \times 8 - 5$ s'écrit 2 3 8 * + 5 -. On constate qu'AUCUNE parenthèse n'apparaît : la notation postfixée n'en a pas besoin, parce que la position des opérateurs suffit à fixer l'ordre des opérations. C'est précisément ce qui la rend commode pour une machine, et c'est la forme qu'un compilateur produit avant de générer le code.

d) L'algorithme. On parcourt le texte caractère par caractère. Si le caractère est une ouvrante, on l'empile. Si c'est une fermante, on regarde la pile : si elle est vide, on rejette ; sinon on dépile et on vérifie que l'ouvrante dépilée correspond au type de la fermante, faute de quoi on rejette. À la fin du parcours, si la pile n'est pas vide, on rejette. Les trois cas de rejet sont donc : une fermante alors que la pile est vide ; une fermante d'un type différent de la dernière ouvrante ; et une pile non vide à la fin.

e) Premier texte, ( [ ] { } ) : on empile la parenthèse, on empile le crochet, la fermante crochet correspond et dépile, on empile l'accolade, la fermante accolade correspond et dépile, la fermante parenthèse correspond et dépile, la pile est vide à la fin. Le texte est ACCEPTÉ. Deuxième texte, ( [ ) ] : on empile la parenthèse et le crochet, puis arrive une fermante parenthèse alors que le sommet est un crochet : les types diffèrent, on REJETTE au deuxième cas. Troisième texte, ( ( : on empile deux parenthèses et le parcours s'achève avec une pile non vide, on REJETTE au troisième cas. Les trois cas de rejet sont donc chacun illustré une fois, sauf le premier, qu'illustrerait un texte commençant par une fermante.

a) L'interface d'une file : créer une file vide ; tester si elle est vide ; enfiler une valeur, qui l'ajoute en queue ; défiler, qui retire et renvoie la valeur de tête. FIFO signifie « premier entré, premier sorti ». Deux situations qui exigent une file : la gestion d'une file d'attente de travaux d'impression, où l'équité impose de servir dans l'ordre d'arrivée ; et le parcours en largeur d'un graphe, où l'on doit épuiser les sommets à distance $k$ avant ceux à distance $k+1$, ce qu'une pile ferait exactement à l'envers.

b) Après les trois enfilements : entrée contient 1, 2, 3 du fond au sommet, sortie est vide. Premier défilement : sortie étant vide, on transvase, donc sortie contient 3, 2, 1 du fond au sommet ; on dépile et on renvoie 1. Deuxième défilement : sortie n'est pas vide, on dépile directement et on renvoie 2 ; sortie contient encore 3. On enfile 4 : entrée contient 4, sortie contient 3. Troisième défilement : sortie n'est pas vide, on renvoie 3 ; sortie est maintenant vide. Quatrième défilement : sortie étant vide, on transvase le 4, puis on le renvoie. Les valeurs renvoyées sont donc 1, 2, 3, 4, dans l'ordre d'arrivée.

c) Parce qu'une pile inverse l'ordre, et qu'inverser deux fois rétablit l'ordre initial. Les éléments entrent dans la pile d'entrée dans leur ordre d'arrivée, donc le plus ancien se retrouve au FOND. Le transvasement les dépile du plus récent au plus ancien et les empile dans la pile de sortie : le plus ancien arrive donc en dernier, c'est-à-dire au SOMMET de la pile de sortie. Un dépilement de la pile de sortie rend alors bien le plus ancien, ce qui est exactement le comportement d'une file.

d) Chaque élément est empilé au plus une fois dans la pile d'entrée, dépilé au plus une fois de celle-ci, empilé au plus une fois dans la pile de sortie et dépilé au plus une fois de celle-ci : il subit donc au plus 4 opérations élémentaires au cours de sa vie entière. Pour $n$ éléments, le coût total est donc au plus $4n$ opérations, c'est-à-dire proportionnel à $n$. Le coût MOYEN par opération est donc constant, bien qu'un défilement isolé puisse coûter beaucoup. Ce type de raisonnement s'appelle une analyse AMORTIE : on ne majore pas chaque opération séparément, on majore le coût total d'une suite d'opérations.

e) Le résultat reste correct : les éléments sortent toujours dans l'ordre d'arrivée, puisque la pile de sortie est maintenue en permanence dans le bon ordre. En revanche le coût explose. Chaque enfilement doit transvaser toute la pile de sortie vers l'entrée, ajouter l'élément, puis tout retransvaser : il coûte donc un temps proportionnel au nombre d'éléments présents. Sur $n$ enfilements, le coût total devient de l'ordre de $1 + 2 + \dots + n = n(n+1)/2$, c'est-à-dire QUADRATIQUE. Pour $n = 10\ 000$, on passe de $40\ 000$ opérations à environ $50\ 000\ 000$, soit mille deux cent cinquante fois plus. Le résultat correct masque donc une régression majeure, que seuls un raisonnement ou une mesure révèlent.

a) Le troisième maillon porte la valeur 9. Pour y accéder, le programme part de la tête, lit le maillon 7 et suit son pointeur, lit le maillon 3 et suit son pointeur, et arrive au maillon 9 : il a dû traverser tous les maillons précédents. Le coût d'un accès au $k$-ième maillon est donc proportionnel à $k$, et dans le pire des cas proportionnel à la longueur de la liste. C'est la différence fondamentale avec un tableau, où l'adresse du $k$-ième élément se calcule par une addition et où l'accès coûte donc un temps constant.

b) La fonction : on initialise un compteur à 0 et une variable courante à tete ; tant que courante n'est pas None, on incrémente le compteur et on remplace courante par courante.suivant ; on renvoie le compteur. Le coût est LINÉAIRE en la longueur, puisque chaque maillon est visité exactement une fois. Contrairement à un tableau, une liste chaînée ne connaît pas sa longueur : il faut la compter, ou bien la maintenir dans un attribut mis à jour à chaque insertion et suppression.

c) Trois opérations : créer un nouveau maillon de valeur 4 ; faire pointer son champ suivant sur l'ancienne tête ; faire pointer la variable tete sur le nouveau maillon. Le coût est CONSTANT, indépendant de la longueur de la liste, et aucun autre maillon n'est touché. Dans un tableau, insérer en tête oblige à décaler tous les éléments d'une case, donc le coût est linéaire. C'est le principal argument en faveur de la liste chaînée.

d) Il faut faire pointer le champ suivant du maillon PRÉCÉDENT, celui de valeur 3, sur le maillon de valeur 5. L'information à conserver pendant le parcours est donc une référence sur le maillon précédent, parce qu'un maillon ne donne accès qu'à son successeur, jamais à son prédécesseur : arrivé sur le maillon 9, il est trop tard, on ne peut plus revenir en arrière. On parcourt donc avec deux variables, précédent et courant, avancées ensemble. Une variante consiste à s'arrêter un cran plus tôt, en testant courant.suivant.valeur, ce qui évite la seconde variable au prix d'un cas particulier sur le premier maillon.

e) Accès au $k$-ième élément : tableau constant, liste linéaire ; avantage au tableau. Insertion en tête : tableau linéaire, liste constante ; avantage à la liste. Insertion en fin : tableau constant en moyenne si de la place est réservée, liste linéaire s'il faut parcourir, constante si l'on maintient un pointeur de queue ; avantage au tableau, sauf conception particulière. Occupation mémoire : le tableau stocke les valeurs seules et de façon contiguë, la liste ajoute un pointeur par maillon, souvent 8 octets, et disperse les maillons en mémoire, ce qui dégrade fortement le cache ; avantage au tableau. Critère de choix : on prend une liste chaînée quand les insertions et suppressions en tête ou en milieu dominent et que l'accès indexé est rare ; dans tous les autres cas, et notamment dès que la performance du cache compte, le tableau gagne.

a) La racine est 8. La taille, c'est-à-dire le nombre de noeuds, vaut 9. La hauteur, comptée en nombre d'arêtes du plus long chemin depuis la racine, vaut 3 : le chemin 8, 3, 6, 4 en compte trois. Les feuilles, noeuds sans aucun fils, sont 1, 4, 7 et 13, soit quatre feuilles. Les noeuds internes sont 8, 3, 6, 10 et 14, soit cinq noeuds. On vérifie : $4 + 5 = 9$, ce qui redonne bien la taille.

b) Le noeud 8 a pour fils gauche 3 et pour fils droit 10. Le noeud 3 a pour fils gauche 1 et pour fils droit 6. Le noeud 6 a pour fils gauche 4 et pour fils droit 7. Le noeud 10 n'a pas de fils gauche et a pour fils droit 14. Le noeud 14 a pour fils gauche 13 et pas de fils droit. Les noeuds n'ayant qu'un seul fils sont donc 10 et 14. Il faut noter que ces deux noeuds ne sont PAS interchangeables avec un noeud dont le fils unique serait de l'autre côté : dans un arbre binaire, un fils gauche unique et un fils droit unique donnent deux arbres différents.

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.

d) La hauteur minimale est $\lfloor \log_{2} n \rfloor$, atteinte quand l'arbre est le plus équilibré possible, chaque niveau étant rempli avant le suivant. La hauteur maximale est $n - 1$, atteinte quand l'arbre dégénère en peigne, chaque noeud n'ayant qu'un seul fils. Pour $n = 9$ : minimum $\lfloor \log_{2} 9 \rfloor = 3$, maximum 8. L'arbre de la figure a la hauteur 3 : il est donc optimalement équilibré. Pour $n = 10^{6}$ : minimum $\lfloor \log_{2} 10^{6} \rfloor = 19$, maximum $999\ 999$. L'écart entre 19 et un million est exactement ce qui rend l'équilibrage indispensable.

e) Un arbre complet de hauteur $h$ compte $2^{k}$ noeuds au niveau $k$, pour $k$ allant de 0 à $h$, donc une taille de $1 + 2 + 4 + \dots + 2^{h} = 2^{h+1} - 1$. Pour $h = 10$ : $2^{11} - 1 = 2\ 047$ noeuds. Pour $h = 20$ : $2^{21} - 1 = 2\ 097\ 151$ noeuds. Doubler la hauteur ne double pas la taille, il l'élève à peu près au carré, à un facteur 2 près : c'est la même croissance exponentielle que celle des pages web du chapitre de SNT, et c'est elle qui explique qu'un arbre équilibré de vingt niveaux suffise à ranger deux millions de valeurs.

a) Parcours PRÉFIXE, racine puis gauche puis droit : 8, 3, 1, 6, 4, 7, 10, 14, 13. Parcours INFIXE, gauche puis racine puis droit : 1, 3, 4, 6, 7, 8, 10, 13, 14. Parcours SUFFIXE, gauche puis droit puis racine : 1, 4, 7, 6, 3, 13, 14, 10, 8. Les trois listes contiennent exactement les neuf mêmes valeurs, seul l'ordre change.

b) Les trois fonctions ont la même structure : si l'arbre est vide, on ne fait rien ; sinon on appelle la fonction sur le sous-arbre gauche, on traite la racine, et on appelle la fonction sur le sous-arbre droit. Elles ne diffèrent que par la POSITION de la ligne qui traite la racine : avant les deux appels pour le préfixe, entre les deux pour l'infixe, après les deux pour le suffixe. C'est la seule différence, et c'est déjà tout le sujet.

c) Le parcours infixe donne 1, 3, 4, 6, 7, 8, 10, 13, 14, c'est-à-dire les valeurs TRIÉES par ordre croissant. Cela révèle que l'arbre est un arbre binaire de RECHERCHE : pour tout noeud, toutes les valeurs de son sous-arbre gauche lui sont inférieures et toutes celles de son sous-arbre droit lui sont supérieures. La réciproque est vraie : un arbre binaire dont le parcours infixe est croissant est un arbre binaire de recherche, et c'est d'ailleurs le test le plus simple pour le vérifier.

d) Parcours en LARGEUR, niveau par niveau et de gauche à droite : 8, 3, 10, 1, 6, 14, 4, 7, 13. Il ne s'écrit pas récursivement parce que la récursion descend naturellement dans un sous-arbre jusqu'au bout avant de passer au suivant, alors que le parcours en largeur exige de traiter tous les noeuds d'un niveau AVANT de descendre. Il faut donc mémoriser explicitement les noeuds en attente, dans l'ordre où ils ont été découverts : c'est exactement le contrat d'une FILE. L'algorithme : enfiler la racine ; tant que la file n'est pas vide, défiler un noeud, le traiter, puis enfiler ses fils non vides. Remplacer la file par une pile transforme d'ailleurs ce parcours en un parcours en profondeur, ce qui montre bien que c'est la structure, et non l'algorithme, qui décide de l'ordre.

e) Le parcours PRÉFIXE sert à recopier ou sérialiser un arbre : la racine étant écrite en premier, la reconstruction peut commencer dès le premier élément lu. Le parcours INFIXE sert à obtenir les valeurs triées d'un arbre binaire de recherche, ou à réécrire une expression arithmétique en notation usuelle. Le parcours SUFFIXE sert à libérer un arbre ou à évaluer une expression : on a besoin des résultats des deux sous-arbres avant de pouvoir traiter la racine, et c'est exactement la notation postfixée de l'exercice 2. Le parcours en LARGEUR sert à trouver le plus court chemin en nombre d'arêtes, puisqu'il découvre les noeuds par distance croissante à la racine, et à afficher un arbre niveau par niveau.

a) La propriété : pour tout noeud, toutes les valeurs du sous-arbre GAUCHE lui sont strictement inférieures, et toutes celles du sous-arbre DROIT lui sont strictement supérieures. Attention, la condition porte sur tout le sous-arbre, pas seulement sur les fils immédiats. Vérification à gauche : chaque noeud n'a qu'un fils droit portant une valeur plus grande, la propriété est satisfaite. À droite : la racine 3 a un sous-arbre gauche contenant 1 et 2, tous deux inférieurs à 3, et un sous-arbre droit contenant 4 et 5, tous deux supérieurs ; les sous-arbres vérifient à leur tour la propriété. Les deux arbres sont donc bien des arbres binaires de recherche.

b) L'arbre de gauche s'obtient en insérant 1, 2, 3, 4, 5 dans cet ordre : chaque valeur étant plus grande que toutes les précédentes, elle descend systématiquement à droite. L'arbre de droite s'obtient par exemple en insérant 3, 2, 4, 1, 5, ou 3, 4, 2, 5, 1. Il faut en conclure que la FORME d'un arbre binaire de recherche ne dépend pas de son contenu mais de l'ORDRE D'INSERTION, et que le pire ordre possible est justement l'ordre trié, qui est aussi le plus fréquent quand on charge un fichier déjà classé. Un arbre construit à partir de données triées dégénère toujours en peigne.

c) Algorithme : partir de la racine ; comparer la valeur cherchée à celle du noeud ; si elles sont égales, c'est trouvé ; si la valeur cherchée est plus petite, descendre à gauche ; sinon descendre à droite ; si l'on atteint un sous-arbre vide, la valeur est absente. Pour chercher 5 dans l'arbre de gauche : on compare à 1, 2, 3, 4 puis 5, soit 5 comparaisons. Dans celui de droite : on compare à 3, puis 4, puis 5, soit 3 comparaisons. Pour une valeur absente, par exemple 6, on descend jusqu'au bout : 5 comparaisons à gauche, 3 à droite ; le coût d'un échec est celui du chemin le plus long emprunté, donc au pire la hauteur plus un.

d) Sur l'arbre de l'exercice 5, chercher 7 : on compare à 8, la valeur est plus petite donc on va à gauche vers 3 ; 7 est plus grand que 3 donc on va à droite vers 6 ; 7 est plus grand que 6 donc on va à droite vers 7, trouvé. Cela fait 4 comparaisons. Chercher 11 : on compare à 8, plus grand donc à droite vers 10 ; plus grand que 10 donc à droite vers 14 ; plus petit que 14 donc à gauche vers 13 ; plus petit que 13 donc à gauche, sous-arbre vide, absent. Cela fait 4 comparaisons. Le lien général : le nombre de comparaisons est au plus la hauteur plus 1, puisque chaque comparaison fait descendre d'exactement un niveau.

e) Pour un million de valeurs, un arbre équilibré a une hauteur d'environ $\lfloor \log_{2} 10^{6} \rfloor = 19$, donc au plus 20 comparaisons. Un arbre dégénéré a une hauteur de $999\ 999$, donc jusqu'à $1\ 000\ 000$ comparaisons : cinquante mille fois plus. Le principe des structures qui garantissent l'équilibre est de RÉÉQUILIBRER à chaque insertion et suppression, par des rotations locales qui préservent la propriété d'arbre binaire de recherche tout en réduisant la hauteur. Le coût d'une rotation est constant, et une insertion n'en déclenche qu'un nombre borné : on paie donc un facteur constant pour garantir la hauteur logarithmique, ce qui est un des meilleurs marchés de toute l'algorithmique.

1) FAUX. Elles diffèrent par l'ORDRE de sortie, qui est le contraire l'un de l'autre : une pile rend le dernier entré, une file rend le premier entré. Ce choix change le résultat de tout algorithme qui les emploie : le même parcours de graphe devient un parcours en profondeur avec une pile et un parcours en largeur avec une file. Énoncé correct : la pile est LIFO, la file est FIFO, et remplacer l'une par l'autre change le comportement, jamais seulement le vocabulaire.

2) FAUX. Dans un tableau, l'adresse du dixième élément se CALCULE par une addition : le coût est constant. Dans une liste chaînée, il faut suivre neuf pointeurs, car aucun maillon ne donne accès qu'à son successeur : le coût est proportionnel à l'indice. Énoncé correct : l'accès indexé est constant dans un tableau et linéaire dans une liste chaînée ; c'est le prix à payer pour l'insertion en tête à coût constant.

3) FAUX. La hauteur dépend de l'ORDRE D'INSERTION, pas du nombre de valeurs. Insérées dans l'ordre croissant, un million de valeurs donnent un peigne de hauteur $999\ 999$. Énoncé correct : la hauteur est comprise entre $\lfloor \log_{2} n \rfloor$ et $n - 1$ ; seule une structure auto-équilibrée garantit la borne logarithmique.

4) FAUX. La récursion explore un sous-arbre entièrement avant de passer au suivant, alors que le parcours en largeur doit traiter tous les noeuds d'un niveau avant de descendre. Énoncé correct : le parcours en largeur s'écrit avec une FILE explicite, dans une boucle ; c'est le seul des quatre parcours qui ne soit pas naturellement récursif.

5) FAUX. La matrice d'adjacence occupe $n^{2}$ cases quel que soit le nombre d'arêtes, et pour un graphe creux, comme un réseau routier, elle est presque entièrement remplie de zéros. Énoncé correct : la matrice est préférable pour un graphe DENSE ou quand on teste souvent l'existence d'une arête précise ; les listes d'adjacence, qui occupent une place proportionnelle au nombre d'arêtes, sont préférables pour un graphe creux et pour tout parcours, où l'on veut énumérer les voisins et non les tester un par un.

a) Les arêtes lues sur la matrice sont A-B, A-D, B-C, C-D, C-E et D-E, soit six arêtes, ce qui correspond au dessin. Les degrés se lisent en sommant chaque ligne : A vaut 2, B vaut 2, C vaut 3, D vaut 3, E vaut 2. La somme des degrés vaut $2 + 2 + 3 + 3 + 2 = 12$, soit deux fois le nombre d'arêtes, ce qui confirme les six arêtes. Deux propriétés nécessaires : la matrice est SYMÉTRIQUE, puisque le graphe n'est pas orienté et qu'une arête relie ses deux extrémités dans les deux sens ; et sa DIAGONALE est nulle, puisqu'aucun sommet n'est relié à lui-même.

b) Listes d'adjacence : A donne B et D ; B donne A et C ; C donne B, D et E ; D donne A, C et E ; E donne C et D. Occupation pour ce graphe : la matrice occupe $5^{2} = 25$ cases, les listes occupent $5 + 2 \times 6 = 17$ entrées, soit une tête de liste par sommet plus deux entrées par arête. L'écart est faible ici. Pour le réseau routier : la matrice occuperait $40\ 000^{2} = 1{,}6 \times 10^{9}$ cases, soit 1,6 milliard, alors que les listes occuperaient $40\ 000 + 2 \times 90\ 000 = 220\ 000$ entrées. Le rapport vaut environ $7\ 273$ : la matrice est ici tout simplement impraticable, et c'est le cas de tous les graphes réels, qui sont creux.

c) Parcours en PROFONDEUR depuis A, voisins par ordre alphabétique : on visite A, puis son premier voisin B, puis le premier voisin non visité de B qui est C, puis le premier voisin non visité de C qui est D, puis le premier voisin non visité de D qui est E. L'ordre est donc A, B, C, D, E. Parcours en LARGEUR depuis A : on visite A, puis tous ses voisins B et D, puis les voisins non encore visités de B, soit C, puis ceux de D, soit E. L'ordre est A, B, D, C, E. Les deux parcours visitent les mêmes sommets, dans un ordre différent.

d) Le parcours en largeur donne les distances suivantes : A à distance 0 ; B et D à distance 1 ; C et E à distance 2. On vérifie sur le dessin : C n'est pas voisin de A, mais il l'est de B et de D, donc il est bien à distance 2. Le parcours en profondeur ne donnerait pas ces distances parce qu'il s'enfonce le plus loin possible avant de revenir : il découvre C au troisième rang par le chemin A, B, C, ce qui donne ici la distance 2 par chance, mais il découvre D par le chemin A, B, C, D, ce qui donnerait la distance 3 alors que D est voisin direct de A. Seul le parcours en largeur garantit qu'un sommet est découvert par un plus court chemin, parce qu'il épuise les sommets à distance $k$ avant d'ouvrir ceux à distance $k+1$.

e) Oui, le graphe est connexe : le parcours depuis A atteint les cinq sommets. La méthode générale consiste à lancer un parcours, en profondeur ou en largeur peu importe, depuis un sommet quelconque, et à comparer le nombre de sommets visités au nombre total de sommets : l'égalité caractérise la connexité. S'il ne l'était pas, il faudrait relancer un parcours depuis un sommet non encore visité, et recommencer tant qu'il en reste : chaque parcours découvre alors une COMPOSANTE CONNEXE, et le nombre de parcours nécessaires est le nombre de composantes. Le coût total reste linéaire en la taille du graphe, puisque chaque sommet et chaque arête n'est examiné qu'une fois.

a) Les SOMMETS sont les cases libres du labyrinthe ; les ARÊTES relient deux cases libres voisines par un côté. Le nombre maximal de sommets est $30 \times 40 = 1\ 200$, atteint quand aucune case n'est murée. Pour les arêtes : il y a $30 \times 39 = 1\ 170$ paires horizontales voisines et $29 \times 40 = 1\ 160$ paires verticales, soit $1\ 170 + 1\ 160 = 2\ 330$ arêtes au maximum. On vérifie l'ordre de grandeur : environ deux arêtes par case, ce qui est bien la signature d'un graphe très creux.

b) Il faut le parcours en LARGEUR, parce qu'il découvre les sommets par distance croissante à la source : le premier chemin par lequel il atteint la sortie est donc nécessairement un plus court. L'algorithme complet : créer une file et y enfiler la case d'entrée, marquée à la distance 0 ; marquer cette case comme visitée ; tant que la file n'est pas vide, défiler une case, et pour chacun de ses voisins libres non visités, le marquer visité, lui attribuer la distance de la case défilée plus 1, et l'enfiler. Si la sortie est marquée, sa distance est la longueur du plus court chemin ; si la file se vide sans l'atteindre, la sortie est inaccessible. Le marquage AVANT l'enfilement, et non au défilement, est essentiel : sans lui, une même case peut être enfilée plusieurs fois et le coût cesse d'être linéaire.

c) On maintient une structure supplémentaire, un tableau de PRÉDÉCESSEURS : au moment où l'on marque un voisin, on enregistre la case depuis laquelle on l'a découvert. À la fin, on part de la sortie et on remonte de prédécesseur en prédécesseur jusqu'à l'entrée, ce qui donne le chemin à l'envers ; il suffit de le retourner. Le coût de cette reconstruction est proportionnel à la longueur du chemin, donc négligeable devant le parcours lui-même, et le surcoût mémoire est d'une case par case, ce qui est le prix normal à payer pour connaître le chemin et pas seulement sa longueur.

d) Sur une grille pleine, aller du coin haut gauche au coin bas droit demande de descendre 29 fois et d'aller à droite 39 fois, dans un ordre quelconque : la distance vaut $29 + 39 = 68$. Le nombre de plus courts chemins est le nombre de façons de placer les 29 descentes parmi les 68 déplacements, soit le coefficient binomial $\binom{68}{29}$. Sa valeur vaut environ $1{,}4 \times 10^{19}$, soit près de quatorze milliards de milliards. C'est un excellent rappel : le plus court chemin est très rarement unique, et un algorithme qui les énumérerait tous serait sans espoir alors que celui qui en trouve un est linéaire.

e) Sur une grille de $3\ 000 \times 4\ 000$, il y a $12\ 000\ 000$ cases et environ $2 \times 12\ 000\ 000 = 24\ 000\ 000$ arêtes. Le coût du parcours en largeur est proportionnel à la somme des deux, soit environ $3{,}6 \times 10^{7}$ opérations, ce qui prend moins d'une seconde. La file contient au plus les cases d'un front d'onde, dont la taille est de l'ordre du périmètre du front : quelques milliers de cases dans le pire cas, ce qui est parfaitement raisonnable. Une matrice d'adjacence serait un contresens complet : elle occuperait $12\ 000\ 000^{2} = 1{,}44 \times 10^{14}$ cases, soit cent quarante mille milliards, alors que le graphe n'a que vingt-quatre millions d'arêtes. C'est le cas d'école du graphe creux, où la représentation implicite par la grille elle-même est encore meilleure que des listes d'adjacence, puisque les voisins d'une case se calculent au lieu d'être stockés.

a) $10 \bmod 7 = 3$, $22 \bmod 7 = 1$, $31 \bmod 7 = 3$, $4 \bmod 7 = 4$, $15 \bmod 7 = 1$ et $45 \bmod 7 = 3$. La case 1 contient les couples de clés 22 et 15, la case 3 ceux de clés 10, 31 et 45, la case 4 celui de clé 4 ; les autres cases sont vides. Collisions : 31 tombe sur 10, 15 tombe sur 22, 45 tombe sur 10 et 31, soit 3 collisions. Six clés dans sept cases suffisent donc à en provoquer trois : les collisions ne sont pas une anomalie, elles sont la règle, et la structure doit les gérer.

b) Pour 45 : la case 3 contient 10, 31 puis 45, donc 3 comparaisons. Pour 17 : $17 \bmod 7 = 3$, on compare à 10, 31 et 45 sans succès, soit 3 comparaisons avant de renvoyer None. Pour 5 : $5 \bmod 7 = 5$, la case est vide, donc 0 comparaison. Le coût d'une recherche ne dépend pas de la taille totale de la table, mais seulement de la longueur de la case visée.

c) Non. La boucle parcourt la case 3, trouve un couple de clé 31 et remplace sa valeur par 'x', puis la fonction se termine : aucun couple n'est ajouté. Le rôle de la boucle est de garantir l'UNICITÉ des clés, qui est le contrat d'un dictionnaire ; sans elle, la case contiendrait deux couples de clé 31, et chercher renverrait toujours le plus ancien.

d) Taux de remplissage : $6 / 7 \approx 0{,}857$. Avec 70 clés uniformément réparties, chaque case en contient 10 ; une recherche fructueuse trouve la clé au rang 1, 2, et ainsi de suite jusqu'à 10 avec la même probabilité, donc $\frac{1 + 2 + \dots + 10}{10} = 5{,}5$ comparaisons en moyenne. Le coût croît donc avec le taux de remplissage. Un vrai dictionnaire AGRANDIT sa table dès que ce taux dépasse un seuil, en général en doublant le nombre de cases et en redistribuant toutes les clés : cette redistribution coûte cher, mais elle est assez rare pour que le coût moyen par insertion reste constant, exactement comme dans l'analyse amortie de l'exercice 3.

e) La case d'un couple est calculée à partir de la clé AU MOMENT de l'insertion. Si la clé était une liste et qu'on la modifiait ensuite, sa nouvelle empreinte désignerait en général une autre case : le couple resterait rangé dans l'ancienne, et plus aucune recherche ne le trouverait. Python interdit donc les objets modifiables comme clés, listes, ensembles et dictionnaires. On utilise à la place le tuple (1, 2), qui contient les mêmes valeurs mais ne peut pas changer.

a) Après les trois écritures, le texte vaut le chat dort et annulables contient le, chat, dort. La première annulation dépile dort, le retire du texte et l'empile dans retablissables ; la seconde fait de même avec chat. Le texte vaut donc le ; annulables contient le ; retablissables contient dort, chat du fond vers le sommet, chat étant au sommet puisqu'il a été annulé en dernier.

b) retablir dépile chat, le remet à la fin du texte et l'empile dans annulables. Le texte vaut le chat ; annulables contient le, chat ; retablissables ne contient plus que dort. Les deux piles fonctionnent en miroir : ce qui sort de l'une entre dans l'autre.

c) ecrire('mange') donne le chat mange et remplace retablissables par une pile vide ; le retablir suivant ne fait donc rien, et le texte reste le chat mange. Vider la pile est indispensable parce que l'historique a DIVERGÉ : dort avait été écrit après chat dans une version du texte que l'utilisateur a abandonnée. Le rétablir maintenant produirait le chat mange dort, un texte que personne n'a jamais écrit.

d) Chaque écriture fait 1 empilement, chaque annulation 1 dépilement et 1 empilement, chaque rétablissement 1 dépilement et 1 empilement, en plus des opérations sur la liste texte. Total : $n + 2n + 2n = 5n$ opérations sur les piles, par exemple $5\ 000$ pour $n = 1\ 000$. Chaque méthode a un coût CONSTANT, indépendant de la longueur de l'historique, parce qu'elle ne touche que les sommets des piles et la fin du texte.

e) Conserver les 100 dernières actions oblige, à la cent unième, à supprimer la PLUS ANCIENNE, qui se trouve au fond de la pile, là où une pile ne donne aucun accès. Il faut une structure qui permette d'ajouter et de retirer aux deux extrémités : une file à double entrée, que Python fournit sous le nom de deque, ou un tableau circulaire de 100 cases comme celui de l'exercice suivant. On retire alors par le fond et on travaille par le sommet, chaque opération restant à coût constant.

a) La racine est 50. Son fils gauche est 30, qui a pour fils 20 et 40 ; 40 a pour fils 35 et 45. Son fils droit est 70, qui a pour fils 60 et 80 ; 60 n'a qu'un fils droit, 65. La hauteur vaut 3, atteinte par les chemins 50, 30, 40, 35 et 50, 70, 60, 65. Les feuilles sont 20, 35, 45, 65 et 80 : il y en a 5.

b) Une feuille n'a aucun descendant : on la détache simplement de son père, en mettant à vide le fils gauche de 30. Aucun autre noeud n'est déplacé, et la propriété reste vraie puisque les valeurs restantes n'ont pas changé de place.

c) On remplace 60 par son unique sous-arbre : 65 devient le fils gauche de 70. La propriété est préservée parce que 65 appartenait déjà au sous-arbre gauche de 70, donc $65 < 70$, et au sous-arbre droit de 50, donc $65 > 50$ : en le remontant d'un niveau, on ne le fait changer d'aucun des sous-arbres qui le contenaient.

d) Le sous-arbre droit de 30 contient 40, 35 et 45 ; sa plus petite valeur est 35, obtenue en descendant toujours à gauche depuis 40. On écrit 35 à la place de 30, puis on supprime l'ancienne feuille 35, ce qui relève du premier cas. Le sous-arbre gauche de la racine a maintenant pour racine 35, avec pour fils gauche 20 et pour fils droit 40, lui-même n'ayant plus qu'un fils droit, 45. On vérifie : 20 est bien inférieur à 35, et 40 et 45 lui sont bien supérieurs.

e) Le successeur est le noeud le plus à gauche du sous-arbre droit : on l'atteint en descendant à gauche tant que c'est possible. S'il avait un fils gauche, ce fils serait plus petit que lui tout en appartenant au même sous-arbre, ce qui contredirait sa minimalité. Sa suppression relève donc toujours du premier ou du deuxième cas, jamais du troisième, et la récursion s'arrête. Parcours infixe de l'arbre obtenu : 20, 35, 40, 45, 50, 60, 65, 70, 80, croissant. Coût : on descend jusqu'au noeud, puis jusqu'au successeur, en suivant un seul chemin depuis la racine, donc au plus la hauteur plus un noeuds visités. La suppression coûte comme la recherche, et hérite du même besoin d'équilibre.

a) Les trois enfilements remplissent les cases 0, 1 et 2. Le premier défilement renvoie 'a' et fait passer tete à 1, le second renvoie 'b' et fait passer tete à 2. On obtient tab = ['a', 'b', 'c', None], tete = 2 et taille = 1. Les valeurs 'a' et 'b' sont encore écrites dans le tableau, mais elles ne font plus partie de la file : seules les cases de tete à tete + taille - 1, modulo 4, comptent.

b) Pour 'd' : $(2 + 1) \bmod 4 = 3$, case 3, taille 2. Pour 'e' : $(2 + 2) \bmod 4 = 0$, case 0, qui écrase l'ancien 'a', taille 3. Pour 'f' : $(2 + 3) \bmod 4 = 1$, case 1, taille 4. État final : tab = ['e', 'f', 'c', 'd'], tete = 2, taille = 4. La queue a fait le tour du tableau et se trouve maintenant AVANT la tête : c'est le sens du mot circulaire.

c) taille vaut 4, égale à la capacité : enfiler lève l'exception « file pleine », et rien n'est écrasé. Les éléments sortiront en partant de la tête, case 2, puis cases 3, 0 et 1 : 'c', 'd', 'e', 'f', c'est-à-dire exactement leur ordre d'arrivée.

d) Notons $q$ l'indice de la prochaine case libre. Une file vide a $q = t$, puisqu'aucun élément ne sépare la tête de la queue. Une file pleine a fait le tour complet, donc $q = (t + 4) \bmod 4 = t$ aussi. Les deux situations donnent les mêmes indices et ne se distinguent plus. Mémoriser la taille lève l'ambiguïté ; l'autre solution classique consiste à s'interdire de remplir la dernière case, une file de capacité 4 n'acceptant alors que 3 éléments.

e) Ici, un défilement lit une case et met à jour deux entiers : coût CONSTANT, même dans le pire cas. Avec pop(0), chaque défilement décale tous les éléments suivants, soit environ $1\ 000$ décalages ; pour $500\ 000$ défilements, cela fait $5 \times 10^{8}$ décalages, là où la file circulaire n'en fait aucun. La file à deux piles est constante en moyenne, grâce à l'analyse amortie, mais un défilement isolé peut transvaser toute la pile : pour un tampon audio qui doit répondre à intervalles réguliers, c'est la garantie dans le pire cas de la file circulaire qui compte.

a) Degrés entrants : A 0, B 1, C 1, D 0, E 3. Peuvent être installés en premier les paquets sans prérequis, c'est-à-dire de degré entrant nul : A et D.

b) On visite A, qui devient gris, puis son premier voisin B, puis le voisin E de B. E n'a aucun successeur : il devient noir le premier. On revient à B, qui devient noir, puis à A, dont le second voisin C mène à E, déjà noir : C devient noir, puis A. La boucle principale passe ensuite à D, encore blanc, dont le voisin E est noir : D devient noir. Ordre des sommets noirs : E, B, C, A, D. La liste renvoyée est son inverse : D, A, C, B, E.

c) Positions dans D, A, C, B, E : A avant B et C, B avant E, C avant E, D avant E. Les cinq arcs vont bien vers l'avant. Un autre ordre valide est A, D, B, C, E. Dénombrement : E doit venir après tous les autres, donc en dernier ; parmi les $4! = 24$ ordres de A, B, C et D, il faut que A précède B et C, ce qui arrive dans un tiers des cas, puisque A doit être le premier des trois. Il y a donc 8 ordres valides : un tri topologique n'est presque jamais unique.

d) Les arcs A vers B, B vers E et E vers A forment un CYCLE : A devrait être installé avant B, B avant E et E avant A, donc A avant lui-même, ce qui est impossible. Dans la trace, A devient gris, puis B, puis E ; en examinant le voisin A de E, on le trouve gris, et l'exception est levée à cet instant, avant qu'aucun sommet soit devenu noir.

e) Les sommets gris sont exactement ceux dont la visite est EN COURS : ils forment le chemin qui mène de la racine du parcours au sommet visité. Trouver un voisin gris, c'est trouver un arc qui revient sur ce chemin, donc un cycle. Un sommet noir, lui, a été entièrement exploré : s'il existait un chemin de lui vers le sommet courant, le parcours l'aurait déjà suivi et le sommet courant serait noir à son tour. L'arc vers un noir mène donc vers une partie déjà terminée, sans retour possible. Coût : chaque sommet est visité une fois et chaque arc examiné une fois, soit un temps proportionnel à $n + m$.