Exercice 2 - Recherche dichotomique · Bac Numérique et Sciences Informatiques Centres étrangers (Afrique) 2025 (jour 2)

Exercice 2 (6 points)

Cet exercice porte sur les listes, les dictionnaires, les fonctions et la récursivité.

Nous souhaitons créer en langage Python un dictionnaire contenant un grand nombre de mots de façon à ce qu'une recherche dans ce dictionnaire soit la plus rapide possible.

Pour cela nous allons créer des groupes de mots, chaque groupe sera une liste Python associée à une clé unique dans le dictionnaire.

Voici un extrait du dictionnaire que nous souhaitons créer (les... indiquent des éléments non listés dans cet extrait):

d = {

44: ['ABAISSEMENT', 'ADMINISTRATEUR',..., 'VERSETS'],

74: ['ABAISSER', 'ABLATION',..., 'TROU'],

243: ['ABANDON', 'ALLEGRETTO',..., 'ZIP'],

36: ['ABANDONNANT', 'ABOLITIONNISTE',..., 'VOULAIT'],

134: ['ABANDONNE', 'AGNOSTICISME',..., 'VOIES'],

40: ['ABANDONNENT', 'ACCOUCHEUSE',..., 'YACK'],

...

} Chaque clé sera un nombre entier positif et chaque valeur sera une liste de mots.

Partie A

Pour générer ces valeurs de clés, nous utiliserons une fonction dite de hachage, c'est-à-dire une fonction qui pour un mot donné calculera la clé qui lui sera associée. Nous choisissons une fonction de hachage simple qui consiste à additionner sur un octet les codes ASCII de chaque lettre de ce mot.

Nous n'utiliserons que des lettres majuscules de l'alphabet, nous rappelons ici le code ASCII (en hexadécimal, c'est-à-dire en base 16) de chacune de ces lettres. Chaque valeur en hexadécimal est notée avec le préfixe 0x, par exemple 0x15 correspond en décimal à $1 \times 16 + 5 \times 1 = 21$.

Partie C

Nous allons maintenant voir comment faire la recherche d'un mot dans notre dictionnaire.

Nous souhaitons une recherche rapide et nous allons profiter du fait que les mots sont classés dans l'ordre alphabétique dans les listes du dictionnaire.

Nous prendrons une approche dichotomique pour écrire une fonction est_present(liste, mot, debut, fin) qui a pour paramètres:

liste, une liste de mots classés dans l'ordre alphabétique;

mot, le mot à rechercher;

debut et fin, les indices entre lesquels la recherche se fait dans liste.

Cette fonction renverra True si liste contient mot entre les indices debut (inclus) et fin (exclus), et renverra False sinon.

Voici son code:

def est_present(liste, mot, debut, fin):

if debut > fin:

return False

milieu = (debut + fin) // 2

if liste[milieu] > mot:

return est_present(liste, mot, 0, milieu - 1)

elif liste[milieu] < mot:

return est_present(liste, mot, milieu + 1, fin)

else:

return True

Nous testons cette fonction ainsi:

>>> liste_mots = ['FONCTION', 'NSI', 'OBJET', 'PYTHON', 'RAM']

>>> est_present(liste_mots, 'NSI', 0, len(liste_mots))

True

8.

Donner, lors de l'exécution de l'exemple précédent, les valeurs des paramètres debut et fin prises lors de chaque appel de la fonction est_present.

1 er appel:

debut =

, fin =

2 e appel:

debut =

, fin =

3 e appel:

debut =

, fin =

9.

Expliquer pourquoi la méthode dichotomique permet d'effectuer, en général, moins d'opérations qu'une recherche simple qui consisterait à comparer un par un les mots de la liste avec le mot cherché.

10.

Donner l'ordre de grandeur du nombre de comparaisons de mots effectuées par la méthode dichotomique sur une liste de longueur $n$ ?