Sujet NSI — Terminale — Métropole — Bac 2025

Exercice 1 (6 points) Cet exercice porte sur les arbres binaires et la programmation Python. Le codage de Shannon-Fano est un système de codage utilisé pour la compression sans pertes de données. Il a été mis au point par Robert Fano d’après une idée de Claude Shannon. Partie A Dans cette partie, on va étudier l’utilisation des arbres de codage. Un arbre de codage est un arbre binaire où chaque feuille contient un symbole du texte que l’on souhaite coder. Le code binaire d’un symbole s’obtient alors en concaténant les et les sur les branches qui mènent de la racine à la feuille contenant ce symbole. 0 1 Par exemple, pour l’arbre de codage donné en Figure 1, le symbole est codé par le c mot binaire , tandis que est codé par le mot binaire . Les codes binaires 1101 d 11000 des symboles ne sont donc pas tous de la même taille. Pour décoder un mot binaire, il suffit de descendre dans l’arbre, depuis la racine, selon les et les qu’on lit jusqu’à 0 1 trouver une feuille (et donc un symbole), puis de recommencer avec la suite du mot binaire pour décoder les symboles suivants. Figure 1. Exemple d’arbre de codage 1. Écrire le mot binaire qui sera utilisé pour encoder le caractère espace, représenté par le symbole dans l’arbre. _ 2. Déterminer le texte codé par le mot binaire . 0001110101111110011001 25-NSIJ2ME1 Page : 2 / 15 3. Citer le type de parcours de l’arbre qui permettrait d’obtenir les symboles classés par taille d’encodage croissante. Partie B Dans cette partie, on va utiliser le codage de Shannon-Fano pour encoder le texte : je pense, donc je suis Dans la méthode de Shannon-Fano, l’arbre de codage est calculé pour un texte donné par l’algorithme suivant. • Étape 1 : classer les symboles du texte par nombre d’occurrences croissant ; • Étape 2 : en gardant le classement obtenu, séparer les symboles en deux sous- groupes de sorte que les totaux des nombres d’occurrences soient les plus proches possibles dans les deux sous-groupes ; • Étape 3 : placer tous les symboles du premier groupe dans le fils gauche (côté étiqueté par ), et ceux du second groupe dans le fils droit (côté étiqueté par ) 1 0 ; • Étape 4 : recommencer récursivement pour chacun des sous-groupes jusqu’à ce qu’ils n’aient plus qu’un seul symbole ;