Question transversaleMathsNSITransmettre et compresser

Existe-t-il un logiciel capable de réduire la taille de n'importe quel fichier ?

Q: Quelle part des fichiers de n bits peut-on raccourcir d'au moins 10 bits ?

Il n'y a que $2ⁿ⁻⁹-1$ fichiers d'au plus $n-10$ bits : moins de $1/512$ des fichiers, environ 0,2 %.

Il y a 2ⁿ fichiers de n bits, mais seulement 2ⁿ − 1 fichiers strictement plus courts (de 0 à n − 1 bits). Par le principe des tiroirs, aucun algorithme sans perte ne peut raccourcir tous les fichiers : s'il en raccourcit certains, il doit en allonger d'autres.

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.

J'ai vu passer une publicité pour un logiciel qui promettait de « compresser n'importe quel fichier de 90 % ». J'ai essayé de compresser un fichier zip déjà compressé, et il a grossi. J'ai voulu savoir si un tel logiciel pouvait exister. Un argument de dénombrement très court m'a donné une réponse définitive.

L'enjeu et les notions du programme

Démontrer une impossibilité par le principe des tiroirs, à l'aide du dénombrement des mots binaires et d'une somme géométrique.

Mathématiques

Dénombrement des mots binaires de longueur n (terminale)
Somme des termes d'une suite géométrique (première)
Raisonnement par l'absurde, principe des tiroirs (seconde, terminale)

Numérique et sciences informatiques

Compression sans perte et avec perte (première)
Représentation des données en binaire (première)

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

1. Introduction
1 min
Un algorithme de compression sans perte transforme un fichier en un fichier plus court, à partir duquel on retrouve exactement l'original. Problématique : peut-il raccourcir tous les fichiers, sans exception ?
2. Mathématiques : le principe des tiroirs
4 min
Un fichier de $n$ n bits est un mot binaire de longueur $n$ n : il y en a $2^{n}$ 2ⁿ. Les fichiers strictement plus courts ont une longueur de 0 à $n - 1$ n-1 : il y en a $1 + 2 + 4 + \dots + 2^{n - 1} = 2^{n} - 1$ 1+2+4+…+2ⁿ⁻¹=2ⁿ-1 (somme géométrique).
Raisonnons par l'absurde : supposons qu'un algorithme raccourcisse tous les fichiers de $n$ n bits. Il envoie $2^{n}$ 2ⁿ fichiers dans un ensemble de $2^{n} - 1$ 2ⁿ-1 fichiers. Par le principe des tiroirs, deux fichiers différents sont envoyés sur le même fichier compressé. Mais alors la décompression ne peut pas savoir lequel retrouver : la compression ne serait pas sans perte. Contradiction.
Conséquence : tout algorithme sans perte qui raccourcit certains fichiers en allonge forcément d'autres (ou les laisse de même taille). Promettre de diviser par deux la taille de la moitié des fichiers est aussi impossible : il n'existe qu'environ $2^{n /2 + 1}$ 2^(n/2+1) fichiers d'au plus $\frac{n}{2}$ n/2 bits, infiniment moins que les $2^{n - 1}$ 2ⁿ⁻¹ fichiers à compresser.
3. NSI : pourquoi la compression marche quand même
3 min
Les fichiers que nous utilisons ne sont pas des mots binaires quelconques : un texte français, une image ou un tableau ont beaucoup de régularités (lettres fréquentes, zones uniformes, répétitions). Les algorithmes comme zip exploitent ces régularités. Ils réduisent les fichiers « structurés », très minoritaires parmi tous les fichiers possibles, et allongent très légèrement les autres.
Un fichier déjà compressé, ou un fichier de bits aléatoires, n'a plus de régularité exploitable : le compresser à nouveau le fait grossir de quelques octets d'en-tête. Les compressions avec perte (JPEG, MP3) échappent à l'argument, car elles ne cherchent pas à retrouver exactement l'original.
4. Conclusion
1,5 min
Aucun logiciel ne peut compresser tous les fichiers sans perte : il y a $2^{n}$ 2ⁿ fichiers de $n$ n bits pour seulement $2^{n} - 1$ 2ⁿ-1 fichiers plus courts. La compression fonctionne parce que nos données sont structurées. J'ouvre sur l'entropie de Shannon, qui mesure précisément cette structure et fixe la limite de la compression.

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.

# {fichiers de n bits} = 2^{n} # {fichiers plus courts} = 1 + 2 + \dots + 2^{n - 1} = 2^{n} - 1 #{ fichiers de n bits }=2ⁿ #{ fichiers plus courts }=1+2+\dots+2ⁿ⁻¹=2ⁿ-1 2^{n} > 2^{n} - 1 \Rightarrow deux fichiers ont la m \overset{e}{ˆ} me image : compression impossible pour tous 2ⁿ>2ⁿ-1 \Rightarrow deux fichiers ont la même image : compression impossible pour tous

Conclusion : la réponse à la question

Un dénombrement suffit à démasquer une promesse impossible. La compression sans perte ne crée pas de place : elle exploite la régularité des données, et allonge forcément les fichiers qui n'en ont pas.

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.

Énoncez le principe des tiroirs.

Si l'on range plus d'objets qu'il n'y a de tiroirs, au moins un tiroir contient deux objets.

Combien de fichiers de moins de 3 bits ?

1 + 2 + 4 = 7, contre 8 fichiers de 3 bits.

Pourquoi un fichier zip grossit-il quand on le recompresse ?

Il n'a plus de régularité exploitable, et le format ajoute un en-tête.

La compression JPEG contredit-elle l'argument ?

Non : elle est avec perte, l'image décompressée n'est pas exactement l'originale.

Quelle part des fichiers de n bits peut-on raccourcir d'au moins 10 bits ?

Il n'y a que $2^{n - 9} - 1$ 2ⁿ⁻⁹-1 fichiers d'au plus $n - 10$ n-10 bits : moins de $\frac{1}{512}$ 1/512 des fichiers, environ 0,2 %.

Les pièges qui coûtent des points

Oublier le fichier vide dans le dénombrement.
Croire qu'un meilleur algorithme pourrait contourner l'argument.
Confondre compression avec perte et sans perte.

Revoir les notions

Autres questions : transmettre et compresser

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 →