Ich bin ein Mathematik-Hauptfach, das sich für TCS interessiert.
Ich möchte die Algorithmen und deren Komplexität zum Lösen der gruppentheoretischen Probleme wie Reihenfolge der Elemente finden, Aufzählung der Nebenmengen, Generator finden und testen, ob eine gegebene Teilmenge die Gruppe erzeugt.
Welches Buch soll ich lesen?
ds.algorithms
reference-request
gr.group-theory
books
Ricardorr
quelle
quelle
Antworten:
Wenn Sie sich für die Gruppentheorie interessieren, die für den Graphisomorphismus relevant ist, kann ich Ihnen neben Seress 'Buch, das David Eppstein erwähnte, sehr empfehlen
Das Obige ist ein Buch über "nur" Gruppentheorie, aber von den Büchern über reine Gruppentheorie ist es wahrscheinlich das relevanteste für den Graphisomorphismus.
Ein Buch, das sich direkter mit Algorithmen für den Graphisomorphismus befasst und gruppentheoretische Algorithmen in den Mittelpunkt stellt, ist:
Letzteres (zusammen mit Paolo Codenottis These) ist derzeit einer der wenigen weithin zugänglichen Orte, an denen Sie wirklich einen vollständigen Überblick über einige der gruppentheoretischeren Algorithmen für den Graphisomorphismus finden.
quelle
Es macht wirklich einen Unterschied, wie die Eingabe für den Algorithmus lautet: Wie geben Sie eine Gruppe an?
Wenn Sie Gruppen von Generatoren und Relatoren erhalten möchten, würde ich die kombinatorische Gruppentheorie von Magnus, Karrass und Solitar vorschlagen (aber Algorithmen sind spärlich, weil zu viele der wichtigen Probleme unentscheidbar sind).
Wenn Sie automatische Gruppen (Gruppen, deren Elemente Zeichenfolgen sind und deren Gruppenoperationen von endlichen Automaten ausgeführt werden, mit Anwendungen in niedrigdimensionaler Topologie) möchten, würde ich die Textverarbeitung in Gruppen von Epstein (nicht von mir!), Cannon, Holt, vorschlagen , Levy, Paterson und Thurston.
Wenn Sie Permutationsgruppen möchten (die Art von gruppentheoretischem Algorithmus, die zB für den Graphisomorphismus am relevantesten ist), dann hat Seress ein Buch Permutationsgruppenalgorithmen, aber ich habe keine Kopie, also kann ich Ihnen nicht sagen, ob es eine gute ist.
Es sollte hier einen vierten Absatz über Matrixgruppenalgorithmen geben, aber ich kenne kein Buch zu diesem Thema. Es gibt ein wenig Berichterstattung in Seress 'Buch.
quelle
Die modernste und umfassendste Literaturstelle ist wahrscheinlich "Handbook of Computational Group Theory" von Holt, Eick und O'Brien (link)
Eine klassische Referenz ist "Computation in Finitely Presented Groups" von Charles Simms.
quelle
Kein Buch, aber vielleicht sind A. Hulpkes Notizen zur Computergruppentheorie von Interesse?
quelle
Wenn Sie sich nur um endliche Permutationsgruppen kümmern, fand ich das Buch "Fundamental Algorithms for Permutation Groups" von Gregory Butler sehr lesbar. Es ist nur für endliche Permutationsgruppen gedacht, aber es war eines der wenigen Bücher, die Pseudocode und algorithmische Beschreibungen enthielten, die ich verstehen konnte (für Schreirer-Sims, starke Stromaggregate usw.). Das von anderen empfohlene Seress-Buch ist anständig, aber aus irgendeinem Grund hat er eine Abneigung gegen Pseudo-Code, so dass es für mich sehr schwer zu verstehen war. Persönlich habe ich das Butler-Buch zum konkreten Verständnis der Algorithmen und das Seress-Buch zum besseren Verständnis von Korrektheitsnachweisen verwendet.
Das Butler-Buch ist mittlerweile ziemlich alt, aber ich habe noch keine bessere Einführung in Algorithmen für endliche Permutationsgruppen gefunden.
quelle
Ich habe meine Zähne bei der Suche nach kombinatorischen Algorithmen zur Generierung von Aufzählungen, http://www.math.mtu.edu/~kreher/cages.html, aufgeschlagen .
Ich kann es nur empfehlen. Sie lernen viel schneller, wie Gruppenalgorithmen von Hand zusammenbrechen. Schnappen Sie sich auch ein System wie Sage oder Magma, um damit zu spielen und es als Bankrechner zu verwenden.
quelle