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 récente 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 toute fin d'année, après les conseils de classe (donc avec un nombre d'élèves très réduit).

Vu la place de cette séance dans la progression (elle ne s'inscrit pas directement dans le programme) et dans l'année (une des dernières séances), je n'ai 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). J'ai donné les consignes suivantes à l'oral (par manque de préparation plutôt que par choix pédagogique).

Le but de l'exercice est de compresser un texte, sans perte. Par exemple, on veut envoyer un texte à un ami par SMS, mais ce texte est plus grand que la taille d'un seul SMS, et l'abonnement téléphonique ne permet plus d'envoyer qu'un seul message. Nous allons donc le compresser, c'est-à-dire trouver un moyen de faire passer le même message avec moins de caractères.

Trouver une méthode qui permette de réduire le nombre de caractères de ce message.

Contraintes

  • La compression doit être sans perte, c'est-à-dire que le texte décompressé doit être exactement le texte original. Cela interdit, entre autres :
    • l'utilisation de synonymes, paraphrases, reformulations du texte (remplacer « répondit l'animal léger » par « répondit le lièvre ») ;
    • l'orthographe doit être respecté : écrire « parlé » pour « parler », « parlait », « parlaient », « parlées », etc. est un moyen de compression de données par SMS très efficace, mais il entraîne une perte d'information.
  • Pour simplifier le travail, dans les textes donnés, on ignore les titres et nom d'auteur, la casse (majuscule et minuscule), la ponctuation, les accents, voire les retours à la ligne.
  • Les caractères autorisés sont ceux acceptés par SMS (donc on ne peut pas transmettre de dessins).
  • La méthode de compression doit fonctionner sur n'importe quel texte (elle ne doit pas être spécifique à un des textes distribués).

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 à 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

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 ».

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é
3
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