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) sua única publicação científica em 1979 neste tópico,
fornecendo um algoritmo mais rápido e provando 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 sua complexidade com Manuel Blum em 1993.
An article of 2011 (by L. Bulteau, G. Fertin and I. Rusu) proved that determining the minimal amount of flips to sort the stack is a NP-complete problem. Naturally, the stack sorting problem is not NP-complete since it can be solved in 2n-3 steps with the naive algorithm and (5n+5)/3 steps with the Gates algorithm. That's determining the minimal amount of steps that is NP.
Mais informações podem ser encontradas na página da wikipédia, como sempre.
Esta atividade também é integrada ao CSIRL (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: