УДК 519.67
группЫ в компьютерной математике
ГГУ им. Ф. Скорины
Общий научный и технический потенциал современного общества во многом определяет наличие высокотехнологических средств поддержки и применения математического знания. Современные компьютерные системы делают возможным проведение сложнейших численных расчётов для решения отдельных задач, аналитическое решение которых затруднено либо в принципе невозможно, построение моделей для последующего изучения сложных экономических, экологических и многих других динамических систем.
Система компьютерной математики может быть определена как совокупность теоретических, алгоритмических, аппаратных и программных средств, предназначенных для эффективного решения различных видов математических задач. Подобные системы уже давно стали неотъемлемым компонентом научных исследований. Среди известных систем компьютерной математики условно можно выделить семь основных классов [1]:
- системы для численных расчетов,
- табличные процессоры,
- матричные системы,
- системы для статистических расчетов,
- системы для специальных расчетов,
- системы для аналитических расчетов,
- универсальные системы.
При этом типовая структура современных систем компьютерной математики включает в себя:
- ядро системы, включающее в себя описание встроенных функций и процедур системы;
- интерфейс системы, обеспечивающий возможность обращения к ядру для решения конкретных задач;
- библиотеки различных процедур и функций, а также дополнительные пакеты расширения системы
Особый интерес с точки зрения исследований в области теории групп представляет система компьютерной математики GAP, на которой остановимся более подробно.
GAP (Groups, Algorithms, Programming - Группы, Алгоритмы, Программирование) - свободно распространяемая на условиях универсальной общественной лицензии GPL (General Public License) открытая, кроссплатформенная система компьютерной математики для вычислительной дискретной алгебры. Последняя версия системы - GAP 4.7.6 (15 ноября 2014) [2].
Разработка данной системы была начата в 1986 г. в г. Аахен (Германия), в 1997 г. координационный центр разработки и технической поддержки пользователей переместился в Университет города Сент-Эндрюс (Шотландия). В настоящее время GAP - это совместный научный проект, объединяющий специалистов в области алгебры, теории чисел, математической логики, информатики и др. наук из различных стран мира.
Система GAP поставляется вместе с исходными текстами, которые написаны на двух языках:
- ядро системы написано на языке С,
- библиотека функций - на специальном паскалеподобном языке (язык GAP), который в отличие от Pascal является языком объектно-ориентированным программирования.
Важной особенностью системы GAP является ее расширяемость. Функционал системы может быть расширен как с помощью внешних специализированных пакетов и библиотек, так и посредством самостоятельного описания недостающих компонент на языке GAP. Интересным является тот факт [3], что разработчики программ для данной системы могут оформить свои разработки в виде пакета для GAP и представить их на рассмотрение в Совет GAP. После прохождения процедуры рецензирования и одобрения советом GAP такой пакет включается в приложение к дистрибутиву GAP и распространяется вместе с ним. Процедура рецензирования позволяет приравнивать принятые Советом GAP пакеты к научной публикации, и ссылаться на них наравне с другими источниками.
Помимо различных пакетов, GAP включает в себя ядро системы, обеспечивающее возможность работы с системой в программном и интерактивном режиме, библиотеки функций и данных и обширную документацию, доступную в различных форматах (txt, pdf, html).
Как уже отмечалось, GAP является кроссплатформенной системой, тем не менее, максимальная эффективность достигается при ее применении в операционной системе Unix/Linux. Так, стандартный интерфейс GAP реализован посредством командной строки, но существует графический пользовательский интерфейс XGAP, который работает исключительно в среде Unix/Linux и кроме всего прочего позволяет строить графические иллюстрации связей групповых структур.
Система GAP прежде всего была задумана как инструмент комбинаторной теории групп - раздела алгебры, изучающего группы, заданные порождающими элементами и определяющими соотношениями. Однако в процессе разработки функционал системы был значительно расширен. Сегодня GAP работает с конечными полями, многочленами от многих переменных, рациональными функциями, векторами и матрицами, доступны разнообразные комбинаторные функции, элементарные теоретико-числовые функции, функции для работы с множествами и списками. В тоже время приоритетной областью применения системы GAP по-прежнему остается абстрактная алгебра. Остановимся на этом более подробно.
В системе GAP группы могут быть заданы в различной форме: как группы подстановок, матричные группы, группы, заданные порождающими элементами и определяющими соотношениями. Кроме того, построив групповую алгебру, можно вычислить ее мультипликативную группу и при необходимости задать ее подгруппу, порожденную конкретными обратимыми элементами групповой алгебры. Ряд групп может быть задан непосредственным обращением к специализированным библиотекам GAP: библиотека всех групп порядка не более 2000 (SmallGroups), библиотека примитивных групп (PrimitiveGroups), библиотека простых групп (SimpleGroups) и т. д. При этом каждая группа в библиотеке имеет свой уникальный номер среди групп своего порядка и в любой момент может быть по нему идентифицирована.
Весьма разнообразен и функциональный аппарат для работы с группами. В GAP включены функции определения порядка группы, нахождения всех подгрупп группы, максимальных подгрупп, коммутанта группы, вычисления различных групповых инвариантов. Здесь стоит отметить, что синтаксис функций максимально приближен к соответствующим математическим идентификаторам.
Рассмотрим пример работы с группами из библиотеки SmallGroups [4]. Данная библиотека содержит все конечные группы, порядок которых не превышает 2000, за исключением групп порядка 1024, причем каждая группа из библиотеки имеет свой уникальный номер, оперделяющий тип изоморфизма для группы, вида [n, m], где n – порядок группы, m – ее номер в каталоге групп порядка n. По данному идентификатору группа может быть вызвана из библиотеки с помощью функции SmallGroup, например:
gap> S:=SmallGroup(16,8);
<pc group of size 16 with 4 generators>
Более того, для многих групп возможно определение их типа изоморфизма посредством функции IdGroup. Так, например, группа диэдра порядка 8 может быть получена как группа с номером 3 из библиотеки групп порядка 8:
gap> D:=DihedralGroup(8);
<pc group of size 8 with 3 generators>
gap> IdGroup(D);
[ 8, 3 ]
Для отбора групп из библиотеки используется также функция AllSmallGroups. Первый обязательный аргумент данной функции является - Size, второй – порядок требуемых групп, затем могут следовать другие пары аргументов, при этом в каждой паре первый аргумент - функция для отбора групп, второй - ее требуемое значение для указанной функции отбора. В следующем примере отобраны все неабелевы группы порядка 64, причем результат выполнения последней команды Length указывает на то, что таких групп 256:
gap> l:=AllSmallGroups(Size,64, IsAbelian, false);;
gap> Length(last);
256
Далее посредством функций работы со списками можно выделить из найденных групп те, которые имеют класс нильпотентности 4 и циклический коммутант:
gap> l:=Filtered(l, x -> (Length(LowerCentralSeries(x))=5 and IsCyclic(DerivedSubgroup(x))));;
gap> Length(last);
16
Выделим из оставшихся 16 групп те, у которых фактор-группа по коммутанту является элементарной абелевой группой:
gap> l:=Filtered(l, x -> IsElementaryAbelian(x/DerivedSubgroup(x)));;
gap> Length(last);
6
Установим тип изоморфизма оставшихся 6 групп:
gap> List(l, IdGroup);
[ [ 64, 186 ], [ 64, 187 ], [ 64, 188 ], [ 64, 189 ], [ 64, 190 ], [ 64, 191 ] ]
Таким образом, система компьютерной алгебры GAP является удобным и эффективным средством тестирования научных гипотез в области теории групп.
Список литературы:
Дьяконов, математика / //Русский переплет [Электронный ресурс]. – 2015. – Режим доступа: http://www. pereplet. ru. – Дата доступа: 20.02.2015. GAP // GAP - Groups, Algorithms, Programming - a System for Computational Discrete Algebra [Электронный ресурс]. – 2015. – Режим доступа: http://www. gap-system. org. – Дата доступа: 20.02.2015. Коновалов, А. Б. Cистема компьютерной алгебры GAP 4.7 / // Brief GAP Guidebook in Russian [Электронный ресурс]. – 2015. – Режим доступа: http://www. gap-system. org/ukrgap/gapbook/chap0.html. – Дата доступа: 20.02.2015. Библиотека групп системы GAP // Изучаем алгебру и теорию чисел с системой компьютерной алгебры GAP [Электронный ресурс]. – 2015. – Режим доступа: http://www. gap-system. org/ukrgap/Examples/Groups. htm. – Дата доступа: 20.02.2015.