El algoritmo Schreier–Sims es un algoritmo de la teoría de grupos computacionales , llamado así por los matemáticos Otto Schreier y Charles Sims . Este algoritmo puede encontrar el orden de un grupo de permutaciones finitas, determinar si una permutación dada es miembro del grupo y otras tareas en tiempo polinomial . Fue introducido por Sims en 1970, basado en el lema de subgrupos de Schreier . El tiempo de ejecución fue mejorado posteriormente por Donald Knuth en 1991. Más tarde, se desarrolló una versión aleatoria aún más rápida del algoritmo.
El algoritmo es un método eficiente para calcular un conjunto generador fuerte y base (BSGS) de un grupo de permutación . En particular, un SGS determina el orden de un grupo y facilita la comprobación de la pertenencia al grupo. Dado que el SGS es fundamental para muchos algoritmos en la teoría de grupos computacionales, los sistemas de álgebra computacional suelen depender del algoritmo Schreier-Sims para realizar cálculos eficientes en grupos.
El tiempo de ejecución de Schreier–Sims varía según la implementación. Sea dado por los generadores . Para la versión determinista del algoritmo, los tiempos de ejecución posibles son:
El uso de vectores Schreier puede tener una influencia significativa en el rendimiento de las implementaciones del algoritmo Schreier-Sims.
Las variantes de Monte Carlo del algoritmo Schreier-Sims tienen la complejidad estimada:
Los sistemas de álgebra computacional modernos, como GAP y Magma , normalmente utilizan un algoritmo de Monte Carlo optimizado .
A continuación se muestra un pseudocódigo en estilo C++ para la idea básica del algoritmo Schreier-Sims. Se pretende dejar de lado todos los detalles más finos, como la gestión de memoria o cualquier tipo de optimización de bajo nivel, para no ofuscar las ideas más importantes del algoritmo. Su objetivo no es compilar.
struct Group { uint stabPoint ; // Un índice en la base para el punto estabilizado por el subgrupo de este grupo. OrbitTree orbitTree ; // Un árbol para realizar un seguimiento de la órbita en nuestro grupo del punto estabilizado por nuestro subgrupo. TransversalSet transversalSet ; // Un conjunto de clases laterales representativas del subgrupo de este grupo. GeneratorSet generatorSet ; // Un conjunto de permutaciones que generan este grupo. Group * subGroup ; // Un puntero al subgrupo de este grupo, o null para indicar el grupo trivial. Grupo ( uint puntoPestaña ) { esto -> puntoPestaña = puntoPestaña ; subGrupo = nullptr ; } }; // El conjunto de generadores dado no necesita ser un conjunto generador fuerte. Solo necesita generar el grupo en la raíz de la cadena. Group * MakeStabChain ( const GeneratorSet & generatorSet , uint * base ) { Group * group = new Group ( 0 ); for ( generator in generatorSet ) group -> Extend ( generator , base ); return group ; } // Extiende la cadena estabilizadora enraizada en este grupo con el generador dado. void Group::Extend ( const Permutation & generator , uint * base ) { // Esta es la optimización principal de Schreier-Sims. Elimina los generadores Schreier redundantes. if ( IsMember ( generator )) return ; // Nuestro grupo acaba de hacerse más grande, pero la cadena estabilizadora arraigada en nuestro subgrupo sigue siendo la misma. generatorSet . Add ( generator ); // Explora todas las nuevas órbitas que podamos alcanzar con la adición del nuevo generador. // Ten en cuenta que si el árbol estaba vacío desde el principio, la identidad debe devolverse // en el conjunto para satisfacer una condición del lema de Schreier. newTerritorySet = orbitTree . Grow ( generator , base ); // Por el teorema del estabilizador de órbita, las permutaciones en el conjunto devuelto son // clases laterales representativas de las clases laterales de nuestro subgrupo. for ( permutation in newTerritorySet ) transversalSet . Add ( permutation ); // Ahora aplicamos el lema de Schreier para encontrar nuevos generadores para nuestro subgrupo. // Algunas iteraciones de este bucle son redundantes, pero lo ignoramos por simplicidad. for ( cosetRepresentative in transversalSet ) { for ( generator in generatorSet ) { schreierGenerator = CalcSchreierGenerator ( cosetRepresentative , generator ); if ( schreierGenerator . IsIdentity ()) continue ; if ( ! subGroup ) subGroup = new Group ( stabPoint + 1 ); subGrupo -> Extender ( generador_escritura , base ); } } } Los detalles notables que se omiten aquí incluyen el crecimiento del árbol de órbitas y el cálculo de cada nuevo generador de Schreier. En lugar del árbol de órbitas, se puede utilizar un vector de Schreier , pero la idea es esencialmente la misma. El árbol tiene su raíz en el elemento de identidad, que fija el punto estabilizado por el subgrupo. Cada nodo del árbol puede representar una permutación que, cuando se combina con todas las permutaciones en el camino desde la raíz hasta él, lleva ese punto a algún nuevo punto no visitado por ningún otro nodo del árbol. Por el teorema del estabilizador de órbitas , estos forman una transversal del subgrupo de nuestro grupo que estabiliza el punto cuya órbita entera es mantenida por el árbol. Calcular un generador de Schreier es una aplicación simple del lema del subgrupo de Schreier .
Otro detalle que se omite es la prueba de pertenencia. Esta prueba se basa en el proceso de cribado. Una permutación se criba a lo largo de la cadena en cada paso encontrando la clase lateral que la contiene, luego se utiliza el representante de esa clase lateral para encontrar una permutación en el subgrupo, y el proceso se repite en el subgrupo con esa permutación encontrada. Si se llega al final de la cadena (es decir, llegamos al subgrupo trivial), entonces la permutación cribada era un miembro del grupo en la parte superior de la cadena.