Я интересуюсь математикой на TCS.
Я хочу самостоятельно изучить алгоритмы и их сложность для решения групповых теоретических задач, таких как поиск порядка элементов, перечисление смежных классов, поиск генератора, проверка, генерирует ли данное подмножество группу.
Какую книгу я должен прочитать?
Ответы:
Если вы интересуетесь теорией групп, которая имеет отношение к изоморфизму графов, то в дополнение к книге Сереса, о которой упоминал Дэвид Эппштейн, я очень рекомендую
Выше приведена книга по теории «просто», но из книг по теории чистых групп она, вероятно, наиболее актуальна для изоморфизма графов.
Книга, которая более непосредственно посвящена алгоритмам изоморфизма графов, в которой теоретико-групповые алгоритмы ставятся в центр внимания:
Последний (вместе с тезисом Паоло Коденотти) в настоящее время является одним из немногих широко доступных мест, где вы можете найти полное описание некоторых из более теоретико-групповых алгоритмов для изоморфизма графов.
источник
Это действительно имеет значение, что вход в алгоритм: как вы определяете группу?
Если вам нужны группы, заданные генераторами и связями, я бы предложил Комбинаторную теорию групп Магнуса, Каррасса и Солитара (но алгоритмы там редки, потому что слишком много важных проблем неразрешимы).
Если вам нужны автоматические группы (группы, элементы которых являются строками символов, а групповые операции выполняются конечными автоматами с приложениями в топологии низкой размерности), я бы предложил обработку текста в группах Эпштейном (не мной!), Cannon, Holt Леви, Патерсон и Терстон.
Если вам нужны группы перестановок (вид теоретико-группового алгоритма, который наиболее актуален, например, для изоморфизма графов), тогда у Сереса есть книга « Алгоритмы групп перестановок», но у меня нет копии, поэтому я не могу сказать вам, хорош ли это.
Здесь должен быть четвертый параграф об алгоритмах матричной группы, но я не знаю книги на эту тему. Есть небольшое освещение в книге Сереса.
источник
Наиболее современным и исчерпывающим справочником, вероятно, является «Справочник по вычислительной теории групп» Холта, Эйка и О'Брайена (ссылка).
Классическая ссылка - «Вычисления в конечно представленных группах» Чарльза Симмса.
источник
Не книга, но, может быть, интерес представляют заметки А. Халпке по теории вычислительных групп ?
источник
Если вас интересуют только конечные группы перестановок, я нашел книгу Грегори Батлера «Фундаментальные алгоритмы для групп перестановок» очень читабельной. Это только для конечных групп перестановок, но это была одна из единственных книг, которые давали понятный мне псевдокод и алгоритмические описания (для Schreirer-Sims, сильных генерирующих множеств и т. Д.). Книга Seress, рекомендованная другими, приличная, но по какой-то причине он испытывает отвращение к псевдокоду, поэтому мне было очень трудно понять. Лично я использовал книгу Батлера для конкретного понимания алгоритмов, а книгу Сересса - для понимания доказательств правильности.
Книга Батлера к настоящему времени устарела, но мне еще предстоит найти лучшее введение в алгоритмы конечных групп перестановок.
источник
Я порезал себе зубы по поиску перечисления генерации комбинаторных алгоритмов, http://www.math.mtu.edu/~kreher/cages.html .
Я очень рекомендую это. Вы изучаете гораздо более быстрые алгоритмы групп кодирования, поскольку примеры вручную ломаются очень быстро. Также возьмите систему, подобную Sage или Magma, чтобы использовать ее в качестве настольного калькулятора.
источник