Вычислительная теория групп — область науки на стыке математики и информатикиSeress, p. 1., изучающая группы с помощью вычислительных машин. Она связана с проектированием, анализом алгоритмов и структур данных для вычисления различных характеристик (чаще всего — конечных) групп. Область интересна исследованием важных с различных точек зрения групп, данные о которых невозможно получить вычислениями вручную.

Направления исследований Основные направления исследований связаны с алгоритмами для:

конечно заданных группSims., полициклических и конечных разрешимых групп, групп перестановокSeress., матричных групп, теории представлений.

Важные алгоритмы Важные алгоритмы в вычислительной теории групп включают: алгоритм Шрайера—Симса для нахождения порядка группы перестановок, алгоритм Тодда—Коксетера и алгоритм Кну́та—Бендикса для перечисления классов смежности, алгоритм перемножения—замены для нахождения случайного элемента группы.

Реализации алгоритмов вычислительной теории групп доступны, в частности, в двух известных системах компьютерной алгебры, 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.

*