Remarque : Avant d'être professeur, j'ai été informaticien, et j'ai notamment travaillé sur la compression de données. Cela explique ma familiarité avec les algorithmes décrits ici.

Remarque : Une version plus ancienne de cet article existe.

J'ai réalisé cette séance, ou des variations, plusieurs fois, avec différentes classes de lycée général. Je présente la dernière version, effectuée en tout début d'année, comme première séance avec une classe de seconde.

L'année ayant commencé avec un demi-groupe de secondes (et la séance avec l'autre groupe n'arrivant qu'une semaine plus tard), j'ai préféré commencer avec une séance « hors programme » plutôt que de démarrer par le programme ou une séance de révisions de collège.

Je n'ai donc pas cherché à faire le lien entre cette activité et le reste du programme.

Consignes

J'ai distribué aux élèves quelques texte (voir la section Téléchargements en fin d'article) Ces textes sont des poésies, plus ou moins enfantines, contenant beaucoup de répétitions (et permettant de faire un petit lien entre mathématiques et littérature).

La consigne (source) était de trouver une méthode pour compresser des textes autant que possible, sans perte.

Les élèves doivent trouver un moyen de réaliser cette compression, en travaillant par groupes de deux ou trois. Je circule pour aider les élèves qui ont du mal, et commenter les réalisations des élèves. Si deux groupes d'élèves ont terminé l'exercice, je les invite à expliquer (si possible par écrit) à l'autre groupe la méthode de décodage, et lui donner un texte compressé à décoder. Cela permet de vérifier que l'algorithme fonctionne, et que leurs explications ne sont pas ambiguës.

À la fin du temps de travail (une vingtaine de minutes), je sélectionne quelques unes des méthodes, et j'invite les groupes correspondant à l'expliquer au tableau. Je laisse la classe réagir, et je pose des questions (erreurs non décelées) et invite à réfléchir sur des pistes d'amélioration.

J'explique ensuite, en distribuant les textes à décoder, deux algorithmes utilisés en pratique : ceux de Huffman (semi-adaptatif) et Lempel-Ziv. Quand cela s'y prête (la plupart du temps), je leur fait remarquer qu'à peu de choses près, ils ont redécouvert l'algorithme de Huffman, publié en 1952 et toujours utilisé (ou ses variantes) de nos jours.

Ils doivent ensuite décoder les deux textes fournis, pour vérifier qu'ils ont compris le principe.

Suivant le temps et la réceptivité des élèves, je peux aussi leur parler des améliorations des algorithmes utilisés :

Commentaires et analyses

Trop difficile

J'ai peur que cet exercice soit trop compliqué, au moins pour des élèves en début de seconde. Pour résoudre le problème, il faut réussir à écrire un algorithme en langue naturelle, ce que les élèves ont beaucoup de mal à faire : ils n'arrivent pas à écrire des phrases complètes pour décrire leur méthode de décompression, à prendre de la distance par rapport à leurs textes compressés, ou ils imaginent qu'elle est évidente, et ne parviennent pas à expliciter l'évidence.

Je me demande si l'arrivée de l'algorithmique et la programmation dés l'entrée au collège va améliorer cela…

Blocage

Plusieurs élèves ont du mal à démarrer au départ, car ils veulent absolument (inconsciemment) que le texte compressé signifie quelque chose (en français ou en mathématique). Par exemple, ils vont coder « Deux et deux quatre » par « 2+2=4 » plutôt que par « 2 & 2 4 ».

Compression avec perte

Souvent, des groupes proposent des compression avec perte, consistant à altérer l'orthographe pour gagner de la place (en utilisant plus ou moins le langage SMS). Je demande alors à l'ensemble des groupes de décoder la phrase « Le dresseur a éT mangÉ » pour leur montrer qu'une telle méthode de compression (bien qu'efficace dans de nombreux cas) cause une perte d'information. En effet, sans contexte, il est impossible de connaître l'état du dresseur : est-il rassasié (« Le dresseur a été manger ») ou mort (« Le dresseur a été mangé ») ?

Conversion des nombres en chiffres

De nombreux élèves codent le début de Pages d'écriture en écrivant les chiffres en toute lettre : « Deux et deux quatre » devient « 2 et 2 4 ». Bien qu'efficace pour ce texte, cette méthode ne s'applique qu'à ce texte, et est quasiment inutile pour les autres. Je pense donc qu'il serait judicieux de ne pas proposer ce texte aux élèves, qui se focalisent sur cette méthode pourtant non transférable.

Productions

La plupart des élèves s'orientent vers un codage avec dictionnaire : les mots ou groupes de mots les plus fréquents sont repérés par une clef, utilisée plus tard. Par exemple, Déjeuner du matin, de Prévert, devient :

1=Il a
2=mis le
3=Dans la tasse
===
1 2 café
1 2 lait
3 de café
1 2 sucre
Dans le café au lait
Avec la petite cuiller
1 tourné
1 bu le café au lait
Et 1 reposé la tasse
Sans me parler

À partir de là, dans la phase de mise en commun, je propose deux améliorations.

  • Je leurs fait remarquer que pour gagner encore plus de place, on peut utiliser des mots du dictionnaire dans le dictionnaire lui même. Ainsi, puisque la locution « Il a mis le » apparaît plusieurs fois, il peut être intéressant d'ajouter au dictionnaire :

     4=1 2
    
  • Vu la longueur des textes, des clefs d'un seul caractère sont suffisantes pour coder toutes les entrées. Néanmoins, avec des textes plus long, certaines entrées seraient codées avec un seul caractère (un chiffre), et d'autres avec deux (voire plus). Est-ce que les clefs sont données de manière arbitraire ou non ? Généralement, quelques élèves comprennent que les clefs les plus courtes doivent être attribuées aux mots les plus fréquents.

    À ce stade, il est très intéressant de noter que, mis à part la représentation en arbre (un outil qu'il n'ont à priori jamais vu sous cette forme), ils ont redécouvert l'algorithme de Huffman semi-adaptatif (qui est très efficace).

Améliorations

Cette séance tient correctement en une séance de cours. Quelques améliorations sont possibles, mais demandent plus de temps.

  • Une erreur souvent faite en recherche (la recherche scientifique professionnelle) est de mesurer l'efficacité d'un algorithme (une méthode, un procédé, etc.) sur les données de travail. Le risque est d'obtenir un algorithme qui est très adapté aux données de travail, mais beaucoup moins efficace pour le reste. Pour pallier cela, le professeur peut ne pas distribuer tous les textes au départ, et en donner de nouveaux lorsque les élèves ont des algorithmes à tester.

  • Un des gros avantages de l'enseignement de l'algorithmique est qu'il est souvent assez facile de mettre en place de la correction par les élèves eux-mêmes. Si les élèves testent les algorithmes de leurs camarades, des erreurs peuvent être décelées, non pas parce que le professeur, autorité supérieure meilleure en math, l'a décidé, mais simplement parce que ça ne fonctionne pas. Appliqué à cet exercice, cela donnerait le mécanisme suivant (avec trois groupes, mais facilement extensible à plus).

    1. Les groupes disposent d'un temps pour inventer un algorithme de compression.
    2. Le groupe A explique cet algorithme au groupe B.
    3. Le professeur distribue un nouveau texte au groupe B, qui doit le compresser en utilisant l'algorithme du groupe A.
    4. Optionnel : Le groupe A peut récupérer une copie du texte compresser pour vérifier si l'algorithme a bien été appliqué.
    5. Le groupe A explique l'algorithme au groupe C.
    6. Le groupe C reçoit le texte compressé par le groupe B, et le décompresse.
    7. On compare le texte compressé-décompressé au texte original, et on commente l'algorithme (erreurs ? ambiguïtés ?).

Téléchargements