Question transversaleMathsNSIArbres et structures de données

Comment un arbre peut-il compresser une image qui contient de grandes zones de même couleur ?

Q: Démontrez 1 + 4 + … + 4^(k) = (4⁽k+1) − 1)/3.

Somme géométrique de raison 4 : (4⁽k+1) − 1)/(4 − 1).

Un arbre quaternaire découpe une image en quatre carrés, puis redécoupe seulement les carrés non uniformes. Une image de 1 024 × 1 024 pixels uniforme tient en un nœud ; au pire, l'arbre a (4¹¹ − 1)/3 = 1 398 101 nœuds, plus que le million de pixels. Le gain dépend donc de l'image.

Grand oral session 2027 : exposé de 10 minutes debout, puis 10 minutes d'échange, sans calculatrice. Plan prévu pour 9,5 min.

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

En NSI, nous avons travaillé sur des images en noir et blanc, et j'ai remarqué qu'un logo avec de grands aplats de couleur était stocké avec autant de pixels qu'une photographie. Le professeur nous a présenté les arbres quaternaires, qui découpent l'image récursivement. J'ai voulu calculer combien de nœuds il faut, dans le meilleur et dans le pire cas.

L'enjeu et les notions du programme

Dénombrer les nœuds d'un arbre quaternaire par une somme géométrique et comparer au stockage pixel par pixel.

Mathématiques

Somme des termes d'une suite géométrique (première)
Puissances de 2 et de 4 (seconde)
Raisonnement par récurrence (terminale)

Numérique et sciences informatiques

Arbres, récursivité (terminale)
Images matricielles, compression (première)

Le plan de l'exposé en 9,5 min

1. Introduction
1 min
Une image de $2^{k} \times 2^{k}$ 2^(k)×2^(k) pixels stockée pixel par pixel occupe toujours $4^{k}$ 4^(k) cases, qu'elle soit uniforme ou très détaillée. Problématique : une structure récursive peut-elle profiter des zones uniformes, et à quel prix dans le pire cas ?
2. NSI : le découpage récursif
3 min
On regarde l'image entière. Si elle est uniforme, on la représente par une feuille portant sa couleur. Sinon, on la coupe en quatre quarts (nord-ouest, nord-est, sud-ouest, sud-est) et on recommence sur chacun : la racine a alors quatre enfants. On s'arrête au plus tard au niveau du pixel.
Pour un logo noir sur fond blanc, les grandes zones uniformes deviennent des feuilles proches de la racine, et seuls les bords sont découpés finement. La fonction de construction est récursive, comme celle qui redessine l'image à partir de l'arbre.
3. Mathématiques : meilleur et pire cas
4 min
Meilleur cas : l'image est uniforme, l'arbre a 1 nœud. Pire cas : aucun carré n'est uniforme (un damier de pixels), on découpe jusqu'au bout. Au niveau $j$ j il y a $4^{j}$ 4^(j) nœuds, pour $j$ j de 0 à $k$ k. Total : $1 + 4 + \dots + 4^{k} = \frac{4 ^{k + 1} - 1}{3}$ 1+4+…+4^(k)=(4^(k+1)-1)/3.
Pour $k = 10$ k=10 (1 024 × 1 024 pixels) : $4^{10} = 1048576$ 4¹⁰=1 048 576 pixels, mais $\frac{4 ^{11} - 1}{3} = 1398101$ (4¹¹-1)/3=1 398 101 nœuds, soit un tiers de plus. Les nœuds internes s'ajoutent aux feuilles : leur nombre, $\frac{4 ^{k} - 1}{3}$ (4^(k)-1)/3, est environ un tiers du nombre de feuilles.
L'arbre ne gagne donc que si l'image comporte de grandes zones uniformes. Un carré uniforme de $2^{j} \times 2^{j}$ 2^(j)×2^(j) pixels, aligné sur le découpage, remplace $\frac{4 ^{j + 1} - 1}{3}$ (4^(j+1)-1)/3 nœuds par un seul.
4. Conclusion
1,5 min
L'arbre quaternaire compresse une image en ne découpant que les zones non uniformes : un nœud pour une image unie, mais environ $\frac{4}{3}$ 4/3 du nombre de pixels dans le pire cas. Toute compression gagne sur certaines données et perd sur d'autres. J'ouvre sur les octrees, leur version en trois dimensions, utilisés dans les jeux vidéo.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

1 + 4 + \dots + 4^{k} = \frac{4 ^{k + 1} - 1}{3} k = 10 : \frac{4 ^{11} - 1}{3} = 1398101 n œ uds 1+4+\dots+4^(k)=(4^(k+1)-1)/3 k=10: (4¹¹-1)/3=1 398 101 nœuds 4^{10} = 1048576 pixels n œ uds internes = \frac{4 ^{k} - 1}{3} \approx \frac{1}{3} \times feuilles 4¹⁰=1 048 576 pixels nœuds internes =(4^(k)-1)/3\approx1/3\times feuilles

Conclusion : la réponse à la question

Une somme géométrique mesure le coût d'un arbre quaternaire : très faible sur une image à grands aplats, supérieur au stockage brut sur une image très détaillée. Une structure récursive n'est efficace que si les données ont une structure à exploiter.

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Combien de nœuds au pire pour une image 4 × 4 ?

$1 + 4 + 16 = 21$ 1+4+16=21, pour 16 pixels.

Démontrez 1 + 4 + … + 4^k = (4^(k+1) − 1)/3.

Somme géométrique de raison 4 : (4^(k+1) − 1)/(4 − 1).

Pourquoi une image de taille 2^k × 2^k ?

Pour pouvoir couper en quatre carrés égaux jusqu'au pixel ; sinon on complète l'image.

Pourquoi ne gagne-t-on rien sur un damier ?

Aucun carré de plus d'un pixel n'est uniforme : il faut descendre partout jusqu'au pixel.

Existe-t-il une compression qui réduit toutes les images ?

Non : il y a plus d'images de n bits que de fichiers plus courts, donc certaines ne peuvent pas être réduites.

Les pièges qui coûtent des points

Oublier les nœuds internes dans le décompte.
Croire qu'un arbre compresse toujours.
Confondre arbre binaire (2 enfants) et quaternaire (4 enfants).

Revoir les notions

Autres questions : arbres et structures de données

Toutes les questions maths-nsi →

Préparer l'oral, pas seulement le contenu

Gestion des 20 minutes de préparation, usage du tableau, posture debout, réponses au jury : la méthode complète, conforme aux règles de la session 2027.

Méthode : traiter une question de Grand oral →

Continuer la préparation

Le Grand oral 2027 →Méthode : traiter une question →Toutes les questions, par combinaison →Questions de maths seules →Questions maths-physique-chimie →Questions maths-SES →Questions maths-SVT →Questions maths-SI →Questions maths-HGGSP →Questions maths-anglais →