Soy un estudiante de matemáticas interesado en TCS.
Quiero estudiar por su cuenta los algoritmos y su complejidad para resolver los problemas teóricos grupales, como encontrar el orden de los elementos, enumeración de coset, encontrar generador, probar si un subconjunto determinado genera el grupo.
¿Qué libro debo leer?
ds.algorithms
reference-request
gr.group-theory
books
ricardorr
fuente
fuente
Respuestas:
Si está interesado en la teoría de grupo que es relevante para el isomorfismo gráfico, entonces, además del libro de Seress que mencionó David Eppstein, recomendaría encarecidamente
Lo anterior es un libro sobre teoría de grupo "justo", pero de los libros sobre teoría de grupo puro, es probablemente el más relevante para el isomorfismo gráfico.
Un libro que trata más directamente sobre algoritmos para el isomorfismo gráfico, que pone los algoritmos de teoría de grupos en el centro del escenario, es:
Este último (junto con la tesis de Paolo Codenotti) es actualmente uno de los pocos lugares ampliamente accesibles donde realmente se puede encontrar una descripción completa de algunos de los algoritmos más teóricos de grupo para el isomorfismo gráfico.
fuente
Realmente hace una diferencia cuál es la entrada al algoritmo: ¿cómo se especifica un grupo?
Si desea grupos dados por generadores y relatores, sugeriría la teoría combinatoria de grupos , de Magnus, Karrass y Solitar (pero los algoritmos son escasos porque muchos de los problemas importantes son indecidibles).
Si desea grupos automáticos (grupos cuyos elementos son cadenas de símbolos y cuyas operaciones grupales son realizadas por autómatas finitos, con aplicaciones en topología de baja dimensión), sugeriría Procesamiento de textos en grupos por Epstein (¡no yo!), Cannon, Holt , Levy, Paterson y Thurston.
Si desea grupos de permutación (el tipo de algoritmo de teoría de grupos que es más relevante, por ejemplo, para el isomorfismo gráfico), Seress tiene un libro Algoritmos de grupo de permutación, pero no tengo una copia, así que no puedo decirle si es bueno.
Debería haber un cuarto párrafo aquí sobre algoritmos de grupo de matriz, pero no conozco un libro sobre ese tema. Hay una pequeña cobertura en el libro de Seress.
fuente
La referencia más moderna y completa es probablemente el "Manual de teoría del grupo computacional" de Holt, Eick y O'Brien (enlace)
Una referencia clásica es "Computación en grupos finamente presentados" por Charles Simms.
fuente
¿No es un libro pero tal vez las Notas de A. Hulpke sobre la teoría del grupo computacional son de interés?
fuente
Si solo le preocupan los grupos de permutación finita, el libro "Algoritmos fundamentales para grupos de permutación" de Gregory Butler es muy legible. Es solo para grupos de permutación finita, pero fue uno de los únicos libros que dio pseudocódigo y descripciones algorítmicas que pude entender (para Schreirer-Sims, grupos electrógenos fuertes, etc.). El libro de Seress recomendado por otros es decente, pero por alguna razón tiene aversión al pseudocódigo, por lo que me fue muy difícil de entender. Personalmente, utilicé el libro de Butler para una comprensión concreta de los algoritmos y el libro de Seress como ayuda para comprender las pruebas de corrección.
El libro de Butler es bastante antiguo, pero todavía tengo que encontrar una mejor introducción sobre los algoritmos de grupos de permutación finita.
fuente
Me corté los dientes en la búsqueda de enumeración de generación de algoritmos combinatorios, http://www.math.mtu.edu/~kreher/cages.html .
Lo recomiendo mucho Aprende algoritmos de grupo de codificación mucho más rápidos ya que los ejemplos a mano se descomponen muy rápidamente. También tome un sistema como Sage o Magma para jugar y usar como calculadora de banco.
fuente