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

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

Палачинка сортирање је варијација алгоритма сортирања у коме је једина дозвољена операција обртање елемената префикса у секвенци. За разлику од традиционалних алгоритама за сортирање, који покушавају да сортирају са што мање могуће поређења, циљ је да се сортира секвенца са што мање обртања. Ова операција може бити замишљена као гомила палачинки у којој је кориснику дозвољено да узме горњих 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:

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

Референце[уреди | уреди извор]

  1. ^ 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.
  2. ^ а б 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. 
  3. ^ „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.” 
  4. ^ 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.
  5. ^ 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. 
  6. ^ „Solving the Pancake Problem with an E. coli Computer”. Архивирано из оригинала 06. 04. 2012. г. Приступљено 29. 05. 2013. 
  7. ^ „iHOP meets iGEM”. Архивирано из оригинала 09. 03. 2012. г. Приступљено 29. 05. 2013. 
  8. ^ Haynes, K.A., et al. "Engineering bacteria to solve the Burnt Pancake Problem." Journal of Biological Engineering, 2(1), 8, 2008.
  9. ^ E.HOP - E. coli House of Pancakes - computing in vivo Архивирано на сајту Wayback Machine (12. фебруар 2012) (flash applet)
  10. ^ 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. 
  11. ^ 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.
  12. ^ Berman, P. and Karpinski, M. "On Some Tighter Inapproximability Results." Proc. 26th ICALP (1999), LNCS 1644, Springer, 200-209, 1999.
  13. ^ 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. .

Спољашње везе[уреди | уреди извор]

Шаблон:Сортирање

Преузето из „https://sr.wikipedia.org/w/index.php?title=Палачинка_сортирање&oldid=26969080”