Bac NSI — Sujet 0.B 2024

Présentation de l'épreuve

Ce sujet est le spécimen officiel 0.B publié en 2024 par l'Éducation nationale pour l'épreuve écrite de spécialité NSI en Terminale. Durée : 3h30, calculatrice interdite. Il comporte 3 exercices indépendants.

Exercice 1 — Listes, récursivité, programmation dynamique (6 points)

Pour forer un puits, on descend dans le sol de niveau en niveau, en allant à gauche ou à droite. Le sol est modélisé par une pyramide d'entiers (le « score de confiance » de chaque zone), représentée en Python par une liste de niveaux, chaque niveau étant une liste. Exemple :

ex1 = [[4], [6, 2], [3, 5, 7], [5, 1, 6, 2], [4, 7, 3, 5, 2]]

Un conduit part du sommet et descend jusqu'au dernier niveau ; son score est la somme des valeurs traversées.

Question 1. Dessiner (ou décrire niveau par niveau) la pyramide ex2 = [[3], [1, 2], [4, 5, 9], [3, 6, 2, 1]].

Question 2. Déterminer un conduit de score maximal dans ex2, et donner son score.

Question 3. Énumérer les 4 conduits possibles dans la pyramide à 3 niveaux [[2], [5, 1], [2, 3, 9]].

Question 4. En codant chaque conduit par une suite de n choix binaires (gauche=0, droite=1), donner le nombre de conduits possibles dans une pyramide à n niveaux.

Question 5. Justifier que tester tous les conduits pour trouver le score maximal n'est pas une approche raisonnable.

On observe que : si cm1 et cm2 sont des conduits maximaux des deux sous-pyramides obtenues en retirant le sommet, alors on obtient un conduit maximal en ajoutant le sommet devant le meilleur des deux ; et si la pyramide n'a qu'un niveau, le score maximal est simplement la valeur du sommet.

On pose score_max(i, j, p) le score maximal d'un conduit partant du nombre d'indice j du niveau i : score_max(len(p)-1, j, p) = p[len(p)-1][j], et score_max(i, j, p) = p[i][j] + max(score_max(i+1, j, p), score_max(i+1, j+1, p)).

Question 6. Écrire la fonction récursive score_max correspondante.

Question 7. Écrire pyramide_nulle(n), qui construit une pyramide à n niveaux, remplie de 0.

Question 8. Compléter prog_dyn(p), qui calcule le score maximal en remplissant une pyramide s de proche en proche (du dernier niveau vers le sommet), sans redondance de calculs :

def prog_dyn(p):
    n = len(p)
    s = ...
    for j in ...
        s[n-1][j] = ...
    for i in ...
        for j in ...
            s[i][j] = ...
    return s[0][0]

Question 9. Montrer que le coût de prog_dyn est quadratique en n.

Question 10. Expliquer comment adapter score_max (en restant récursive) pour éviter la redondance de calculs et obtenir aussi un coût quadratique.

Exercice 2 — Systèmes d'exploitation, commandes UNIX, LIFO/FIFO, processus (6 points)

Question 1. Expliquer succinctement la différence entre logiciel libre et logiciel propriétaire.

Question 2. Expliquer le rôle d'un système d'exploitation.

On donne une arborescence de fichiers GNU/Linux (racine /) : /home/elsa/documents/boulot/rapport.odt, /home/elsa/documents/fiche.ods, /home/max/images/photos_vac/photo_1.jpg, /home/max/images/ski/gdbd_3.jpg, ainsi que /bin, /boot/grub/grub.cfg, /dev, /etc, /lib, /media/usb0, /mnt.

Question 3. Donner le chemin absolu de rapport.odt.

Question 4. En supposant le répertoire courant /home/elsa, donner le chemin relatif de photo_1.jpg.

Question 5. Depuis /home/elsa, on exécute cp documents/fiche.ods documents/boulot. Donner le contenu résultant des répertoires documents et documents/boulot.

Question 6. Un processus est soit élu, soit bloqué, soit prêt. Décrire les trois transitions (élection, blocage, déblocage) entre ces états, à partir de « réveil » (prêt) jusqu'à « fin » (depuis élu).

Question 7. Donner un exemple de situation faisant passer un processus de l'état élu à l'état bloqué.

Question 8. Nommer une structure de données linéaire de type LIFO.

On considère l'ordonnancement « par ordre de soumission » (FIFO, non préemptif) pour 5 processus :

Question 9. Représenter l'occupation du processeur (chronogramme) avec cet algorithme.

Question 10. Reprendre la question avec l'algorithme « par tourniquet » (round-robin), quantum Q=2 (un processus qui n'a pas terminé retourne en fin de file après avoir utilisé son quantum ; les nouveaux arrivants rejoignent la file dans l'ordre d'arrivée avant que le processus interrompu n'y retourne).

Question 11. Décrire une situation d'interblocage entre deux processus P1, P2 se disputant deux ressources R1, R2.

Exercice 3 — Dictionnaires, POO, bases de données : livres de science-fiction (8 points, 3 parties indépendantes)

On stocke des livres de science-fiction : id, titre, nom_auteur, ann_pub, note :

Partie A — dictionnaire Python

dico_livres = {
    'id': [1, 2, 14, 4, 8, 7, 15, 17, 9, 10],
    'titre': ['1984', 'Dune', 'Fondation', 'Ubik', 'Blade Runner',
              'Les Robots', 'Ravage', 'Chroniques martiennes',
              'Dragon déchu', 'Fahrenheit 451'],
    'auteur': ['Orwell', 'Herbert', 'Asimov', 'K.Dick', 'K.Dick', 'Asimov',
               'Barjavel', 'Bradbury', 'Hamilton', 'Bradbury'],
    'ann_pub': [1949, 1965, 1951, 1953, 1968, 1950, 1943, 1950, 2003, 1953],
    'note': [10, 8, 9, 9, 8, 10, 6, 7, 8, 8],
}
a = dico_livres['note']
b = dico_livres['titre'][2]

Question 1. Déterminer a et b.

Question 2. Compléter titre_livre(dico, id_livre), qui renvoie le titre correspondant à un identifiant (None s'il n'existe pas) :

def titre_livre(dico, id_livre):
    for i in range(len(dico['id'])):
        if dico['id'][i] == ... :
            return dico['titre'][...]
    return ...

Question 3. Écrire note_maxi(dico), qui renvoie la note maximale.

Question 4. Écrire livres_note(dico, n), qui renvoie la liste des titres ayant obtenu la note n.

Question 5. Écrire livre_note_maxi(dico), qui renvoie la liste des titres ayant obtenu la meilleure note.

Partie B — programmation orientée objet

class Livre:
    def __init__(self, id_livre, titre, auteur, ann_pub, note):
        self.id = id_livre
        self.titre = titre
        self.auteur = auteur
        self.ann_pub = ann_pub
        self.note = note
    def get_id(self): return self.id
    def get_titre(self): return self.titre
    def get_auteur(self): return self.auteur
    def get_ann_pub(self): return self.ann_pub
 
class Bibliotheque:
    def __init__(self):
        self.liste_livre = []
    def ajout_livre(self, livre):
        self.liste_livre.append(livre)
    def titre_livre(self, id_livre):
        for livre in self.liste_livre:
            if ... == id_livre:
                return ...
        return ...

Question 6. Citer un attribut et une méthode de la classe Livre.

Question 7. Écrire la méthode get_note de Livre.

Question 8. Écrire le code créant le livre Blade Runner et l'ajoutant à une Bibliotheque.

Question 9. Compléter la méthode titre_livre de Bibliotheque.

Partie C — base de données relationnelle

Table livres(id, titre, auteur, ann_pub, note), id clé primaire.

Question 10. Pourquoi auteur ne peut-il pas être choisi comme clé primaire ?

Question 11. Résultat de SELECT titre FROM livres WHERE auteur = 'K.Dick'; ?

Question 12. Requête donnant les titres d'Asimov publiés après 1950.

Question 13. Requête faisant passer la note de Ubik de 9 à 10.

On sépare ensuite auteurs(id, nom, prenom, annee_naissance) — Orwell(1903), Herbert(1920), Asimov(1920), K.Dick(1928), Bradbury(1920), Barjavel(1911), Hamilton(1960) — et livres référence désormais id_auteur.

Question 14. Pourquoi utiliser deux tables plutôt qu'une seule ?

Question 15. Rôle de id_auteur dans livres ?

Question 16. Requête donnant nom et prénom des auteurs de livres publiés après 1960.

Question 17. Décrire en français le résultat de :

SELECT titre FROM livres
JOIN auteurs ON id_auteur = auteurs.id
WHERE ann_pub - annee_naissance < 30;

Question 18. Un élève veut créer un annuaire de classe (nom, prénom, date de naissance, téléphone, e-mail). En quoi ce projet peut-il être problématique ?