Monges, torres e porque não adianta apenas comprar mais hardware

Se você já visitou a casa de algum pai que goste de presentear seus filhos com brinquedos educacionais (ou você é um desses pais), já deve ter visto uma torre de Hanoi. É aquele brinquedo que é composto de várias peças de tamanhos diferentes e três pauzinhos onde as peças se encaixam.

Este jogo não existe para Playstation 3

Este jogo não existe para Playstation 3

O que poucas pessoas sabem (principalmente as crianças que ganham esses brinquedos) é que esse é um quebra cabeças, com regras bem definidas e cuja solução algorítmica até já foi estudada por vários pesquisadores de matemática e computação.

Existe uma lenda sobre a torre de Hanoi, que diz que existem monges em um templo tentando resolver uma torre de Hanoi para o caso de 64 discos de ouro. E que quando eles conseguirem resolver, o mundo vai acabar. Agora você deve ter ficado preocupado, porque provavelmente se você conseguiu resolver a torre de Hanoi que seu filho tem em casa, daqui a pouco esses monges que não tem mais nada para fazer vão terminar esse negócio e o mundo vai acabar. E você já pagou suas férias de dezembro!!

Calma, se tudo der certo, você ainda vai poder viajar em dezembro. Pelo menos dificilmente os monges vão atrapalhar suas férias. O número mínimo de operações para se resolver uma torre de Hanoi de 64 discos é 264-1 movimentos. Ou seja, mesmo que os monges nunca errassem e pudessem realizar cada movimento em 1 segundo, a solução do problema inteiro levaria mais de 580 bilhões de anos para terminar. Sem pausa para a novela.

E se os monges fizessem um upgrade e usassem uma máquina tão rápida quanto o supercomputador mais potente atualmente? Olhando no TOP500, o campeão atual é o Roadrunner, um cluster da IBM, que realizou no benchmark até 1456704 GFlops (bilhões de operações de ponto flutuante por segundo). Como o problema da torre de Hanoi não pode ser paralelizado (sempre tenho que mover uma peça por vez) para simplificar vamos pegar um de seus processadores, que faz 12.8 GFlops. Se os monges pudessem realizar 12800000000 movimentos por segundo será que o fim do mundo aconteria antes da próxima copa do mundo? Melhoraria bastante (só uns 45 anos) mas ainda ocorreriam muitas copas até lá. 

Para quem já resolveu uma torre de Hanoi de brinquedo, com 8 discos, deve ser muito estranho uma torre que nem tem tantos discos a mais necessitar de um número tão grande de operações para ser resolvida. Isso em computação é muito comum e e conhecido como explosão exponencial. Às vezes o problema parece bobo quando você aplica o algoritmo para versões pequenas do problema, mas o número de operações para resolver versões só um pouco maiores cresce para um tamanho probitivo, em que simplesmente não valeria a pena tentar resolver por levar tempo demais.

O exemplo desse fenômeno é encontrado na resolução da torre de Hanoi. A versão infantil, com 8 discos, exige no mínimo 255 operações. Dobrando-se o número de discos, 65535 operações. Com 24 discos, 16777215 operações. Moral da história: se quiser deixar seu filho bem ocupado, dê uma torre de Hanoi com uns 20 discos.

É raro uma empresa se deparar com um problema desses e tentar resolvê-lo (na ignorância de que o problema gera uma explosão exponencial). E você nem precisa trabalhar em uma empresa que resolve torres de Hanoi. Depois de algum tempo tentando resolver o problema, a empresa pode se frustrar e desistir, ou culpar o coitado do programador que fica marcado como incompetente.

Obs.: Este post foi livremente inspirado nas aulas do professor Coelho do IME-USP. O original obviamente é melhor.

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s