„Palacsintarendezés” változatai közötti eltérés

A Wikipédiából, a szabad enciklopédiából
Újabb szerkesztés →
Tartalom törölve Tartalom hozzáadva
VizuálisWikiszöveges
Syp (vitalap | szerkesztései)
járőrök
89 988 szerkesztés
Új oldal, tartalma: „File:Pancake sort operation.png|right|frame|A palacsintarendezés fő művelete. A spatulával megfordítják a felső három palacsintát, az eredmény lent láthat…”
Címke: HTML-sortörés
(Nincs különbség)

A lap 2017. július 30., 20:18-kori változata

A palacsintarendezés fő művelete. A spatulával megfordítják a felső három palacsintát, az eredmény lent látható. Az égetett palacsinta-problémában a művelet után az átfordított palacsinták tetején lenne az égés, nem az aljukon.

A palacsintarendezés (pancake sorting) az a matematikai probléma, melynek során különböző méretű palacsintákból álló oszlopot nagyság szerinti sorba rendeznek oly módon, hogy az oszlopba bárhol beszúrható egy fordítólapát, és az összes fölötte lévő palacsinta megfordítható vele. A palacsintaszám (pancake number) az adott számú palacsinta rendezéséhez szükséges minimális fordítások száma. A problémát ebben a formában először Jacob E. Goodman amerikai mértanász vetette fel.[1] A rendezési probléma egy változata, melyben az egyetlen lehetséges művelet a sorozat valamely prefixumának (a karakterlánc elejétől kezdődő rész-sztringnek) megfordítása. A hagyományos rendezési algoritmusokkal ellentétben, melyeknél általában az összehasonlítások számának minimalizálására törekszenek, itt a cél a lehető legkevesebb megfordítást elvégezni. A probléma változata „égetett” palacsintákkal foglalkozik, melyek oldalait megkülönböztetjük (az egyik égett), és a palacsintákat nem egyszerűen nagyság szerinti sorba kell rendezni, hanem a rendezés végén az égett oldalukkal lefelé kell lenniük.

A palacsintaproblémák

Az eredeti palacsintaprobléma

Hat palacsintából álló oszlop. Az {5 ; 3 ; 6 ; 1 ; 4 ; 2} kiindulási állapot látható, a két hat elemű konfiguráció egyike, ami 7 manipulációt igényel (a másik a {4 ; 6 ; 2 ; 5 ; 1 ; 3}).

Az n palacsintát tartalmazó oszlop rendezéséhez mindig elégséges, minimális átfordítások száma és (kb. és ) között van, de a pontos érték nem ismert.[2]

A legegyszerűbb palacsintarendező algoritmusnak lépésre van szüksége. Ez a kiválasztásos rendezés olyan változata, melyben a nem a helyén lévő palacsinták közül a legnagyobbat egy átfordítással a tetejére, majd egy másik átfordítással közvetlenül a helyére juttatjuk el, addig ismételve a folyamatot, míg az összes palacsinta a helyére nem kerül.

1979-ben Bill Gates és Christos Papadimitriou[3] felső korlátot igazolt. Ezt 30 évvel később -re javította a University of Texas at Dallas egyetem Hal Sudborough által vezetett kutatócsoportja.[4] (Chitturi et al., 2009[5]).

2011-ben Laurent Bulteau, Guillaume Fertin és Irena Rusu[6] bebizonyították, hogy egy adott palacsintaoszlop rendezéséhez szükséges legrövidebb átfordítás-sorozat megtalálása NP-nehéz feladat.

Az égetett palacsinta problémája

Az égetett palacsinta-problémaként (burnt pancake problem) ismert változatban a palacsinták alja megégett, és a rendezés végén minden palacsintának az égett oldalával alul kel elhelyezkednie. Ebben az előjeles permutációban ha az i palacsinta égett oldalával felfelé van, akkor a permutációban az i helyén az i` negatív elem szerepel. 2008-ban egyetemi hallgatók olyan bakteriális számítógépet építettek, ami képes volt az égetett palacsinta-probléma egyszerű változatának megoldására úgy, hogy az E. coli bacilusok DNS-szakaszokat fordítottak meg az égetett palacsinták analógiájára. A DNS-molekula rendelkezik irányítással (5' és 3') és sorrenddel (promoterek a kódoló szakaszok előtt). Bár a DNS-átfordítások által képviselt számítási teljesítmény alacsony volt, egy tenyészetben a baktériumok nagy száma erősen párhuzamosítható feladatok megoldására alkalmassá teheti őket. A kísérleti elrendezésben a baktériumok akkor oldották meg a problémát, amikor antibiotikum-ellenállóvá váltak.[7]

Az egyforma palacsinták problémája

A feladatot az indiai kenyér (csapáti vagy róti) elkészítési módja ihlette. A kiindulási állapotban az összes róti egy oszlopba van felhalmozva, majd a szakács lapáttal átfordítja őket, hogy minden róti minden oldala egy ideig a tűz közvetlen közelében sülhessen. Különböző változatok képzelhetők el: a rótikat tekinthetjük egy- vagy kétoldalasnak, megtilthatjuk, hogy ugyanahhoz a rótihoz kétszer hozzáérjünk. A probléma ezen változatát Arka Roychowdhury vizsgálta elsőként.[8]

A palacsintaprobléma karakterláncokon

A fenti problémákban a palacsinták egyediek voltak, tehát az elvégzett prefix-megfordítási művelet permutáció. Karakterláncok esetében azonban a szimbólumok ismétlődhetnek, ami csökkentheti az elvégzendő prefix-megfordítási műveletek számát. Chitturi and Sudborough (2010), illetve Hurkens et al. (2007) egymástól függetlenül megmutatták, hogy két kompatibilis karakterlánc között minimális számú prefix-megfordítási művelettel történő transzformáció NP-nehéz feladat. Néhány korlátot is meghatároztak erre. Hurkens et al. pontos algoritmust adott bináris és ternáris karakterláncok rendezésére. Chitturi[9] (2011) bizonyította azt is, hogy a két kompatibilis, előjeles karakterlánc között minimális számú prefix-megfordítási művelettel történő transzformáció – ami az égetett palacsinta-probléma karakterlánc-változata – szintén NP-nehéz feladat.

Története

Bár sokszor csak oktatási eszköznek tekintik, a palacsintarendezésnek fontos alkalmazásai vannak párhuzamos processzorhálózatok területén a processzorok között hatékony útválasztási algoritmus biztosításában.[10][11]

A probléma népszerűségét az is növelte, hogy ebben a témában jelent meg az egyedüli matematikai publikációja a Microsoft alapítójának, Bill Gatesnek (mint William Gates), Bounds for Sorting by Prefix Reversal címmel. Az 1979-ben megjelent publikációban leír egy hatékony palacsintarendező algoritmust.[3] Ráadásul a Futurama társszerzője, David X. Cohen (mint David S. Cohen) is foglalkozott az égetett palacsinta-problémával.[12]

Néhány kapcsolódó problémát is tanulmányoztak a közelmúltban, az előjeles, megfordítással történő rendezés és a megfordítással történő rendezés problémáit. Ezeknél nem csak a sztring elejétől kezdődő, prefix-megfordítást lehet végezni, hanem bármilyen karakterlánc megfordítható. Bár az előjeles esetre hatékony egzakt algoritmust sikerült találni,[13] az előjel nélkülinek még bizonyos konstans faktorral történő közelítése is nehéznek bizonyult,[14] bár polinom időben közelíthetőnek bizonyult 1,375-ös approximációs faktorral.[15]

Palacsintagráfok

Bővebben: Palacsintagráf
A P3 palacsintagráf
A P4 palacsintagráf rekurzívan előállítható a P3 4 kópiájából úgy, hogy az {1, 2, 3, 4} halmaz más-más elemét fűzzük hozzá az egyes kópiákhoz.

Egy n-palacsintagráf, jelölése Pn olyan egyszerű, irányítatlan, hurokmentes gráf, melynek csúcshalmaza az 1,2,...,n számok permutációinak (sorbaállításainak) halmaza. Két permutáció között akkor húzódik él, ha az egyik tranzitív módon átvihető a másikba egy kezdőszeletének megfordításával (prefix reversal). A palacsintarendezési probléma és a palacsintagráf átmérőjének meghatározása egymással ekvivalens.[16]

Az n méretű palacsintagráf, Pn rekurzívan előállítható a Pn−1 palacsintagráf n kópiájából oly módon, hogy az {1, 2, …, n} halmaz más-más elemét fűzzük hozzá az egyes kópiákhoz.

A Pn palacsintagráf reguláris, csúcsainak száma n!, fokszáma n−1. Girthparamétere:

.

A Pn palacsintagráf γ(Pn) génuszáról elmondható, hogy[17]:

A palacsintagráfok számos érdekes tulajdonsággal rendelkeznek – szimmetrikus és rekurzív szerkezetük (Cayley-gráfok, ezért csúcstranzitívek), szublogaritmikus fokszámmal és átmérővel rendelkeznek és relatíve ritkák (pl. a hiperkockagráfokhoz képest), ezért a permutáló csillaggráfok mellett a párhuzamos számítógépek hálózati összeköttetéseinek modelljeként komoly érdeklődés tárgyát képezik.[17][18][19][20] Hálózati összeköttetések modelljeként tekintve a palacsintagráfokra, a gráf átmérője a kommunikációs késleltetést reprezentálja[21][22].

Kapcsolódó sorozatok

Adott n magasságú oszlopok száma, melyek rendezése k átfordítást igényel
Magasság
n		 k
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
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
13 1 12 132 1451 14556 130096 1030505 7046318 40309555 184992275 639783475 1525125357 2183056566 1458653648 186874852 2001

The Online Encyclopedia of Integer Sequences-sorozatok a témában:

  • OEIS A058986 – maximális szükséges átfordítások száma
  • OEIS A067607 – a maximális átfordítást igénylő oszlopok száma (lásd fent)
  • OEIS A078941 – maximális szükséges átfordítások száma az „égetett” esetben
  • OEIS A078942 – szükséges átfordítások száma a rendezett „égetett oldal felül” oszlopnál
  • OEIS A092113 – a fenti háromszög, soronként kiolvasva

[9]

Fordítás

  • Ez a szócikk részben vagy egészben a Pancake sorting című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

  1. ↑ Simon Singh. „Flipping pancakes with mathematics”, The Guardian , 2013. november 14. (Hozzáférés: 2014. március 25.) 
  2. ↑ Fertin, G. and Labarre, A. and Rusu, I. and Tannier, E. and Vialette, S.. Combinatorics of Genome Rearrangements. The MIT Press (2009). ISBN 9780262062824 
  3. ↑ a b Gates, W. (1979). „Bounds for Sorting by Prefix Reversal”. Discrete Mathematics 27, 47–57. o. DOI:10.1016/0012-365X(79)90068-2.  
  4. ↑ Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics. University of Texas at Dallas News Center, 2008. szeptember 17. (Hozzáférés: 2008. november 10.) „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.”
  5. ↑ Chitturi, B. (2009. augusztus 31.). „An (18/11)n upper bound for sorting by prefix reversals”. Theoretical Computer Science 410 (36), 3372–3390. o. DOI:10.1016/j.tcs.2008.04.045.  
  6. ↑ „Pancake Flipping Is Hard”. Journal of Computer and System Sciences 81, 1556–1574. o. DOI:10.1016/j.jcss.2015.02.003.  
  7. ↑ (2008) „Engineering bacteria to solve the Burnt Pancake Problem”. Journal of Biological Engineering 2, 8. o. DOI:10.1186/1754-1611-2-8. PMID 18492232.  
  8. ↑ https://arkaroychowdhury1.wordpress.com/portfolio/flippingpancakes/
  9. ↑ a b „A NOTE ON COMPLEXITY OF GENETIC MUTATIONS”. Discrete Mathematics, Algorithms and Applications 03 (03). DOI:10.1142/S1793830911001206.  
  10. ↑ (1993) „Fault tolerant routing in the star and pancake interconnection networks”. Information Processing Letters 45 (6), 315–320. o. DOI:10.1016/0020-0190(93)90043-9.  .
  11. ↑ Proceedings of Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies, 2006 (PDCAT '06), 254–259. o.. DOI: 10.1109/PDCAT.2006.56 (2006). ISBN 0-7695-2736-1 .
  12. ↑ (1995) „On the problem of sorting burnt pancakes”. Discrete Applied Mathematics 61 (2), 105. o. DOI:10.1016/0166-218X(94)00009-3.  
  13. ↑ 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.
  14. ↑ Berman, P. and Karpinski, M. "On Some Tighter Inapproximability Results." Proc. 26th ICALP (1999), LNCS 1644, Springer, 200-209, 1999.
  15. ↑ 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.
  16. ↑ Asai, Shogo (2006. szeptember 1.). „Computing the Diameter of 17-Pancake Graph Using a PC Cluster.”. Euro-Par 2006 Parallel Processing: 12th International Euro-Par Conference. DOI:10.1007/11823285_117.  
  17. ↑ a b Nguyen, Quan (2009. november 5.). „On the Genus of Pancake Network.”. The International Arab Journal of Information Technology 8 (3), 289–292. o.  
  18. ↑ Akl, S.G. (1993. május 21.). „Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry.”. Networks 23 (4), 215–225. o. DOI:10.1002/net.3230230403.  
  19. ↑ Bass, D.W. (2003. március 1.). „Pancake problems with restricted prefix reversals and some corresponding Cayley networks.”. Journal of Parallel and Distributed Computing 63 (3), 327–336. o. DOI:10.1016/S0743-7315(03)00033-9.  
  20. ↑ Berthomé, P. (1996. december 1.). „Optimal information dissemination in star and pancake networks.”. IEEE Transactions on Parallel and Distributed Systems 7 (12), 1292–1300. o. DOI:10.1109/71.553290.  
  21. ↑ Kumar, V., Grama, A., Gupta, A., Karypis, G.: Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin/Cummings (1994)
  22. ↑ Quinn, M.J.: Parallel Computing: Theory and Practice, second edition. McGrawHill (1994)

Irodalom

  • Heydari, M. H. and Sudborough, I. H. "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.

További információk

A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Palacsintarendezés&oldid=18962365”