Schreierův vektor - Schreier vector

v matematika, zejména oblast teorie výpočetních grup, a Schreierův vektor je nástroj pro snížení časové a prostorové složitosti potřebné k výpočtu oběžné dráhy a permutační skupina.

Přehled

Předpokládejme, že G je konečný skupina s generující sekvencí ${displaystyle X = {x_ {1}, x_ {2}, ..., x_ {r}}}$ který činy na konečné množině ${displaystyle Omega = {1,2, ..., n}}$. Běžným úkolem ve výpočetní teorii grup je výpočet obíhat nějakého prvku ${displaystyle omega in Omega}$ pod G. Současně lze zaznamenat Schreierův vektor pro ${displaystyle omega}$. Tento vektor lze poté použít k vyhledání prvku ${displaystyle gin G}$ uspokojující ${displaystyle omega ^ {g} = alfa}$, pro všechny ${displaystyle alpha in omega ^ {G}}$. Použití Schreierových vektorů k tomu vyžaduje menší úložný prostor a časovou složitost než jejich explicitní ukládání.

Formální definice

Všechny zde použité proměnné jsou definovány v přehledu.

Schreierův vektor pro ${displaystyle omega in Omega}$ je vektor ${displaystyle mathbf {v} = (v [1], v [2], ..., v [n])}$ takové, že:

1. ${displaystyle v [omega] = - 1}$
2. Pro ${displaystyle alpha in omega ^ {G} setminus {{omega}}, v [alpha] v {1, ..., r}}$ (způsob, jakým ${displaystyle v [alfa]}$ budou vybrány, bude objasněno v další části)
3. ${displaystyle v [alfa] = 0}$ pro ${displaystyle alfa otin omega ^ {G}}$

Použití v algoritmech

Zde ilustrujeme pomocí pseudo kód, použití Schreierových vektorů ve dvou algoritmech

• Algoritmus pro výpočet oběžné dráhy ω pod G a odpovídající Schreierův vektor

Vstup: ω v Ω, ${displaystyle X = {x_ {1}, x_ {2}, ..., x_ {r}}}$

pro i za {0, 1,…, n }:

soubor proti[i] = 0

soubor obíhat = { ω }, proti[ω] = −1

pro α v obíhat a i za {1, 2,…, r }:

-li ${displaystyle alpha ^ {x_ {i}}}$ není v obíhat:

připojit ${displaystyle alpha ^ {x_ {i}}}$ na obíhat

soubor ${displaystyle v [alpha ^ {x_ {i}}] = i}$

vrátit se obíhat, proti

• Algoritmus k nalezení a G v G takhle ω^G = α pro některé α v Ω, za použití proti od prvního algoritmu

Vstup: proti, α, X

-li proti[α] = 0:

vrátit false

soubor G = E, a k = proti[α] (kde E je prvek identity G)

zatímco k ≠ −1:

soubor ${displaystyle g = {x_ {k}} g, alpha = alpha ^ {x_ {k} ^ {- 1}}, k = v [alfa]}$

vrátit se G

Reference

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Schreierův vektor"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Února 2008) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

• Butler, G. (1991), Základní algoritmy pro permutační skupiny, Přednášky v informatice, 559, Berlín, New York: Springer-Verlag, ISBN  978-3-540-54955-0, PAN  1225579
• Holt, Derek F. (2005), Příručka teorie výpočetní skupiny, Londýn: CRC Press, ISBN  978-1-58488-372-2
• Seress, Ákos (2003), Algoritmy permutačních skupin„Cambridge Tracts in Mathematics“, 152, Cambridge University Press, ISBN  978-0-521-66103-4, PAN  1970241