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()
: renvoieTrue
siabr
est vide etFalse
sinon.abr.racine()
: renvoie la valeur située à la racine deabr
siabr
n'est pas vide et provoque une erreur sinon.abr.gauche()
: renvoie le sous-arbre à gauche deabr
siabr
n'est pas vide et provoque une erreur sinon.abr.droite()
: renvoie le sous-arbre à droite deabr
siabr
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 |
|
Recopier et compléter les lignes 5, 7 et 9 de cette méthode.
Réponse
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)
: renvoieTrue
si la filef
est vide etFalse
sinon ;enfile(f, e)
: ajoute l'élémente
à la queue de la filef
;defile(f)
: renvoie l'élément situé à la tête de la filef
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 |
|
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 |
|
Réponse
🐍 Script Python | |
---|---|
1 2 3 4 5 6 7 8 9 10 |
|
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 |
|
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
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
etmdp
de type chaine de caractères ; - qui renvoie
True
si le mot de passe est un élément de la filef
etFalse
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 |
|
Réponse
🐍 Script Python | |
---|---|
1 2 3 4 5 6 7 8 9 10 11 |
|
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
def modification(f, nouveau):
if est_valide(nouveau):
if not est_element(f, nouveau):
ajoute_mot(f, nouveau)
return True
return False
Ou bien
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
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.
from hashlib import md5
def crypt(texte):
return md5(bytes(texte, 'utf-8')).hexdigest()
Code fonctionnel - pour preuve
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