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

12

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ć?

Ricardorr
źródło
4
Czy możesz sprecyzować, co rozumiesz przez „podstawowe problemy teorii grup”? W zależności od zainteresowań różne źródła mogą być mniej lub bardziej odpowiednie ...
Joshua Grochow
Rzeczy takie jak znalezienie cosetów, znalezienie generatorów, sprawdzenie, czy podzbiór grupy jest generatorem, znalezienie kolejności elementów, znalezienie podgrup
ricardorr
@ricardorr być może mógłbyś edytować swoje pytanie, aby było bardziej precyzyjne? Jak mówi Joshua, istnieje kilka różnych klas problemów związanych z teorią grup.
András Salamon,

Odpowiedzi:

6

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.

Joshua Grochow
źródło
16

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.

David Eppstein
źródło
6

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.

NietzscheanAI
źródło
2

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.

użytkownik834
źródło
1

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.

Chad Brewbaker
źródło
Tylko uwaga, że ​​rozdział tej książki o grupach wydaje się przede wszystkim dotyczyć grup permutacyjnych.
David Eppstein,