Vidéo : Binaire, Hanoï et Sierpinski, 1re partie

Transcription de vidéo

Aujourd’hui, je veux partager avec vous un moyen élégant de résoudre le casse-tête des tours de Hanoï, simplement en comptant dans un système de numérotation différent. Et étonnamment, cela concerne la recherche d’une courbe qui remplisse le triangle de Sierpinski.

J’ai appris cela de l’un de mes anciens conférenciers. Il s’appelle Keith Schwarz. Et je dois dire que cet homme est l’un des meilleurs éducateurs que j’ai jamais rencontré. En fait, j’ai enregistré un peu de la conversation où il m’a montré ce genre de choses. Vous pouvez donc entendre une partie de ce qu’il a décrit directement.

KEITH : C’est bizarre. Je ne suis pas normalement le genre de personne qui aime les petits casse-tête et les jeux. Mais j’adore regarder l’analyse des puzzles et des jeux. Et j’adore regarder uniquement les schémas mathématiques et d’où vient-il ?

Au cas où vous ne le connaissez pas, décrivons simplement le casse-tête des tours de Hanoï.

KEITH : Donc, vous avez une collection de trois piquets. Et vous avez ces disques de taille décroissante.

Vous pensez que ces disques ont un trou au milieu, de sorte que vous pouvez les installer sur une cheville. Le jeu que je représente ici comprend cinq disques, que je nommerai zéro, un, deux, trois, quatre. Mais en principe, vous pouvez avoir autant de disques que vous le souhaitez.

KEITH : Donc, ils commencent tous empilés du plus grand au plus petit sur une broche. Et le but est de déplacer la tour entière d’un fuseau à l’autre. La règle est que vous ne pouvez déplacer qu’un disque à la fois. Et vous ne pouvez pas déplacer un disque plus gros sur un disque plus petit.

Par exemple, votre premier déplacement doit impliquer le déplacement du disque zéro, car tout autre disque est recouvert d’éléments qui doivent être écartés avant de pouvoir être déplacés. Après cela, vous pouvez déplacer le disque un. Mais il doit continuer avec tout ce qui ne possède pas actuellement le disque zéro. Sinon, vous placeriez un disque plus gros sur un disque plus petit, ce qui n’est pas autorisé. Si vous n’avez jamais vu cela auparavant, je vous encourage fortement à faire une pause et à sortir des livres de différentes tailles et à les essayer vous-même. Juste un peu avoir une idée de ce que le puzzle est. Si c’est difficile, pourquoi c’est difficile. Si ce n’est pas le cas, pourquoi ne l’est-il pas ?

Maintenant, Keith m’a montré quelque chose de vraiment surprenant à propos de ce casse-tête : vous pouvez le résoudre simplement en comptant en binaire et en associant le rythme de ce compte à un certain rythme de mouvements de disque. Pour ceux qui ne connaissent pas le binaire, je vais prendre un moment pour faire un bref aperçu ici. En fait, même si vous êtes familier avec le binaire, je voudrais l’expliquer en mettant l’accent sur le rythme de comptage, auquel vous avez peut-être déjà pensé ou pas.

Toute description de binaire commence généralement par une introspection sur notre façon habituelle de représenter des nombres, ce que nous appelons la base 10, puisque nous utilisons 10 chiffres distincts. Zéro, un, deux, trois, quatre, cinq, six, sept, huit, neuf. Le rythme de comptage commence en parcourant chacun des 10 chiffres. Puis, étant à court de nouveaux chiffres, vous exprimez le nombre suivant, 10, avec deux chiffres : un, zéro. Vous dites que l’un se situe à la place des dizaines, car il est destiné à encapsuler le groupe de 10 que vous avez déjà compté jusqu’à présent, tout en libérant l’emplacement pour les remettre à zéro.

Le rythme de comptage se répète comme ceci : compter jusqu’à neuf, basculer vers la place des dizaines, compter jusqu’à neuf autres, rouler jusqu’à la place des dizaines, etc. Jusqu’à ce que, après avoir répété ce processus neuf fois, vous passez à des centaines d’endroits. Un chiffre qui garde la trace du nombre de groupes de 100 que vous avez touchés, libérant les deux autres chiffres pour les remettre à zéro. De cette façon, le rythme de comptage est un peu semblable à soi. Même si vous effectuez un zoom arrière à plus grande échelle, le processus ressemble à faire quelque chose, basculer, refaire la même chose, basculer et répéter neuf fois avant un basculement encore plus important.

En binaire, également appelé base deux, vous vous limitez à deux chiffres, zéro et un, communément appelés bits, qui est l’abréviation de binary digits. Le résultat est que lorsque vous comptez, vous devez passer tout le temps dessus. Après avoir compté zéro, un, vous êtes déjà à court de bits. Vous devez donc passer à la place des deux, écrire un, zéro et résister à toutes les envies de votre cerveau entraîné en base 10 pour lire ceci comme 10. Et à la place, comprenez que cela signifie un groupe de deux plus zéro. Ensuite, incrémentez jusqu’à un, un, ce qui représente trois. Et déjà, vous devez encore rouler. Et puisqu’il y en a un à la place de deux, il doit également être reporté, ce qui vous donne un, zéro, zéro, ce qui représente un groupe de quatre plus zéro groupes de deux plus zéro.

De la même manière que les chiffres en base 10 représentent des puissances de 10, les bits en base deux représentent des puissances différentes de deux. Ainsi, au lieu de parler de lieux de dizaines, de centaines, de milliers, etc., vous parlez de deux, de quatre et de huit. Le rythme de comptage est maintenant beaucoup plus rapide. Mais cela le rend presque plus visible. Retournez le dernier, roulez une fois, retournez le dernier, roulez deux fois, retournez le dernier, roulez une fois, retournez le dernier, roulez trois fois. Encore une fois, il y a une certaine auto-similitude à ce modèle.

À toutes les échelles, le processus consiste à faire quelque chose, à basculer, puis à refaire la même chose. À petite échelle, disons en comptant jusqu’à trois — ce qui est un, un en binaire — cela signifie que vous inversez le dernier bit, passez au deuxième, puis inversez le dernier bit. À plus grande échelle, comme en comptant jusqu’à 15 — ce qui correspond à un, un, un, un en binaire — le processus consiste à laisser les trois derniers compter jusqu’à sept. Rendez-vous à la place des huit. Ensuite, laissez les trois derniers bits compter à nouveau. En comptant jusqu’à 255, ce qui correspond à huit successives, il semblerait que les sept derniers bits soient comptés jusqu’à ce qu’ils soient pleins, se déplaçant à la place des 128. Ensuite, laissez les sept derniers bits compter à nouveau.

Bon, avec cette mini introduction, le fait surprenant que Keith m’a montré est que nous pouvons utiliser ce rythme pour résoudre les tours de Hanoï. Vous commencez par compter à partir de zéro. Chaque fois que vous ne faites que basculer ce dernier bit d’un zéro à un, déplacez le disque zéro d’un pion vers la droite. S’il se trouvait déjà sur le pion le plus à droite, il vous suffit de le renvoyer au premier pion. Si dans votre comptage binaire, vous passez une fois à la place des deux, ce qui signifie que vous retournez les deux derniers bits, vous déplacez le disque numéro un. «Où le déplacez-vous ?», Pourriez-vous demander.

Eh bien, vous n’avez pas le choix. Vous ne pouvez pas le placer sur le disque zéro. Et il n’y a qu’une seule autre cheville. Donc, vous le déplacez là où vous êtes obligé de le faire. Donc après cela, en comptant jusqu’à un, un, cela implique simplement d’inverser le dernier bit. Donc, vous déplacez le disque zéro à nouveau. Ensuite, lorsque votre comptage binaire revient deux fois à la place du quatre, déplacez le disque numéro deux. Et le motif continue comme ça. Retournez le dernier, déplacez le disque zéro. Retournez les deux derniers, déplacez le disque un. Retournez le dernier, déplacez le disque zéro. Et ici, il va falloir rouler trois fois à la place des huit. Et cela correspond au disque numéro trois.

KEITH : Il y a quelque chose de magique à ce sujet. Comme quand j’ai vu ceci pour la première fois, comme : « ça ne peut pas marcher ». Comme je ne sais pas comment ça marche. Je ne sais pas pourquoi ça marche. Maintenant je sais, mais c’est juste magique quand on le voit. Et je me souviens d’avoir mis l’autre animation pour cela quand je l’enseignais. Et comme vous savez, je sais comment cela fonctionne. Je sais tout ce qu’il y a dedans. C’est toujours amusant de simplement s’asseoir et juste comme, vous savez,...

GRANT : Regardez-le jouer ?

KEITH : Oh oui.

Je veux dire, il n’est même pas clair au début que cela va toujours donner des coups légaux. Par exemple, comment savez-vous que chaque fois que vous passez à la place des huit, ce disque trois sera nécessairement libéré pour pouvoir être déplacé ?

KEITH : Dans le même temps, la solution a immédiatement soulevé ces questions. Comme, d’où ça vient ? Pourquoi ça marche ? Et est-il une meilleure façon de le faire alors, d’avoir à faire deux aux 𝑛 moins une des étapes ?

Il s’avère que cela ne résout pas seulement les tours de Hanoï. Mais il le fait de la manière la plus efficace possible. Comprendre pourquoi cela fonctionne, comment ça marche et ce qui se passe, revient à une certaine perspective du puzzle, ce que les gens de CS pourraient appeler une perspective récursive.

KEITH : Le disque trois se dit : « Ok, deux, un et zéro »! Comme : « Tu dois te faire-Tu dois te sortir de moi »! Comme : « Je ne peux pas, je ne peux pas vraiment fonctionner sous autant de poids et de pression ». Et donc, du point de vue du disque trois, si vous voulez comprendre comment le disque trois va arriver ici, je me fiche de savoir comment, les disques deux, un et zéro doivent arriver à cette broche B. C’est la seule façon pour eux de bouger. Si l’un de ces disques se trouve sur trois, il ne peut pas bouger. Si l’un d’entre eux est dans la broche C, il ne peut pas y aller. Donc, d’une manière ou d’une autre, nous devons en avoir deux, un et zéro. Cela fait, nous pouvons déplacer le disque trois là-bas. Et puis le disque trois dit : « Je suis prêt. Tu n’as plus besoin de me déplacer. Tout le monde trouve comment arriver ici ».

KEITH : Et dans un sens, vous avez maintenant une version plus petite du même problème. Maintenant, vous avez les disques zéro, un et deux assis sur la broche B. Nous devons les amener à C. Donc l’idée est que si je me concentre sur un disque et que je pense à ce que je vais devoir faire pour l’obtenir Pour que le disque fonctionne, je peux transformer mon plus gros problème en quelque chose de légèrement plus petit. Et puis comment résoudre ce problème ? Eh bien, c’est exactement la même chose. Le disque deux va dire : « Le disque un, le disque zéro, vous devez, vous savez. Ce n’est pas toi ; c’est moi. J’ai juste besoin d’un peu d’espace. Descendez »!

KEITH : Ils doivent déménager quelque part. Ensuite, le disque deux peut se déplacer là où il doit aller. Ensuite, les disques un et zéro peuvent le faire. Mais ce qui est intéressant, c’est que chaque disque a exactement la même stratégie. Ils disent tous : « Tout le monde au-dessus de moi, descends ! Et puis je vais bouger. Ok, tout le monde, continuez ». Lorsque vous connaissez cette idée, vous pouvez coder quelque chose qui résoudra Tours de Hanoï en cinq ou six lignes de code, ce qui représente probablement le rapport d’investissements intellectuels par rapport aux lignes de code jamais atteint.

Et si vous y réfléchissez un peu, il devient évident que cela doit être la solution la plus efficace. À chaque étape, vous ne faites que ce qui vous est imposé. Vous devez retirer les disques de zéro à deux avant de pouvoir déplacer le disque trois. Et vous devez déplacer le disque trois. Ensuite, vous devez déplacer les disques de zéro à deux. Il n’y a tout simplement aucune marge d’inefficacité de ce point de vue. Alors pourquoi compter en binaire capture cet algorithme ?

Eh bien, ce qui se passe ici est que ce modèle de résolution d’un sous-problème, de déplacer un grand disque, puis de résoudre à nouveau un sous-problème, est parfaitement mis en parallèle avec le modèle de comptage binaire. Comptez un montant, roulez, comptez à nouveau jusqu’à ce même montant. Et cet algorithme et le comptage binaire des tours de Hanoï sont des processus auto-similaires, en ce sens que si vous effectuez un zoom arrière et comptez jusqu’à une puissance de deux, ou si vous résolvez des tours de Hanoï avec plus de disques, ils ont toujours la même structure : sous-problème, faire une chose, sous-problème.

Par exemple, à une assez petite échelle, la résolution de Tours de Hanoï pour deux disques -déplacer le disque zéro, déplacer le disque un, déplacer le disque zéro- est reflétée en comptant jusqu’à trois en binaire. Retournez le dernier bit, retournez une fois, retournez le dernier bit. À une échelle légèrement plus grande, résoudre Tours de Hanoï pour trois disques ressemble à faire tout ce qu’il faut pour résoudre deux disques, déplacer le disque numéro deux. Ensuite, faites ce qu’il faut pour résoudre deux disques à nouveau. De manière analogue, compter jusqu’à un, un, un en binaire implique de compter jusqu’à trois, de parcourir les trois bits, puis de compter trois autres. À toutes les échelles, les deux processus ont la même panne.

KEITH : Donc, dans un sens, la raison pour laquelle cette solution binaire fonctionne ou au moins une explication-je me sens comme, vous savez, il n’y a pas une explication. Mais je pense que le plus naturel est que le modèle que vous utiliseriez pour générer ces nombres binaires a exactement la même structure que celui que vous utiliseriez pour Tours de Hanoï. C’est pourquoi, si vous regardez les bits qui se retournent, vous inversez effectivement ce processus. Vous dites quel processus a généré ces. Comme si j’essayais de comprendre comment ces bits ont été inversés pour me donner cette chose, vous effectuez un reverse engineering de l’algorithme récursif des Tours de Hanoï, ce qui explique pourquoi cela fonctionne.

C’est plutôt cool, non ? Mais en fait, il fait plus frais ! Je n’ai même pas compris en quoi cela se rapporte au triangle de Sierpinski. Et c’est exactement ce que je vais faire dans la vidéo suivante, deuxième partie. Bon, avec ça, je vous verrai à la prochaine vidéo. Et je pense que vous allez vraiment aimer où ça va.