Вычислительная теория групп
Вычислительная теория групп — область науки на стыке математики и информатики[1], изучающая группы с помощью вычислительных машин. Она связана с проектированием, анализом алгоритмов и структур данных для вычисления различных характеристик (чаще всего — конечных) групп. Область интересна исследованием важных с различных точек зрения групп, данные о которых невозможно получить вычислениями вручную.
Направления исследований
Основные направления исследований связаны с алгоритмами для[1]:
- конечно заданных групп[2],
- полициклических и конечных разрешимых групп,
- групп перестановок[3],
- матричных групп,
- теории представлений.
Важные алгоритмы
Важные алгоритмы в вычислительной теории групп включают:
- алгоритм Шрайера—Симса для нахождения порядка группы перестановок,
- алгоритм Тодда—Коксетера и алгоритм Кну́та—Бендикса для перечисления классов смежности,
- алгоритм перемножения—замены для нахождения случайного элемента группы.
Реализации алгоритмов вычислительной теории групп доступны, в частности, в двух известных системах компьютерной алгебры, GAP и MAGMA.
Достижения
Некоторые достижения, непосредственно связанные с вычислительной теорией групп:
- полное перечисление всех конечных групп порядка меньше 2000,
- вычисление представлений всех спорадических групп.
Примечания
Литература
- Derek F. Holt, Bettina Eick, Bettina, Eamonn A. O’Brien, «Handbook of computational group theory», Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2005. ISBN 1-58488-372-3
- Charles C. Sims, «Computation with Finitely-presented Groups», Encyclopedia of Mathematics and its Applications, vol 48, Cambridge University Press, Cambridge, 1994. ISBN 0-521-43213-8
- Ákos Seress, «Permutation group algorithms», Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. ISBN 0-521-66103-X.
- Обзор (на англ.) данной области от Ákos Seress из Университета штата Огайо, являющийся расширенной версией статьи в журнале «Заметки Американского математического общества». Имеется также обзор (на англ.) от Чарльза Симса из Rutgers University и более старый (на англ.) — от Joachim Neubüser из RWTH Aachen.
