Палачинка сортирање
Палачинка сортирање је варијација алгоритма сортирања у коме је једина дозвољена операција обртање елемената префикса у секвенци. За разлику од традиционалних алгоритама за сортирање, који покушавају да сортирају са што мање могуће поређења, циљ је да се сортира секвенца са што мање обртања. Ова операција може бити замишљена као гомила палачинки у којој је кориснику дозвољено да узме горњих k палачинки и обрне их. Постоји варијација проблема која се тиче “изгорених” палачинки, код које свака палачинка има једну изгорену страну и на крају свака палачинка мора завршити са изгореном страном окренутом ка дну.

Проблеми палачинки

Оригинални проблем палачинки 

Максимални број окретања потребан да се сортира гомила од n палачинки је између (15/14)n и (18/11)n али тачна вредност још није позната.

Најједноставнији алгоритам палачинка сортирања захтева највише 2n−3 обртања. У овом алгоритму варијација сортирања селекцијом, доводимо на врх највећу палачинку која још није сортирана једним обртањем и онда је одводимо доле на њену коначну позицију још једним обртањем, а онда понављамо поступак за остатак палачинки. Приметите да не меримо време потребно за проналазак највеће палачинке већ само број обртања; да смо желели да направимо реалну машину која извршава овај алгоритам у линерном времену, морала би да извршава замену префикса(обртање) и проналажење максимума бројева у низу у константном времену.

17. септембра 2008. године тим истраживача са Тексашког Универзитета у Даласу предвођени професором Хал Судбороу-ом најавио је прихватање ефикаснијег алгоритма за палачинка сортирање од алгоритма предложеног од стране Гејтса и Пападимитроуа у журналу Теоретска Информатика. Ово побољшање остварује горњу границу од (18/11)n у односу на претходну границу од (5/3)n из 1979.

2. новембра 2011. године рад је послат у arXiv који најављује да је проблем NP-тежак и тако одговорио на питање отворено више од три деценије. Битно је приметити да се NP-тежак проблем састоји од израчунавања минималног броја окретања потребно да се сортира n палачинки, а не само сортирање палачинки. Као напоменуто изнад, сортирање се може тривијално израчунати у времену O(n), које тај проблем смешта у полиномијалну класу проблема.

Проблем изгорених палачинки 

У тежој варијацији проблема званој проблем изгорених палачинки, дно сваке палачинке на гомили је изгорено и сортирање мора да заврши са сваком палачинком са изгореном страном окренуто ка доле. 2008. године група студената направила је “бактеријски рачунар” који израчунава једноставни пример проблема програмирајући “ешерихију коли” да обрће делове ДНК, што је аналогно изгореним палачинкама. ДНК има оријентацију (5' и 3') и правило (промотер пре кодирања). Иако је снага процесирања изражена преко ДНК мала, велики број бактерија у култури даје велику сличност платформи за израчунавање. Извештаји о бактеријама након решавања проблема постајући имуни на антибиотике. Анимација која описује овај процес је направљена.

Проблем палачинки на нискама 
Претходна дискусија подразумева да је свака палачинка јединствена тј. никоје две нису идентичне. Тако да је секвенца на којој се врши обртање префикса пермутација, тј. секвенца у којој се сваки симбол појављује тачно једном. Међутим “ниске” су секвенце у којима симболи могу да се понављају. Chitturi и Sudborough (2010) и Hurkens et al. (2007) су независно показали да је сложеност трансформисања компатибилне ниске у другу заменом префикса NP-комплетан проблем. Hurkens et al. су дали истоветан алгоритам за сортирање бинарних и тернарних ниски. Chitturi (2011) је доказао да је сложеност трансформирања компатибилне означене ниске у другу помоћу обртања префикса тј. проблем изгорених палачинки на нискама, такође NP-комплетан проблем.

Историјат 
Иако више оруђе за образовање, палачинка сортирање се појављује у апликацијама за паралелно процесиране мреже, у којима може да допринесе ефектан алгоритам за рутирање између процесора.

Проблем је препознатљив као једини широко познати математички рад написан од стране оснивача Microsoft-а Bill Gates-а, назван "Bounds for Sorting by Prefix Reversal". Објављен 1979. године, даје ефикасан алгоритам за палачинка сортирање. Такође један од познатих радова од стране ко-креатора Футураме David X. Cohen који се тиче проблема изгорених палачинки. Њихови сарадници су били Christos Papadimitriou и Manuel Blum респективно.

Повезани проблеми означеног сорирања обртањем и сортирања обртањем су поменута у скорије време. Где је ефикасност истих алгоритама пронађена од стране, за означено сортирање обртањем [Kaplan, Shamir, Tarjan, 1997], а проблем сортирања обртањем је доказан да је тежак за апроксимизацију чак и за одређене константне факторе[Berman, Karpinski, 1999], и доказано да је приближан полиномијалном времену у приближавајућем фактору 1.375[Berman, Karpinski, Hannenhalli, 2002].

Повезане секвенце целих бројева 

Секвенце из The Online Encyclopedia of Integer Sequences од стране Neil Sloane:
  – максимални број обртања
  – број гомила којима је потребан максимални број обртања (изнад)
  – максимални број обртања за “изгорену” гомилу
  – број обртања за сортирану гомилу “ изгорене стране на врху”
  – троугао изнад читан по редовима

Референце

Додатна литература 
 Mohammad, H.H. and Hal Sudborough, I. "On the Diameter of the Pancake Network," Journal of Algorithms 25 (1), 67-94, 1997.
 Roney-Dougal, C. and Vatter, V. "Of pancakes, mice and men," Plus Magazine 54, March 2010.
 Chitturi, B. and Sudborough, H. "Prefix reversals on strings". Proc. Int. Conf. Bioinformatics and Computational Biology, Vol. 2 (2010)591–598.
 Hurkens, C., Iersel, L. V., Keijsper, J., Kelk, S., Stougie, L. and Tromp J. "Prefix reversals on binary and ternary strings". SIAM J. Discrete Math. 21(3)(2007) 592–611.
 .

Спољашње везе 
 Cut-the-Knot: Flipping pancakes puzzle, including a Java applet for the pancake problem and some discussion.
 Douglas B. West's "The Pancake Problems"
 
 Animation explaining the bacterial computer that can solve the burnt pancake problem.

Алгоритми сортирања
Палачинка сортирање је варијација алгоритма сортирања у коме је једина дозвољена операција обртање елемената префикса у секвенци . За разлику од традиционалних алгоритама за сортирање , који покушавају да сортирају са што мање могуће поређења , циљ је да се сортира секвенца са што мање обртања . Ова операција може бити замишљена као гомила палачинки у којој је кориснику дозвољено да узме горњих k палачинки и обрне их . Постоји варијација проблема која се тиче “ изгорених ” палачинки , код које свака палачинка има једну изгорену страну и на крају свака палачинка мора завршити са изгореном страном окренутом ка дну . Проблеми палачинки Оригинални проблем палачинки Максимални број окретања потребан да се сортира гомила од n палачинки је између14 )n и11 )n али тачна вредност још није позната . Најједноставнији алгоритам палачинка сортирања захтева највише−3 обртања . У овом алгоритму варијација сортирања селекцијом , доводимо на врх највећу палачинку која још није сортирана једним обртањем и онда је одводимо доле на њену коначну позицију још једним обртањем , а онда понављамо поступак за остатак палачинки . Приметите да не меримо време потребно за проналазак највеће палачинке већ само број обртања ; да смо желели да направимо реалну машину која извршава овај алгоритам у линерном времену , морала би да извршава замену префикса( обртање ) и проналажење максимума бројева у низу у константном времену. 17. септембра године тим истраживача са Тексашког Универзитета у Даласу предвођени професором Хал Судбороу-ом најавио је прихватање ефикаснијег алгоритма за палачинка сортирање од алгоритма предложеног од стране Гејтса и Пападимитроуа у журналу Теоретска Информатика . Ово побољшање остварује горњу границу од11 )n у односу на претходну границу од3 )n из 2. новембра године рад је послат у arXiv који најављује да је проблем NP-тежак и тако одговорио на питање отворено више од три деценије . Битно је приметити да се NP-тежак проблем састоји од израчунавања минималног броја окретања потребно да се сортира n палачинки , а не само сортирање палачинки . Као напоменуто изнад , сортирање се може тривијално израчунати у времену O( n ) , које тај проблем смешта у полиномијалну класу проблема . Проблем изгорених палачинки У тежој варијацији проблема званој проблем изгорених палачинки , дно сваке палачинке на гомили је изгорено и сортирање мора да заврши са сваком палачинком са изгореном страном окренуто ка доле. године група студената направила је “ бактеријски рачунар ” који израчунава једноставни пример проблема програмирајући “ ешерихију коли ” да обрће делове ДНК , што је аналогно изгореним палачинкама . ДНК има оријентацију и ) и правило ( промотер пре кодирања ) . Иако је снага процесирања изражена преко ДНК мала , велики број бактерија у култури даје велику сличност платформи за израчунавање . Извештаји о бактеријама након решавања проблема постајући имуни на антибиотике . Анимација која описује овај процес је направљена . Проблем палачинки на нискама Претходна дискусија подразумева да је свака палачинка јединствена тј. никоје две нису идентичне . Тако да је секвенца на којој се врши обртање префикса пермутација , тј. секвенца у којој се сваки симбол појављује тачно једном . Међутим “ ниске ” су секвенце у којима симболи могу да се понављају . Chitturi и Sudboroughи Hurkens et al.су независно показали да је сложеност трансформисања компатибилне ниске у другу заменом префикса NP-комплетан проблем . Hurkens et al. су дали истоветан алгоритам за сортирање бинарних и тернарних ниски . Chitturiје доказао да је сложеност трансформирања компатибилне означене ниске у другу помоћу обртања префикса тј. проблем изгорених палачинки на нискама , такође NP-комплетан проблем . Историјат Иако више оруђе за образовање , палачинка сортирање се појављује у апликацијама за паралелно процесиране мреже , у којима може да допринесе ефектан алгоритам за рутирање између процесора . Проблем је препознатљив као једини широко познати математички рад написан од стране оснивача Microsoft-а Bill Gates-а , назван " Bounds for Sorting by Prefix Reversal " . Објављен године , даје ефикасан алгоритам за палачинка сортирање . Такође један од познатих радова од стране ко-креатора Футураме David X . Cohen који се тиче проблема изгорених палачинки . Њихови сарадници су били Christos Papadimitriou и Manuel Blum респективно . Повезани проблеми означеног сорирања обртањем и сортирања обртањем су поменута у скорије време . Где је ефикасност истих алгоритама пронађена од стране , за означено сортирање обртањем [ Kaplan , Shamir , Tarjan , , а проблем сортирања обртањем је доказан да је тежак за апроксимизацију чак и за одређене константне факторе[ Berman , Karpinski , , и доказано да је приближан полиномијалном времену у приближавајућем фактору375[ Berman , Karpinski , Hannenhalli , . Повезане секвенце целих бројева Секвенце из The Online Encyclopedia of Integer Sequences од стране Neil Sloane : – максимални број обртања – број гомила којима је потребан максимални број обртања ( изнад ) – максимални број обртања за “ изгорену ” гомилу – број обртања за сортирану гомилу “ изгорене стране на врху ” – троугао изнад читан по редовима Референце Додатна литература Mohammad , H.H. and Hal Sudborough , I . " On the Diameter of the Pancake Network , " Journal of Algorithms( 1 ) , Roney-Dougal , C. and Vatter , V . " Of pancakes , mice and men , " Plus Magazine March Chitturi , B. and Sudborough , H . " Prefix reversals on strings " . Proc . Int . Conf . Bioinformatics and Computational Biology , Vol.( 2010 ) 591–598. Hurkens , C . , Iersel , L . V . , Keijsper , J . , Kelk , S . , Stougie , L. and Tromp J . " Prefix reversals on binary and ternary strings " . SIAM J. Discrete Math.3)( 2007) 611 . \ . Спољашње везе Cut-the-Knot : Flipping pancakes puzzle , including a Java applet for the pancake problem and some discussion . Douglas B. West's " The Pancake Problems " Animation explaining the bacterial computer that can solve the burnt pancake problem . Алгоритми сортирања