tous les documents
  • tous les documents
  • Images
  • Films
  • Rushes
  • Publications
  • Audio
Recherche avancée
Ensemble de recherche :
tous les documents
  • tous les documents
  • Images
  • Films
  • Rushes
  • Publications
  • Audio
Recherche par couleur
Ensemble de recherche :
tous les documents
  • tous les documents
  • Images
  • Films
  • Rushes
  • Publications
  • Audio
Code HTML Copiez-collez le code ci-dessous pour l'intégrer dans une page Web.
Titre :
Marie Duflot, informatique débranchée : comprendre l'algorithme de Huffman avec les marmottes au sommeil léger.
Légende - Résumé :
Comprendre l'informatique en jouant : comprendre l'algorithme de Huffman avec les marmottes au sommeil léger. L'informatique débranchée permet de s’initier aux algorithmes, à la vérification, à la détection d’erreurs, etc. sans ordinateur.
Avec Marie Duflot-Kremer, maître de conférence à l'Université de Lorraine, membre de l'équipe VERIDIS du centre Inria Nancy - Grand Est et du LORIA.
Nom de fichier :
Inria-1048_MarieDuflot_LesMarmottes_VF.mp4
Titre :
Marie Duflot, informatique débranchée : comprendre l'algorithme de Huffman avec les marmottes au sommeil léger.
Année :
2016
Durée (min) :
00:17:36
Publications :
https://videotheque.inria.fr/videotheque/doc/1048
Autres versions :
Master VF : 1048
Master VEN :
Autre : Lien externe :
Lien Equipe-projet :
Lien Centre de Recherche :
Mots clés :
N° master :
1048
Durée :
17 min 36 sec
IsyTag :
= - 1 - 15 - 2 - 3 - 30 - 4 - 5 - 6 - 8 - algorithme - arbre - c' - celle-ci - code - couloir - déplacement - foi - Huffman - lettre - marmotte - marmottes - nombre - terrier - texte
Transcription automatiqu :
L'idée c'est qu'on a une colonie marmottes qui doivent recreuser un nouveau terrier pour l'hiver Mais il y a quelques règles à respecter La première c'est que - mettons que là c'est l'entrée du terrier - on ne peut faire que deux couloirs qui mènent à cette entrée sinon on risque un effondrement du terrain Donc après à partir du bout du couloir bien sûr on peut recreuser deux nouveaux couloirs et puis continuer comme ça notre terrier Les autres contraintes sont dues au fait que les marmottes ont le sommeil léger Et donc il est totalement impensable de mettre une marmotte ici sachant qu'après par ces couloirs-là d'autres marmottes pourront passer Donc nos marmottes le seul endroit où on peut les mettre c'est au bout d'un couloir et là ne plus creuser dans la suite Et puis il y a une dernière chose comme elles ont vraiment le sommeil léger à chaque fois qu'elle se réveille dans l'hiver elles vont devoir parcourir tout le chemin qui les amène jusqu'à la sortie et sur chaque marmotte il y a un nombre ici qui représente le nombre de fois que cette marmotte se lève dans l'hiver Donc le but du jeu c'est à vous d'essayer de construire le terrier de telle sorte que si je compte le nombre de fois où elle se réveille multiplié par le nombre de morceaux de chemin qu'elle doit faire et puis je fais ça pour toutes les marmottes que le total sur le plus petit possible Si c'est pas clair vous m'appelez et je vous explique sinon allez-y Donc typiquement cette marmotte-ci ne va se lever que deux fois donc ce n'est pas très grave de la mettre au bout d'un couloir d'un ensemble de couloirs assez longs alors que celle-ci qui se réveille huit fois dans hiver si on la met au bout d'un long couloir par exemple ici elle va se lever huit fois et pendant les huit fois où elle se lève elle va à chaque fois parcourir trois morceaux de couloir aller et retour Donc si on veut compter le nombre de pas qu'elle fait on va compter en couloirs donc ça va faire 3 x 8 = 24 morceaux de couloir aller retour Donc c'est pas très rentable peut-être que cette marmotte-là on voudra la mettre plus près de l'entrée Si on la met ici elle va faire juste 8 morceaux de couloir aller retour Donc l'idée c'est de construire le terrier avec différents morceaux de couloirs et d'y placer les marmottes de sorte que le nombre de déplacements soit le plus petit possible Donc sur ce terrier cette marmotte qui se réveille 7 fois elle va faire 7 x 3 21 déplacements Celle-ci 2 x 3 = 6 21 et 6 = 27 Celle-là elle va faire 3 x 3 = 9 27 et 9 = 36 Celle-ci 3 x 5 = 15 36 et 15 = 51 et 8 = 59 mais on pourrait essayer de faire un autre terrier par exemple je rapproche un peu celle-ci de l'entrée et cette fois-ci et ça sera 1 2 3 4 X 3 = 12 12 et 20 32 32 et 6 38 38 et 14 48 52 et 8 60 Et on peut expérimenter et tester pleins de terriers différents La question est comment on peut faire le meilleur terrier Eh ben pour ça il y a un algorithme une méthode qui va marcher à chaque fois et qui va nous trouver le terrier qui va minimiser le nombre de déplacements des marmottes On va commencer par choisir les deux marmotte qui se lèvent le moins souvent dans l'hiver et on va les accrocher ensemble Donc ici c'est marmotte deux fois et cette marmotte trois fois et maintenant à cet ensemble de marmottes on va y donner un poids c'est-à-dire le nombre de fois où à elles deux elles vont se lever pendant l'hiver Ici c'est cinq fois ces deux marmottes se réveillent cinq fois Et on va prendre ce bloc de marmottes ici ce début de terrier comme si c'était une marmotte Et maintenant dans nos 1 2 3 4 marmottes ou ensemble de marmottes on va choisir les deux qui lèvent le moins souvent Et ici c'est celle-ci qui se lève cinq fois et celle-là cinq fois donc encore une fois on va les raccrocher ensemble et puis sur le haut ici on va noter le nombre de fois où elles se lèvent ici c'est dix fois Et donc maintenant j'ai un ensemble de marmottes qui se lèvent dix fois et puis une marmotte sept fois une marmotte huit fois donc on va mettre ensemble ces deux marmottes Et ici on va noter le nombre de fois où elle se réveille c'est-à-dire 15 fois Et maintenant il ne nous reste plus que deux ensembles de marmottes donc je n'ai plus qu'à les relier Et au final si je fais la somme ici c'est donc 25 x C'est le nombre de fois où toutes mes marmottes vont se réveiller pendant l'hiver Et si je veux compter le nombre de déplacements je peux faire comme tout à l'heure compter que 3 x 3 ça fait 9 + 3 x 2 6 etc Ou alors je peux compter les nombres qui sont écrits ici Si je fais la somme de ces nombres-là je vais avoir le nombre de déplacements au total Donc ça fait 25 et 15 = 40 50 55 pourquoi ça marche parce que ici Comme celle-là se déplace deux fois et celle-là se déplace trois fois ces deux couloirs ici vont être au total empruntés cinq fois trois fois ici et deux fois là Et maintenant ici ces couloirs ici vont être empruntés dix fois cinq fois celui-ci est cinq fois celui-là et si on continue pareil ici 7 fois celui-ci plus 8 fois celui-là ça fait 15 fois ces deux couloirs Et ici 15 fois ce couloir-là plus 10 fois ce couloir-là ça fait que ces deux couloirs ensemble vont être empruntés 25 fois Donc en faisant la somme ici le nombre de déplacements au total Donc on vient de voir qu'on avait 50 cinq déplacements c'est toujours mieux que les valeurs qu'on avait tout à l'heure Et même il y a des gens qui ont prouvé que cette façon de faire un terrier est la meilleure pour diminuer au maximum pour minimiser les déplacements dans les couloirs parce que les marmottes à chaque fois qu'elles se déplacent elles font du bruit avec leurs petites pattes et ça risquerait de réveiller leurs congénères Sur un exemple plus grand on va voir ce que ça pourrait donner Je n'ai plus 5 mais 8 marmottes avec chacune le nombre de fois où elle se réveille dans l'hiver et puis j'ai toujours des couloirs pour faire mon terrier Donc je vais appliquer la même méthode Donc là le moins de fois où les marmottes peuvent se réveiller c'est deux fois ces deux marmottes-là je vais les relier et puis je vais noter ici quatre fois Ensuite si je regarde ce qui me reste j'ai 5 5 6 c'est trop grand c'est trop grand Ici j'ai une marmotte qui se réveille 4 fois une 2 fois et une 4 fois et ici 4 fois aussi Donc je vais relier cette marmotte-là avec au choix celle-ci celle-ci ou cet ensemble-là Ici je relie ces marmottes-là et puis 2 et 4 je note 6 ici Ensuite si je regarde ce qui me reste Donc j'ai un ensemble de marmottes 4 fois et une marmotte 4 fois C'est le moins que j'ai Je vais les relier quatre et quatre ça fait huit je note 8 ici au croisement Ca fait au total 30 Et 30 c'est bien la somme des valeurs qui sont écrites sur chacune des marmottes Si je veux calculer ici le nombre de fois où elles se réveillent à elles toutes comme tout à l'heure je fais la somme 30 et 12 42 60 66 76 84 88 Donc l'ensemble mes marmottes va se réveiller 88 fois Sur cet exemple on va essayer de voir comment cet arbre est plus efficace que les autres On va essayer d'autres arbres Alors une chose que les informaticiens pourraient essayer de faire dans ces cas-là c'est faire un arbre où toutes les branches ont la même longueur Donc par exemple ici si jamais j'échange ces deux morceaux ici toutes les marmottes sont à distance 3 de la sortie Et donc si maintenant je fais la somme des valeurs écrites sur mes chemins ça fait 10 et 10 = 20 20 et 30 50 60 70 80 j'ai une valeur de 90 Une autre chose qui pourrait être essayée c'est d'essayer de mettre au plus près de la sortie ceux qui se déplacent le plus donc comme ça je mets celui qui se déplace le plus au plus près de la sortie Et puis ensuite le deuxième plus près de la sortie sera celui qui se déplace 5 fois voilà et je continue Voilà si je fais la somme des déplacements 6 et 4 10 20 34 53 77 et 30 107 On a donc 107 déplacements dans les couloirs du terrier ce qui est beaucoup moins efficace que le terrier de tout à l'heure qui était fait en suivant notre algorithme Là on revient à l'arbre optimal c'est pas exactement le même de tout à l'heure parce qu'on a plusieurs façons par exemple si j'échange ces branches de terrier ici et avec celui là ça fera exactement le même nombre de déplacements donc pour un informaticien ça ça ne s'appelle pas un terrier ça s'appelle un arbre Un arbre c'est quoi C'est un objet qui a un racine ici c'était l'entrée de mon terrier et puis ensuite des branches qui partent dans différents sens et telles que il n'y a jamais de cycles c'est-à-dire un endroit où deux branches qui sont séparées vont se rejoindre alors les choses au bout des branches ici en informatique ça s'appelle des feuilles Le départ ici ça s'appelle une racine Alors le truc rigolo c'est que pour un informaticien la racine en général elle est en haut des arbres et les feuilles sont en bas Mais modulo un torticolis ça ressemble assez à un arbre standard Maintenant c'est bien gentil on a créé des terriers pour ces marmottes Elles ne vont pas beaucoup se réveiller elles ne vont pas beaucoup se déplacer Mais la question est quel est le lien avec l'informatique Eh ben le lien avec l'informatique il est de l'autre côté Cet algorithme qui permet de construire ce que moi j'appelle un arbre s'appelle l'algorithme de Huffman Et donc le codage qui va avec c'est le codage de Huffman Bien sûr vous n'utilisez pas ça tous les jours sauf que si mais vous le savez pas Dès que vous compresses en zip dès que vous utilisez de la musique qui est compressée en mp3 un film en mpeg Dans tous ces trucs de compression y'a Huffman dernière Ici et là tout de suite ça fait plus informaticien parce qu'il y a des zéros et des uns dessus Eh ben cet arbre il est utilisé en informatique pour faire de la compression de textes Si vous regardez sur au dos de chacune des marmottes il y a une lettre et il a écrit le nombre de fois où cette lettre apparaît dans un texte Si vous prenez la phrase très très utile qui est Barbara a rasé Basile le barbier Prenez cette phrase-là et ous notez toutes les lettres et vous comptez combien de fois elles apparaissent dans le texte Barbara a rasé Basile le barbier Eh bien c'est exactement ce qui est écrit ici Donc il y a 6A 5R 2I 2L 4E 2S 4 signes espace et 5B Et maintenant en règle générale quand on code un texte on le code avec le code ASCII Le code ASCII consiste à donner huit chiffres binaires zéro ou un pour chaque lettre Mais ça c'est pas le plus efficace Parce que ce qu'on a vu avec nos marmottes c'est que les marmottes qui se réveillaient le plus souvent il fallait qu'elles soient proches de la sortie Dans un texte ça veut dire que les lettres qui apparaissent le plus souvent dans notre texte lettre ou caractère doivent avoir le code le plus court possible Et bien ici sur cet arbre je peux lire le code de chacune des lettres Ici le choix de code pour A ce serait 0 0 le choix de code pour L ce serait 1 1 1 et 1 Et on voit que la lettre L a un code plus long que la lettre A parce qu'elle apparaît deux fois au lieu de six dans notre texte Donc donner Huit signes binaires ou le même nombre pour toutes les lettres ce n'est pas efficace si certaines lettres sont plus fréquentes que d'autres Donc ce n'est pas grave de donner un code plus long dans mon texte à L puisque le L apparaît moins souvent si j'avais donné des codes de même longueur pour toutes les lettres on a vu que toutes les lettres auraient eu un code de taille 3 et la taille totale de mon texte écrit avec des chiffres binaires ça aurait été 90 En suivant cet arbre-là on se retrouve avec des lettres qui on un code plus petit que 3 des lettres qui un code plus grand que 3 mais au final la taille totale du texte c'est-à-dire 6 fois un code de taille 2 plus 4 fois un de taille 3 etc ça va être plus compact et ça va prendre moins de place en mémoire Alors ici le gain n'est pas si grand parce que c'était 88 par rapport à 90 mais quand vous avez des textes beaucoup plus grands et donc avec beaucoup plus de lettres ce serait pas sur trois chiffres binaires qu'on devrait écrire chaque lettre mais sur huit Et donc du coup le gain obtenu par cette méthode est beaucoup plus grand en particulier j'ai testé sur le texte de Cyrano de Bergerac Le gain est de 40% on a presque gagné la moitié de la taille du texte en appliquant cette méthode Si vous vous rappelez des contraintes une lettre un code on peut pas faire mieux que ça Et tout ça avec des marmottes Dans l'activité on peut faire un parallèle entre les règles qu'on a imposé et l'utilité que ça d'un point de vue informatique Par exemple le fait de ne pouvoir creuser que deux chemins à partir d'un même point eh bien ça c'est lié au fait que le code qu'on fait après étant binaire il y a deux branches 0 et 1 et donc il ne faut que deux couloirs dans le terrier La deuxième chose que je vous ai dit c'est que on ne pouvait pas faire dormir une marmotte au milieu d'un couloir Eh bien ça c'est très important pour le codage parce que si on fait dormir une marmotte au milieu d'un couloir ça voudrait dire qu'il y a une lettre dont le code est le début du code d'une autre lettre Si on ne respecte pas cette règle-là il peut y avoir pour un même texte en binaire compressé plusieurs textes correspondant Et ça on ne veut absolument pas l'avoir Et la troisième chose qu'on avait dit c'est qu'on voulait minimiser les déplacements des marmottes Eh bien ça on voit bien à quoi ça correspond ça correspond au fait que les lettres qui sont les plus fréquentes doivent avoir les codes les plus courts pour qu'au final le texte compressé soit le plus court possible Il faut savoir que cet algorithme il est pas juste présenté parce qu'il est facile d'utilisation En fait c'est un algorithme qui premièrement est le plus efficace pour la compression une lettre un code On peut pas faire mieux que cet algorithme de Huffman Si on veut faire mieux que ça alors il faut trouver d'autres manières de faire par exemple utiliser un bloc de lettres qu'on utilise souvent par exemple LES L E S et trouver un code qui correspond à un bloc de lettres et en pratique cet algorithme est utilisé dans de nombreux programmes de compression Par exemple si vous envoyez des fichiers zip dedans l'une des composantes de cette compression est l'algorithme de Huffman C'est pareil pour les images ou pour la vidéo Il y a une première étape qui est propre aux types de données par exemple aux images aux sons aux textes et ensuite à la fin il y a un algorithme de Huffman qui est appliqué Une des choses qui est bien avec cette activité des marmottes au sommeil léger c'est qu'on peut la faire avec un public assez varié L'expérimentation et le fait d'essayer de jouer à trouver le terrier le plus optimal pour les marmottes peut se faire dès l'âge de primaire Mais on peut faire des extensions par exemple partir du texte trouver les fréquences d'apparition et continuer jusqu'à la réalisation de l'arbre avec un public plus âgé qui profitera plus de toutes les facettes de cette activité
Inria-1048_MarieDuflot_LesMarmottes_VF.mp4

Format : .mp4
766,7 Mo
1920 x 1080 pixels
Inria-1048_MarieDuflot_L_HD.MP4

Format : .mp4
645,8 Mo
1024 x 576 pixels
Moyenne définition - équivalent DVD
Encodage PAL .MP4 H264
5 Mbits/s
Sélection
Voir Selection
Déposer ici pour retirer de la sélection