Перечисление смежных классов
В математике нумерация смежных классов представляет собой задачу подсчета смежных классов подгруппы H группы заданной G, в терминах представления . В качестве побочного продукта получается представление перестановок для G в смежных классах H . Если H дает порядок G. имеет известный конечный порядок, перечисление смежных классов также
Для небольших групп иногда можно выполнить перебор смежных классов вручную. Однако для больших групп это требует много времени и чревато ошибками, поэтому обычно выполняется с помощью компьютера . Перечисление смежных классов обычно считается одной из фундаментальных проблем вычислительной теории групп .
Оригинальный алгоритм перечисления смежных классов был изобретен Джоном Артуром Тоддом и Х.С.М. Коксетером . различные улучшения исходного алгоритма Тодда-Коксетера Были предложены , в частности классические стратегии В. Фелша и HLT (Хазелгроув, Лич и Троттер). Практическая реализация этих стратегий с уточнениями доступна на сайте ACE. [1] Алгоритм Кнута-Бендикса также может выполнять перечисление смежных классов и, в отличие от алгоритма Тодда-Коксетера, иногда может решать проблему слов для бесконечных групп.
Основные практические трудности при создании перечислителя смежных классов заключаются в том, что трудно или невозможно предсказать, сколько памяти или времени потребуется для завершения процесса. Если группа конечна, то перечисление ее смежных классов в конечном итоге должно завершиться, хотя оно может занять сколь угодно много времени и использовать произвольный объем памяти, даже если группа тривиальна. В зависимости от используемого алгоритма может случиться так, что внесение небольших изменений в представление, не меняющих группу, тем не менее, окажет большое влияние на количество времени или памяти, необходимое для завершения перечисления. Такое поведение является следствием неразрешимости проблемы слова для групп .
Небольшое введение в перечисление смежных классов дано в тексте Ротмана по теории групп. [2] Более подробную информацию о правильности, эффективности и практической реализации можно найти в книгах Симса. [3] и Холт и др. [4]
Ссылки
[ редактировать ]- ^ ACE: Advanced Coset Enumer Джорджа Хаваса и Колина Рамзи. Архивировано 1 сентября 2007 г. в Wayback Machine.
- ^ Ротман, Джозеф Дж. (1995). Введение в теорию групп . Спрингер. ISBN 0-387-94285-8 .
- ^ Симс, Чарльз К. (1994). Вычисления с конечно представленными группами . Издательство Кембриджского университета. ISBN 0-521-43213-8 .
- ^ Холт, Дерек Ф. (2005). Справочник по вычислительной теории групп . ЦРК Пресс. ISBN 1-58488-372-3 .