Vídeo: Binário, Hanói e Sierpinski, Parte 1

Grant Sanderson • 3Blue1Brown • Boclips

Binário, Hanói e Sierpinski, Parte 1

12:35

Transcrição do vídeo

Hoje, quero compartilhar com você uma maneira elegante de resolver o quebra-cabeça das Torres de Hanói, contando apenas em um sistema numérico diferente. E, surpreendentemente, esse material está relacionado à descoberta de uma curva que preenche o triângulo de Sierpinski.

Eu aprendi sobre isso com um ex-professor meu de CS. O nome dele é Keith Schwarz. E eu tenho que dizer, esse homem é um dos melhores educadores que eu já conheci. Na verdade, gravei um pouco da conversa em que ele me mostrou essas coisas. Então vocês podem ouvir um pouco do que ele descreveu diretamente.

KEITH: É estranho. Normalmente, não sou o tipo de pessoa que gosta de pequenos quebra-cabeças e jogos. Mas eu adoro olhar para a análise de quebra-cabeças e jogos. E eu amo apenas olhar para padrões matemáticos e — de onde isso veio?

Caso você não esteja familiarizado, vamos definir o que realmente é o quebra-cabeça das Torres de Hanói.

KEITH: Então você tem uma coleção de três pinos. E você tem esses discos de tamanho decrescente.

Você pensa nesses discos como tendo um orifício no meio, para encaixá-los em um pino. O conjunto que imaginei aqui tem cinco discos, que vou rotular de zero, um, dois, três, quatro. Mas, em princípio, você pode ter quantos discos quiser.

KEITH: Então, todos começam empilhados do maior para o menor em um pino. E o objetivo é mover a torre inteira de um eixo para outro. A regra é que você só pode mover um disco de cada vez. E você não pode mover um disco maior em cima de um disco menor.

Por exemplo, sua primeira jogada deve envolver a movimentação do disco zero, pois qualquer outro disco possui itens que precisam sair do caminho antes que possam se mover. Depois disso, você pode mover o disco um. Mas tem que continuar em qualquer pino que não possua disco zero no momento. Como, caso contrário, você colocaria um disco maior em um menor, o que não é permitido. Se você nunca viu isso antes, recomendo que você faça uma pausa e retire alguns livros de tamanhos variados e experimente você mesmo. Apenas sinta o que é o quebra-cabeça. Se é difícil, porque é difícil. Se não é, porque não é, essas coisas.

Agora, Keith me mostrou algo verdadeiramente surpreendente sobre esse quebra-cabeça, que é que você pode resolvê-lo apenas contando em binário e associando o ritmo daquele contando a um certo ritmo de movimentos do disco. Para qualquer pessoa que não esteja familiarizada com o binário, levarei um momento para fazer uma rápida visão geral aqui primeiro. Na verdade, mesmo se você estiver familiarizado com o binário, quero explicá-lo com foco no ritmo da contagem, no qual você pode ou não ter pensado antes.

Qualquer descrição de binário normalmente começa com uma introspecção sobre nossa maneira usual de representar números, o que chamamos de base 10, pois usamos 10 algarismos separados. Zero, um, dois, três, quatro, cinco, seis, sete, oito, nove. O ritmo da contagem começa percorrendo todos esses 10 algarismos. Depois de ficar sem novos algarismos, você expressa o próximo número, 10, com dois algarismos: um, zero. Você diz que um está no lugar das dezenas, pois serve para encapsular o grupo dos 10 que você já contou até o momento, enquanto libera o lugar dos que são redefinidos para zero.

O ritmo da contagem se repete assim: contar nove, rolar para a casa das dezenas, contar mais nove, rolar para a casa das dezenas, etc. Até depois de repetir esse processo nove vezes, você passa para centenas. Um algarismo que monitora quantos grupos de 100 você atingiu, liberando os outros dois algarismos para redefinir para zero. Dessa maneira, o ritmo da contagem é meio auto semelhante. Mesmo que você reduza o zoom para uma escala maior, o processo parece fazer algo, rolando, fazendo a mesma coisa, rolando e repetindo nove vezes antes de uma rolagem ainda maior.

Em binário, também conhecido como base dois, você se limita a dois algarismos, zero e um, comumente chamados de bits, abreviação de algarismos binários. O resultado é que, quando você conta, precisa rolar o tempo todo. Depois de contar zero, você já ficou sem bits. Portanto, você precisa rolar para o lugar do dois, escrevendo um, zero e resistindo a todos os impulsos do seu cérebro treinado na base 10 para ler isso como 10. E, em vez disso, entenda que isso significa um grupo de dois mais zero. Em seguida, incremente até um, um, o que representa três. E já, você precisa rolar novamente. E como existe um naquele lugar, isso também deve rolar, fornecendo um, zero, zero, o que representa um grupo de quatro mais zero grupos de dois mais zero.

Do mesmo modo que os algarismos na base 10 representam potências de 10, os bits na base dois representam potências diferentes de dois. Então, em vez de falar sobre um lugar de dezenas, um lugar de centenas, um lugar de milhares, coisas assim, você fala sobre um lugar de dois, um lugar de quatro e um lugar de oito. O ritmo da contagem agora é muito mais rápido. Mas isso quase torna mais perceptível. Virar o último, rolar uma vez, virar o último, rolar duas vezes, virar o último, rolar uma vez, virar o último, rolar três vezes. Novamente, há uma certa semelhança com esse padrão.

Em todas as escalas, o processo é fazer algo, rolar e fazer a mesma coisa novamente. Em pequena escala, digamos contar até três — que é um, um em binário — isso significa virar o último bit, rolar para os dois e depois virar o último bit. Em uma escala maior, como contar até 15 — que é um, um, um, um em binário — o processo é permitir que os três últimos contem até sete. Passe para o lugar do oito. Então deixe os três últimos bits contarem novamente. Contando até 255, que são oito sucessivos uns, parece que os últimos sete bits contam até estarem completos, passando para o lugar dos 128. Então, deixando os últimos sete bits serem contados novamente.

Tudo bem, então com essa mini introdução, o fato surpreendente que Keith me mostrou é que podemos usar esse ritmo para resolver as torres de Hanói. Você começa contando a partir de zero. Sempre que você estiver alterando apenas o último bit de um zero a um, mova o disco zero um pino para a direita. Se já estava no pino mais à direita, basta repetir voltar no primeiro pino. Se em sua contagem binária, você rola uma vez para o lugar do dois, ou seja, virar os dois últimos bits, moverá o disco número um. “Para onde você o move?”, Você pode perguntar.

Bem, você não tem escolha. Você não pode colocá-lo no topo do disco zero. E há apenas um outro pino. Então você o move para onde você é forçado a movê-lo. Então, depois disso, contar até um, um, envolve apenas virar o último bit. Então você move o disco zero novamente. Então, quando sua contagem binária passar duas vezes para o lugar do quatro, mova o disco número dois. E o padrão continua assim. Vire o último, mova o disco zero. Vire os dois últimos, mova o disco um. Vire o último, mova o disco zero. E aqui, teremos que rolar três vezes para o lugar do oito. E isso corresponde ao disco número três em movimento.

KEITH: Há algo de mágico nisso. Como quando vi pela primeira vez, “Isso não funciona”. Como eu — não sei como isso funciona. Não sei por que isso funciona. Agora eu sei, mas é mágico quando você o vê. E eu lembro de colocar a outra animação para isso — quando eu estava ensinando isso. E assim, você sabe, eu sei como isso funciona. Eu sei todas as coisas nele. Ainda é divertido apenas sentar e, tipo, você sabe, …

GRANT: Vê isso acontecer?

KEITH: Ah, sim.

Quero dizer, nem está claro a princípio que isso sempre dará movimentos legais. Por exemplo, como você sabe que toda vez que passa para o lugar do oito, esse disco três é necessariamente liberado para se mover?

KEITH: Ao mesmo tempo, a solução levantou imediatamente essas questões. Tipo, de onde isso vem? Por que isso funciona? E existe uma maneira melhor de fazer isso, tendo que fazer dois a 𝑛 menos um passo?

Acontece que isso não apenas resolve as Torres de Hanói. Mas faz isso da maneira mais eficiente possível. Entender por que isso funciona e como funciona e o que diabos está acontecendo se resume a uma certa perspectiva do quebra-cabeça, o que o pessoal da CS pode chamar de perspectiva recursiva.

KEITH: O disco três está pensando: “Ok, dois, um e zero!” Como: “Você tem que sair — Você tem que sair de cima de mim!” Como: “Eu não posso — não posso realmente funcionar sob muito peso e pressão.” E assim, apenas da perspectiva do disco três, se você quiser descobrir como o disco três vai chegar até aqui, de alguma forma, eu não me importo como, o disco dois, um e zero precisam chegar esse pino B. Essa é a única maneira que eles podem se mover. Se qualquer um desses discos estiver no topo de três, ele não poderá se mover. Se algum deles estiver no pino C, ele não pode se mover para lá. Então, de alguma forma, temos que obter dois, um e zero. Feito isso, podemos mover o disco três para lá. E o disco três diz: “Estou pronto. Você nunca precisa me mudar de novo. Todo mundo sabe como chegar aqui.”

KEITH: E, em certo sentido, agora você tem uma versão menor do mesmo problema. Agora você tem os discos zero, um e dois no pino B. Temos que levá-los ao C. Portanto, a ideia é que, se eu apenas focalizar um disco e pensar no que vou fazer para conseguir fazer esse disco funcionar, posso transformar meu problema maior em algo um pouco menor. E então como eu resolvo isso? Bem, é exatamente a mesma coisa. O disco dois dirá: “Disco um, disco zero, você precisa, você sabe. Não é você; sou eu. Eu só preciso de um pouco de espaço. Sai fora!”

KEITH: Eles precisam se mudar para algum lugar. Em seguida, o disco dois pode se mover para onde precisa ir. Em seguida, os discos um e zero podem fazer isso. Mas o ponto interessante é que cada disco tem praticamente a mesma estratégia. Todos dizem: “Todo mundo acima de mim, saia! E então eu vou me mudar. Ok, pessoal, empilhem-se.” Quando você conhece esse insight, pode codificar algo que resolverá a Towers of Hanoi em cinco ou seis linhas de código, que provavelmente tem a maior razão de investimentos intelectuais semelhantes às linhas de código de todos os tempos.

E se você pensar um pouco, fica claro que essa deve ser a solução mais eficiente. A cada passo, você está apenas fazendo o que lhe é imposto. Você precisa desativar os discos de zero a dois antes de poder mover o disco três. E você tem que mover o disco três. E então você deve mover os discos de zero a dois de volta para ele. Não há espaço para ineficiência dessa perspectiva. Então, por que contar em binário captura esse algoritmo?

Bem, o que está acontecendo aqui é que esse padrão de resolver um subproblema, mover um disco grande e depois resolver novamente um subproblema, é perfeitamente paralelo ao padrão da contagem binária. Contar alguma quantia, passar, contar até a mesma quantia novamente. E esse algoritmo das Torres de Hanói e a contagem binária são processos auto semelhantes, no sentido de que se você diminuir o zoom e contar até uma potência maior de dois ou resolver as Torres de Hanói com mais discos, eles ainda terão a mesma estrutura: subproblema, faça uma coisa, subproblema.

Por exemplo, em uma escala bem pequena, a solução das Torres de Hanói para dois discos — mova o disco zero, mova o disco um, mova o disco zero — é refletida contando até três em binário. Virar o último bit, rolar uma vez, virar o último bit. Em uma escala um pouco maior, resolver Torres de Hanói para três discos parece fazer o que for necessário para resolver dois discos, mova o disco número dois. Em seguida, faça o que for necessário para resolver dois discos novamente. Analogamente, contar até um, um, um em binário envolve contar até três, rolar os três bits e depois contar mais três. Em todas as escalas, os dois processos têm o mesmo detalhamento.

KEITH: Então, em certo sentido, a razão pela qual essa solução binária funciona ou pelo menos explica — sinto que, você sabe, não há uma explicação. Mas acho que o mais natural é que o padrão que você usaria para gerar esses números binários tem exatamente a mesma estrutura que o padrão que você usaria para as Torres de Hanói. É por isso que, se você observar os bits virando, está revertendo efetivamente esse processo. Você está dizendo que processo os gerou. Como se eu estivesse tentando entender como esses bits foram invertidos para me fornecer essa coisa, você efetivamente faz engenharia reversa do algoritmo recursivo para as Torres de Hanói, e é por isso que funciona.

Isso é bem legal, né? Mas na verdade fica mais legal! Eu ainda não entendi como isso se relaciona com o triângulo de Sierpinski. E é exatamente isso que farei no vídeo a seguir, parte dois. Tudo bem, então com isso, vejo vocês no próximo vídeo. E acho que você realmente vai gostar de onde isso está indo.

A Nagwa usa cookies para garantir que você tenha a melhor experiência em nosso site. Saiba mais sobre nossa Política de privacidade.