Ordenamiento de panqueques para niños
El ordenamiento de panqueques es un problema matemático divertido que se trata de organizar una pila de panqueques de diferentes tamaños. Imagina que tienes una torre de panqueques desordenados y quieres que queden del más grande al más pequeño, de abajo hacia arriba. La única herramienta que puedes usar es una espátula.
Con la espátula, puedes levantar cualquier parte de la pila y voltear todos los panqueques que están encima de ella. El objetivo es lograr el orden correcto usando la menor cantidad de volteos posible. Este problema fue presentado de esta manera por un geómetra estadounidense llamado Jacob E. Goodman. Es un tipo especial de problema de ordenamiento donde solo puedes invertir una parte de la secuencia.
A diferencia de otros métodos de ordenación que buscan hacer pocas comparaciones, aquí el objetivo es ordenar la pila con el menor número de volteos. Existe una variación del problema donde los panqueques tienen un lado "quemado" y, al final, todos deben tener ese lado hacia abajo.
[[Archivo:Pancake_sort_operation.png|thumb|Demostración de la operación primaria.
Contenido
¿Qué es el problema del ordenamiento de panqueques?
El problema original de los panqueques
El número máximo de volteos necesarios para ordenar cualquier pila de n panqueques se ha estudiado mucho. Se sabe que está entre 15/14n y 18/11n, pero el valor exacto aún no se conoce con precisión.
Un método sencillo para ordenar panqueques requiere como máximo 2n - 3 volteos. Este método es parecido a cómo se ordena por selección. Primero, se coloca el panqueque más grande que aún no está en su lugar en la parte superior de la pila con un volteo. Luego, se voltea una vez más para ponerlo en su posición final, en la parte inferior. Este proceso se repite con los panqueques restantes hasta que toda la pila esté ordenada.
En 1979, Bill Gates y Christos Papadimitriou lograron mejorar la estimación de volteos a 5/3n. Treinta años después, un grupo de investigadores de la Universidad de Texas en Dallas la mejoró aún más, a 18/11n.
Determinar el número mínimo de movimientos para una pila específica de panqueques es un problema muy difícil. En 2015, se demostró que es un problema "NP-hard", lo que significa que es muy complicado de resolver de forma rápida para pilas grandes.
El problema del panqueque quemado: un desafío extra
Existe una versión más complicada llamada el problema del panqueque quemado. En esta versión, cada panqueque tiene un lado quemado. Al final del ordenamiento, todos los panqueques deben tener su lado quemado hacia abajo.
En 2008, un grupo de estudiantes universitarios hizo algo asombroso. Crearon una especie de "computadora bacteriana" para resolver una versión sencilla de este problema. Programaron bacterias E. coli para que "voltearan" segmentos de ADN, que actuaban como los panqueques quemados. Aunque la capacidad de procesamiento de una sola bacteria es pequeña, un cultivo con muchísimas bacterias funciona como una gran plataforma de computación paralela. Las bacterias indicaban que habían resuelto el problema volviéndose resistentes a los antibióticos.
¿Por qué es importante el problema de los panqueques?
Historia y aplicaciones prácticas
Aunque a menudo se ve como un problema divertido para aprender, el ordenamiento de panqueques tiene aplicaciones reales. Por ejemplo, se usa en redes de procesamiento paralelo. En estas redes, donde muchas computadoras trabajan juntas, puede ayudar a encontrar la mejor manera de enviar información entre los procesadores.
Este problema es famoso porque fue el tema del único artículo matemático conocido escrito por Bill Gates, el fundador de Microsoft. Lo publicó en 1979 y en él describía un método eficiente para resolver el problema del ordenamiento de panqueques. Además, David X. Cohen, uno de los creadores de la serie animada Futurama, también publicó un artículo importante sobre el problema de los panqueques quemados.
Galería de imágenes
-
Demostración de la operación primaria.
Véase también
En inglés: Pancake sorting Facts for Kids
