Schreier-Sims algoritmus | |
---|---|
| |
Valaki után elnevezve | Charles Sims és Otto Schreyer |
Szerző | Charles Sims |
célja | Permutációs csoport sorrendjének meghatározása |
Adatstruktúra | Permutációk |
legrosszabb idő |
A Schreier-Sims algoritmus a számítási csoportelmélet területéről származó algoritmus , amely lehetővé teszi, hogy egyetlen végrehajtás után lineáris időben megtaláljuk a permutációk által generált csoport sorrendjét , ellenőrizzük, hogy egy elem egy ilyen csoportba tartozik-e, és felsoroljuk az elemeit. . Az algoritmust Charles Sims javasolta 1970-ben primitív permutációs csoportok keresésére [1] , és Schreier alcsoportgenerálási lemmáján [2] alapul . Az algoritmus által talált permutációs csoport reprezentációja hasonló a mátrix lépésformájához a sorterére [3] . A Sims által kifejlesztett módszerek képezik a legtöbb permutációs csoportokkal való munkavégzés modern algoritmusának alapját [4] , az algoritmus módosításait olyan modern számítógépes algebrai rendszerekben is alkalmazzák, mint a GAP és a Magma [5] . Az algoritmus egyik legkézenfekvőbb alkalmazása, hogy a Rubik-kocka megoldására használható [6] .
A permutációs csoportok elméletének egyik fő problémája az adott fokú permutációs csoportok keresése (vagyis egy halmaz elemeinek minimális száma, amelynek permutációs csoportja egy adott permutációs csoportot tartalmaz). 1970-re a 2-től 11-ig terjedő hatványokhoz az összes permutációs csoportot megtalálták, a 12-től 15-ig terjedő hatványokhoz az összes tranzitív csoportot (vagyis a generátorkészleten tranzitívan ható alcsoportokat ), a 16-tól 20-ig terjedő hatványokhoz pedig csak primitív csoportokat találtak. csoportok permutációit találtak . A magasabb fokú primitív csoportok keresésére Charles Sims kifejlesztett egy programot, amely rendet és valamilyen struktúrát talál a generátorkészlete által megadott permutációs csoportban [1] .
A Sims cikkében említett eredeti program az IBM 7040 számára készült a Rutgers Egyetemen , és minden olyan csoportot támogatott, akiknek végzettsége 50 alatt volt [7] . Egy algoritmus futási idejének pontos becslését először Furst, Hopcroft és Lax végezte el 1980-ban [8] . A futási időt Jerrum 1982-ben [9] és Donald Knuth 1981-ben [10] javította . 1980-ban kidolgozták az algoritmus hatékony valószínűségi változatát [11] . Az algoritmus különféle változatait, köztük azokat, amelyek a pályafa helyett a Schreier-vektort használják, Sheresh 2003- ban leszerelte [12] [13] .
A számítási csoportelméletben a permutációs csoportok feletti algoritmusok az egyik legfejlettebb terület, és még ma is ezeknek az algoritmusoknak a többsége a Sims által kidolgozott módszereken alapul [4] .
A permutációs csoporttal végzett számítások hatékonysága alapvetően attól függ, hogyan van megadva a programban [2] . Ennek egyik hatékony módja az, hogy számos alcsoportját elkülönítjük, és a sorozat minden egyes alcsoportjához egyedi koseteket választunk az elődhöz képest. A Charles Sims által javasolt algoritmus számos olyan alcsoportot talál, amelyekben minden következő csoport az előző stabilizátora . Azt a pontsorozatot, amelyre stabilizátorokat készítenek, bázisnak nevezzük , a sorozat egyes csoportjaihoz tartozó generáló elemeket tartalmazó halmazt pedig erős generáló halmaznak [2] .
Az algoritmus létrehoz egy bázist és egy erős generátorkészletet a generátorkészlete által megadott permutációs alcsoporthoz , Schreier lemmáját felhasználva a generátorkészletek megtalálásához. A közbenső lépésekben kapott halmazok mérete exponenciálisan növekszik, ezért az algoritmusnak olyan változatait fejlesztették ki, amelyek csökkentik a figyelembe vett generáló elemek számát [2] .
A fent leírt reprezentáció feloszt egy csoportot a benne beágyazott részhalmazok szorzatára, hasonlóan ahhoz, ahogy a lépéses reprezentáció a vektorteret a benne beágyazott alterek közvetlen összegére hasítja [3] .
A szimmetrikus csoport olyan csoport, amelynek elemei valamely halmaz elemeinek permutációi . Általában a .-t ilyen halmaznak tekintik . Ebben a jelölésben egy csoport elemeit leképezéseknek tekinthetjük, amelyek magukba foglalnak egy halmazt , vagyis annak automorfizmusait . Az ilyen jelölésben szereplő csoportművelet a permutációk összetétele a permutációkhoz, és definíciója: , ahol for . Ennek megfelelően az egységpermutáció olyan permutáció lesz , hogy , és a fordított permutáció megadható [14] .
Legyen a hosszúságú permutációk halmaza . Egy halmaz generált alcsoportja a legkisebb befoglalási alcsoport , amely részhalmazként vagy ennek megfelelő módon az elemek és inverzeik véges szorzataként ábrázolható összes elem alcsoportját tartalmazza. Egy permutációs csoport sorrendje a benne lévő elemek száma, foka pedig annak a halmaznak a kardinalitása, amelyre hat. Ilyen jelölés esetén az algoritmusnak képesnek kell lennie [7] :
Az algoritmusmódosításokat a két legnépszerűbb , számítási csoportelméletre szakosodott számítógépes algebra rendszerben – a GAP -ban és a Magmában [5] valósítják meg . A permutációs csoportokkal való munkavégzésre szolgáló eszközök, beleértve a kosetfelsorolási algoritmusokat és a Schreier-Sims algoritmust, szintén elérhetők a népszerűbb Maple és Mathematica rendszerekben [15] . Kezdetben az algoritmust egy adott fokú primitív permutációs csoportok keresésére fejlesztették ki [1] , de később az alkalmazási köre sokszorosára nőtt – például ezzel az algoritmussal lehet megoldásokat találni egy adott Rubik-kocka konfigurációra . mivel forgásai egy csoportot alkotnak [6] . Ezenkívül az algoritmus jól mutatkozott a mátrixcsoportokkal végzett munka során [16] .
Legyen valamilyen véges csoport részcsoportja , amelyet a bal oldali kosettek családjának keresztirányával jelölünk . Bármely elem egyedileg ábrázolható , hol és . Ha ezt az eredményt egymás után alkalmazzuk alcsoportjaira, az alábbi formában általánosítható [3] [17] :
Legyen alcsoportok sorozata . Ekkor bármely elem egyedileg ábrázolható , ahol . |
A fent leírt nézet a következő tulajdonságokkal rendelkezik:
Ahhoz, hogy egy generált alcsoporthoz tartozó elemeket is ellenőrizhessük, speciális formájú alcsoportok sorozatát kell figyelembe venni, nevezetesen a stabilizátorokból állókat [7] .
Hadd cselekedjen a forgatáson . Kiválasztunk egy elemhalmazt, és számos alcsoportot alkotunk úgy, hogy hol legyen az elem stabilizátora . Más szavakkal, az elemek egy alcsoportja, amely az egyes elemeket önmagába fordítja [7] . Ezzel a megközelítéssel minden következő lépésben a halmaz azon része , amelyre a következő alcsoport nem triviálisan hat , egy elemmel csökken, és annak az alcsoportnak a sorrendje, amellyel a munkát végezzük, legalább kétszerese lesz. . Ebből következik, hogy a kívánt partíció megtalálása előtt az algoritmus iterációira lesz szükség [18] .
A kosettek megszerkesztéséhez ki kell használni azt a tényt, hogy a pálya elemei és a stabilizátor bal oldali kosettjei között egy-egy megfelelés (bijekció) van [19] .
BizonyítékA pályákra és stabilizátorokra vonatkozó tétel szerint a kosettek halmaza és a pálya ekvivalens teljesítményű. Minden elemet társítson a pálya egy eleméhez .
Legyen , majd a halmazok és egybeesnek. De ebből az is következik, hogy egybeesik és :
t egy ω = t egy ( G ω ω ) = ( t egy G ω ) ω = ( t 2 G ω ) ω = t 2 ( G ω ω ) = t 2 ω {\displaystyle t_{1}\omega =t_{1}(G_{\omega }\omega )=(t_{1}G_{\omega })\omega =(t_{2}G_{\omega })\ omega =t_{2}(G_{\omega }\omega )=t_{2}\omega }Minden kosetthez pontosan egy elemet rendeltek hozzá a pályának. Mivel a kosetek az egész csoportot lefedik , minden illeszkedő elem eltérő. Tehát ez valóban egy bijekció. ■
A bizonyításból következik, hogy a kosetek képviselőiként vehetünk olyan elemeket, amelyek a pálya különböző pontjait valósítják meg [19] .
Jelölje olyan elemmel , hogy . A stabilizátorok sorozatára való felosztás lehetővé teszi, hogy ellenőrizze, hogy az elem a [7] csoportba tartozik-e :
Ezek a tulajdonságok lehetővé teszik az átmenetet a -ról a -ra , ami végül ahhoz a tényhez vezet, hogy az aktuális elemnek a -ban kell lennie . Ha ez valóban így van, akkor , ahonnan lehetséges a [7] kifejezés .
Legyen a csoportnak generátorkészlete . Bármely elem pályája egy csoport működése alatt a következő formájú fába szervezhető [17] :
A leírt fa mélységi bejárással is felépíthető , ehhez minden csúcson végig kell rendezni az elemet , amíg ki nem derül, hogy a [17] számára még nincs csúcs kijelölve . Megvalósítási példa Pythonban :
# Egy pályafát épít adott w elemnek és S generáló halmaznak build_schreier_tree ( w , S , orbit ): for g in S : if g [ w ] not in orbit : orbit [ g [ w ]] = alkalmaz ( g , orbit [ w ]) build_schreier_tree ( g [ w ], S , orbit )Itt a függvény visszaadja a csoportművelet elemre történő alkalmazásának eredményét, valamint első és második argumentumként, és az elemet a -ban tárolja .
A Schreier-lemmából az következik, hogy a stabilizátort a Schreier-generátorok halmaza állítja elő: . Ez az eredmény lehetővé teszi, hogy generáló halmazt alkossunk a for generátorkészletből és az elem pályájából . Egy új generátorkészletet visszaadó függvény lehetséges megvalósítása [20] :
# Egy generátorkészletet vesz fel G_{w-1}-hez és egy w pályát # Egy generátorkészletet ad vissza G_w def make_gen ( S , orbit ): n = len ( next ( iter ( S ))) newS = set () for s in S : for u in orbit : newS . add ( redukál ( alkalmaz , [ inverz ( kering [ s [ u ]]), s , kering [ u ]])) return newSAz algoritmus ezzel nem merül ki, hiszen bár az új generátorkészlet mérete polinomiálisan függ a pálya és a régi generátorkészlet méretétől egy egyedi hívás esetén, összességében ennek a függvénynek a hívása esetén a generáló halmaz mérete. halmaz exponenciálisan nő [2] .
A generátorkészletek ellenőrizetlen növekedésének elkerülése érdekében szitálási eljárást kell alkalmazni . Ehhez a következő nyilatkozatra lenne szükség [3] [20] :
Hadd . Ekkor legfeljebb olyan elemekből álló halmazt lehet megszerkeszteni , hogy . |
Először is bizonyítsuk be a következő lemmát:
Hadd . Ekkor a következő átalakítások nem változnak :
|
E műveletek egyikének alkalmazása után egy halmazt kapunk . Nyilvánvaló, hogy . Másrészt ezek a konverziók megfordíthatók azonos típusú konverziókkal, tehát . Szóval . ■
Ilyen transzformációk segítségével a halmazt olyan alakra redukálhatjuk, hogy a halmaz bármely párjához legfeljebb egy olyan elem legyen , hogy:
s ( ω egy ) = ω egy , s ( ω 2 ) = ω 2 , … , s ( ω én − egy ) = ω én − egy , s ( ω én ) = ω j ≠ ω én {\displaystyle s(\omega _{1})=\omega _{1},\ s(\omega _{2})=\omega _{2},\dots ,\ s(\omega _{i- 1})=\omega _{i-1},\ s(\omega _{i})=\omega _{j}\neq \omega _{i}} Ezt úgy érhetjük el, hogy egyenként hozzáadjuk az elemeket az új halmazhoz , és a Gauss-módszerhez hasonlóan járunk el :Ez az algoritmus csak a fent jelzett elemi műveleteket használja, ezért . Figyeljük meg, hogy ha , akkor , tehát az algoritmusban az átmenet helyes, és minden pár valójában legfeljebb egy permutációnak felel meg. Figyelembe véve, hogy legfeljebb ilyen párok vannak , megkapjuk a szükséges állítást.
■A bizonyításban leírt eljárást Sims-szűrőnek nevezik, és a [21] -ben működik . A megvalósítása így nézhet ki:
# Felvesz egy szülőhalmazt S # Egy vékonyított szülőhalmazt ad vissza S' def normalize ( S ): n = len ( next ( iter ( S ))) newS = set () base = [{} for i in range ( n )] s - hez S -ben : x - hez a tartományban ( 0 , n ): ha s [ x ] != x : ha s [ x ] alapban [ x ]: s = alkalmazza ( inverz ( s ) , alap [ x ] [ s ] [ x ]]) else : alap [ x ][ s [ x ]] = s newS . add ( s ) break return newSA Sims szűrőn kívül a Jerrum szűrővel [22] lehet keresni egy kis készletet . A Sims szűrővel ellentétben, amely a legtöbb elemből álló halmazt találja meg, a Jerrum szűrő legfeljebb egy elemből álló halmazt talál . Ugyanakkor a Jerrum szűrő működik -re , így a Schreier-Sims algoritmus esetén célszerű a Sims szűrőt használni [21] .
A fentiek együttesen egy olyan algoritmust adnak, amely a következőképpen valósítható meg tömören [20] :
# Egy generátorkészletet vesz fel S = s1, ..., sk # Coset transzverzális U1, ..., Uk def schreier_sims ( S ): n = len ( next ( iter ( S ))) ans = [] w = 0 míg S : orbit = {} keringés [ w ] = sor ( tartomány ( n )) build_schreier_tree ( w , S , orbit ) ans += [[ kering [ i ] for i in orbit ]] S = normalizál ( make_gen ( S , orbit )) w += 1 return ansLépésről lépésre cselekvéseinek jelentése a következő:
A kimeneten az algoritmus egy listát ad vissza, amelynek elemei a cosets transzverzálisai .
Összességében az algoritmus nem igényel több iterációt. Minden iteráció a következőkből áll:
Az érték abban az esetben, ha a halmaz adott , nem változik az algoritmus során, és egyenlő: . A generátorkészlet mérete kezdetben egyenlő , és minden további lépésben nem haladja meg a . Így az algoritmus teljes futási ideje a fenti megvalósításban a következőre becsülhető: [8] [12] [13] .
Korábban kimutatták, hogy az algoritmus iterációkat igényel. Általános esetben a csoport mérete nagyságrendileg lehet , és ebben az esetben a Stirling-képlet szerint, ami nyilvánvalóan nagyobb . De bizonyos esetekben a csoport sorrendje kicsi, és ezért jövedelmezőbb egy olyan algoritmus használata, amely a -tól függ , és nem - például ha valamilyen ismert csoportról van szó, amelyet permutációs csoportként adnak meg [12] .
Cayley tétele szerint bármely véges csoport izomorf valamilyen permutációs csoporttal . Egy ilyen csoport mértéke nagy lehet, de sok csoportnál a sorrendjük olyan, hogy . Például a diédercsoport izomorf a ciklikus eltolódás és reflexió által generált permutációs csoporttal . Vagyis ennek a csoportnak a foka , a sorrend pedig , és . Az ilyen csoportokhoz futásidejű algoritmusok jöhetnek számításba , amelyeket pszeudo-lineárisnak neveznek [12] .
Annak érdekében, hogy az algoritmust közelebb hozza a pszeudo-lineárishoz, és csökkentse a futási idejében lévő fokot, Sheresh az algoritmus olyan verzióihoz jutott, amelyek megkövetelik [18] :
Az algoritmus első működő valószínűségi változatát Jeffrey Leon fejlesztette ki 1980-ban [11] . Általában erre gondolnak, amikor a valószínűségi Schreyer-Sims módszerről beszélnek. Ebben a Schreier generátorok ritkításánál ez az eljárás idő előtt megszakadt, ha egymás után 20 generátor bizonyult faktorizáltnak. Sheresh megmutatta, hogy néhány optimalizálással együtt ez az eljárás a következő állítást adja [5] :
Bármely konstanshoz létezik egy Monte Carlo-típusú algoritmus , amely maximum hibavalószínűséggel egy erős generátorkészletet hoz létre a permutációs csoporthoz idő és memória felhasználásával . |
A modern számítógépes algebrai rendszerekben általában az algoritmus ezen változatának különféle heurisztikájú módosításait használják a program gyorsítására [5] .
Csoportelmélet | |
---|---|
Alapfogalmak | |
Algebrai tulajdonságok | |
véges csoportok |
|
Topológiai csoportok | |
Algoritmusok csoportokon |