b'\n_START_ARTICLE_\nOrdenamiento de panqueques\n_START_PARAGRAPH_\nEl ordenamiento de panqueques (panecillos, arepas...) es el t\xc3\xa9rmino coloquial para el problema matem\xc3\xa1tico de ordenar una pila desordenada de panqueques por orden de tama\xc3\xb1o utilizando una esp\xc3\xa1tula que puede ser insertada en cualquier punto en la pila para voltear todos los panqueques encima de ella. Un n\xc3\xbamero de panqueque es el n\xc3\xbamero m\xc3\xadnimo de volteos requeridos para ordenar un n\xc3\xbamero dado de panqueques. Este problema fue presentado de esta forma por el ge\xc3\xb3metra americano Jacob E. Goodman.\xe2\x80\x8b Es una variaci\xc3\xb3n del problema de ordenamiento en que la \xc3\xbanica operaci\xc3\xb3n permitida la de invertir los elementos de alg\xc3\xban prefijo de la secuencia. A diferencia de un algoritmo de ordenaci\xc3\xb3n tradicional, que intenta ordenar con el menor n\xc3\xbamero de comparaciones posible, su objetivo es ordenar la secuencia en el menor n\xc3\xbamero 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\xc3\xa1s, acaba con este, en la parte inferior.\n_START_SECTION_\nEl problema de panqueque original\n_START_PARAGRAPH_\nEl n\xc3\xbamero m\xc3\xadnimo de volteos requeridos para ordenar cualquier pila de n panqueques se ha demostrado que est\xc3\xa1 entre 15/14n y 18/11n, pero el valor exacto no es conocido.\xe2\x80\x8b_NEWLINE_El algoritmo de ordenamiento panqueques m\xc3\xa1s sencillo requiere a lo sumo de 2n\xe2\x80\x89\xe2\x88\x92\xe2\x80\x893 volteos. En este algoritmo - una variaci\xc3\xb3n del ordenamiento por selecci\xc3\xb3n- ponemos el panqueque m\xc3\xa1s grande todav\xc3\xada sin ordenar en el tope de la pila con un volteo, y entonces volteamos una vez m\xc3\xa1s poni\xc3\xa9ndolo en su posici\xc3\xb3n final. Se repite el procedimiento para los restantes panqueques._NEWLINE_En 1979, Bill Gates y Christos Papadimitriou\xe2\x80\x8b dieron una cota superior de 5/3n. Treinta a\xc3\xb1os m\xc3\xa1s tarde, esta cota fue mejorada a 18/11n por un equipo de investigadores en la Universidad de Texas en Dallas (Chitturi et al., 2009)._NEWLINE_Se ha demostrado que el problema de determinar el n\xc3\xbamero m\xc3\xadnimo de movimientos para una pila dada es NP-hard en un art\xc3\xadculo publicado en 2015, respondiendo de este modo una cuesti\xc3\xb3n abierta durante m\xc3\xa1s de tres d\xc3\xa9cadas.\xe2\x80\x8b\n_START_SECTION_\nEl problema del panqueque quemado\n_START_PARAGRAPH_\nEn una variaci\xc3\xb3n m\xc3\xa1s dif\xc3\xadcil llamada el problema del panqueque quemado, el fondo de cada panqueque en la pila est\xc3\xa1 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\xc3\xb3 una computadora bacteriana que puede solucionar un ejemplo sencillo del problema de los panqueques quemado por la programaci\xc3\xb3n de E. coli para voltear los segmentos de ADN los cuales son an\xc3\xa1logos a panqueques quemados. A pesar de que la capacidad de procesamiento expresado por el volteo de ADN es bajo, el alto n\xc3\xbamero de bacterias en un cultivo proporciona una gran plataforma de computaci\xc3\xb3n paralela. Las bacterias reportan cuando han resuelto el problema al volverse resistentes a los antibi\xc3\xb3ticos.\xe2\x80\x8b\n_START_SECTION_\nEl problema de panqueques en cadenas\n_START_PARAGRAPH_\nLa discusi\xc3\xb3n anterior presupone que cada pancake es \xc3\xbanico, es decir, la secuencia en la que se realizan las inversiones de prefijo es una permutaci\xc3\xb3n. Sin embargo, "las cadenas" son secuencias en las que se puede repetir un s\xc3\xadmbolo.hitturi y Sudborough (2010) y Hurkens et al. (2007) mostraron de forma independiente que la complejidad de la transformaci\xc3\xb3n de una cadena en otra con inversiones de prefijo es NP-completo. Tambi\xc3\xa9n dieron cotas para el mismo. Hurkens et al. dio un algoritmo exacto para ordenar cadenas binarias y ternarias. Chitturi (2011) demostr\xc3\xb3 que la complejidad de la transformaci\xc3\xb3n de una cadena en otra con inversiones de prefijo, es decir, el problema de los panqueques quemados en las cadenas, es NP-completo.\n_START_SECTION_\nHistoria\n_START_PARAGRAPH_\nA pesar de ser visto m\xc3\xa1s a menudo como un problema educativo, el ordenamiento de panqueques tambi\xc3\xa9n aparece en en redes de procesamiento paralelo, en el que puede proporcionar un algoritmo de encaminamiento eficaz entre procesadores.\xe2\x80\x8b\xe2\x80\x8b_NEWLINE_El problema es notable por ser el tema del \xc3\xbanico art\xc3\xadculo matem\xc3\xa1tico conocido escrito por el fundador de Microsoft, Bill Gates (cuando William Gates), titulado "Cotas para el ordenamiento por inversi\xc3\xb3n de prefijos", publicado en 1979 donde se describe un algoritmo eficaz para el problema de ordenamiento de panqueques.\xe2\x80\x8b Adem\xc3\xa1s, el art\xc3\xadculo m\xc3\xa1s notable publicado por el co-creador de Futurama, David X. Cohen (como David S. Cohen) se refer\xc3\xada al problema de los panqueques quemados.\xe2\x80\x8b Sus colaboradores eran Christos Papadimitriou (entonces en Harvard, ahora en Berkeley) y Manuel Blum (entonces en Berkeley, ahora en Carnegie Mellon Universidad), respectivamente.'