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.