Książka do samodzielnego studiowania algorytmów w teorii grup

Jestem głównym matematykiem zainteresowanym TCS.

Chcę samemu przestudiować algorytmy i ich złożoność w celu rozwiązania grupowych problemów teoretycznych, takich jak znajdowanie porządku elementów, wyliczanie zbioru, wyszukiwanie generatora, testowanie, czy dany podzbiór generuje grupę.

Jaką książkę powinienem przeczytać?

Jeśli interesuje Cię teoria grup, która jest istotna dla Graph Isomorphism, to oprócz książki Seressa, o której wspomniał David Eppstein, gorąco polecam

Grupy permutacyjne Dixona i Mortimera

Powyżej jest książka o „tylko” teorii grup, ale z książek o teorii czystych grup jest prawdopodobnie najbardziej odpowiednia dla Graph Isomorphism.

Książka, która bardziej bezpośrednio dotyczy algorytmów dla izomorfizmu grafów, w której algorytmy teoretyki grupowej znajdują się w centrum uwagi, jest następująca:

Christoph Hoffman. Teoretyczne algorytmy grupowe i izomorfizm grafów . Wykład Springera z informatyki 136.

Ta ostatnia (wraz z tezą Paolo Codenottiego) jest obecnie jednym z niewielu szeroko dostępnych miejsc, w których można naprawdę znaleźć pełne zestawienie niektórych bardziej teoretycznych algorytmów grupowych dla izomorfizmu grafowego.

To naprawdę robi różnicę na podstawie danych wejściowych do algorytmu: w jaki sposób określasz grupę?

Jeśli chcesz grup podanych przez generatory i relatory, sugerowałbym kombinatoryjną teorię grup Magnusa, Karrassa i Solitar (ale algorytmy są rzadkie, ponieważ zbyt wiele ważnych problemów jest nierozstrzygalnych).

Jeśli chcesz grup automatycznych (grup, których elementami są ciągi symboli i których operacje grupowe są wykonywane za pomocą automatów skończonych, z aplikacjami w topologii niskiego wymiaru), sugerowałbym przetwarzanie tekstu w grupach przez Epsteina (nie mnie!), Cannon, Holt , Levy, Paterson i Thurston.

Jeśli chcesz grup permutacyjnych (rodzaj algorytmu teoretycznego grupowego, który jest najistotniejszy np. W przypadku izomorfizmu grafowego), Seress ma książkę Algorytmy grup permutacyjnych, ale nie mam kopii, więc nie mogę ci powiedzieć, czy jest dobra.

Powinien być tutaj czwarty akapit na temat algorytmów grup macierzy, ale nie znam książki na ten temat. W książce Seress jest trochę relacji.

Najbardziej nowoczesnym i wszechstronnym odniesieniem jest prawdopodobnie „Podręcznik teorii obliczeniowej grupy” Holta, Eicka i O'Briena (link)

Klasycznym odniesieniem jest „Obliczenia w skończonych grupach” Charlesa Simmsa.

Nie książka, ale może Notatki A. Hulpke dotyczące obliczeniowej teorii grup są interesujące?

Jeśli martwisz się tylko o skończone grupy permutacyjne, książkę „Fundamentalne algorytmy dla grup permutacyjnych” Gregory Butler uznałem za bardzo czytelną. To tylko dla skończonych grup permutacyjnych, ale była jedną z niewielu książek, które dały pseudo-kod i opisy algorytmów, które mogłem zrozumieć (dla Schreirera-Sima, silnych zestawów generujących itp.). Książka Seress zalecana przez innych jest przyzwoita, ale z jakiegoś powodu ma awersję do pseudokodu, więc bardzo trudno mi ją zrozumieć. Osobiście wykorzystałem książkę Butlera do konkretnego zrozumienia algorytmów, a książkę Seress jako pomoc w zrozumieniu dowodów poprawności.

Książka Butlera jest już dość stara, ale wciąż muszę znaleźć lepsze wprowadzenie do algorytmów skończonych grup permutacyjnych.

Obcinam zęby przy wyszukiwaniu wyliczeń algorytmów kombinatorycznych, http://www.math.mtu.edu/~kreher/cages.html .

Gorąco polecam. Uczysz się znacznie szybszych algorytmów grupowania kodowania, ponieważ ręczne przykłady rozkładają się naprawdę szybko. Weź także system taki jak Sage lub Magma, aby grać jako kalkulator stołowy.