Книга для самостоятельного изучения алгоритмов в теории групп

12

Я интересуюсь математикой на TCS.

Я хочу самостоятельно изучить алгоритмы и их сложность для решения групповых теоретических задач, таких как поиск порядка элементов, перечисление смежных классов, поиск генератора, проверка, генерирует ли данное подмножество группу.

Какую книгу я должен прочитать?

ricardorr
источник
4
Можете ли вы быть более конкретными о том, что вы подразумеваете под «фундаментальными проблемами теории групп»? В зависимости от ваших интересов, более или менее подходящими могут быть разные источники ...
Джошуа Грохоу
Такие вещи, как поиск смежных классов, поиск генераторов, проверка, является ли подмножество группы генератором, поиск порядка элементов, поиск подгрупп
ricardorr
@ricardorr, возможно, вы могли бы отредактировать свой вопрос, чтобы сделать его более точным? Как говорит Джошуа, существует несколько разных классов проблем, связанных с теорией групп.
Андрас Саламон

Ответы:

6

Если вы интересуетесь теорией групп, которая имеет отношение к изоморфизму графов, то в дополнение к книге Сереса, о которой упоминал Дэвид Эппштейн, я очень рекомендую

Группы перестановок Диксона и Мортимера

Выше приведена книга по теории «просто», но из книг по теории чистых групп она, вероятно, наиболее актуальна для изоморфизма графов.

Книга, которая более непосредственно посвящена алгоритмам изоморфизма графов, в которой теоретико-групповые алгоритмы ставятся в центр внимания:

Кристоф Хоффман. Теоретико-групповые алгоритмы и изоморфизм графов . Лекционные заметки Спрингера в области компьютерных наук 136.

Последний (вместе с тезисом Паоло Коденотти) в настоящее время является одним из немногих широко доступных мест, где вы можете найти полное описание некоторых из более теоретико-групповых алгоритмов для изоморфизма графов.

Джошуа Грохов
источник
16

Это действительно имеет значение, что вход в алгоритм: как вы определяете группу?

Если вам нужны группы, заданные генераторами и связями, я бы предложил Комбинаторную теорию групп Магнуса, Каррасса и Солитара (но алгоритмы там редки, потому что слишком много важных проблем неразрешимы).

Если вам нужны автоматические группы (группы, элементы которых являются строками символов, а групповые операции выполняются конечными автоматами с приложениями в топологии низкой размерности), я бы предложил обработку текста в группах Эпштейном (не мной!), Cannon, Holt Леви, Патерсон и Терстон.

Если вам нужны группы перестановок (вид теоретико-группового алгоритма, который наиболее актуален, например, для изоморфизма графов), тогда у Сереса есть книга « Алгоритмы групп перестановок», но у меня нет копии, поэтому я не могу сказать вам, хорош ли это.

Здесь должен быть четвертый параграф об алгоритмах матричной группы, но я не знаю книги на эту тему. Есть небольшое освещение в книге Сереса.

Дэвид Эппштейн
источник
6

Наиболее современным и исчерпывающим справочником, вероятно, является «Справочник по вычислительной теории групп» Холта, Эйка и О'Брайена (ссылка).

Классическая ссылка - «Вычисления в конечно представленных группах» Чарльза Симмса.

NietzscheanAI
источник
2

Если вас интересуют только конечные группы перестановок, я нашел книгу Грегори Батлера «Фундаментальные алгоритмы для групп перестановок» очень читабельной. Это только для конечных групп перестановок, но это была одна из единственных книг, которые давали понятный мне псевдокод и алгоритмические описания (для Schreirer-Sims, сильных генерирующих множеств и т. Д.). Книга Seress, рекомендованная другими, приличная, но по какой-то причине он испытывает отвращение к псевдокоду, поэтому мне было очень трудно понять. Лично я использовал книгу Батлера для конкретного понимания алгоритмов, а книгу Сересса - для понимания доказательств правильности.

Книга Батлера к настоящему времени устарела, но мне еще предстоит найти лучшее введение в алгоритмы конечных групп перестановок.

user834
источник
1

Я порезал себе зубы по поиску перечисления генерации комбинаторных алгоритмов, http://www.math.mtu.edu/~kreher/cages.html .

Я очень рекомендую это. Вы изучаете гораздо более быстрые алгоритмы групп кодирования, поскольку примеры вручную ломаются очень быстро. Также возьмите систему, подобную Sage или Magma, чтобы использовать ее в качестве настольного калькулятора.

Чад Brewbaker
источник
Просто обратите внимание, что глава этой книги о группах, кажется, в основном о группах перестановок.
Дэвид Эппштейн