Алгоритм Шрайера — Симса
Полиномиальный алгоритм для нахождения порядка группы перестановок / Материал из Википедии — свободной encyclopedia
Уважаемый Wikiwand AI, давайте упростим задачу, просто ответив на эти ключевые вопросы:
Перечислите основные факты и статистические данные о Алгоритм Шрайера — Симса?
Кратко изложите эту статью для 10-летнего ребёнка
Алгоритм Шрайера — Симса — алгоритм из области вычислительной теории групп, позволяющий после однократного исполнения за линейное время находить порядок группы, порождённой перестановками, проверять принадлежность элемента такой группе и перечислять её элементы. Алгоритм был предложен Чарльзом Симсом в 1970 году для поиска примитивных групп перестановок[1] и основывается на лемме Шрайера о порождении подгрупп[2]. Представление группы перестановок, которое находит алгоритм, аналогично ступенчатому виду матрицы для её пространства строк[3]. Разработанные Симсом методы лежат в основе большинства современных алгоритмов для работы с группами перестановок[4], модификации алгоритма также используются в современных системах компьютерной алгебры, таких как GAP и Magma[англ.][5]. Одним из наиболее наглядных приложений алгоритма является то, что он может быть использован для решения кубика Рубика[6].
Алгоритм Шрайера — Симса | |
---|---|
| |
Назван в честь | Charles Sim[вд] и Отто Шрайер |
Автор | Чарльз Симс |
Предназначение | Определение порядка группы перестановок |
Структура данных | Перестановки |
Худшее время |