Maths & NSI

Baccalauréat — Amérique du Nord J1 — 2024 — NSI

Bac NSI — Amérique du Nord 2024 (Jour 1)

Sujet

Présentation de l'épreuve

Sujet officiel du baccalauréat général, épreuve de spécialité Numérique et Sciences Informatiques, session 2024, Amérique du Nord, jour 1 (code sujet 24-NSIJ1AN1). Durée 3h30, calculatrice interdite. Le sujet comporte 3 exercices indépendants, tous à traiter.

Exercice 1 — File, ordonnancement et interblocage (6 points)

On étudie les processus et leur ordonnancement au sein d'un système d'exploitation monoprocesseur.

  1. Citer les trois états dans lesquels un processus peut se trouver.

On dispose d'une classe Processus : Processus(nom: str, duree: int) crée un processus nommé nom, de durée duree cycles ; p.execute_un_cycle() exécute le processus pendant un cycle ; p.est_fini() renvoie True si le processus est terminé. Pour simplifier, on ne s'intéresse pas aux ressources qu'un processus pourrait acquérir ou libérer.

  1. Citer les deux seuls états possibles pour un processus dans ce contexte simplifié.

On utilise une file (FIFO) pour l'ordonnancement :

class File:
    def __init__(self):
        """ Cree une file vide """
        self.contenu = []
 
    def enfile(self, element):
        """ Enfile element dans la file """
        self.contenu.append(element)
 
    def defile(self):
        """ Renvoie le premier element de la file et l'enleve de la file """
        return self.contenu.pop(0)
 
    def est_vide(self):
        """ Renvoie True si la file est vide, False sinon """
        return self.contenu == []

On constate que f = File(); print(f.defile()) produit une erreur.

  1. Rectifier la classe File pour que defile renvoie None lorsque la file est vide (au lieu de produire une erreur).

On ordonnance les processus par la méthode du tourniquet : à chaque cycle, si un nouveau processus est créé, il est mis dans la file d'attente ; ensuite, on défile un processus et on l'exécute pendant un cycle ; si ce processus n'est pas terminé, on le replace dans la file. On décrit les processus et leur cycle de création par un dictionnaire depart_proc (un seul processus créé par cycle) :

p1 = Processus("p1", 4)
p2 = Processus("p2", 3)
p3 = Processus("p3", 5)
p4 = Processus("p4", 3)
depart_proc = {0: p1, 1: p3, 2: p2, 3: p4}
  1. Construire le chronogramme (processus exécuté à chaque cycle) pour p1, p2, p3, p4.

Classe Ordonnanceur (l'attribut temps est le cycle en cours), code incomplet :

class Ordonnanceur:
    def __init__(self):
        self.temps = 0
        self.file = File()
 
    def ajoute_nouveau_processus(self, proc):
        '''Ajoute un nouveau processus dans la file de l'ordonnanceur.'''
        ...
 
    def tourniquet(self):
        '''Effectue une etape d'ordonnancement et renvoie le nom
        du processus elu.'''
        self.temps += 1
        if not self.file.est_vide():
            proc = ...
            ...
            if not proc.est_fini():
                ...
            return proc.nom
        else:
            return None
  1. Compléter le code ci-dessus.

À chaque appel, tourniquet renvoie le nom du processus élu, ou None s'il n'y en a pas.

  1. Écrire un programme qui utilise p1, p2, p3, p4 et depart_proc, crée un ordonnanceur, ajoute chaque nouveau processus au bon moment, affiche le processus choisi à chaque cycle, et s'arrête lorsqu'il n'y a plus de processus à exécuter.

En réalité, dans l'exemple des processus A, B, C, D (créés respectivement aux cycles 2, 1, 4, 0, de durées 3, 4, 3, 5), ceux-ci utilisent des ressources : un fichier commun, le clavier, le GPU, le port 25000. Le détail des actions de chaque processus est :

  • A : acquérir le GPU ; faire des calculs ; libérer le GPU.
  • B : acquérir le clavier ; acquérir le fichier ; libérer le clavier ; libérer le fichier.
  • C : acquérir le port ; faire des calculs ; libérer le port.
  • D : acquérir le fichier ; faire des calculs ; acquérir le clavier ; libérer le clavier ; libérer le fichier.
  1. En simulant l'ordonnancement tourniquet de A, B, C, D (mêmes cycles de création et durées que ci-dessus) et en faisant correspondre une action de la liste à chaque cycle d'exécution de chaque processus, montrer que l'ordre d'exécution obtenu aboutit à une situation d'interblocage.

Exercice 2 — Graphes : un réseau d'amis (6 points)

Un groupe de huit personnes (Anas, Emma, Gabriel, Jade, Lou, Milo, Nina, Yanis) a les relations d'amitié suivantes : Gabriel-Jade, Gabriel-Yanis, Gabriel-Nina, Gabriel-Milo ; Jade-Yanis, Jade-Emma, Jade-Lou ; Yanis-Emma, Yanis-Nina, Yanis-Milo, Yanis-Anas ; Emma-Nina ; Milo-Anas.

Partie A — Matrice d'adjacence.

  1. Représenter ce graphe (sommets = personnes, arêtes = liens d'amitié).

  2. Une matrice d'adjacence contient un 1 à l'intersection de deux amis, 0 sinon. Compléter, pour les sommets dans l'ordre G, J, Y, E, N, M, A, L :

# sommets :  G, J, Y, E, N, M, A, L
matrice_adj = [[0, 1, 1, 0, 1, 1, 0, 0],  # G
               [...],  # J
               [...],  # Y
               [...],  # E
               [...],  # N
               [...],  # M
               [...],  # A
               [...]]  # L

On dispose de sommets = ['G', 'J', 'Y', 'E', 'N', 'M', 'A', 'L'] et d'une fonction position(l, s) qui renvoie la position du sommet s dans la liste l, ou None s'il est absent.

  1. Donner les retours de position(sommets, 'G') et position(sommets, 'Z').

  2. Compléter la fonction nb_amis(L, m, s), qui prend une liste de sommets L, une matrice d'adjacence m et un sommet s, et renvoie le nombre d'amis de s (None si s n'est pas dans L) :

def nb_amis(L, m, s):
    pos_s = ...
    if pos_s == None:
        return ...
    amis = 0
    for i in range(len(m)):
        amis += ...
    return ...
  1. Donner le retour de nb_amis(sommets, matrice_adj, 'G').

Partie B — Dictionnaire de listes d'adjacence.

  1. Dans un dictionnaire Python {c: v}, que représentent c et v ?

  2. Compléter le dictionnaire de listes d'adjacence graphe du groupe d'amis (graphe = {'G': ['J', 'Y', 'N', 'M'], 'J': ..., ...}).

  3. Écrire nb_amis(d, s), qui prend un dictionnaire d'adjacence d et un sommet s (présent dans d) et renvoie son nombre d'amis. Exemple : nb_amis(graphe, 'L') renvoie 1.

Milo se fâche avec Gabriel et Yanis ; Anas se fâche avec Yanis ; Gabriel et Yanis, de leur côté, cessent également d'être amis. Le nouveau dictionnaire d'adjacence est :

graphe = {'G': ['J', 'N'],
          'J': ['G', 'Y', 'E', 'L'],
          'Y': ['J', 'E', 'N'],
          'E': ['J', 'Y', 'N'],
          'N': ['G', 'Y', 'E'],
          'M': ['A'],
          'A': ['M'],
          'L': ['J']}
  1. On appelle « cercle d'amis » de Nom l'ensemble des personnes atteignables depuis Nom par un parcours en profondeur dans ce graphe. Donner le cercle d'amis de Lou.

Un algorithme de parcours en profondeur possible est :

visites = liste vide des sommets deja visites

fonction parcours_en_profondeur(d, s)
    ajouter s a la liste visites
    pour tous les sommets voisins v de s :
        si v n'est pas dans la liste visites :
            parcours_en_profondeur(d, v)
    retourner la liste visites
  1. Compléter le code Python de parcours_en_profondeur(d, s, visites=[]), qui prend un dictionnaire d'adjacence d et un sommet s, et renvoie la liste des sommets issus du parcours en profondeur depuis s :
def parcours_en_profondeur(d, s, visites=[]):
    ...
    for v in d[s]:
        ...
        parcours_en_profondeur(d, v)
    ...

Exercice 3 — Flashcards et boîtes de Leitner (8 points)

Une flashcard (carte de mémorisation) porte une question au recto et sa réponse au verso.

Partie A. Une étudiante stocke ses flashcards dans un fichier CSV. Extrait de flashcards.csv :

discipline;chapitre;question;reponse
histoire;crise de 1929;jeudi noir - date;24 octobre 1929
histoire;crise de 1929;jeudi noir - quoi;krach boursier
histoire;2GM;l'Axe;Allemagne, Italie, Japon
histoire;2GM;les Allies;Chine, Etats-Unis, France, Royaume-Uni, URSS
histoire;2GM;Pearl Harbor - date;7 decembre 1941
philosophie;travail;Marx;alienation de l'ouvrier
philosophie;travail;Beauvoir;donne de la valeur a l'homme
philosophie;travail;Locke;permet de fonder le droit de propriete
philosophie;travail;Crawford;satisfaction et estime de soi
  1. Donner le séparateur choisi par l'étudiante pour ce fichier.
  2. Justifier ce choix.

Code de l'étudiante pour utiliser ses flashcards :

import csv
import time
 
def charger(nom_fichier):
    with ...
        donnees = ...
    return ...
 
def choix_discipline(donnees):
    disciplines = []
    for i in range(len(donnees)):
        disc = donnees[i]['discipline']
        if not disc in disciplines:
            disciplines.append(disc)
    for i in range(len(disciplines)):
        print(i + 1, disciplines[i])
    num_disc = int(input('numero de la discipline ? '))
    return disciplines[num_disc - 1]
 
def choix_chapitre(donnees, disc):
    chapitres = []
    for i in range(len(donnees)):
        if donnees[i]['discipline'] == disc:
            ch = donnees[i]['chapitre']
            if not ch in chapitres:
                chapitres.append(ch)
    for i in range(len(chapitres)):
        print(i + 1, chapitres[i])
    num_ch = int(input('numero du chapitre ? '))
    return chapitres[num_ch - 1]
 
def entrainement(donnees, disc, ch):
    for i in range(len(donnees)):
        if donnees[i]['discipline'] == disc and donnees[i]['chapitre'] == ch:
            print('QUESTION : ', donnees[i]['question'])
            time.sleep(5)
            print(donnees[i]['reponse'])
            time.sleep(1)
 
flashcard = ...
d = ...
c = ...
entrainement(...)
  1. Compléter le code de charger(nom_fichier), qui lit le fichier et renvoie les données sous la forme d'une liste de dictionnaires (comme csv.DictReader).
  2. Quelle méthode du module time est utilisée dans ce code ?
  3. Donner le type de la variable donnees[i].
  4. Compléter les lignes finales (chargement du fichier puis appel des trois fonctions).

Partie B. Pour espacer la révision (méthode des boîtes de Leitner), les questions sont réparties en 5 boîtes. Initialement, toutes les questions sont en boîte 1. Les questions de boîte 1 sont posées tous les jours, boîte 2 tous les 2 jours, boîte 3 tous les 4 jours, boîte 4 tous les 8 jours, boîte 5 tous les 15 jours. Bonne réponse (et boîte < 5) : le numéro de boîte est incrémenté. Mauvaise réponse : retour en boîte 1.

Base relationnelle à 4 tables : discipline(id INT PK, lib TEXT), chapitre(id INT PK, lib TEXT, id_disc INT FK vers discipline.id), boite(id INT PK, lib TEXT, frequence INT), flashcard(id INT PK, id_ch INT FK vers chapitre.id, id_boite INT FK vers boite.id, question TEXT, reponse TEXT, date_interro DATE). Table boite déjà remplie pour les boîtes 1 à 4 (fréquences 1, 2, 4, 8 jours).

  1. Écrire la requête complétant boite avec la boîte 5 (libellé 'tous les quinze jours', fréquence 15).

Une requête sur flashcard affiche l'enregistrement : 5, 2, 1, Pearl Harbor - date, 6 decembre 1941 (ordre des colonnes : id, id_ch, id_boite, question, reponse).

  1. Écrire la requête mettant à jour la date renvoyée par erreur pour Pearl Harbor (la bonne date est le 7 décembre 1941 — ici la question porte sur le champ reponse, dont le texte contenait par erreur « 6 décembre 1941 »).
  2. Écrire la requête donnant la liste des libellés des disciplines.
  3. Écrire la requête donnant la liste des libellés des chapitres de la discipline 'histoire'.
  4. Écrire la requête donnant la liste des identifiants des flashcards de la discipline 'histoire'.
  5. Écrire la requête supprimant toutes les flashcards de la boîte d'identifiant 3.

Corrigé

Corrigé réservé aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compteSe connecter