Bac NSI 2023 — Polynésie — Jour 2

Sujet officiel du baccalauréat général, épreuve d'enseignement de spécialité numérique et sciences informatiques, session 2023, Polynésie, jour 2. Durée 3 heures 30, calculatrice non autorisée. 3 exercices, tous à traiter.

Exercice 1 (4 points) — Arbres binaires, arbres binaires de recherche, POO et récursivité

1. On considère l'arbre suivant : racine 13, dont les deux enfants sont 6 (à gauche) et 4 (à droite) ; 6 a pour enfants 7 (à gauche) et 5 (à droite) ; 5 a un unique enfant, 1 (à droite). a. Justifier que cet arbre est un arbre binaire. b. Indiquer si cet arbre est un arbre binaire de recherche (ABR). Justifier.

2. On définit la classe Noeud :

class Noeud:
    def __init__(self, g, v, d):
        """crée un noeud d'un arbre binaire"""
        self.gauche = g
        self.valeur = v
        self.droit = d

et la fonction construire, qui prend en paramètre deux entiers mini et maxi (mini <= maxi) et renvoie un arbre :

def construire(mini, maxi):
    """mini, maxi: entiers respectant mini <= maxi"""
    assert isinstance(mini, int) and isinstance(...,...) and ...
    if maxi - mini == 1 or maxi - mini == 0:
        return Noeud(None, mini, None)
    elif maxi - mini == 2:
        return Noeud(None, (mini+maxi)//2, None)
    else:
        sag = construire(mini, (mini+maxi)//2)
        sad = construire((mini+maxi)//2, maxi)
        return Noeud(sag, (mini+maxi)//2, sad)

isinstance(obj, t) renvoie True si obj est du type t, sinon False. a. Recopier et compléter la ligne 3 de l'assertion (conditions sur mini et maxi). b. On exécute construire(0,8). Représenter, sous forme d'arborescence, les appels récursifs de construire qui en découlent. c. Dessiner (décrire) l'arbre renvoyé par construire(0,8). d. Dessiner (décrire) l'arbre renvoyé par construire(0,3). e. Donner le résultat d'un parcours infixe sur l'arbre de la question 2.c. Expliquer pourquoi ce parcours permet d'affirmer que l'arbre est un ABR. f. La fonction récursive maximum prend en paramètre un ABR abr et renvoie la valeur maximale de ses nœuds. Recopier et compléter les lignes 5 et 7 :

def maximum(abr):
    if abr is None:
        return None
    elif abr.droit is None:
        return .........
    else:
        return .........

3. On donne l'ABR abr_7_noeuds suivant : racine 6, enfants 4 (gauche) et 8 (droite) ; 4 a pour enfants 3 et 5 ; 8 a pour enfants 7 et 9. On donne mystere :

def mystere(abr, x, liste):
    """
    abr -- arbre binaire de recherche
    x -- int
    liste -- list
    Renvoie -- list"""
    if abr is None:
        return []
    else:
        liste.append(abr.valeur)
        if x == abr.valeur:
            return liste
        elif x < abr.valeur:
            return mystere(abr.gauche, x, liste)
        else:
            return mystere(abr.droit, x, liste)

a. Donner les résultats de mystere(abr_7_noeuds,5,[]), puis mystere(abr_7_noeuds,6,[]), puis mystere(abr_7_noeuds,2,[]). b. Décrire quel peut être le rôle de la fonction mystere.

Exercice 2 (4 points) — Modèle relationnel et SQL

Un site permet à ses membres de proposer et de louer du matériel. Le modèle relationnel comprend 4 tables : Membre(id_membre, nom, prenom, cp), Objet(id_objet, description, tarif), Reservation(id_reservation, id_objet, id_membre, date_location, date_retour), Possede(id_membre, id_objet) — cette dernière liant les membres aux objets qu'ils proposent à la location, avec pour clé primaire le couple (id_membre, id_objet).

Contenu à un instant donné :

Membre : (1, "Ali", "Mohamed", "69110") ; (2, "Alonso", "Fernando", "69005") ; (3, "Dupont", "Antoine", "69003") ; (4, "Ferrand", "Pauline", "69160") ; (5, "Kane", "Harry", "69003").

Possede : (1,4), (1,6), (2,4), (3,3), (3,5), (4,1), (4,2).

Objet : (1, "Nettoyeur haute pression", 20) ; (2, "Taille-haie", 15) ; (3, "Perforatrice", 15) ; (4, "Appareil à raclette", 10) ; (5, "Scie circulaire", 15) ; (6, "Appareil à gaufre", 10).

Reservation : (1,4,5,2022-02-18,2022-02-19) ; (2,1,2,2022-05-05,2022-05-06) ; (3,3,1,2022-07-10,2022-07-12) ; (4,3,1,2022-08-12,2022-08-14) ; (5,2,2,2022-10-20,2022-10-22) ; (6,2,2,2022-10-20,2022-10-22).

1. Sans écrire de requête SQL, en étudiant les tables : a. Indiquer les prénoms et noms du ou des membres qui proposent la location d'un appareil à raclette. b. Donner le prénom et le nom du membre qui ne propose aucun objet à la location.

2. a. Donner le résultat de SELECT nom, prenom FROM Membre WHERE cp = "69003"; b. Écrire une requête donnant le tarif de location d'une scie circulaire. c. Écrire une requête modifiant le tarif de location d'un nettoyeur à haute pression, désormais 15 € par jour (au lieu de 20 €). d. Écrire une requête ajoutant Wendie Renard, habitant à Villeurbanne (code postal 69100), dans Membre, avec id_membre 6.

3. a. Expliquer la limitation importante que poserait le couple (id_objet, id_membre) comme clé primaire de Reservation. b. Mohamed Ali quitte le site. On tente DELETE FROM Membre WHERE nom = "Ali" AND prenom ="Mohamed"; : cette requête produit une erreur. Expliquer pourquoi. c. Proposer une suite de requêtes utilisant DELETE, précédant la requête ci-dessus, pour supprimer correctement Mohamed Ali (id_membre 1) de la base (rappel : la relation Objet décrit un type d'objet, elle n'a rien à supprimer lors du départ d'un membre).

4. Ces requêtes utilisent des jointures (id_membre et id_objet supposés non connus) : a. Écrire une requête comptant le nombre de réservations réalisées par Fernando Alonso. b. Écrire une requête donnant les noms et prénoms des membres possédant un appareil à raclette.

Exercice 3 (4 points) — Architecture matérielle, processus et ordonnancement

1. Avec ps -aef on obtient un extrait montrant, entre autres, les processus de PID 9617 (PPID 8887, commande /usr/lib/firefox/firefox), 9657, 9697, 9750, 9794 (tous de PPID 9617), et 9795 (PPID 9794) ; le processus 8887 a pour commande bash. a. Donner, sous forme d'un arbre de PID, la hiérarchie des processus liés à firefox. b. Indiquer la commande qui a lancé le premier processus de firefox. c. La commande kill supprime un processus via son PID (ex. kill 8600). Indiquer la commande permettant de supprimer tous les processus liés à firefox, et uniquement ceux-là.

2. a. Recopier et compléter le schéma d'ordonnancement des processus (Nouveau → un premier état → un deuxième état → Terminé, avec un aller-retour vers un troisième état) avec les termes : Élu, En attente, Prêt, Blocage, Déblocage, Mise en exécution.

Quatre processus à exécuter : P1 (arrivée 0, durée 8), P2 (arrivée 2, durée 6), P3 (arrivée 3, durée 2), P4 (arrivée 7, durée 2). Méthode d'ordonnancement : parmi les processus en attente, on exécute un cycle de celui dont la durée restante est la plus courte (égalité départagée par l'arrivée la plus ancienne), et on recommence jusqu'à épuisement.

Ordonnancement obtenu (exemple donné) : P1,P1,P1,P3,P3,P1,P1,P4,P4,P1,P1,P1,P2,P2,P2,P2,P2,P2 (18 cycles).

b. Le temps d'exécution d'un processus est la différence entre son instant de terminaison et son instant d'arrivée. Calculer la moyenne des temps d'exécution des quatre processus.

On modifie l'ordonnancement : l'algorithme reste identique, mais le processeur exécute désormais deux cycles à chaque fois (au lieu d'un seul) du processus choisi (égalité toujours départagée par l'arrivée la plus ancienne).

c. Déterminer le nouvel ordonnancement des quatre processus (par blocs de 2 cycles). d. Calculer la nouvelle moyenne des temps d'exécution, et indiquer si cet ordonnancement est plus performant que le précédent.

3. Chaque processus est représenté par une liste comportant autant d'éléments que de durées (en cycles), suivis d'autant de chaînes vides que sa date de création (pour simuler l'attente) :

p1 = ['1.8','1.7','1.6','1.5','1.4','1.3','1.2','1.1']
p2 = ['2.6','2.5','2.4','2.3','2.2','2.1','','']
p3 = ['3.2','3.1','','','']
p4 = ['4.2','4.1','','','','','','','']
liste_proc = [p1, p2, p3, p4]

a. Recopier (sans les commentaires) et compléter choix_processus, qui renvoie l'indice du processus le plus court parmi ceux en liste d'attente :

def choix_processus(liste_attente):
    """Renvoie l'indice du processus le plus court parmi
    ceux présents en liste d'attente liste_attente"""
    if liste_attente != []:
        mini = len(liste_attente[0])
        indice = 0
        ...
        return indice

b. Une fonction scrutation (non étudiée) parcourt liste_proc et renvoie la liste d'attente des processus en fonction de leur arrivée (les processus présents, sans chaînes vides en fin de liste, sont ajoutés ; sinon un élément vide est retiré). Recopier et compléter ordonnancement :

def ordonancement(liste_proc):
    """Exécute l'algorithme d'ordonnancement
    liste_proc -- liste des processus
    Renvoie la liste d'exécution des processus"""
    execution = []
    attente = scrutation(liste_proc, [])
    while attente != []:
        indice = choix_processus(attente)
        ... # A FAIRE (plusieurs lignes de code) ...
        attente = scrutation(liste_proc, attente)
    return execution