Correction du bac blanc

Exercice 1 : ligne de commande, base de données

1. a. Les commandes permettant de se positionner dans timbres depuis fiches sont : commande 1 et commande 5

   b. Pour accéder au répertoire timbres depuis la racine, on peut écrire : cd home/document/collections/timbres

1. Les descripteurs de ce fichier sont :

   • nom_timbre avec pour valeurs Gustave Eiffel, Marianne et Alan Turing,
   • annee_fabrication avec pour valeurs 1950, 1989 et 2021,
   • nom_collectionneur avec pour valeurs Dupont, Durand et ̀Dupont.

2. a. La clé primaire d'une relation est un attribut (ou ensemble d'attributs) permettant d'identifier de façon unique chaque enregistrement (ses valeurs doivent donc ne pas pouvoir comporter de doublon).

   b. L'attribut nom ne peut pas servir de clé primaire car il n'est pas unique pour chaque enregistrement. Dans l'exemple proposé plusieurs timbres ont pour nom Gustave Eiffel.

   c. Pour la même raison, l'attribut annee_fabrication ne peut pas servir de clé primaire non plus. Dans l'exemple proposé plusieurs timbres ont pour année de fabrication 1989.

   d. On peut ajouter un attribut id_timbre numérique qui sera différent pour chaque enregistrement (par exemple en l'incrémentant de 1 à chaque nouvelle ligne)

3. a. Cette requête modifie l'attribut ref_licence en Ythpswz pour les enregistrements dont l'attribut nom est Dupond. Après cette requête la relation devient (en italique, les valeurs modifiées):

   ref_licence	nom	prenom	annee_naissance	nbre_timbres
   Hqdfapo	Dupuis	Daniel	1953	53
   Ythpswz	Dupond	Jean-Pierre	1961	157
   Qdfqnay	Zaouï	Jamel	1973	200
   Aerazri	Pierre	Jean	1967	130
   Ythpswz	Dupond	Alexandra	1960	61

   b. L'attribut ref_licence ne peut plus être une clé primaire puisqu'il est n'est plus unique (la valeur Ythpswz apparaît pour deux enregistrement)

4. SELECT nom, prenom, nbre_timbres 
   FROM collectionneurs
   WHERE annee_naissance >= 1963;
   

Exercice 2 : fonctions récursives

1. a. Une fonction récursive qui est une fonction qui s'appelle elle-même.

   b. La fonction compte_rebours ne fait rien si l'argument n passé en paramètre est négatif car la condition du if sera fausse. Après l'affichage de 0, compte_rebours est appelé avec la valeur -1 et donc le programme s'arrête.

2. def fact(n):
       """ Renvoie le produit des nombres entiers strictement positifs inférieurs à n """
       if n == 0:
           return 1
       else:
           return n * fact(n-1)
   

3. a. Dans la console l'affichage produit sera :

   3
   2
   1
   

   En effet, somme_entiers_rec(3) va afficher 3 et appeler somme_entiers(2) qui va afficher 2 et appeler somme_entiers(1) qui va afficher 1.

   b. La valeur 6 sera affecté à la variable res (\(3 + 2 + 1\))

4. Une solution possible :

def somme_entiers(n):
    somme = 0
    for k in range(1,n+1):
        somme = somme + k
    return somme

Exercice 3 : Arbres binaires de recherche et programmation orientée objet

Dans un entrepôt de e-commerce, un robot mobile autonome exécute successivement les tâches qu'il reçoit tout au long de la journée.

La mémorisation et la gestion de ces tâches sont assurées par une structure de données.

1. Dans l'hypothèse où les tâches devraient être extraites de cette structure (pour être exécutées) dans le même ordre qu'elles ont été mémorisées, préciser si ce fonctionnement traduit le comportement d'une file ou d'une pile. Justifier.

En réalité, selon l'urgence des tâches à effectuer, on associe à chacune d'elles, lors de la mémorisation, un indice de priorité (nombre entier) distinct : il n'y a pas de valeur en double.

Plus cet indice est faible, plus la tâche doit être traitée prioritairement.

La structure de données retenue est assimilée à un arbre binaire de recherche (ABR) dans lequel chaque nœud correspond à une tâche caractérisée par son indice de priorité.

Par exemple, le robot a reçu successivement, dans l'ordre, des tâches d'indice de priorité 12, 6, 10, 14, 8 et 13. En partant d'un arbre binaire de recherche vide, l'insertion des différentes priorités dans cet arbre donne la figure 1.

3. Lorsque le robot reçoit une nouvelle tâche, on déclare un nouvel objet, instance de la classe Noeud, puis on l'insère dans l'arbre binaire de recherche (instance de la classe ABR) du robot. Ces 2 classes sont définies comme suit :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Noeud:
    """ Tache à accomplir et ses liens avec les autres """

    def __init__(self, tache, indice):
        self.tache = tache
        self.indice = indice
        self.gauche = ABR()
        self.droite = ABR()
 
 
class ABR: 
    """ arbre binaire de recherche initialement vide """

    def __init__(self): 
        self.racine = None  # modélisation de l'arbre vide
        # Remarque : si l'arbre n'est pas vide,
        #    racine est une instance de la classe Noeud
 
    def est_vide(self): 
        """ Détermine si l'arbre auto-référencé est vide """
        return self.racine == None

    def insere(self, nouveau_noeud):
        """ Insère un nouveau nœud,
          instance de la classe Noeud, dans l'ABR
        """
        if self.est_vide():
            self.racine = nouveau_noeud
        elif self.racine.indice ...... nouveau_noeud.indice
            self.racine.gauche.insere(nouveau_noeud)
        else: 
            self.racine.droite.insere(nouveau_noeud)

3.a) Donner les noms des attributs de la classe Noeud.

3.b) Expliquer en quoi la méthode insere est dite récursive et justifier rapidement qu'elle se termine.

3.c) Indiquer le symbole de comparaison manquant dans le test à la ligne 29 de la méthode insere pour que l'arbre binaire de recherche réponde bien à la définition de l'encadré « Rappel » précédent.

3.d) On considère le robot dont la liste des tâches est représentée par l'arbre de la figure 1. Ce robot reçoit, successivement et dans l'ordre, des tâches d'indice de priorité 11, 5, 16 et 7, sans avoir accompli la moindre tâche entretemps.

Recopier et compléter la figure 1 après l'insertion de ces nouvelles tâches.

elif self.racine.indice > nouveau_noeud.indice

4. Avant d'insérer une nouvelle tâche dans l'arbre binaire de recherche, on s'assure que son indice de priorité n'est pas déjà présent.

Écrire une méthode est_present de la classe ABR qui répond à la description :

def est_present(self, indice_recherche) : 
    """ Détermine si l'indice de priorité indice_recherche (int),
    passé en paramètre, est déjà l'indice d'un nœud de l'arbre.
    
    Renvoie un booléen.
    """

def est_present(self,indice_recherche):
    if self.est_vide():
        return False
    elif self.racine.indice == indice_recherche:
        return True
    elif self.racine.indice > indice_recherche:
        return self.racine.gauche.est_present()
    else:
        return self.racine.droite.est_present()

5. Comme le robot doit toujours traiter la tâche dont l'indice de priorité est le plus petit, on envisage un parcours infixe de l'arbre binaire de recherche.

5.a) Donner l'ordre des indices de priorité obtenus à l'aide d'un parcours infixe de l'arbre binaire de recherche de la figure 1.

5.b) Expliquer comment exploiter ce parcours pour déterminer la tâche prioritaire.

6. Afin de ne pas parcourir tout l'arbre, il est plus efficace de rechercher la tâche du nœud situé le plus à gauche de l'arbre binaire de recherche : il correspond à la tâche prioritaire.

Recopier et compléter la méthode récursive tache_prioritaire de la classe ABR :

def tache_prioritaire(self): 
    """ Renvoie la tache du noeud situé le plus 
    à gauche de l'ABR supposé non vide
    """
    if self.racine. ......... .est_vide():  # pas de nœud plus à gauche
        return self.racine. .........
    else: 
        return self.racine.gauche. .........()

def tache_prioritaire(self):
    """ Renvoie la tache du noeud situé le plus 
    à gauche de l'ABR supposé non vide
    """
    if self.racine.gauche.est_vide():
        return self.racine.tache
    else:
        return self.racine.gauche.tache_prioritaire()

7. Une fois la tâche prioritaire effectuée, il est nécessaire de supprimer le nœud correspondant pour que le robot passe à la tâche suivante :

• Si le nœud correspondant à la tâche prioritaire est une feuille, alors il est simplement supprimé de l'arbre (cette feuille devient un arbre vide)
• Si le nœud correspondant à la tâche prioritaire a un sous-arbre à droite non vide, alors ce sous-arbre à droite remplace le nœud prioritaire qui est alors écrasé, même s'il s'agit de la racine.

Dessiner alors, pour chaque étape, l'arbre binaire de recherche (seuls les indices de priorités seront représentés) obtenu pour un robot, initialement sans tâche, et qui a, successivement dans l'ordre :

• étape 1 : reçu une tâche d'indice de priorité 14 à accomplir
• étape 2 : reçu une tâche d'indice de priorité 11 à accomplir
• étape 3 : reçu une tâche d'indice de priorité 8 à accomplir
• étape 4 : accompli sa tâche prioritaire
• étape 5 : reçu une tâche d'indice de priorité 12 à accomplir
• étape 6 : accompli sa tâche prioritaire
• étape 7 : accompli sa tâche prioritaire
• étape 8 : reçu une tâche d'indice de priorité 15 à accomplir
• étape 9 : reçu une tâche d'indice de priorité 19 à accomplir
• étape 10 : accompli sa tâche prioritaire