Ordenamiento de panqueques
El ordenamiento de panqueques (crepes, panecillos, arepas...) es el término coloquial para el problema matemático de ordenar una pila desordenada de panqueques por orden de tamaño utilizando una espátula que puede ser insertada en cualquier punto en la pila para voltear todos los panqueques encima de ella. Un número de panqueque es el número máximo de volteos requeridos sin repetir para ordenar un número dado de panqueques. Este problema fue presentado de esta forma por el geómetra americano Jacob E. Goodman.[1] Es una variación del problema de ordenamiento en que la única operación permitida la de invertir los elementos de algún prefijo de la secuencia. A diferencia de un algoritmo de ordenación tradicional, que intenta ordenar con el menor número de comparaciones posible, su objetivo es ordenar la secuencia en el menor número posible de inversiones.Una variante del problema se ocupa de panqueque quemados donde cada uno de estos tiene un lado quemado y todos los panqueques deben además, acaba con este, en la parte inferior.
En una pila de panqueques, la espátula está volteando los tres primeros, con el resultado mostrado debajo. En el problema de los panqueques quemados, luego del volteo sus lados quemados quedan en la parte superior en lugar de la inferior.
Los problemas de panqueque editar
El problema de panqueque original editar
El número máximo de volteos requeridos para ordenar cualquier pila de n panqueques se ha demostrado que está entre 15/14n y 18/11n, pero el valor exacto no es conocido.[2]
El algoritmo de ordenamiento panqueques más sencillo requiere a lo sumo de 2n − 3 volteos. En este algoritmo - una variación del ordenamiento por selección- ponemos el panqueque más grande todavía sin ordenar en el tope de la pila con un volteo, y entonces volteamos una vez más poniéndolo en su posición final. Se repite el procedimiento para los restantes panqueques.
En 1979, Bill Gates y Christos Papadimitriou[3] dieron una cota superior de 5/3n. Treinta años más tarde, esta cota fue mejorada a 18/11n por un equipo de investigadores en la Universidad de Texas en Dallas (Chitturi et al., 2009).
Se ha demostrado que el problema de determinar el número mínimo de movimientos para una pila dada es NP-hard en un artículo publicado en 2015, respondiendo de este modo una cuestión abierta durante más de tres décadas.[4]
El problema del panqueque quemado editar
En una variación más difícil llamada el problema del panqueque quemado, el fondo de cada panqueque en la pila está quemado, y el ordenamiento tiene que ser completado con el lado quemado de cada panqueque en la parte inferior. En 2008, un grupo de estudiantes universitarios construyó una computadora bacteriana que puede solucionar un ejemplo sencillo del problema de los panqueques quemado por la programación de E. coli para voltear los segmentos de ADN los cuales son análogos a panqueques quemados. A pesar de que la capacidad de procesamiento expresado por el volteo de ADN es bajo, el alto número de bacterias en un cultivo proporciona una gran plataforma de computación paralela. Las bacterias reportan cuando han resuelto el problema al volverse resistentes a los antibióticos.[5]
El problema de panqueques en cadenas editar
La discusión anterior presupone que cada pancake es único, es decir, la secuencia en la que se realizan las inversiones de prefijo es una permutación. Sin embargo, "las cadenas" son secuencias en las que se puede repetir un símbolo.hitturi y Sudborough (2010) y Hurkens et al. (2007) mostraron de forma independiente que la complejidad de la transformación de una cadena en otra con inversiones de prefijo es NP-completo. También dieron cotas para el mismo. Hurkens et al. dio un algoritmo exacto para ordenar cadenas binarias y ternarias. Chitturi (2011) demostró que la complejidad de la transformación de una cadena en otra con inversiones de prefijo, es decir, el problema de los panqueques quemados en las cadenas, es NP-completo.
Historia editar
A pesar de ser visto más a menudo como un problema educativo, el ordenamiento de panqueques también aparece en redes de procesamiento paralelo, en el que puede proporcionar un algoritmo de encaminamiento eficaz entre procesadores.[6][7]
El problema es notable por ser el tema del único artículo matemático conocido escrito por el fundador de Microsoft, Bill Gates (cuando William Gates), titulado "Cotas para el ordenamiento por inversión de prefijos", publicado en 1979 donde se describe un algoritmo eficaz para el problema de ordenamiento de panqueques.[3] Además, el artículo más notable publicado por el cocreador de Futurama, David X. Cohen (como David S. Cohen) se refería al problema de los panqueques quemados.[8] Sus colaboradores eran Christos Papadimitriou (entonces en Harvard, ahora en Berkeley) y Manuel Blum (entonces en Berkeley, ahora en Carnegie Mellon Universidad), respectivamente.
Referencias editar
- ↑ Simon Singh (November 14, 2013).
- ↑ Fertin, G. and Labarre, A. and Rusu, I. and Tannier, E. and Vialette, S. (2009).
- ↑ a b Gates, W.; Papadimitriou, C. (1979).
- ↑ Bulteau, Laurent; Fertin, Guillaume; Rusu, Irena.
- ↑ Haynes, Karmella A; Broderick, Marian L; Brown, Adam D; Butner, Trevor L; Dickson, James O; Harden, W Lance; Heard, Lane H; Jessen, Eric L; Malloy, Kelly J; Ogden, Brad J; Rosemond, Sabriya; Simpson, Samantha; Zwack, Erin; Campbell, A Malcolm; Eckdahl, Todd T; Heyer, Laurie J; Poet, Jeffrey L (2008).
- ↑ Gargano, L.; Vaccaro, U.; Vozella, A. (1993).
- ↑ Kaneko, K.; Peng, S. (2006).
- ↑ Cohen D.S.; Blum, M. (1995).
Datos: Q2736589
Multimedia: Pancake sort / Q2736589
