Вычислительная теория групп

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

Направления исследований

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

• конечно заданных групп^[2],
• полициклических и конечных разрешимых групп,
• групп перестановок^[3],
• матричных групп,
• теории представлений.

Важные алгоритмы

Важные алгоритмы в вычислительной теории групп включают:

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

Реализации алгоритмов вычислительной теории групп доступны, в частности, в двух известных системах компьютерной алгебры, GAP и MAGMA.

Достижения

Некоторые достижения, непосредственно связанные с вычислительной теорией групп:

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