Палачинка сортирање

Демонстрација главне операције. Спатула преврће горње три палачинке, а резултат је на слици испод. У проблему изгорених палачинки, њихове горње странице би сада биле изгорене уместо доњих.

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

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

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

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

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

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

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

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

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

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

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

Историјат

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

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

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

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

Број гомила одређене висине којима је потребно 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:

A058986 – максимални број обртања
A067607 – број гомила којима је потребан максимални број обртања (изнад)
A078941 – максимални број обртања за “изгорену” гомилу
A078942 – број обртања за сортирану гомилу “ изгорене стране на врху”
A092113 – троугао изнад читан по редовима

Референце

^ Fertin, G. and Labarre, A. and Rusu, I. and Tannier, E. and Vialette, S. Combinatorics of Genome Rearrangements Архивирано на веб-сајту Wayback Machine (11. октобар 2012). The MIT Press, 2009.
^ ^а ^б Gates, W.; Papadimitriou, C. (1979). „Bounds for Sorting by Prefix Reversal” (PDF). Discrete Mathematics. 27: 47—57. doi:10.1016/0012-365X(79)90068-2. Архивирано из оригинала (PDF) 10. 06. 2007. г. Приступљено 29. 05. 2013.
^ „Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics”. University of Texas at Dallas News Center. 17. 9. 2008. Архивирано из оригинала 05. 04. 2012. г. Приступљено 10. 11. 2008. „A team of UT Dallas computer science students and their faculty adviser have improved upon a longstanding solution to a mathematical conundrum known as the pancake problem. The previous best solution, which stood for almost 30 years, was devised by Bill Gates and one of his Harvard instructors, Christos Papadimitriou, several years before Microsoft was established.”
^ 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.
^ Bulteau, Laurent; Fertin, Guillaume; Rusu, Irena (2012). „Pancake Flipping is Hard”. Mathematical Foundations of Computer Science 2012. Lecture Notes in Computer Science. 7464. стр. 247—258. ISBN 978-3-642-32588-5. S2CID 12472692. arXiv:1111.0434 . doi:10.1007/978-3-642-32589-2_24.
^ „Solving the Pancake Problem with an E. coli Computer”. Архивирано из оригинала 06. 04. 2012. г. Приступљено 29. 05. 2013.
^ „iHOP meets iGEM”. Архивирано из оригинала 09. 03. 2012. г. Приступљено 29. 05. 2013.
^ Haynes, K.A., et al. "Engineering bacteria to solve the Burnt Pancake Problem." Journal of Biological Engineering, 2(1), 8, 2008.
^ E.HOP - E. coli House of Pancakes - computing in vivo Архивирано на веб-сајту Wayback Machine (12. фебруар 2012) (flash applet)
^ Cohen D.S.; Blum, M. (1995). „On the problem of sorting burnt pancakes”. Discrete Applied Mathematics. 61 (2): 105—120. doi:10.1016/0166-218X(94)00009-3.
^ 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, P. and Karpinski, M. "On Some Tighter Inapproximability Results." Proc. 26th ICALP (1999), LNCS 1644, Springer, 200-209, 1999.
^ 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.

Додатна литература

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.
Chitturi, Bhadrachalam (2011). „A Note on Complexity of Genetic Mutations”. Discrete Mathematics, Algorithms and Applications. 03 (3): 269—286. doi:10.1142/S1793830911001206. .