La clasificación de panqueques es el problema matemático de ordenar una pila desordenada de panqueques por orden de tamaño cuando se puede insertar una espátula en cualquier punto de la pila y usarla para voltear todos los panqueques que están encima. Un número de panqueques es el número mínimo de volteos necesarios para una cantidad dada de panqueques. En esta forma, el problema fue discutido por primera vez por el geómetra estadounidense Jacob E. Goodman . [1] Una variante del problema se relaciona con los panqueques quemados , donde cada panqueque tiene un lado quemado y todos los panqueques deben, además, terminar con el lado quemado hacia abajo.
Todos los métodos de ordenación requieren que se comparen pares de elementos. En el caso del problema de ordenación tradicional , el problema que se estudia habitualmente es minimizar el número de comparaciones necesarias para ordenar una lista . El número de operaciones reales, como intercambiar dos elementos, es entonces irrelevante. En cambio, en los problemas de ordenación pancake, el objetivo es minimizar el número de operaciones, donde las únicas operaciones permitidas son las inversiones de los elementos de algún prefijo de la secuencia. Ahora bien, el número de comparaciones es irrelevante.
Se ha demostrado que el número mínimo de vueltas necesarias para ordenar cualquier pila de n panqueques se encuentra entre 15/14 n y 18/11 n (aproximadamente 1,07 n y 1,64 n ), pero no se conoce el valor exacto. [2]
El algoritmo de ordenación de panqueques más simple realiza como máximo 2 n − 3 giros. En este algoritmo, una especie de ordenación por selección , llevamos el panqueque más grande que aún no se ha ordenado a la parte superior con un giro; lo bajamos a su posición final con un giro más; y repetimos este proceso para los panqueques restantes.
En 1979, Bill Gates y Christos Papadimitriou [3] dieron un límite inferior de 17/16n (aproximadamente 1,06 n ) volteretas y un límite superior de(5 y +5)/3 . El límite superior fue mejorado, treinta años después, para 18/11 n por un equipo de investigadores de la Universidad de Texas en Dallas , dirigido por el profesor fundador Hal Sudborough. [4] [5]
En 2011, Laurent Bulteau, Guillaume Fertin e Irena Rusu [6] demostraron que el problema de encontrar la secuencia más corta de giros para una pila dada de panqueques es NP-difícil , respondiendo así una pregunta que había estado abierta durante más de tres décadas.
En una variación llamada el problema del panqueque quemado , se quema la parte inferior de cada panqueque en la pila, y la clasificación debe completarse con el lado quemado de cada panqueque hacia abajo. Es una permutación con signo , y si un panqueque i está "quemado hacia arriba", se coloca un elemento negativo i` en lugar de i en la permutación. En 2008, un grupo de estudiantes universitarios construyó una computadora bacteriana que puede resolver un ejemplo simple del problema del panqueque quemado programando E. coli para que invierta segmentos de ADN que son análogos a los panqueques quemados. El ADN tiene una orientación (5' y 3') y un orden (promotor antes de codificación). Aunque la potencia de procesamiento expresada por las inversiones de ADN es baja, la gran cantidad de bacterias en un cultivo proporciona una gran plataforma de computación paralela . Las bacterias informan cuando han resuelto el problema volviéndose resistentes a los antibióticos. [7]
La discusión anterior presupone que cada panqueque 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 un símbolo puede repetirse, y esta repetición puede reducir el número de inversiones de prefijo necesarias para ordenar. Chitturi y Sudborough (2010) y Hurkens et al. (2007) demostraron de forma independiente que la complejidad de transformar una cadena compatible en otra con el número mínimo de inversiones de prefijo es NP-completa . También dieron límites para el mismo. Hurkens et al. dieron un algoritmo exacto para ordenar cadenas binarias y ternarias. Chitturi [8] (2011) demostró que la complejidad de transformar una cadena con signo compatible en otra con el número mínimo de inversiones de prefijo con signo (el problema del panqueque quemado en cadenas) es NP-completa.
El problema de la clasificación de panqueques fue planteado por primera vez por Jacob E. Goodman , escribiendo bajo el seudónimo de "Harry Dweighter" ("camarero agobiado"). [9]
Aunque se considera más a menudo como un dispositivo educativo, la clasificación de panqueques también aparece en aplicaciones en redes de procesadores paralelos, en las que puede proporcionar un algoritmo de enrutamiento eficaz entre procesadores. [10] [11]
El problema es notable por ser el tema del único artículo matemático conocido del fundador de Microsoft, Bill Gates (como William Gates), titulado "Límites para la ordenación por inversión de prefijo" y escrito en coautoría con Christos Papadimitriou . Publicado en 1979, describe un algoritmo eficiente para la ordenación de panqueques. [3] Además, el artículo más notable publicado por el cocreador de Futurama, David X. Cohen (como David S. Cohen), escrito en coautoría con Manuel Blum , se refería al problema del panqueque quemado. [12]
Más recientemente, también se han estudiado los problemas relacionados de ordenamiento con signo por reversiones y ordenamiento por reversiones. Mientras que se han encontrado algoritmos exactos y eficientes para el ordenamiento con signo por reversiones, [13] se ha demostrado que el problema del ordenamiento por reversiones es difícil incluso de aproximar dentro de un cierto factor constante, [14] y también se ha demostrado que es aproximable en tiempo polinómico dentro del factor de aproximación 1,375. [15]
Un grafo de n -panqueques es un grafo cuyos vértices son las permutaciones de n símbolos desde 1 hasta n y sus aristas están dadas entre permutaciones transitivas por inversiones de prefijo. Es un grafo regular con n! vértices, su grado es n−1. El problema de ordenamiento de panqueques y el problema para obtener el diámetro del grafo de panqueques son equivalentes. [16]
El gráfico de panqueque de dimensión n , P n, se puede construir recursivamente a partir de n copias de P n−1 , asignando un elemento diferente del conjunto {1, 2, …, n} como sufijo a cada copia.
Su circunferencia :
El género γ(P n ) de P n es: [17]
Dado que los gráficos de panqueque tienen muchas propiedades interesantes, como estructuras simétricas y recursivas, grados y diámetros pequeños en comparación con el tamaño del gráfico, se les presta mucha atención como modelo de redes de interconexión para computadoras paralelas. [18] [19] [20] Cuando consideramos los gráficos de panqueque como el modelo de las redes de interconexión, el diámetro del gráfico es una medida que representa el retraso de la comunicación. [21] [22]
Los gráficos de panqueque son gráficos de Cayley (por lo tanto, son transitivos en vértices ) y son especialmente atractivos para el procesamiento paralelo. Tienen grado y diámetro sublogarítmicos y son relativamente dispersos (en comparación con, por ejemplo, los hipercubos ). [17]
A continuación se muestra un ejemplo del algoritmo de ordenamiento de panqueques en Python . El código es similar al ordenamiento de burbuja o al ordenamiento por selección .
def flip ( arr , k : int ) -> Ninguno : izquierda = 0 mientras que izquierda < k : arr [ izquierda ], arr [ k ] = arr [ k ], arr [ izquierda ] k- = 1 izquierda += 1def max_index ( arr , k : int ) -> int : índice = 0 para i en el rango ( k ): si arr [ i ] > arr [ índice ]: índice = i índice de retornodef pancake_sort ( arr ) -> Ninguno : n = len ( arr ) mientras n > 1 : maxidx = índice máximo ( arr , n ) si maxidx != n - 1 : si maxidx != 0 : voltear ( arr , maxidx ) voltear ( arr , n - 1 ) n- = 1arreglo = [ 15 , 8 , 9 , 1 , 78 , 30 , 69 , 4 , 10 ]ordenamiento_panqueque ( arr )imprimir ( arr )Secuencias de la Enciclopedia en línea de secuencias de números enteros :
Un equipo de estudiantes de informática de la UT Dallas y su asesor académico han mejorado una solución de larga data para un enigma matemático conocido como el problema del panqueque. La mejor solución anterior, que se mantuvo durante casi 30 años, fue ideada por Bill Gates y uno de sus instructores de Harvard, Christos Papadimitriou, varios años antes de que se estableciera Microsoft.