Bac NSI — Sujet zéro 2021

Présentation de l'épreuve

Ce sujet est le spécimen officiel (« sujet zéro ») publié en 2021 par l'Éducation nationale pour la nouvelle épreuve écrite de spécialité NSI en Terminale. Durée : 3h30, calculatrice interdite. Le sujet comporte 5 exercices indépendants ; le candidat doit en choisir 3 à traiter (chaque exercice compte pour environ un tiers de la note).

Exercice 1 — Piles et tri de crêpes

Cet exercice porte sur la structure de pile (LIFO) et la programmation Python de base. On rappelle la structure abstraite Pile, munie de quatre primitives : creer_pile_vide(), est_vide(pile), empiler(pile, element) et depiler(pile) (qui renvoie le sommet en le retirant).

Question 1. La pile P contient, du sommet vers le fond, les valeurs 4, 2, 5, 8. On exécute :

Q = creer_pile_vide()
while not est_vide(P):
    empiler(Q, depiler(P))

Quel est le contenu de la pile Q à la fin de cette boucle ?

Question 2.

1. On veut écrire une fonction hauteur_pile(P) qui renvoie le nombre d'éléments de P, tout en restituant P dans son état initial (elle ne doit pas la « consommer »). Compléter le programme suivant, où chaque ??? doit être remplacé par une instruction :

def hauteur_pile(P):
    Q = creer_pile_vide()
    n = 0
    while not (est_vide(P)):
        ???
        x = depiler(P)
        empiler(Q, x)
    while not (est_vide(Q)):
        ???
        empiler(P, x)
    return ???

2. Écrire une fonction max_pile(P, i) qui renvoie la position (le sommet valant 1) de l'élément maximal parmi les i derniers éléments empilés de P, sans modifier durablement P. Exemple : avec la pile de la question 1, max_pile(P, 2) vaut 1.

Question 3. Écrire une fonction retourner(P, j) qui inverse l'ordre des j derniers éléments empilés de P (et ne renvoie rien). On pourra utiliser deux piles auxiliaires. Exemple : avec la pile de la question 1 (4, 2, 5, 8 du sommet vers le fond), après retourner(P, 3), P devient 5, 2, 4, 8.

Question 4. On modélise une pile de crêpes par une pile d'entiers (le diamètre de chaque crêpe). On veut les trier de la plus grande (en bas) à la plus petite (en haut), à l'aide d'une seule opération : retourner d'un coup toutes les crêpes situées au-dessus d'une certaine position. La méthode (« tri crêpes ») consiste, tant qu'il reste des crêpes non triées, à répéter :

• chercher la plus grande crêpe parmi les non-triées ;
• la retourner en haut de la pile (retourner le paquet qui va jusqu'à sa position) ;
• puis retourner tout le paquet non trié, ce qui l'amène tout en bas, à sa place définitive.

Écrire la fonction tri_crepes(P) qui trie ainsi la pile P, en réutilisant hauteur_pile, max_pile et retourner. Exemple : la pile 7, 14, 12, 5, 8 (sommet vers fond) devient 5, 7, 8, 12, 14.

Exercice 2 — Chemin de somme maximale (récursivité et programmation dynamique)

On considère un tableau T de n lignes et p colonnes. Un chemin va de la case (0, 0) à la case (n-1, p-1) en ne se déplaçant que vers la droite ou vers le bas. La somme d'un chemin est la somme des valeurs traversées. Exemple, avec

T = [[4, 1, 1, 3],
     [2, 0, 2, 1],
     [3, 1, 5, 1]]

le chemin (0,0)-(0,1)-(0,2)-(1,2)-(2,2)-(2,3) a pour somme 14.

Question 1. Un chemin de (0,0) à (2,3) comprend nécessairement 3 déplacements vers la droite.

1. Combien comprend-il de déplacements vers le bas ?
2. En déduire que tout chemin de (0,0) à (2,3) a une longueur (nombre de cases) égale à 6.

Question 2. En énumérant les chemins de (0,0) à (2,3) dans T, déterminer celui de somme maximale et sa valeur.

Question 3. On construit un tableau T' où T'[i][j] est la somme maximale des chemins allant de (0,0) à (i, j).

1. Compléter le tableau T' associé à T ci-dessus (dont voici un extrait partiel) :

T' = [[ 4,  5,  6, ?],
      [ 6,  ?,  8, 10],
      [ 9, 10,  ?, 16]]

2. Justifier que, pour j différent de 0, T'[0][j] = T[0][j] + T'[0][j-1].

Question 4. Justifier que, pour i et j différents de 0, T'[i][j] = T[i][j] + max(T'[i-1][j], T'[i][j-1]).

Question 5. On veut écrire une fonction récursive somme_max(T, i, j) qui renvoie la somme maximale d'un chemin de (0,0) à (i, j).

1. Quel est le cas de base (traité directement, sans appel récursif) ? Que renvoie-t-on dans ce cas ?
2. En déduire l'écriture Python de somme_max.
3. Quel appel permet de résoudre le problème initial (tout le tableau T) ?

Exercice 3 — Arbres binaires et arbres binaires de recherche

On convient que la hauteur d'un arbre réduit à un seul nœud vaut 1.

Question 1. Déterminer la taille (nombre de nœuds) et la hauteur de l'arbre binaire A-B-E (niveau 2), C-D-F (niveau 3, enfants de B et E respectivement), G (enfant de D), H-I (enfants de F) — c'est-à-dire : A a pour fils B (gauche) et E (droite) ; B a pour fils C (gauche) et D (droite) ; D a pour fils gauche G ; E a pour fils gauche F ; F a pour fils H (gauche) et I (droite).

Question 2. On numérote en binaire les nœuds : la racine porte le numéro 1 ; le fils gauche d'un nœud numéroté $k$ porte le numéro obtenu en ajoutant le chiffre 0 à droite de $k$ ; le fils droit, en ajoutant 1. Sur l'arbre précédent, A porte 1, B porte 10, C porte 100, E porte 11, F porte 110.

1. Quel est le numéro binaire de G ?
2. Quel nœud porte le numéro dont la valeur décimale est 13 ?
3. Pour un arbre de hauteur $h$, sur combien de bits sont numérotés les nœuds du niveau le plus bas ?
4. Justifier que, pour un arbre de hauteur $h$ et de taille $n \geqslant 2$, on a $h \leqslant n \leqslant 2^h - 1$.

Question 3. Un arbre binaire complet (tous les niveaux remplis) de taille $n$ peut être représenté par un tableau de taille $n+1$ : la racine à l'indice 1, le fils gauche du nœud d'indice $i$ à l'indice $2i$, le fils droit à l'indice $2i+1$, et la taille $n$ à l'indice 0.

1. Donner le tableau représentant un arbre binaire complet à 15 nœuds numérotés de A (racine) à O (dernière feuille), remplis niveau par niveau de gauche à droite.
2. Quel est, dans ce tableau, l'indice du père du nœud d'indice $i$ (avec $i \geqslant 2$) ?

Question 4. On considère un arbre binaire de recherche complet représenté comme ci-dessus, où chaque nœud est strictement supérieur aux valeurs de son sous-arbre gauche et strictement inférieur à celles de son sous-arbre droit. Écrire une fonction recherche(arbre, element) qui renvoie True si element figure dans l'arbre, False sinon.

Exercice 4 — Bases de données et SQL

Un lycée gère les élèves de seconde dans une table seconde : num_eleve (entier, clé primaire), langue1, langue2, option, classe (chaînes de caractères). Un extrait des données du fichier source, avant import, est reproduit ci-dessous :

Question 1.

1. Quel est l'intérêt, dans le modèle relationnel, de l'attribut num_eleve ?
2. Écrire la requête SQL insérant l'élève MARTIN Léa (ligne 1) dans la table seconde (rappel : seconde ne contient pas nom/prenom, seulement num_eleve, langue1, langue2, option, classe).
3. Lors de la saisie de BERNARD Yanis (ligne 2), une erreur a été commise sur langue1, enregistrée par erreur comme 'anglais' au lieu de 'allemand'. Écrire la requête SQL corrigeant cette donnée.

Question 2. On suppose que seconde contient exactement les 6 lignes ci-dessus.

1. Que renvoie SELECT num_eleve FROM seconde; ?
2. Que renvoie SELECT COUNT(num_eleve) FROM seconde; ?
3. Écrire la requête comptant le nombre d'élèves ayant l'allemand en langue1 ou langue2.

Question 3. Le lycée crée une seconde table eleve : num_eleve (clé primaire, clé étrangère vers seconde), nom, prenom, datenaissance.

1. Qu'apporte la clé étrangère num_eleve de cette table en termes d'intégrité des données ?
2. Écrire la requête (jointure eleve/seconde) listant nom, prénom et date de naissance des élèves de la classe 2A.

Question 4. Proposer la structure d'une table coordonnees (adresse, code postal, ville, e-mail pour chaque élève), en précisant sa clé primaire et sa clé étrangère.

Exercice 5 — Réseaux : protocoles RIP et OSPF

Un réseau de 7 routeurs A à G est interconnecté ainsi (liens bidirectionnels) : A-B, A-C, A-D, B-D, C-E, C-F, D-E, E-G, F-G.

Le protocole RIP. La métrique RIP est le nombre de sauts (routeurs à traverser). Voici les tables de routage obtenues :

Question 1.

1. Déterminer, en nombre minimal de sauts, un trajet de A vers G.
2. En déduire une table de routage possible pour le routeur G (on précisera le raisonnement pour chaque destination).

Question 2. Le routeur C tombe en panne. Reconstruire la table de routage de A (C devient inaccessible).

Le protocole OSPF. La métrique OSPF est la somme des coûts des liaisons traversées, avec $\text{coût} = \dfrac{10^8}{d}$ ($d$ en bit/s). On donne les débits : A-B 10 Gb/s, A-C 10 Mb/s, A-D 100 Mb/s, B-D 20 Mb/s, C-E 50 Mb/s, C-F 100 Mb/s, D-E 100 Gb/s, E-G 100 Mb/s, F-G 100 Mb/s.

Question 3.

1. Vérifier que le coût de la liaison A-B vaut 0,01.
2. La liaison B-D a un coût de 5. Retrouver son débit à partir de la formule.

Question 4. Déterminer, en détaillant le raisonnement, le chemin de A à G dont la somme des coûts est minimale, et donner cette somme.