Informatique au lycée Faustin Fleret

Entraînement 1:

Soit le dictionnaire :

>>> d = {'ville': 'le moule', 'departement': 'Guadeloupe', 'habitants': 30000}

1. Corriger l'erreur dans habitants, la bonne valeur est 20000.
2. Implémenter du code pour afficher la liste des clés du dictionnaire.
3. Implémenter du code pour afficher la liste des valeurs du dictionnaire.
4. Implémenter du code pour afficher la liste des paires clé/valeur du dictionnaire.
5. Écrire la phrase "le moule a 20000 habitants" à l'aide du dictionnaire d.

Entraînement 2 :

Supposons que vous ayez une chaîne de caractères et que vous vouliez compter le nombre de fois où apparaît chaque lettre. A l'aide d'un dictionnaire, coder une fonction qui réalise cela.

Entraînement 3 :

On donne un extrait des logins d’accès au réseau du lycée :

toto  to12
tata    ta12
titi    1234

1) Créer une variable de type dict qui contient les couples identifiant - mot_de_passe ci-dessus.

2) Implémenter la saisie du login avec deux variables : identifiant et mot_de_passe

Construire une variable booléenne qui donne True en cas d’identification

correcte, et False dans le cas contraire :

Entraînement 3 :

On donne un extrait des logins d’accès au réseau du lycée :

toto  to12
tata    ta12
titi    1234

1) Créer une variable de type dict qui contient les couples identifiant - mot de passe ci-dessus.

2) La saisie du login fournit deux variables identifiant et mot_de_passe : une pour l’identifiant et l’autre pour le mot de passe.

Construire une variable booléenne qui donne True en cas d’identification

correcte, et False dans le cas contraire :

Entraînement 4 :

Voici un exemple de données permettant de manipuler un livre de recettes de cuisine`a partir de la liste des ingrédients desrecettes :

On va modéliser en Python un livre de recettes, par un dictionnaire de type dict(str : list(str))dans lequel :

• les noms des recettes, de type str, comme clés,
• l’ensemble des ingrédients, de type list(str), comme valeurs associées

1. Construire un dictionnaire mes_recettes correspondant au tableau ci-dessus.
Voir une solution

Solution

recette = {"Gâteau au chocolat":["chocolat", "oeuf", "farine", "sucre", "beurre"], "Gâteau au yaourt" :["yaourt", "oeuf", "farine", "sucre"], "Crêpes" :["oeuf", "farine", "lait", "biere"], "Quatre-quarts" :["oeuf", "farine", "beurre", "sucre"], "Kouign-amann" :["farine", "beurre", "sucre"]} Masquer

2. Définir une fonction nb_ingredients(D, nom) qui à partir d’un dictionnaire de recettes D, défini comme décrit ci-dessus,renvoie le nombre d’ingrédients de la recette nommé nom.
3. Définir une fonction recherche_recettes(D,i) renvoyant l’ensemble des recettes du dictionnaire D qui utilisent l’ingrédient i.
4. Définir une fonction recherche_recettes_2(D,i1,i2)renvoyant l’ensemble des recettes du dictionnaire D qui utilisent les ingrédients i1 et i2.
5. Définir une fonction recherche_recettes_multi(D,Li) renvoyant l’ensemble des recettes du dictionnaire D qui utilisent tous les ingrédients de la liste Li.
6. Définir une fonction recherche_recettes_sans_multi(D,Li) renvoyant l’ensemble des recettes du dictionnaire D qui n’utilisent aucun des ingrédients de la liste Li.

Entraînement 5 : Gestion d’un HashSet avec gestion des conflits de hachage

À partir du code ci-dessous, vous allez compléter et modifier certaines parties afin de manipuler les tables de hachage et de comprendre leur fonctionnement. Le code initial consiste à stocker des chaînes de caractères dans un tableau de hachage (HashSet) en utilisant une fonction de hachage simple.

# Tableau qui servira de squelette pour le HashSet
hashSet = []

# Initialisation du HashSet: Tableau de tableau de taille 2000
for i in range(2000):
    hashSet.append([])

def keyToInt(key):
    '''
    Fonction de hashage:
        Objectif: conversion du texte en valeur numérique pour trouver le bon sous-tableau dans HashSet
        Paramètre: key -> clé à ajouter/chercher dans HashSet
        Fonctionnement: Somme des caractères convertis en code ASCII avec ord moins 96 (ainsi 'a' = 1)
    '''
    val = 0
    for char in key:
        val += ord(char) - 96
    return val % 2000

def isHere(key, hashSet):
    '''
    Fonction de recherche
        Objectif: vérifie si la clé <key> se trouve dans la table de hachage <hashSet>
    '''
    index = keyToInt(key)
    return key in hashSet[index]

def addHash(key, hashSet):
    '''
    Fonction d'ajout
        Objectif: ajouter la clé <key> dans le tableau de hachage <hashSet> si elle n'est pas présente
    '''
    index = keyToInt(key)
    if key not in hashSet[index]:
        hashSet[index].append(key)

# Code de test
addHash("salut", hashSet)
print(isHere("salut", hashSet))

Questions

1. Compréhension de la fonction de hachage
   Expliquez ce que fait la fonction keyToInt et pourquoi elle utilise ord(char) - 96 pour chaque caractère de la clé. Voir une solution

   Solution

   Explication : La fonction keyToInt utilise ord(char) - 96 pour convertir chaque caractère de key en un entier compris entre 1 et 26 (par exemple, 'a' = 1, 'b' = 2, etc.). Ensuite, elle fait la somme de ces valeurs et applique mod 2000 pour s'assurer que l'index est compris entre 0 et 1999. Cette fonction est simple, mais elle peut engendrer de nombreuses collisions (clés différentes ayant le même index), car elle ne prend pas en compte l'ordre des caractères. Masquer

2. Modification de la taille de la table de hachage
   Modifiez la taille de hashSet à 5000 au lieu de 2000. Que pensez-vous que cela changera dans les performances de l’algorithme ? Testez votre hypothèse avec le code. Voir une solution

   Solution

   Changer la taille de hashSet à 5000 réduira théoriquement le nombre de collisions, car il y a plus de sous-tableaux disponibles pour stocker les clés. Cela permet de mieux répartir les valeurs dans la table, ce qui peut améliorer la performance pour de grandes quantités de données. Masquer

3. Gestion des conflits de hachage
   Imaginez qu’on veuille ajouter la clé "hello" et la clé "world" mais que les deux clés aient le même index avec la fonction de hachage actuelle.
   • Expliquez ce qui se passe actuellement dans ce cas.
   • Codez une fonction countCollisions(hashSet) qui retourne le nombre de collisions dans le HashSet (i.e., le nombre de sous-tableaux ayant plus d’un élément). Voir une solution

     Solution

     Lorsque deux clés génèrent le même index (collision), elles sont toutes deux stockées dans le même sous-tableau. Le HashSet actuel utilise la technique de chaining : il ajoute simplement la clé dans une liste qui contient déjà d'autres clés ayant le même index.

     def countCollisions(hashSet):
         collisions = 0
         for sublist in hashSet:
             if len(sublist) > 1:
                 collisions += len(sublist) - 1
         return collisions

     Masquer

4. Insertion et recherche dans le HashSet
   Expliquez le fonctionnement de addHash et isHere. Quelles sont les limites de ce HashSet ? Voir une solution

   Solution

   Fonctionnement de addHash : Cette fonction calcule l'index avec keyToInt et ajoute la clé dans le sous-tableau si elle n'est pas déjà présente. Cependant, si la clé existe déjà, elle n'est pas ajoutée, ce qui empêche les doublons. Fonctionnement de isHere : Cette fonction calcule l'index de key et recherche si elle est présente dans le sous-tableau correspondant. Elle retourne True si la clé est trouvée, False sinon. Masquer

5. Amélioration de la fonction de hachage
   La fonction de hachage actuelle est très simple. Modifiez la fonction keyToInt pour la rendre plus efficace. Par exemple, utilisez un poids croissant pour chaque caractère de la clé (i.e., le premier caractère n’a pas le même poids que le dernier). Voir une solution

   Solution

   Pour améliorer keyToInt, nous allons pondérer chaque caractère de la chaîne avec une puissance croissante d'un nombre premier (par exemple, 31). Cela permet de mieux distribuer les clés dans la table.Masquer

   • Comparez les résultats en termes de collisions avec countCollisions.