Aller au contenu

Mini-projet☘

Attention, cette page comporte deux sujets. Vous devez rendre uniquement le projet qui correspond au sujet que vous a attribué l'enseignant.

Le fichier complété sera à rendre sur le cahier de texte de l'ENT, dans l'espace prévu à cet effet.

Sujet A - Tableau de tuples triés☘

Dans ce mini-projet, vous devrez construire en POO une structure de tableau associatif munie des méthodes suivantes :

Méthode/Opérations Description
d = Dico() Initialisation d'un tableau associatif vide
d.est_vide() Renvoie True si le tableau associatif est vide, False sinon.
d.est_plein() Renvoie True si le tableau associatif est complet, False sinon
d.hashage(cle) Renvoie l'indice qui correspond à cle,
renvoie -1 si cle est absente du tableau associatif
d.contient(cle) Renvoie True si cle est une clef du tableau associatif, False sinon
d. ajout(cle, valeur) Associe valeur à une nouvelle clef cle.
Si cle est déjà présente, modifie la valeur associée.
print(d) Chaîne de caractère renvoyée pour l'affichage du tableau associatif sous la forme :
    DEBUT
    cle1 : valeur1
    cle2 : valeur2
    (...)
    FIN
Les cellules (clés) vides ne s'affichent pas
d.valeur(cle) Renvoie la valeur associée à la clef clef
d.supprime(cle) Supprime la clef clef (et donc la valeur associée)
len(d) Renvoie le nombre de clés non vides stockées dans le tableau associatif

Fichier à trous☘

Téléchargez puis complétez le fichier « à trous » projet02_A.py (clic droit -> [Enregistrer sous]).

Dans ce fichier, la classe se nomme Dico2. Elle comporte trois attributs :

  • longueur : entier (puissance de 2), nombre total de clés non vides pouvant être contenues dans le tableau associatif ;
  • couples : tableau (type list en Python) de longueur couples (tuples) vides.
    Chaque tuple représentera un couple (cle, valeur) ;
  • nb_elements : entier, le nombre de clés non vides stockées dans le tableau associatif.

Énoncé☘

  1. Complétez le constructeur de la classe Dico2 et vérifiez l'initialisation de chacun des attributs.

    Exemple de tests

    Les entrées du tableau associatif sont stockées dans un tableau de tuples de la forme (cle, valeur) trié par ordre croissant de clé. Vous pouvez utilisez la méthode .sort() pour trier un tableau (type list) si nécessaire.

    >>> d = Dico2(3)
>>> d.couples
[(), (), (), (), (), (), (), ()]

  2. Complétez le code des méthodes est_vide() puis est_plein().

  3. Complétez le code de la méthode hachage() qui prend en paramètre une clef cle et qui renvoie -1 si cle n'existe dans aucun couple du tableau couples ou qui renvoie l'indice du couple dans lequel on peut trouver cle dans le tableau couples.

    Contrainte

    Cette recherche doit être effectuée par dichotomie (cf. cours de 1ère).

    Exemple de tests

    Si d.couples est [ (), (), (), (), (), ('deux', 2), ('trois', 3), ('un', 1) ], alors on obtient les renvois suivants : 

    >>> d.hachage('deux')
5

>>> d.hachage('quatre')
-1

  4. Complétez le code de la méthode contient() qui prend en paramètre une clef cle et qui renvoie True si cle est présente dans un des couples du tableau couples, False sinon.

  5. Complétez le code de la méthode ajout() qui prend en paramètres une clef cle et une valeur valeur.

    • Ou bien la cle existe déjà, alors on modifie la valeur dans le couple correspondant du tableau couples ;
    • Ou bien cle n'existe pas et on place le couple (cle, valeur) dans le tableau couples puis on trie à l'aide de la méthode .sort()
      Attention, le tableau associatif est peut-être complet...

    Exemple de tests

    >>> d = Dico2(3)

>>> for i in range(5, 12, 3):
...     d.ajout(i, 12-i)

>>> d.couples
[(), (), (), (), (), (5, 7), (8, 4), (11, 1)]

>>> for i in range(2, 25, 3):
...     d.ajout(i, 15-i)

>>> d.couples
[(2, 13), (5, 10), (8, 7), (11, 4), (14, 1), (17, -2), (20, -5), (23, -8)]

>>> d.ajout(0, 14)
AssertionError: Le tableau associatif est complet

  6. Complétez le code de la méthode __repr__() qui renvoie la chaîne d'affichage du tableau associatif.

    Exemple de tests

    >>> d = Dico2(3)

>>> for i in range(5, 9):
...     d.ajout(i, 9-i)

>>> d
    DEBUT
    5 : 4 
    6 : 3 
    7 : 2 
    8 : 1 
    FIN

  7. Terminez en complétant les codes des méthodes valeur(), supprime() puis __len__().
    Ajoutez les tests nécessaires au programme principal.

Sujet B - Chaînage linéaire☘

Dans ce mini-projet, vous devrez construire en POO une structure de tableau associatif munie des méthodes suivantes.
Attention, il y a une petite modification pour la méthode d'affichage...

Méthode/Opérations Description
d = Dico() Initialisation d'un tableau associatif vide
d.est_vide() Renvoie True si le tableau associatif est vide, False sinon.
d.est_plein() Renvoie True si le tableau associatif est complet, False sinon
d.hashage(cle) Renvoie l'indice qui correspond à cle,
renvoie -1 si cle est absente du tableau associatif
d.contient(cle) Renvoie True si cle est une clef du tableau associatif, False sinon
d. ajout(cle, valeur) Associe valeur à une nouvelle clef cle.
Si cle est déjà présente, modifie la valeur associée.
print(d) Chaîne de caractère renvoyée pour l'affichage du tableau associatif sous la forme :
    DEBUT
    indice - cle1 : valeur1
    indice - cle2 : valeur2
    (...)
    FIN
Les cellules (clés) vides ne s'affichent pas
« indice » représente l'indice de la table de hachage contenant le couple (cle, valeur)
d.valeur(cle) Renvoie la valeur associée à la clef clef
d.supprime(cle) Supprime la clef clef (et donc la valeur associée)
len(d) Renvoie le nombre de clés non vides stockées dans le tableau associatif

Fichier à trous☘

Téléchargez puis complétez le fichier « à trous » projet02_B.py (clic droit -> [Enregistrer sous]).

Dans ce fichier, la classe se nomme Dico3. Elle comporte trois attributs :

  • longueur : entier (puissance de 2), nombre total de clés non vides pouvant être contenues dans le tableau associatif ;
  • table : tableau (type list en Python) qui est initialisé avec longueur éléments de valeur None ;
  • collisions : entier, le compteur de collisions.

Les entrées du tableau associatif sont stockées dans table qui une table de hachage représentée sous la forme d'un tableau de tableaux pour lequel :

  • la position de l’élément dans la table de niveau 0 est déterminée à partir de la fonction de hachage hash() pré-programmée de Python ;
  • les collisions sont gérées au moyen d'un tableau de niveau 1 qui contient tous les éléments donnant le même résultat par la fonction de hachage.

Exemple

On initialise un tableau associatif de type Dico3 de longueur 4.
On suppose que les associations suivantes ont été ajoutées dans ce tableau :

  • la clef 'un' associée à la valeur 1 ;
  • la clef 'deux' associée à la valeur 2 ;
  • la clef 'trois' associée à la valeur 3 ;

Le tableau couples est alors :

1
couples = [ [ ('deux', 2), ('trois', 3) ], [ ('un', 1) ], None, None ]

La position des éléments dans le tableau se justifie par les calculs suivants (on utilise la fonction hash() pré-programmée de Python) :

  • hash('un') renvoie la valeur -1518006808732739691.
    Cette valeur modulo 4 (la longueur) donne 1 donc la clef 'un' est stockée à l'indice 1 ;
  • hash('deux') renvoie la valeur 8437999069040821552.
    Cette valeur modulo 4 donne 0 donc la clef 'deux' est stockée à l'indice 0 ;
  • hash('trois') renvoie la valeur 4075383284573333572.
    Cette valeur modulo 4 donne 0 donc la clef 'trois' est stockée à l'indice 0, comme la clef 'deux'.

Important

Pour un paramètre donné, la fonction hash() de Python renvoie toujours la même valeur.
Par contre, d'une session à l'autre, cette valeur peut être différente. Par exemple :

  • Dans une première session : 
    >>> hash('un')
2491182608428176711

>>> hash('un')
2491182608428176711
  • Dans une deuxième session : 
    >>> hash('un')
-5822393557601738687

>>> hash('un')
-5822393557601738687

Par conséquent, il est normal de ne pas obtenir des résultats identiques à ceux présentés par les tests présentés dans ce mini-projet.

Énoncé☘

  1. Complétez le constructeur de la classe Dico3 et vérifiez l'initialisation de chacun des attributs.

    Exemple de tests

    >>> d = Dico3(3)
>>> d.longueur
8

>>> d.table
[None, None, None, None, None, None, None, None]

>>> d.collisions
0

  2. Complétez le code des méthodes est_vide() puis est_plein().
    Réfléchissez bien !

  3. Complétez le code de la méthode hachage() en faisant appel à la fonction pré-programmée hash() de Python.

  4. Complétez le code de la méthode contient() qui prend en paramètre une clef cle et qui renvoie True si cle est présente dans un des couples d'indice hachage(cle) du tableau table, False sinon.

  5. Complétez le code de la méthode ajout() qui prend en paramètres une clef cle et une valeur valeur.

    • Ou bien cle existe déjà, alors on modifie la valeur dans le couple correspondant d'indice hachage(cle) du tableau table ;
    • Ou bien cle n'existe pas et on place le couple (cle, valeur) dans le tableau table à l'indice hachage(cle).
      Ne pas oublier de mettre à jour le nombre de collisions.

    Exemple de tests

    >>> d = Dico3(2)
>>> d.ajout('un', 1)
>>> d.table
[None, [('un', 1)], None, None]

>>> d.ajout('deux', 2)
>>> d.ajout('trois', 3)
>>> d.table
[None, [('un', 1)], [('deux', 2), ('trois', 3)], None]

  6. Complétez le code de la méthode __repr__() qui renvoie la chaîne d'affichage du tableau associatif.

    Exemple de tests

    >>> d = Dico3(2)
>>> d.ajout('un', 1)
>>> d.ajout('deux', 2)
>>> d.ajout('trois', 3)
>>> d 
    DEBUT
    1 - 'un' : 1 
    2 - 'deux' : 2 
    2 - 'trois' : 3 
    FIN

  7. Terminez en complétant les codes des méthodes valeur(), supprime() puis __len__().
    Ajoutez les tests nécessaires au programme principal.