Ordenação da panqueca

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.

O que posso fazer para melhorar este universo do PLM?

Como sempre, existem várias coisas que podem ser feitas no código deste universo para melhorá-lo: