|
Palacsintarendezés 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 egy 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ákAz eredeti palacsintaprobléma
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ájaAz é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 kell 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. Erre a változatra David S. Cohen (David X. Cohen) és Manuel Blum 1995-ben a következő állítást igazolták: (ahol a felső korlát csak -től válik igazzá).[7] 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.[8]
Az egyforma palacsinták problémájaA 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.[9] A palacsintaprobléma karakterláncokonA 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[10] (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éneteBá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.[11][12] 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.[13] 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,[14] az előjel nélkülinek még bizonyos konstans faktorral történő közelítése is nehéznek bizonyult,[15] bár polinom időben közelíthetőnek bizonyult 1,375-ös approximációs faktorral.[16] Palacsintagráfok  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.[17] 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:[18]
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.[18][19][20][21] 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.[22][23] Kapcsolódó sorozatok
OEIS-sorozatok a témában:
MegvalósításaC# public static void PancakeSort<T>(IList<T> arr, int cutoffValue = 2)
where T : IComparable
{
for (int i = arr.Count - 1; i >= 0; --i)
{
int pos = i;
// Find position of max number between beginning and i
for (int j = 0; j < i - 1; j++)
{
if (arr[j].CompareTo(arr[pos]) > 0)
{
pos = j;
}
}
// is it in the correct position already?
if (pos == i)
{
continue;
}
// is it at the beginning of the array? If not flip array section so it is
if (pos != 0)
{
Flip(arr, pos + 1);
}
// Flip array section to get max number to correct position
Flip(arr, i + 1);
}
}
private static void Flip<T>(IList<T> arr, int n)
where T : IComparable
{
for (int i = 0; i < n; i++)
{
--n;
T tmp = arr[i];
arr[i] = arr[n];
arr[n] = tmp;
}
}
Fordítás
Jegyzetek
Irodalom
További információk
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Portal di Ensiklopedia Dunia
