right|frame|Демонстрација главне операције. Спатула преврће горње три палачинке, а резултат је на слици испод. У проблему изгорених палачинки, њихове горње странице би сада биле изгорене уместо доњих. Палачинка сортирање је варијација алгоритма сортирања у коме је једина дозвољена операција обртање елемената префикса у секвенци. За разлику од традиционалних алгоритама за сортирање, који покушавају да сортирају са што мање могуће поређења, циљ је да се сортира секвенца са што мање обртања. Ова операција може бити замишљена као гомила палачинки у којој је кориснику дозвољено да узме горњих k палачинки и обрне их. Постоји варијација проблема која се тиче “изгорених” палачинки, код које свака палачинка има једну изгорену страну и на крају свака палачинка мора завршити са изгореном страном окренутом ка дну.
Проблеми палачинки
Оригинални проблем палачинки
Максимални број окретања потребан да се сортира гомила од n палачинки је између (15/14)n и (18/11)n али тачна вредност још није позната.Fertin, G. and Labarre, A. and Rusu, I. and Tannier, E. and Vialette, S. Combinatorics of Genome Rearrangements . The MIT Press, 2009.
Најједноставнији алгоритам палачинка сортирања захтева највише 2n−3 обртања. У овом алгоритму варијација сортирања селекцијом, доводимо на врх највећу палачинку која још није сортирана једним обртањем и онда је одводимо доле на њену коначну позицију још једним обртањем, а онда понављамо поступак за остатак палачинки. Приметите да не меримо време потребно за проналазак највеће палачинке већ само број обртања; да смо желели да направимо реалну машину која извршава овај алгоритам у линерном времену, морала би да извршава замену префикса(обртање) и проналажење максимума бројева у низу у константном времену.
17. септембра 2008. године тим истраживача са Тексашког Универзитета у Даласу предвођени професором Хал Судбороу-ом најавио је прихватање ефикаснијег алгоритма за палачинка сортирање од алгоритма предложеног од стране Гејтса и Пападимитроуа у журналу Теоретска Информатика. Ово побољшање остварује горњу границу од (18/11)n у односу на претходну границу од (5/3)n из 1979.Chitturi, B., Fahle, W., Meng, Z., Morales, L., Shields, C.O., Sudborough, I. H., and Voit, W. "An (18/11)n upper bound for sorting by prefix reversals." Theoretical Computer Science, 410(36), 3372-3390, 2009.
2. новембра 2011. године рад је послат у arXiv који најављује да је проблем NP-тежак и тако одговорио на питање отворено више од три деценије. Битно је приметити да се NP-тежак проблем састоји од израчунавања минималног броја окретања потребно да се сортира n палачинки, а не само сортирање палачинки. Као напоменуто изнад, сортирање се може тривијално израчунати у времену O(n), које тај проблем смешта у полиномијалну класу проблема.
Проблем изгорених палачинки
У тежој варијацији проблема званој проблем изгорених палачинки, дно сваке палачинке на гомили је изгорено и сортирање мора да заврши са сваком палачинком са изгореном страном окренуто ка доле. 2008. године група студената направила је “бактеријски рачунар” који израчунава једноставни пример проблема програмирајући “ешерихију коли” да обрће делове ДНК, што је аналогно изгореним палачинкама. ДНК има оријентацију (5' и 3') и правило (промотер пре кодирања). Иако је снага процесирања изражена преко ДНК мала, велики број бактерија у култури даје велику сличност платформи за израчунавање. Извештаји о бактеријама након решавања проблема постајући имуни на антибиотике.Haynes, K.A., et al. [http://www.jbioleng.org/content/2/1/8 , 2(1), 8, 2008. Анимација која описује овај процес је направљена.E.HOP - E. coli House of Pancakes - computing in vivo (flash applet)
Проблем палачинки на нискама Претходна дискусија подразумева да је свака палачинка јединствена тј. никоје две нису идентичне. Тако да је секвенца на којој се врши обртање префикса пермутација, тј. секвенца у којој се сваки симбол појављује тачно једном. Међутим “ниске” су секвенце у којима симболи могу да се понављају. 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],Kaplan, H., Shamir, R. and Tarjan, R.E. "Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals." Proc. 8th ACM-SIAM SODA (1997), 178-187, 1997. а проблем сортирања обртањем је доказан да је тежак за апроксимизацију чак и за одређене константне факторе[Berman, Karpinski, 1999],Berman, P. and Karpinski, M. "On Some Tighter Inapproximability Results." Proc. 26th ICALP (1999), LNCS 1644, Springer, 200-209, 1999. и доказано да је приближан полиномијалном времену у приближавајућем фактору 1.375[Berman, Karpinski, Hannenhalli, 2002].Berman, P., Karpinski M. and Hannenhalli, S., "1.375-Approximation Algorithms for Sorting by Reversals." Proc. 10th ESA (2002), LNCS 2461, Springer, 200-210, 2002.
Повезане секвенце целих бројева
+ Број гомила одређене висине којима је потребно N обртања за сортирање Висина N 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 1 2 1 1 3 1 2 2 1 4 1 3 6 11 3 5 1 4 12 35 48 20 6 1 5 20 79 199 281 133 2 7 1 6 30 149 543 1357 1903 1016 35 8 1 7 42 251 1191 4281 10561 15011 8520 455 9 1 8 56 391 2278 10666 38015 93585 132697 79379 5804 10 1 9 72 575 3963 22825 106461 377863 919365 1309756 814678 73232 11 1 10 90 809 6429 43891 252737 1174766 4126515 9981073 14250471 9123648 956354 6 12 1 11 110 1099 9883 77937 533397 3064788 14141929 49337252 118420043 169332213 111050066 13032704 167
Секвенце из The Online Encyclopedia of Integer Sequences од стране Neil Sloane: – максимални број обртања – број гомила којима је потребан максимални број обртања (изнад) – максимални број обртања за “изгорену” гомилу – број обртања за сортирану гомилу “ изгорене стране на врху” – троугао изнад читан по редовима
Референце
Додатна литература Mohammad, H.H. and Hal Sudborough, I. . Roney-Dougal, C. and Vatter, V. , 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.
Категорија:Алгоритми сортирања