Palačinka sortiranje

S Vikipedije, slobodne enciklopedije
Demonstracija glavne operacije. Spatula prevrće gornje tri palačinke, a rezultat je na slici ispod. U problemu izgorenih palačinki, njihove gornje stranice bi sada bile izgorene umesto donjih.

Palačinka sortiranje je varijacija algoritma sortiranja u kome je jedina dozvoljena operacija obrtanje elemenata prefiksa u sekvenci. Za razliku od tradicionalnih algoritama za sortiranje, koji pokušavaju da sortiraju sa što manje moguće poređenja, cilj je da se sortira sekvenca sa što manje obrtanja. Ova operacija može biti zamišljena kao gomila palačinki u kojoj je korisniku dozvoljeno da uzme gornjih k palačinki i obrne ih. Postoji varijacija problema koja se tiče “izgorenih” palačinki, kod koje svaka palačinka ima jednu izgorenu stranu i na kraju svaka palačinka mora završiti sa izgorenom stranom okrenutom ka dnu.

Problemi palačinki[uredi | uredi izvor]

Originalni problem palačinki[uredi | uredi izvor]

Maksimalni broj okretanja potreban da se sortira gomila od n palačinki je između (15/14)n i (18/11)n ali tačna vrednost još nije poznata.[1]

Najjednostavniji algoritam palačinka sortiranja zahteva najviše 2n−3 obrtanja. U ovom algoritmu varijacija sortiranja selekcijom, dovodimo na vrh najveću palačinku koja još nije sortirana jednim obrtanjem i onda je odvodimo dole na njenu konačnu poziciju još jednim obrtanjem, a onda ponavljamo postupak za ostatak palačinki. Primetite da ne merimo vreme potrebno za pronalazak najveće palačinke već samo broj obrtanja; da smo želeli da napravimo realnu mašinu koja izvršava ovaj algoritam u linernom vremenu, morala bi da izvršava zamenu prefiksa(obrtanje) i pronalaženje maksimuma brojeva u nizu u konstantnom vremenu.

17. septembra 2008. godine tim istraživača sa Teksaškog Univerziteta u Dalasu predvođeni profesorom Hal Sudborou-om najavio je prihvatanje efikasnijeg algoritma za palačinka sortiranje od algoritma predloženog od strane Gejtsa i Papadimitroua u žurnalu Teoretska Informatika.[2] Ovo poboljšanje ostvaruje gornju granicu od (18/11)n u odnosu na prethodnu granicu od (5/3)n iz 1979.[3][4]

2. novembra 2011. godine rad je poslat u arXiv koji najavljuje da je problem NP-težak[5] i tako odgovorio na pitanje otvoreno više od tri decenije. Bitno je primetiti da se NP-težak problem sastoji od izračunavanja minimalnog broja okretanja potrebno da se sortira n palačinki, a ne samo sortiranje palačinki. Kao napomenuto iznad, sortiranje se može trivijalno izračunati u vremenu O(n), koje taj problem smešta u polinomijalnu klasu problema.

Problem izgorenih palačinki[uredi | uredi izvor]

U težoj varijaciji problema zvanoj problem izgorenih palačinki, dno svake palačinke na gomili je izgoreno i sortiranje mora da završi sa svakom palačinkom sa izgorenom stranom okrenuto ka dole. 2008. godine grupa studenata napravila je “bakterijski računar” koji izračunava jednostavni primer problema programirajući “ešerihiju koli” da obrće delove DNK, što je analogno izgorenim palačinkama.[6][7] DNK ima orijentaciju (5' i 3') i pravilo (promoter pre kodiranja). Iako je snaga procesiranja izražena preko DNK mala, veliki broj bakterija u kulturi daje veliku sličnost platformi za izračunavanje. Izveštaji o bakterijama nakon rešavanja problema postajući imuni na antibiotike.[8] Animacija koja opisuje ovaj proces je napravljena.[9]

Problem palačinki na niskama[uredi | uredi izvor]

Prethodna diskusija podrazumeva da je svaka palačinka jedinstvena tj. nikoje dve nisu identične. Tako da je sekvenca na kojoj se vrši obrtanje prefiksa permutacija, tj. sekvenca u kojoj se svaki simbol pojavljuje tačno jednom. Međutim “niske” su sekvence u kojima simboli mogu da se ponavljaju. Chitturi i Sudborough (2010) i Hurkens et al. (2007) su nezavisno pokazali da je složenost transformisanja kompatibilne niske u drugu zamenom prefiksa NP-kompletan problem. Hurkens et al. su dali istovetan algoritam za sortiranje binarnih i ternarnih niski. Chitturi (2011) je dokazao da je složenost transformiranja kompatibilne označene niske u drugu pomoću obrtanja prefiksa tj. problem izgorenih palačinki na niskama, takođe NP-kompletan problem.

Istorijat[uredi | uredi izvor]

Iako više oruđe za obrazovanje, palačinka sortiranje se pojavljuje u aplikacijama za paralelno procesirane mreže, u kojima može da doprinese efektan algoritam za rutiranje između procesora.[traži se izvor]

Problem je prepoznatljiv kao jedini široko poznati matematički rad napisan od strane osnivača Microsoft-a Bill Gates-a, nazvan "Bounds for Sorting by Prefix Reversal". Objavljen 1979. godine, daje efikasan algoritam za palačinka sortiranje.[2] Takođe jedan od poznatih radova od strane ko-kreatora Futurame David X. Cohen koji se tiče problema izgorenih palačinki.[10] Njihovi saradnici su bili Christos Papadimitriou i Manuel Blum respektivno.

Povezani problemi označenog soriranja obrtanjem i sortiranja obrtanjem su pomenuta u skorije vreme. Gde je efikasnost istih algoritama pronađena od strane, za označeno sortiranje obrtanjem [Kaplan, Shamir, Tarjan, 1997],[11] a problem sortiranja obrtanjem je dokazan da je težak za aproksimizaciju čak i za određene konstantne faktore[Berman, Karpinski, 1999],[12] i dokazano da je približan polinomijalnom vremenu u približavajućem faktoru 1.375[Berman, Karpinski, Hannenhalli, 2002].[13]

Povezane sekvence celih brojeva[uredi | uredi izvor]

Broj gomila određene visine kojima je potrebno N obrtanja za sortiranje
Visina 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

Sekvence iz The Online Encyclopedia of Integer Sequences od strane Neil Sloane:

  • OEIS A058986 – maksimalni broj obrtanja
  • OEIS A067607 – broj gomila kojima je potreban maksimalni broj obrtanja (iznad)
  • OEIS A078941 – maksimalni broj obrtanja za “izgorenu” gomilu
  • OEIS A078942 – broj obrtanja za sortiranu gomilu “ izgorene strane na vrhu”
  • OEIS A092113 – trougao iznad čitan po redovima

Reference[uredi | uredi izvor]

  1. ^ Fertin, G. and Labarre, A. and Rusu, I. and Tannier, E. and Vialette, S. Combinatorics of Genome Rearrangements Arhivirano na sajtu Wayback Machine (11. oktobar 2012). The MIT Press, 2009.
  2. ^ a b 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. Arhivirano iz originala (PDF) 10. 06. 2007. g. Pristupljeno 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. Arhivirano iz originala 05. 04. 2012. g. Pristupljeno 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. str. 247—258. ISBN 978-3-642-32588-5. S2CID 12472692. arXiv:1111.0434 Slobodan pristup. doi:10.1007/978-3-642-32589-2_24. 
  6. ^ „Solving the Pancake Problem with an E. coli Computer”. Arhivirano iz originala 06. 04. 2012. g. Pristupljeno 29. 05. 2013. 
  7. ^ „iHOP meets iGEM”. Arhivirano iz originala 09. 03. 2012. g. Pristupljeno 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 Arhivirano na sajtu Wayback Machine (12. februar 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.

Dodatna literatura[uredi | uredi izvor]

  • 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. .

Spoljašnje veze[uredi | uredi izvor]

Šablon:Sortiranje

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