Schreier-Sims algoritmus | |
---|---|
Earl Cayley Group | |
Pojmenoval podle | Charles Sims a Otto Schreyer |
Autor | Charles Sims |
účel | Určení řádu permutační grupy |
Datová struktura | Permutace |
nejhorší čas |
Algoritmus Schreier-Sims je algoritmus z oblasti výpočetní teorie grup , který umožňuje po jediném provedení v lineárním čase najít pořadí skupiny generované permutacemi , zkontrolovat, zda prvek do takové skupiny patří a vyjmenovat její prvky. . Algoritmus navrhl Charles Sims v roce 1970 k nalezení primitivních permutačních grup [1] a je založen na Schreierově lemmatu generování podskupin [2] . Reprezentace permutační grupy, kterou algoritmus najde, je podobná stupňovité formě matice pro její řádkový prostor [3] . Metody vyvinuté Simsem tvoří základ nejmodernějších algoritmů pro práci s permutačními skupinami [4] , modifikace algoritmu se používají i v moderních systémech počítačové algebry jako GAP a Magma [5] . Jednou z nejzřejmějších aplikací algoritmu je, že jej lze použít k řešení Rubikovy kostky [6] .
Jedním z hlavních problémů teorie permutačních grup je hledání permutačních grup daného stupně (tedy minimálního počtu prvků množiny, jejíž permutační grupa obsahuje danou permutační grupu). Do roku 1970 byly pro mocniny 2 až 11 nalezeny všechny permutační grupy, pro mocniny 12 až 15 všechny tranzitivní grupy (tj. podgrupy působící tranzitivně na generátoru ) a pro mocniny 16 až 20 pouze primitivní skupiny byly nalezeny permutace . Pro hledání primitivních skupin vyššího stupně vyvinul Charles Sims program, který najde řád a nějakou strukturu v permutační skupině dané její generující množinou [1] .
Původní program zmíněný v Simsově článku byl napsán pro IBM 7040 na Rutgers University a podporoval jakoukoli skupinu, jejíž míra byla nižší než 50 [7] . Přesný odhad doby běhu algoritmu poprvé provedli Furst, Hopcroft a Lax v roce 1980 [8] . Průběžnou dobu zlepšil Jerrum v roce 1982 [9] a Donald Knuth v roce 1981 [10] . V roce 1980 byla vyvinuta efektivní pravděpodobnostní verze algoritmu [11] . Různé varianty algoritmu, včetně těch, které používají Schreierův vektor místo orbitového stromu, byly rozebrány Sheresh v roce 2003 [12] [13] .
Ve výpočetní teorii grup jsou algoritmy nad permutačními grupami jednou z nejrozvinutějších oblastí a dokonce i dnes je většina těchto algoritmů založena na metodách vyvinutých Simsem [4] .
Efektivita výpočtů s permutační skupinou v podstatě závisí na tom, jak je specifikována v programu [2] . Jedním z účinných způsobů, jak toho dosáhnout, je izolovat řadu jejích podskupin a vybrat jedinečné množiny pro každou podskupinu v této řadě vzhledem k jejímu předchůdci. Algoritmus navržený Charlesem Simsem najde řadu podskupin, ve kterých každá další skupina je stabilizátorem té předchozí. Posloupnost bodů, pro které jsou stabilizátory konstruovány, se nazývá základ a množina obsahující generující prvky pro každou skupinu v řadě se nazývá silná generující množina [2] .
Algoritmus zkonstruuje základ a silnou generátorovou množinu pro permutační podskupinu danou její generátorovou sadou , pomocí Schreierova lemmatu k nalezení množin generátorů. Velikost množin získaných v mezikrokech roste exponenciálně, proto byly vyvinuty varianty algoritmu, které snižují počet uvažovaných generujících prvků [2] .
Výše popsaná reprezentace rozděluje skupinu na součin podmnožin v ní vnořených, podobně jako kroková reprezentace rozděluje vektorový prostor na přímý součet podprostorů v něm vnořených [3] .
Symetrická grupa je grupa, jejíž prvky jsou permutacemi prvků nějaké množiny . Obvykle se jako taková sada bere . V takovém zápisu lze na prvky grupy nahlížet jako na zobrazení , která do sebe berou množinu , tedy její automorfismy . Skupinovou operací v takovém zápisu je složení permutací, pro permutace a definované jako , kde pro . V souladu s tím bude jednotková permutace taková permutace, že , a obrácená permutace může být dána jako [14] .
Dovolit je množina permutací délky . Vygenerovaná podskupina množiny je nejmenší inkluzní podskupinou , která obsahuje jako podmnožinu nebo ekvivalentně podskupinu všech prvků , které lze reprezentovat jako konečný součin prvků a jejich inverzí. Pořadí permutační grupy je počet prvků v ní a její stupeň je mohutnost množiny , na kterou působí. V takovém zápisu by měl být algoritmus schopen [7] :
Modifikace algoritmů jsou implementovány ve dvou nejpopulárnějších systémech počítačové algebry specializovaných na výpočetní teorii grup — GAP a Magma [5] . Nástroje pro práci s permutačními skupinami, včetně algoritmů pro výčet cosetů a algoritmu Schreier-Sims, jsou také dostupné v obecnějších populárních systémech Maple a Mathematica [15] . Zpočátku byl algoritmus vyvinut pro hledání primitivních permutačních grup daného stupně [1] , ale následně se rozsah jeho použití mnohonásobně rozrostl - například pomocí tohoto algoritmu lze nalézt řešení pro danou konfiguraci Rubikovy kostky , jelikož její rotace tvoří skupinu [6] . Algoritmus se také dobře ukázal při práci s maticovými skupinami [16] .
Dovolit být podgrupou nějaké konečné grupy , označované transverzálem rodiny levých coset . Jakýkoli prvek může být jednoznačně reprezentován jako , where a . Postupnou aplikací tohoto výsledku na a jeho podskupiny jej lze zobecnit v následující podobě [3] [17] :
Dovolit být řada podskupin . Potom může být jakýkoli prvek jednoznačně reprezentován jako , where . |
Výše popsaný pohled má následující vlastnosti:
Abychom mohli také zkontrolovat, zda prvky patří do vygenerované podskupiny, je nutné uvažovat řadu podgrup speciálního tvaru, konkrétně podskupiny složené ze stabilizátorů [7] .
Nechte působit na sadě . Vybereme si množinu prvků a sestrojíme řadu podskupin tak, že kde je stabilizátor prvku . Jinými slovy, je podskupinou prvků , které převádějí každý z prvků do sebe [7] . S tímto přístupem se v každém dalším kroku část množiny , na kterou netriviálně působí další podskupina , sníží o jeden prvek a pořadí podskupiny, se kterou se pracuje, bude nejméně dvojnásobné. . Z toho vyplývá, že před nalezením požadovaného oddílu bude nutné provést iterace algoritmu [18] .
Ke konstrukci kosset je potřeba využít faktu, že mezi prvky orbity a levými kosetami stabilizátoru existuje korespondence jedna ku jedné (bijekce) [19] .
DůkazPodle věty o drahách a stabilizátorech jsou množina koset a oběžná dráha výkonově ekvivalentní. Přiřaďte každý prvek prvku oběžné dráhy .
Nechte , pak se množiny a shodují. Ale z toho vyplývá, že se také shodují a :
t jeden ω = t jeden ( G ω ω ) = ( t jeden 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 }Každé kosetě byl přiřazen přesně jeden prvek oběžné dráhy. Protože cosety pokrývají celou skupinu , jsou všechny spárované prvky odlišné. Jde tedy skutečně o bijekci. ■
Z důkazu vyplývá, že jako zástupce kosset lze brát prvky realizující různé body oběžné dráhy [19] .
Označte takovým prvkem , že . Rozdělení na řadu stabilizátorů vám umožní zkontrolovat, zda prvek patří do skupiny [7] :
Tyto vlastnosti umožňují provést přechod z do , což nakonec povede k tomu, že aktuální prvek by měl ležet v . Pokud tomu tak skutečně je, pak , odkud je možné vyjádřit [7] .
Nechte skupinu mít generovací sadu . Dráhu libovolného prvku pod působením skupiny lze organizovat do stromu následujícího tvaru [17] :
Popsaný strom lze sestavit hloubkovým procházením, k tomu je nutné třídit prvek v každém vrcholu , dokud se neukáže, že vrchol ještě nebyl přidělen [17] . Příklad implementace v Pythonu :
# Sestaví orbitový strom daný element w a vygeneruje sadu S def build_schreier_tree ( w , S , orbit ): pro g v S : pokud g [ w ] není na oběžné dráze : orbit [ g [ w ]] = použít ( g , orbit [ w ]) build_schreier_tree ( g [ w ], S , orbita )Zde funkce vrátí výsledek použití operace skupiny na prvky a jako první a druhý argument a prvek je uložen v .
Ze Schreierova lemmatu vyplývá, že stabilizátor je generován množinou Schreierových generátorů: . Tento výsledek nám umožňuje sestavit generující množinu pro z generující množiny pro a oběžné dráhy prvku . Možná implementace pro funkci, která vrací novou generující sadu [20] :
# Vezme sadu generátorů pro G_{w-1} a orbit w # Vrátí sadu generátorů pro G_w def make_gen ( S , orbit ): n = len ( next ( iter ( S ))) newS = set () for s v S : pro u na oběžné dráze : newS . přidat ( snížit ( aplikovat , [ inverzní ( oběžná dráha [ s [ u ]]), s , oběžná dráha [ u ]])) vrátit novéSAlgoritmus tím není vyčerpán, protože ačkoli velikost nové generující množiny závisí polynomiálně na velikosti orbity a staré generující množiny pro jedno jednotlivé volání, v souhrnu pro všechna volání této funkce je velikost generující množiny množina roste exponenciálně [2] .
Aby se zabránilo nekontrolovanému růstu generátorových soustrojí, musí být aplikován postup prosévání . To by vyžadovalo následující prohlášení [3] [20] :
Nechte _ Pak je možné sestrojit množinu maximálně prvků tak, že . |
Nejprve dokažme následující lemma:
Nechte _ Potom se následující transformace nezmění :
|
Nechť po aplikaci jedné z těchto operací dostaneme množinu . Je zřejmé, že . Na druhou stranu lze tyto konverze zvrátit konverzemi stejného typu, takže . Takže . ■
Pomocí takových transformací můžeme množinu zredukovat do takové podoby, že pro každou dvojici v množině existuje maximálně jeden prvek takový, že:
s ( ω jeden ) = ω jeden , s ( ω 2 ) = ω 2 , … , s ( ω i − jeden ) = ω i − jeden , s ( ω i ) = ω j ≠ ω i {\displaystyle s(\omega _{1})=\omega _{1},\ s(\omega _{2})=\omega _{2},\tečky ,\ s(\omega _{i- 1})=\omega _{i-1},\ s(\omega _{i})=\omega _{j}\neq \omega _{i}} Toho lze dosáhnout přidáváním prvků do nové množiny jeden po druhém a postupem podobně jako Gaussova metoda :Tento algoritmus používá pouze základní operace uvedené výše, proto . Všimněte si, že if , then , takže přechod do z v algoritmu je správný a každý pár ve skutečnosti odpovídá ne více než jedné permutaci. Vezmeme-li v úvahu, že takových dvojic je nejvíce , získáme požadované tvrzení.
■Postup popsaný v důkazu se nazývá Sims filtr a funguje v [21] . Jeho implementace může vypadat takto:
# Vezme nadřazenou množinu S # Vrátí ztenčenou nadřazenou množinu S' def normalize ( S ): n = len ( další ( iter ( S ))) newS = sada () základ = [{} pro i v rozsahu ( n )] for s v S : pro x v rozsahu ( 0 , n ): if s [ x ] != x : if s [ x ] v základu [ x ]: s = platí ( inverzní ( s ), základ [ x ][ s [ x ]]) else : základ [ x ][ s [ x ]] = s newS . přidat ( s ) přerušit návrat novinkySKromě filtru Sims lze pro vyhledání malé sady použít filtr Jerrum [22] . Na rozdíl od filtru Sims, který najde množinu maximálně prvků, filtr Jerrum najde množinu maximálně prvků. Zároveň funguje filtr Jerrum pro , takže v případě algoritmu Schreier-Sims je vhodnější použít filtr Sims [21] .
Vše výše uvedené dohromady dává algoritmus, který lze stručně implementovat následovně [20] :
# Vezme generující množinu S = s1, ..., sk # Vrátí transverzály koset U1, ..., Uk def schreier_sims ( S ): n = len ( další ( iter ( S ))) ans = [] w = 0 zatímco S : orbita = {} orbita [ w ] = n-tice ( rozsah ( n )) build_schreier_tree ( w , S , orbit ) ans += [[ orbit [ i ] pro i na oběžné dráze ]] S = normalizovat ( make_gen ( S , orbit )) w += 1 návrat ansKrok za krokem mají jeho akce následující význam:
Na výstupu algoritmus vrátí seznam, jehož prvky jsou transverzály coset .
Celkově algoritmus nevyžaduje žádné další iterace. Každá iterace se skládá z:
Hodnota v případě, že je zadána množina, se v průběhu algoritmu nemění a je rovna . Velikost generující sady je zpočátku rovna a v každém následujícím kroku nepřesahuje . Celkovou dobu běhu algoritmu ve výše uvedené implementaci lze tedy odhadnout jako [8] [12] [13] .
Dříve se ukázalo, že algoritmus vyžaduje iterace. V obecném případě může být velikost skupiny řádově , a v tomto případě podle Stirlingova vzorce , který je samozřejmě větší . Ale v některých případech je řád skupiny malý, a proto je výhodnější mít algoritmus, který závisí na , a nikoli - například pokud jde o nějakou známou skupinu, která je dána jako permutační skupina [12] .
Podle Cayleyho teorému je jakákoli konečná grupa izomorfní k nějaké permutační grupě . Stupeň takové skupiny může být velký, ale u mnoha skupin je jejich pořadí takové, že . Například dihedrální skupina je izomorfní k permutační skupině generované cyklickým posunem a odrazem . To znamená, že stupeň této skupiny je , a pořadí je , a . Pro takové skupiny lze uvažovat o algoritmech s dobou běhu , které se nazývají pseudolineární [12] .
Ve snaze přiblížit algoritmus pseudo-lineárnímu a snížit stupeň , zahrnutý v jeho době běhu, Sheresh dospěl k verzím algoritmu, které vyžadují [18] :
První pracovní pravděpodobnostní verze algoritmu byla vyvinuta Jeffrey Leonem v roce 1980 [11] . Obvykle to mají na mysli, když mluví o pravděpodobnostní Schreyer-Simsově metodě. V něm byl tento postup při ztenčování Schreierových generátorů předčasně ukončen, pokud se ukázalo, že 20 generátorů v řadě bylo faktorizováno. Sheresh ukázal, že spolu s některými optimalizacemi dává tento postup následující tvrzení [5] :
Pro jakoukoli konstantu existuje algoritmus typu Monte Carlo , který s pravděpodobností chyby nanejvýš zkonstruuje silnou sadu generátorů pro permutační skupinu pomocí času a paměti. |
V moderních systémech počítačové algebry se obvykle pro zrychlení programu používají modifikace této verze algoritmu s různou heuristikou [5] .
Teorie skupin | |
---|---|
Základní pojmy | |
Algebraické vlastnosti | |
konečné skupiny |
|
Topologické skupiny | |
Algoritmy na skupinách |