| dbo:abstract
|
- El algoritmo de Schreier-Sims es un algoritmo basado en los estudios del matemático y desarrollado por alrededor de los años 1970 y 1971. Este algoritmo busca encontrar una base, definida como una secuencia de puntos estabilizados, y un del grupo o SGS por sus siglas en inglés (Strong Generating Set), dado un conjunto generador. El orden de un grupo de permutación es comparable al del grupo simétrico del cual es subgrupo, es decir de orden factorial sobre (donde es el conjunto asociado al grupo simétrico). Debido a esto, el enfoque de fuerza bruta no es una opción a la hora de calcular el orden del grupo dado un conjunto generador de , determinar si un elemento en pertenece a o algunas otras operaciones de verificación o generación de elementos en . El algoritmo se basa en la teoría de acción de grupos para calcular la base o cadena de estabilizadores del grupo para, finalmente, obtener el SGS, es decir, una representación del grupo simétrico que permite computar eficientemente sobre este. Este problema está clasificado como un algoritmo de , el mismo permite computar el orden, listar elementos, generar elementos aleatorios, verificar la pertenencia de elementos e insertar elementos en el grupo eficientemente. (es)
- The Schreier–Sims algorithm is an algorithm in computational group theory, named after the mathematicians Otto Schreier and Charles Sims. This algorithm can find the order of a finite permutation group, test membership (is a given permutation contained in a group?), and many other tasks in polynomial time. It was introduced by Sims in 1970, based on Schreier's subgroup lemma. The timing was subsequently improved by Donald Knuth in 1991. Later, an even faster randomized version of the algorithm was developed. (en)
- Алгоритм Шрайера — Симса — алгоритм из области вычислительной теории групп, позволяющий после однократного исполнения за линейное время находить порядок группы, порождённой перестановками, проверять принадлежность элемента такой группе и перечислять её элементы. Алгоритм был предложен Чарльзом Симсом в 1970 году для поиска примитивных групп перестановок и основывается на лемме Шрайера о порождении подгрупп. Представление группы перестановок, которое находит алгоритм, аналогично ступенчатому виду матрицы для её пространства строк. Разработанные Симсом методы лежат в основе большинства современных алгоритмов для работы с группами перестановок, модификации алгоритма также используются в современных системах компьютерной алгебры, таких как GAP и . Одним из наиболее наглядных приложений алгоритма является то, что он может быть использован для решения кубика Рубика. (ru)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 6640 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- The Schreier–Sims algorithm is an algorithm in computational group theory, named after the mathematicians Otto Schreier and Charles Sims. This algorithm can find the order of a finite permutation group, test membership (is a given permutation contained in a group?), and many other tasks in polynomial time. It was introduced by Sims in 1970, based on Schreier's subgroup lemma. The timing was subsequently improved by Donald Knuth in 1991. Later, an even faster randomized version of the algorithm was developed. (en)
- El algoritmo de Schreier-Sims es un algoritmo basado en los estudios del matemático y desarrollado por alrededor de los años 1970 y 1971. Este algoritmo busca encontrar una base, definida como una secuencia de puntos estabilizados, y un del grupo o SGS por sus siglas en inglés (Strong Generating Set), dado un conjunto generador. El algoritmo se basa en la teoría de acción de grupos para calcular la base o cadena de estabilizadores del grupo para, finalmente, obtener el SGS, es decir, una representación del grupo simétrico que permite computar eficientemente sobre este. (es)
- Алгоритм Шрайера — Симса — алгоритм из области вычислительной теории групп, позволяющий после однократного исполнения за линейное время находить порядок группы, порождённой перестановками, проверять принадлежность элемента такой группе и перечислять её элементы. Алгоритм был предложен Чарльзом Симсом в 1970 году для поиска примитивных групп перестановок и основывается на лемме Шрайера о порождении подгрупп. Представление группы перестановок, которое находит алгоритм, аналогично ступенчатому виду матрицы для её пространства строк. Разработанные Симсом методы лежат в основе большинства современных алгоритмов для работы с группами перестановок, модификации алгоритма также используются в современных системах компьютерной алгебры, таких как GAP и . Одним из наиболее наглядных приложений алгорит (ru)
|
| rdfs:label
|
- Algoritmo de Schreier–Sims (es)
- Schreier–Sims algorithm (en)
- Алгоритм Шрайера — Симса (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
