Esta atividade é inspirada por um problema introduzido pela primeira vez em
1975 por Harry Dweighter no American Mathematical Monthly. A pergunta não é
apenas ordenar panquecas, mas determinar f(n)
a quantidade
minima de viradas necessárias para ordenar qualquer pilha de tamanho
n
.
Este problema é agora famoso por que Bill Gates escreveu (com
C. Papadimitriou) a única publicação científica dele em 1979 neste tópico, a
fornecer um algoritmo mais rápido e a provar que 17n/16 ≤ f(n) ≤
(5n+5)/3
. Este foi a única publicação de Bill Gates antes dele
inventar o Windows e ficar rico.
Então, David X. Cohen, o inventor dos quadrinhos Futurama com muitas referências matemáticas, introduziu a variante com panquecas queimadas e estudou a complexidade dele com Manuel Blum em 1993.
Um artigo de 2011 (por L. Bulteau, G. Fertin e I. Rusu) provou que determinar a quantidade mínima de voltas para ordenar a pilha é um problema NP-completo. Naturalmente, o problema de ordenação da pilha não é NP-completo já que pode ser resolvido em 2n-3 passos com o algoritmo ingénuo e (5n+5)/3 passos com o algoritmo Gates. Isso é determinar a quantidade mínima de passos que é NP.
Mais informações encontram-se na página da wikipédia, como sempre.
Esta atividade também é integrada ao CSIRL (o meu repositório de atividades offline livres para introdução de ciência da computação, disponível em http://www.loria.fr/~quinson/Mediation/SMN/) e pode ser interessante executar as atividades offline antes de implementar estes algoritmos no PLM.
Como sempre, existem várias coisas que podem ser feitas no código deste universo para melhorá-lo: