Aller au contenu

Identifiants des clients d'une entreprise⚓︎

D'après 2023, Métropole, J2, Ex. 3

Cet exercice porte sur les arbres binaires, les files et la programmation orientée objet. Cet exercice comporte deux parties indépendantes.

PARTIE 1⚓︎

Une entreprise stocke les identifiants de ses clients dans un arbre binaire de recherche.

Arbre binaire

On rappelle qu'un arbre binaire est une structure de nature récursive composée de nœuds, c'est :

  • soit un arbre binaire vide, (le cas de base) ;
  • soit un nœud qui porte une valeur et qui pointe vers deux sous-arbres binaires, un à gauche, un autre à droite.

Un arbre binaire vide n'a pas de sous-arbre binaire.

Les sous-arbres binaires d'un arbre binaire non vide peuvent être vides.

Taille et hauteur d'un arbre binaire

  • La taille d'un arbre binaire est le nombre de nœuds qu'il contient.

  • La hauteur d'un arbre binaire vide est 0.

  • Sinon, sa hauteur est le nombre de nœuds du plus long chemin qui joint le nœud racine à un sous-arbre vide.

Ainsi, la hauteur d'un arbre binaire ne contenant qu'un nœud vaut 1 et celle de l'arbre binaire vide vaut 0.

Dans cet arbre binaire de recherche, chaque nœud contient une valeur, ici une chaine de caractères. Suivant l'ordre lexicographique (celui du dictionnaire) :

  • La chaine de caractères est strictement supérieure à toutes les valeurs des nœuds du sous-arbre binaire à gauche ;
  • La chaine de caractères est strictement inférieure à toutes les valeurs des nœuds du sous-arbre binaire à droite.

Ainsi les valeurs de cet arbre sont toutes distinctes.

On considère l'arbre binaire de recherche suivant :

Figure 1. Arbre binaire de recherche.

graph
N0['dfifi'] --- N1['annieji']
N0 --- N2['helene']
N1 --- N3['aalice']
N1 --- N4['celine']
N2 --- N5( )
N2 --- N6( )
N3 --- N7( )
N3 --- N8( )
N4 --- N9( )
N4 --- NA( )

1. Donner la taille et la hauteur de l'arbre binaire de recherche de la figure 1.

Réponse
  • La taille de cet arbre binaire de recherche est 5.
  • Sa hauteur est de 3.

2. Recopier cet arbre après l'ajout des identifiants suivants : 'davidbg' et 'papicoeur' dans cet ordre.

Réponse
graph
N0['dfifi'] --- N1['annieji']
N0 --- N2['helene']
N1 --- N3['aalice']
N1 --- N4['celine']
N2 --- N5( )
N2 --- N6['papicoeur']
N3 --- N7( )
N3 --- N8( )
N4 --- N9( )
N4 --- NA['davidbg']
NA --- NB( )
NA --- NC( )
N6 --- ND( )
N6 --- NE( )

3. On décide de parcourir cet arbre pour obtenir la liste des identifiants dans l'ordre lexicographique. Recopier la lettre correspondant au parcours à utiliser parmi les propositions suivantes :

  • A : Parcours en largeur
  • B : Parcours en profondeur dans l'ordre préfixe
  • C : Parcours en profondeur dans l'ordre infixe
  • D : Parcours en profondeur dans l'ordre suffixe (ou postfixe)
Réponse

C

En effet, on commence par l'élément inférieur, s'il existe, donc on parcourt en profondeur pour aller d'abord dans le sous arbre à gauche avant de traiter la racine, on termine par le sous arbre à droite. Parcours infixe.

4. Pour traiter informatiquement les arbres binaires, nous allons utiliser une classe ABR.

Cette classe ABR, fonctionnelle, est proposée en fin d'énoncé, uniquement à des fins informatives ; sa lecture n'est pas nécessaire pour cet exercice.

Un arbre binaire de recherche (même vide), nommé abr dispose des méthodes suivantes :

  • abr.est_vide() : renvoie True si abr est vide et False sinon.
  • abr.racine() : renvoie la valeur située à la racine de abr si abr n'est pas vide et provoque une erreur sinon.
  • abr.gauche() : renvoie le sous-arbre à gauche de abr si abr n'est pas vide et provoque une erreur sinon.
  • abr.droite() : renvoie le sous-arbre à droite de abr si abr n'est pas vide et provoque une erreur sinon.

On a commencé à écrire une méthode récursive est_present de la classe ABR, où le paramètre identifiant est une chaine de caractères et qui renvoie True si identifiant est dans l'arbre binaire de recherche et False sinon.

🐍 Script Python
1
2
3
4
5
6
7
8
9
def est_present(self, identifiant):
    if self.est_vide():
        return False
    elif self.racine() < identifiant:
        return self.droite(). ...
    elif self.racine() > identifiant:
        return ...
    else:
        return ...

Recopier et compléter les lignes 5, 7 et 9 de cette méthode.

Réponse
🐍 Script Python
def est_present(self, identifiant):
    if self.est_vide():
        return False
    elif self.racine() < identifiant:
        return self.droite().est_present(identifiant)
    elif self.racine() > identifiant:
        return self.gauche().est_present(identifiant)
    else:
        return True  # Cas d'égalité, identifiant présent

PARTIE 2⚓︎

On considère une structure de données file que l'on représentera par des éléments en ligne, l'élément à droite étant la tête de la file et l'élément à gauche étant la queue de la file.

On appellera f_1 la file suivante :

flowchart LR
    q( ) --> A
    A['bac'] --> B['nsi']
    B --> C['2023']
    C --> D['file']
    D --> E( )

On suppose que les quatre fonctions suivantes ont été programmées préalablement en langage Python :

  • file_vide() : renvoie une file vide ;
  • est_vide(f) : renvoie True si la file f est vide et False sinon ;
  • enfile(f, e) : ajoute l'élément e à la queue de la file f ;
  • defile(f) : renvoie l'élément situé à la tête de la file f et le retire de la file. Si la file était vide, provoque une erreur.

5. Les trois questions suivantes sont indépendantes.

5.a) Donner le résultat renvoyé après l'appel de la fonction est_vide(f_1).

Réponse

False

5.b) Représenter la file f_1 après l'exécution du code defile(f_1).

Réponse

Quand on défile, l'élément en tête (ici à droite) est extrait d'une file non vide.

flowchart LR
    q( ) --> A
    A['bac'] --> B['nsi']
    B --> C['2023']
    C --> D( )

5.c) Représenter la file f_2 après l'exécution du code suivant :

🐍 Script Python
1
2
3
4
f_2 = file_vide()
animaux = ['castor', 'python', 'poule']
for bete in animaux:
    enfile(f_2, bete)
Réponse
flowchart LR
    q( ) --> A
    A['poule'] --> B['python']
    B --> C['castor']
    C --> D( )

Le castor a été enfilé en premier, il sera en tête, prêt à être défilé, ici à droite.

6. Recopier et compléter les lignes 4, 6 et 7 de la fonction longueur qui prend en paramètre une file f et qui renvoie le nombre d'éléments qu'elle contient.

Après un appel à la fonction, la file f doit retrouver son état d'origine.

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def longueur(f):
    resultat = 0
    g = file_vide()
    while ... :
        elt = defile(f)
        resultat = ...
        enfile(... , ...)
    while not est_vide(g):
        enfile(f, defile(g))
    return resultat
Réponse
🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def longueur(f):
    resultat = 0
    g = file_vide()
    while not est_vide(f):
        elt = defile(f)
        resultat = resultat + 1
        enfile(g , elt)
    while not est_vide(g):
        enfile(f, defile(g))
    return resultat

7. Un site impose à ses clients des critères sur leur mot de passe. Pour cela il utilise la fonction est_valide qui prend en paramètre une chaine de caractères mot et qui renvoie True si mot correspond aux critères et False sinon.

🐍 Script Python
1
2
3
4
5
6
7
def est_valide(mot):
    if len(mot) < 8:
        return False
    for c in mot:
        if c in ['!', '#', '@', ';', ':']:
            return True
    return False

Parmi les mots de passe suivants, recopier celui qui sera validé par cette fonction.

  • A : 'best@'
  • B : 'paptap23'
  • C : '2!@59fgds'
Réponse
  • C : '2!@59fgds'

Le A est refusé par manque de caractères, il n'y en a que 5.

Le B est refusé par manque de caractères, il manque au moins un caractère spécial.

8. Le tableau suivant montre, sur deux exemples, l'évolution d'une file f_3 après l'exécution de l'instruction ajoute_mot(f3, 'super') :

Exemple 1

État initial de f_3

flowchart LR
    q( ) --> A
    A['bac'] --> B['nsi']
    B --> C['2023']
    C --> D( )

État de f_3 après l'instruction ajoute_mot(f_3, 'super')

flowchart LR
    q( ) --> A
    A['super'] --> B['bac']
    B --> C['nsi']
    C --> D( )

Exemple 2

État initial de f_3

flowchart LR
    q( ) --> A
    A['test'] --> B['info']
    B --> C( )

État de f_3 après l'instruction ajoute_mot(f_3, 'super')

flowchart LR
    q( ) --> A
    A['super'] --> B['test']
    B --> C['info']
    C --> D( )

Écrire le code de cette fonction ajoute_mot qui prend en paramètres une file f (qui a au plus 3 éléments) et une chaine de caractères valide mdp. Cette fonction met à jour la file de stockage f des mots de passe en y ajoutant mdp et en défilant, si nécessaire, pour avoir au maximum trois éléments dans cette file.

On pourra utiliser la fonction longueur de la question 6.

Réponse
🐍 Script Python
def ajoute_mot(f, mdp):
    if longueur(f) == 3:
        defile(f)
    enfile(f, mdp)

9. Pour intensifier sa sécurité, le site stocke les trois derniers mots de passe dans une file et interdit au client lorsqu'il change son mot de passe d'utiliser l'un des mots de passe stockés dans cette file.

Recopier et compléter les lignes 7 et 8 de la fonction est_element :

  • qui prend en paramètres une file f et mdp de type chaine de caractères ;
  • qui renvoie True si le mot de passe est un élément de la file f et False sinon.

Après un appel à cette fonction, la file f doit retrouver son état d'origine.

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def est_element(f, mdp):
    g = file_vide()
    present = False
    while not est_vide(f):
        elt = defile(f)
        enfile(g, elt)
        if ...:
            present = ...
    while not est_vide(g):
        enfile(f, defile(g))
    return present
Réponse
🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def est_element(f, mdp):
    g = file_vide()
    present = False
    while not est_vide(f):
        elt = defile(f)
        enfile(g, elt)
        if elt == mdp:
            present = True
    while not est_vide(g):
        enfile(f, defile(g))
    return present

10. Écrire une fonction modification qui prend en paramètres une file f et une chaine de caractères nouveau. Si le mot de passe nouveau répond bien aux deux exigences des questions 7 et 9, alors elle modifie la file des mots de passe stockés et renvoie True. Dans le cas contraire, elle renvoie False.

On pourra utiliser les fonctions est_element, est_valide et ajoute_mot.

Réponse
🐍 Script Python
def modification(f, nouveau):
    if est_valide(nouveau):
        if not est_element(f, nouveau):
            ajoute_mot(f, nouveau)
            return True
    return False

Ou bien

🐍 Script Python
def modification(f, nouveau):
    if est_valide(nouveau) and not(est_element(f, nouveau)):
        ajoute_mot(f, nouveau)
        return True
    return False

Ou bien encore

🐍 Script Python
def modification(f, nouveau):
    if not est_valide(nouveau)
        return False
    if est_element(f, nouveau):
        return False
    ajoute_mot(f, nouveau)
    return True

Sécurité

En pratique, on ne stockerait pas les mdp dans la file, mais plutôt des signatures, par exemple, avec la bibliothèque hashlib et la fonction md5.

Il ne faut pas stocker des mots de passe en clair.

🐍 Script Python
from hashlib import md5

def crypt(texte):
    return md5(bytes(texte, 'utf-8')).hexdigest()
Code fonctionnel - pour preuve
🐍 Script Python
class ABR:
    def __init__(self):
        self.valeur = None

        self.sag = None  # le sous arbre à gauche
        self.sad = None  # le sous arbre à droite
        # None ne signifie pas qu'il est vide
        # None signifie qu'il n'existe pas !

    def ajout(self, identifiant):
        if self.est_vide():
            self.valeur = identifiant
            self.sag = ABR()
            self.sad = ABR()
        elif self.valeur < identifiant:
            self.sad.ajout(identifiant)
        elif self.valeur > identifiant:
            self.sag.ajout(identifiant)
        else:
            pass  # cas d'égalité, on ne fait rien ; pas de doublon

    def est_vide(self):
        return self.valeur is None

    def racine(self):
        if self.est_vide():
            raise ValueError("L'arbre vide ne possède pas de racine")
        return self.valeur

    def gauche(self):
        if self.est_vide():
            raise ValueError("L'arbre vide ne possède pas de sous arbre à gauche")
        return self.sag

    def droite(self):
        if self.est_vide():
            raise ValueError("L'arbre vide ne possède pas de sous arbre à droite")
        return self.sad

    def est_present(self, identifiant):
        if self.est_vide():
            return False
        elif self.racine() < identifiant:
            return self.droite().est_present(identifiant)
        elif self.racine() > identifiant:
            return self.gauche().est_present(identifiant)
        else:
            return True  # Cas d'égalité, identifiant présent


abr = ABR()
for p in [5, 2, 3, 7]:
    abr.ajout(p)

for p in [5, 2, 3, 7]:
    assert abr.est_present(p) is True

for p in [0, 1, 4, 6, 8]:
    assert abr.est_present(p) is False