Exercice 1 - Arbres binaires · Bac Numérique et Sciences Informatiques Amérique du Nord 2025 (jour 2)

Exercice 1 (6 points)

Cet exercice porte sur les tableaux, les dictionnaires, les arbres binaires, la programmation en Python et la récursivité.

Lors de la transmission de données, des erreurs peuvent se glisser.

On se propose d'étudier des techniques permettant de minimiser les conséquences de telles erreurs.

Partie A

Pour encoder un texte en binaire, on traduit chaque caractère en un octet, par exemple en utilisant le code ASCII. La table ASCII permet de traduire les caractères classiques en entiers compris entre 0 et 127, qui peuvent ensuite être écrits en binaire sur un octet, c'est-à-dire une suite de 8 bits valant chacun 0 ou 1.

Dans la table ASCII, le code associé au caractère a est 97.

On se propose de construire un décodeur pour le code de Hamming (4, 7) à l'aide d'un arbre binaire. Il s'agit d'un arbre binaire de hauteur 7 dont chaque feuille est étiquetée par le mot de 4 bits susceptible d'avoir donné le code correspondant au chemin menant à cette feuille.

Pour décoder un code reçu, on descend dans l'arbre en lisant ce code de la gauche vers la droite. Si on rencontre un bit valant 0, on continue dans le sous-arbre gauche. Si on rencontre un bit valant 1, on continue dans le sous-arbre droit.

Par exemple, le chemin indiqué en gras sur la Figure 1 indique comment on peut retrouver le mot 0010 après avoir reçu le code 0101010.

9.

Indiquer combien l'arbre décodeur complet du code de Hamming (4,7) comporte de feuilles.

Un arbre binaire non vide est représenté en Python par une classe Noeud qui possède 3 attributs:

gauche correspond à son sous-arbre gauche s'il s'agit d'un nœud interne, et vaut None s'il s'agit d'une feuille;

droit correspond à son sous-arbre droit s'il s'agit d'un nœud interne, et vaut None s'il s'agit d'une feuille;

etiquette correspond à la chaîne de caractères désignant le mot décodé s'il s'agit d'une feuille, et vaut None s'il s'agit d'un nœud interne.

10.

Recopier et compléter les lignes 12 à 14 du code de la fonction récursive decode, donné ci-après. Cette fonction prend en paramètres un arbre décodeur arbre, une liste code et un indice i et renvoie le mot étiquetant la feuille atteinte.

def decode(arbre, code, i):

'''

Descend dans l'arbre binaire arbre en lisant le

tableau code à partir de l'indice i et renvoie

le mot étiquetant la feuille atteinte.

Précondition: arbre est un arbre binaire

de hauteur len(code) - i

'''

if i == len(code):

return arbre.etiquette

if code[i] == 0:

return decode(...)

if code[i] == 1:

return decode(...)