Русская Википедия:Алгоритм Шрайера — Симса

Алгоритм Шрайера — Симса — алгоритм из области вычислительной теории групп, позволяющий после однократного исполнения за линейное время находить порядок группы, порождённой перестановками, проверять принадлежность элемента такой группе и перечислять её элементы. Алгоритм был предложен Чарльзом Симсом в 1970 году для поиска примитивных групп перестановокШаблон:Sfn и основывается на лемме Шрайера о порождении подгруппШаблон:Sfn. Представление группы перестановок, которое находит алгоритм, аналогично ступенчатому виду матрицы для её пространства строк Шаблон:Sfn. Разработанные Симсом методы лежат в основе большинства современных алгоритмов для работы с группами перестановокШаблон:Sfn, модификации алгоритма также используются в современных системах компьютерной алгебры, таких как GAP и Шаблон:Не переведено 5 Шаблон:Sfn. Одним из наиболее наглядных приложений алгоритма является то, что он может быть использован для решения кубика Рубика Шаблон:Sfn.

История

Файл:Charles Sims.jpg

Чарльз Симс

Одной из основных задач в теории групп перестановок является поиск групп перестановок заданной степени (то есть минимального числа элементов множества, в группу перестановок которого вкладывается заданная группа перестановок). К 1970 году для степеней от 2 до 11 были найдены все группы перестановок, для степеней от 12 до 15 были найдены все транзитивные группы (то есть подгруппы, действующие на порождающем множестве транзитивно), а для степеней от 16 до 20 были найдены только Шаблон:Не переведено 5. Для поиска примитивных групп большей степени Чарльз Симс разработал программу, которая находит порядок и некоторую структуру в группе перестановок, заданной своим порождающим множествомШаблон:Sfn.

Оригинальная программа, упомянутая в работе Симса, была написана для Шаблон:Не переведено 5 в Ратгерском университете и поддерживала работу с любыми группами, чья степень не превосходила 50Шаблон:Sfn. Точная оценка времени работы алгоритма была впервые проведена Фурстом, Хопкрофтом и Шаблон:Не переведено 5 в 1980 годуШаблон:Sfn. Время работы было улучшено Шаблон:Не переведено 5 в 1982Шаблон:Sfn и Дональдом Кнутом в 1981 годуШаблон:Sfn. В 1980 году была разработана эффективная вероятностная версия алгоритмаШаблон:Sfn. Различные вариации алгоритма, включая те, которые используют Шаблон:Не переведено 5 вместо дерева орбиты, были разобраны Шаблон:Не переведено 5 в 2003 годуШаблон:Sfn Шаблон:Sfn.

В вычислительной теории групп алгоритмы над группами перестановок — одна из наиболее развитых областей, и даже сегодня большинство из этих алгоритмов основываются на методах, разработанных СимсомШаблон:Sfn.

Основная идея

Эффективность вычислений с группой перестановок существенно зависит от того, как она задана в программеШаблон:Sfn. Один из эффективных способов такого задания — выделить ряд её подгрупп и выбрать однозначных представителей смежных классов для каждой подгруппы в этом ряду относительно её предшественника. Предложенный Чарльзом Симсом алгоритм находит ряд подгрупп, в котором каждая следующая группа является стабилизатором предыдущей. Последовательность точек, для которых строятся стабилизаторы, называется Шаблон:Не переведено 5, а множество, содержащее образующие элементы для каждой группы в ряду, — Шаблон:Не переведено 5 Шаблон:Sfn.

Алгоритм строит базу и сильное порождающее множество для подгруппы перестановок, заданной своим порождающим множеством, используя лемму Шрайера для нахождения порождающих множеств. Размер получаемых на промежуточных шагах множеств растёт экспоненциально, поэтому были разработаны вариации алгоритма, уменьшающие количество рассматриваемых порождающих элементовШаблон:Sfn.

Описанное выше представление разбивает группу в произведение вложенных в неё подмножеств аналогично тому, как ступенчатое представление разбивает векторное пространство в прямую сумму вложенных в него подпространствШаблон:Sfn.

Постановка задачи

Симметрической группой <math>S_n</math> называют группу, элементами которой являются перестановки элементов некоторого множества <math>\Omega</math>. Обычно в качестве такого множества берётся <math>\Omega=\{1,2,\dots,n\}</math>. В таких обозначениях элементы группы можно рассматривать как отображения <math>\sigma : \Omega \to \Omega</math>, переводящие множество <math>\Omega</math> в себя, то есть его автоморфизмы. Групповой операцией в таких обозначениях является композиция перестановок, для перестановок <math>\sigma_1</math> и <math>\sigma_2</math> определяемая как <math>\sigma = \sigma_1 \sigma_2</math>, где <math>\sigma(\omega) = \sigma_1(\sigma_2(\omega))</math> для <math>\omega \in \Omega</math>. Соответственно, единичной перестановкой будет перестановка <math>\sigma</math> такая, что <math>\sigma(\omega)=\omega</math>, а обратная перестановка может быть задана как <math>\sigma^{-1}(\sigma(\omega))=\omega</math>Шаблон:Sfn.

Пусть <math>S=\{g_1, \dots, g_m\} \subset S_n</math> — множество перестановок длины <math>n</math>. Порождённой подгруппой множества <math>S</math> называют наименьшую по включению подгруппу <math>\langle S \rangle</math>, которая содержит <math>S</math> как подмножество или, что эквивалентно, подгруппу всех элементов <math>S_n</math>, которые могут быть представлены в виде конечного произведения элементов <math>S</math> и обратных к ним. Порядком группы перестановок <math>S</math> называют число элементов в ней <math>|S|</math>, а её степенью — мощность множества <math>|\Omega|</math>, на котором она действует. В таких обозначениях алгоритм должен уметьШаблон:Sfn:

Получать порядок <math display="inline">|\langle S\rangle|</math> подгруппы, порождённой данными перестановками,
По перестановке <math>g</math> проверять, лежит ли она в порождённой подгруппе <math>\langle S \rangle</math>,
Последовательно перечислять элементы порождённой подгруппы без повторений.

Применения

Модификации алгоритма реализованы в двух наиболее популярных специализированных на вычислительной теории групп системах компьютерной алгебры — GAP и Шаблон:Не переведено 5 Шаблон:Sfn. Инструменты для работы с группами перестановок, включая алгоритмы перечисления смежных классов и алгоритм Шрайера — Симса также представлены в популярных системах более широкого профиля Maple и Mathematica Шаблон:Sfn. Изначально алгоритм был разработан для поиска примитивных групп перестановок заданной степениШаблон:Sfn, однако впоследствии область его применения многократно выросла — например, с помощью данного алгоритма можно находить решения к заданной конфигурации кубика Рубика, так как его вращения образуют группуШаблон:Sfn. Также алгоритм хорошо показал себя при работе с Шаблон:Не переведено 5 Шаблон:Sfn.

Алгоритм

Факторизация группы

Пусть <math>H</math> — подгруппа некоторой конечной группы <math>G</math>, через <math>G/H</math> обозначим трансверсаль семейства левых смежных классов <math>\{gH:g\in G\}</math>. Любой элемент <math>g \in G</math> может быть единственным образом представлен как <math>g=th</math>, где <math>t \in G/H</math> и <math>h \in H</math>. Последовательно применяя этот результат к <math>H</math> и её подгруппам, его можно обобщить в следующем видеШаблон:Sfn Шаблон:Sfn:Шаблон:Теорема

Вычисление порядка и перечисление элементов

Описанное выше представление обладает такими свойствами:

По теореме Лагранжа порядок группы может быть вычислен по формуле <math display="inline">|G| = |G^{(0)}/G^{(1)}| \times |G^{(1)} / G^{(2)}| \times \dots \times |G^{(k-1)}/G^{(k)}|</math>Шаблон:Sfn,
Элементы группы можно перечислить, перебирая все возможные представления <math>g=g_1 g_2 \dots g_k</math>Шаблон:Sfn.

Чтобы также иметь возможность проверять элементы на принадлежность порождённой подгруппе, нужно рассматривать ряды подгрупп особого вида, а именно — составленные из стабилизаторов Шаблон:Sfn.

Орбиты и стабилизаторы

Пусть <math>G</math> действует на множестве <math>\Omega</math>. Выберем набор элементов <math display="inline">\omega_1, \dots, \omega_k \in \Omega</math> и построим ряд подгрупп так, чтобы выполнялось <math display="inline">G^{(i)} = G^{(i-1)}_{\omega_i}</math>, где <math>G_\omega=\{g:g\omega=\omega\}</math> — стабилизатор элемента <math>\omega</math>. Другими словами, <math display="inline">G^{(i)}</math> — это подгруппа элементов <math>G</math>, которые переводят каждый из элементов <math display="inline">\omega_1, \dots, \omega_i</math> в себяШаблон:Sfn. При таком подходе на каждом следующем шаге часть множества <math>\Omega</math>, на которую нетривиально действует очередная подгруппа <math>G</math>, будет уменьшаться на один элемент, а порядок подгруппы, с которой ведётся работа, — хотя бы в два раза. Из этого следует, что понадобится <math>\min(|\Omega|, \log |G|)</math> итераций алгоритма, прежде чем будет найдено искомое разбиениеШаблон:Sfn.

Для построения смежных классов нужно воспользоваться тем, что существует взаимно-однозначное соответствие (биекция) между элементами орбиты <math>G\omega</math> и левыми смежными классами <math display="inline">G / G_\omega</math> стабилизатора <math display="inline">G_\omega</math>Шаблон:Sfn.

Шаблон:Доказательство

Из доказательства следует, что в качестве представителей смежных классов можно брать элементы, реализующие различные точки орбиты <math>G\omega</math>Шаблон:Sfn.

Проверка принадлежности

Обозначим через <math>\overline u</math> такой элемент <math>G / G_\omega</math>, что <math>\overline{u}\omega=u</math>. Разбиение в ряд стабилизаторов позволит проверять элемент на принадлежность группеШаблон:Sfn:

Если <math>g \in G^{(i-1)}</math>, то найдётся элемент <math>t_i \in G^{(i-1)} / G^{(i)}</math> такой, что <math>g\in t_iG^{(i)}</math>, то есть <math>t_i^{-1}g\in G^{(i)}</math>,
В силу биекции между элементами смежного класса и точками орбиты, можно однозначно определить, что <math>t_i = \overline{g(\omega_i)}</math>.

Эти свойства позволяют сделать переход от <math>G^{(i-1)}</math> к <math>G^{(i)}</math>, что в итоге приведёт к тому, что текущий элемент должен лежать в <math>G^{(k)}=\{e\}</math>. Если это действительно так, то <math>e=t_k^{-1}\dots t_2^{-1}t_1^{-1}g</math>, откуда можно выразить <math>g = t_1 t_2 \dots t_k</math>Шаблон:Sfn.

Вычисление орбиты

Пусть у группы <math>G</math> есть порождающее множество <math>S</math>. Орбиту любого элемента <math>\alpha</math> под действием группы <math>G=\langle S \rangle</math> можно организовать в дерево следующего видаШаблон:Sfn:

В корне дерева записан некоторый элемент <math>\alpha \in \Omega</math>,
В каждой вершине дерева записан некоторый элемент <math display="inline">\beta \in G(\alpha)</math> из орбиты элемента <math>\alpha</math>,
На ребре, ведущем из вершины с элементом <math>u</math> в вершину с элементом <math>v</math>, записан элемент <math>s \in S</math> такой, что <math>s(u) = v</math>.

Описанное дерево можно построить обходом в глубину, для этого нужно в каждой вершине <math>u</math> перебирать элемент <math>s \in S</math>, пока не окажется, что для <math>s(u)</math> ещё не была выделена вершинаШаблон:Sfn. Пример реализации на языке Python:

# Строит дерево орбиты по заданному элементу w и порождающему множеству S
def build_schreier_tree(w, S, orbit):
    for g in S:
        if g[w] not in orbit:
            orbit[g[w]] = apply(g, orbit[w])
            build_schreier_tree(g[w], S, orbit)

Здесь функция <math>\mathsf{apply}(a, b)</math> возвращает результат применения групповой операции к элементам <math>a</math> и <math>b</math> в качестве первого и второго аргумента, а в <math>\mathsf{orbit}[\alpha]</math> хранится элемент <math>\overline{\alpha}</math>.

Лемма Шрайера

Шаблон:Основная статья

Из леммы Шрайера следует, что стабилизатор <math>G_\alpha</math> порождается множеством генераторов Шрайера: <math>G_\omega = \langle \{(\overline{su})^{-1} s\overline u \mid u \in G\omega,s \in S\}\rangle</math>. Этот результат позволяет по порождающему множеству для <math>G^{(w-1)}</math> и орбите элемента <math>\omega</math> построить порождающее множество для <math>G^{(\omega)}</math>. Возможная реализация для функции, возвращающей новое порождающее множествоШаблон:Sfn:

# Принимает порождающее множество для G_{w-1} и орбиту элемента w
# Возвращает порождающее множество для G_w
def make_gen(S, orbit):
    n = len(next(iter(S)))
    newS = set()
    for s in S:
        for u in orbit:
            newS.add(reduce(apply, [inverse(orbit[s[u]]), s, orbit[u]]))
    return newS

Этим алгоритм не исчерпывается, так как хотя размер нового порождающего множества и зависит полиномиально от размера орбиты и старого порождающего множества для одного отдельного вызова, в совокупности по всем вызовам данной функции размер порождающего множества растёт экспоненциальноШаблон:Sfn.

Просеивание генераторов

Чтобы избежать неконтролируемого роста порождающих множеств, необходимо применять процедуру просеивания. Для этого потребуется следующее утверждениеШаблон:Sfn Шаблон:Sfn: Шаблон:Теорема Шаблон:Доказательство

Описанная в доказательстве процедура называется фильтром Симса и работает за <math>O(|S|\cdot\Omega^2)</math>^[1]. Её реализация может выглядеть так:

# Принимает порождающее множество S
# Возвращает прореженное порождающее множество S'
def normalize(S):
    n = len(next(iter(S)))
    newS = set()
    base = [{} for i in range(n)]
    for s in S:
        for x in range(0, n):
            if s[x] != x:
                if s[x] in base[x]:
                    s = apply(inverse(s), base[x][s[x]])
                else:
                    base[x][s[x]] = s
                    newS.add(s)
                    break
    return newS

Помимо фильтра Симса для поиска небольшого набора <math>S'</math> может использоваться фильтр Джеррума^[2]. В отличие от фильтра Симса, который находит набор из не более, чем <math>|\Omega|^2</math> элементов, фильтр Джеррума находит набор из не более чем <math>|\Omega|</math> элементов. В то же время фильтр Джеррума работает за <math>O(|S| \cdot |\Omega|^4)</math>, поэтому в случае алгоритма Шрайера — Симса предпочтительнее использовать именно фильтр Симса^[1].

Алгоритм

Всё вышенаписанное вместе даёт алгоритм, который может быть лаконично реализован следующим образомШаблон:Sfn:

# Принимает порождающее множество S = s1, ..., sk
# Возвращает трансверсали смежных классов U1, ..., Uk
def schreier_sims(S):
    n = len(next(iter(S)))
    ans = []
    w = 0
    while S:
        orbit = {}
        orbit[w] = tuple(range(n))
        
        build_schreier_tree(w, S, orbit)
        ans += [[orbit[i] for i in orbit]]
        
        S = normalize(make_gen(S, orbit))
        w += 1
    return ans

По шагам его действия имеют следующий смысл:

Строится орбита элемента <math>\omega_i</math> поиском в глубину,
Вычисляются все генераторы Шрайера для <math>G^{(i+1)}</math>,
Множество генераторов прореживается, чтобы избежать их экспоненциального роста.

На выходе алгоритм вернёт список, элементами которого являются трансверсали смежных классов <math>G^{(0)} / G^{(1)}, G^{(1)}/G^{(2)}, \dots, G^{(k-1)}/G^{(k)}</math>.

Время работы алгоритма

Всего алгоритм требует не больше <math>|\Omega|</math> итераций. Каждая итерация состоит из:

Построения дерева орбиты, которое занимает <math>O(|S| \cdot |\Omega|)</math> элементарных операций,
Построения генераторов Шрайера, которое занимает <math>O(|S|\cdot |\Omega|^2)</math> элементарных операций и возвращает <math>|S|\cdot |\Omega|</math> генераторов,
Нормализации порождающего множества, которое занимает <math>O(|S'|\cdot|\Omega|^2)</math> элементарных операций, где <math>S'</math> — множество, полученное на прошлом шаге.

Величина <math>|\Omega|</math> в случае, когда дан набор <math>S=\{g_1, \dots, g_m\}\subset S_n</math>, на протяжении алгоритма не меняется и равна <math>n</math>. Размер порождающего множество изначально равен <math>m</math>, а на каждом последующем шаге не превышает <math>|\Omega|^2=n^2</math>. Таким образом, общее время работы алгоритма в приведённой реализации можно оценить как <math>O(n^3m+n^6)</math>Шаблон:Sfn Шаблон:Sfn Шаблон:Sfn.

Вариации алгоритма

Псевдо-линейные версии

Ранее было показано, что алгоритм требует <math>\min(|\Omega|,\log |G|)</math> итераций. В общем случае размер группы может быть порядка <math>n!</math>, и в таком случае по формуле Стирлинга <math>\log |G| \sim n \log n</math>, что заведомо больше <math>|\Omega|=n</math>. Но в некоторых случаях порядок группы небольшой, в связи с чем выгоднее иметь алгоритм, который зависит от <math>\log |G|</math>, а не <math>n</math> — например, когда речь идёт о какой-то известной группе, которая задана как группа перестановокШаблон:Sfn.

По теореме Кэли любая конечная группа изоморфна некоторой группе перестановок. Степень такой группы <math>n</math> может быть большой, но для многих групп их порядок <math>|G|</math> таков, что <math>\log |G| < n</math>. Например, диэдральная группа <math>D_n</math> изоморфна группе перестановок, порождённой циклическим сдвигом <math>r=(1~~2~~\dots ~~ n)</math> и отражением <math>s=(1~~n)(2~~n-1)(3~~n-2)\dots</math>. То есть степень данной группы равна <math>n</math>, а порядок — <math>2n</math>, и <math>\log |G| \sim \log n</math>. Для таких групп можно рассматривать алгоритмы со временем работы <math>O(nm\log^c|G|)</math>, которые называются псевдо-линейнымиШаблон:Sfn.

В попытке приблизить алгоритм к псевдо-линейному и снизить степень <math>n</math>, входящую в его время работы, Шереш пришёл к версиям алгоритма, требующимШаблон:Sfn:

<math>O(n^2\log^3|G|+mn^2\log |G|)</math> времени и <math>O(n^2 \log |G| + mn)</math> памяти,
<math>O(n^3 \log^3 |G|+mn^3 \log |G|)</math> времени и <math>O(n \log^2 |G| + mn)</math> памяти.

Вероятностная версия

Первая рабочая вероятностная версия алгоритма была разработана Джефри Леоном в 1980 годуШаблон:Sfn. Обычно именно её имеют в виду, когда говорят про вероятностный метод Шрайера — Симса. В нём при прореживании генераторов Шрайера данная процедура досрочно прекращалась, если 20 генераторов подряд оказывались разложенными на множители. Шереш показал, что в совокупности с некоторыми оптимизациями эта процедура даёт следующее утверждениеШаблон:Sfn: Шаблон:Теорема В современных системах компьютерной алгебры обычно используются модификации данной версии алгоритма с различными эвристиками для ускорения работы программыШаблон:Sfn.

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Шаблон:Теория групп Шаблон:Хорошая статья

↑ ^1,0 ^1,1 Шаблон:Cite web
↑ Шаблон:Cite web

[:10-1] 1,0 ^1,1 Шаблон:Cite web

[2] Шаблон:Cite web

[1]

[2]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.

Русская Википедия:Алгоритм Шрайера — Симса

Содержание

История

Основная идея

Постановка задачи

Применения

Алгоритм

Факторизация группы

Вычисление порядка и перечисление элементов

Орбиты и стабилизаторы

Проверка принадлежности

Вычисление орбиты

Лемма Шрайера

Просеивание генераторов

Алгоритм

Время работы алгоритма

Вариации алгоритма

Псевдо-линейные версии

Вероятностная версия

Примечания

Литература

Навигация

Действия на странице

Действия на странице

Персональные инструменты

Навигация

Поиск

Инструменты