УДК 519.725
ИЗУЧЕНИЕ АЛГЕБРЫ И ТЕОРИИ ЧИСЕЛ
С ПОМОЩЬЮ СИСТЕМЫ КОМПЬЮТЕРНОЙ АЛГЕБРЫ GAP
Коновалов А. Б., к.ф.-м.н., доц. (Запорожский государственный университет)
Лысенко Д.А., асс. (Запорожская государственная инженерная академия)
1. Компьютерная алгебра как область науки
Компьютерная алгебра – современная область науки, возникшая на стыке математики и информационных технологий. Ее предметом является осуществление символьных вычислений с помощью ЭВМ (например, разложение многочлена на множители, аналитическое интегрирование и дифференцирование, разнообразные задачи дискретной математики, в т.ч. проверка изоморфизма графов, сборка Кубика Рубика и др.).
Технический прогресс привел к появлению различных программных продуктов для символьных вычислений – т.наз. систем компьютерной алгебры. Наиболее известны из них свободно распространяемые системы GAP, KANT, Singular, коммерческие системы MAGMA, Maple, Mathematica, Statistica, MathCAD, MathLab, и др. Каждая из них в той или иной степени адаптирована для решения задач в конкретных областях науки. Так, системы компьютерной алгебры нашли применение в исследованиях в области дискретной математики, геометрии, механики, кристаллографии, криптографии и др. наук. Для решения вычислительных задач в области абстрактной алгебры наиболее подходящими и развитыми системами на сегодняшний день являются GAP и MAGMA.
2. Краткая характеристика системы GAP
Система компьютерной алгебры GAP (http://www.gap-system.org/), название которой расшифровывается как "Groups, Algorithms and Programming", была задумана около 18 лет назад как инструмент комбинаторной теории групп — раздела алгебры, изучающего группы, заданные порождающими элементами и определяющими соотношениями. Разработка системы была начата в 1986 г. в г.Аахен, Германия (http://www.math.rwth-aachen.de/LDFM/). Впоследствии система была расширена и на другие разделы алгебры. В 1997 г. центр координации разработки и технической поддержки пользователей переместился в Университет г.Сент-Эндрюс, Шотландия (http://www-circa.mcs.st-and.ac.uk/). Сегодня GAP является уникальным всемирным совместным научным проектом, объединяющим специалистов в области алгебры, теории чисел, математической логики, информатики и др. наук из различных стран мира. Текущая версия системы GAP 4.4.3 была выпущена в мае 2004 г.
Система GAP работает в разнообразных версиях ОС Unix/Linux, а также в Windows и MacOS. Максимальная производительность достигается в Unix/Linux-системах, а некоторые пакеты (например, графический интерфейс XGAP, см. http://www.math.rwth-aachen.de/~Max.Neunhoeffer/xgap4) вообще работают только в ОС семейства Unix/Linux.
GAP является свободно распространяемой, открытой и расширяемой системой. Она распространяется в соответствии с GNU Public License (cм. http://www.gap-system.org/Download/copyright.html). Cистема поставляется вместе с исходными текстами, которые написаны на двух языках: ядро системы – на С, а библиотека функций – на специальном языке, также называемом GAP. Пользователи могут создавать свои собственные программы на этом языке, используя в качестве образца исходные тексты. Они также могут оформить свои разработки в виде пакета для системы GAP и представить их на рассмотрение в Совет GAP. После рецензирования и одобрения советом GAP такой пакет рассматривается как научная публикация, на которую можно ссылаться наравне с другими источниками.
Помимо уже упомянутых пакетов, система состоит из следующих четырех основных компонент:
-
ядра системы, обеспечивающего интерпретацию языка GAP, работу с системой в программном и интерактивном режиме;
-
библиотеки функций, в которой реализованы разнообразные алгебраические алгоритмы (более 4000 пользовательских функций, более 140000 строк программ на языке GAP);
-
библиотеки данных, включая, например, библиотеку всех групп порядка не более 2000 (за исключением 49487365422 групп порядка 1024, количество которых также было определено с помощью системы GAP!), библиотеку примитивных групп подстановок, таблицы характеров конечных групп и др. эффективные средства для выдвижения и тестирования гипотез;
-
обширной (около 1500 страниц) документации, доступной в разнообразных форматах (tex, ps, pdf, html), а также через Интернет.
GAP работает с гигантскими целыми и рациональными числами, которые ограничены только объемом доступной памяти, с конечными и циклотомическими полями, р-адическими числами, многочленами от многих переменных, рациональными функциями, векторами и матрицами. Имеются различные комбинаторные функции, элементарные теоретико-числовые функции, разнообразные функции для работы с множествами и списками.
Группы могут быть заданы как группы подстановок, матричные группы, а также с помощью порождающих элементов и определяющих соотношений. Есть функции для задания стандартных групп (например, симметрических и знакопеременных, циклических, и т.д.). Функции для работы с группами позволяют определить порядок группы, вычислить классы сопряженных элементов, центр и коммутант группы, ее различные подгруппы, группу автоморфизмов, и т.д. Для конечных групп малых порядков доступно определение их типа изоморфизма. Эффективность теоретико-групповых алгоритмов демонстрирует пример на сайте GAP, в котором строится группа подстановок, описывающая кубик Рубика, а затем определяется, что он имеет 43252003274489856000 различных состояний, и демонстрируется его сборка из произвольного начального состояния в среднем за 100 ходов.
Среди других областей применения системы – линейная алгебра, теория графов и их автоморфизмов, теория кодирования, теория полугрупп, кристаллография, и многое другое (см. http://www.gap-system.org/).
3. Простейшие примеры работы с системой GAP
После запуска системы Вы увидите строку с приглашением gap> для ввода команд. Например, Вы можете использовать GAP как калькулятор:
gap> (9 - 7) * (5 + 6);
22
gap> 2^64;
18446744073709551616
Теперь определим, например, последние пять из 6320430 цифр 40-го числа Мерсенна 220996011-1, найденного в ноябре 2003 г. в ходе проекта GIMPS (Great Internet Mersenne Prime Search, см. http://www.mersenne.org), и являющегося на сегодня самым большим из известных науке простых чисел:
gap> 2^20996011-1 mod 100000;
82047
В следующем примере разложим целое число на простые множители:
gap> FactorsInt(2^200-1);
[3, 5, 5, 5, 11, 17, 31, 41, 101, 251, 401, 601, 1801,
4051, 8101, 61681, 268501, 340801, 2787601, 3173389601]
Обратимся теперь к линейной алгебре. Сначала зададим матрицу A:
gap> A:=[[1,2,3,4],[4,2,1,5],[-1,10,0,0],[2,-4,7,0]];;
Для ее удобочитаемого вывода на экран применяется команда Display:
gap> Display(A);
[ [ 1, 2, 3, 4 ],
[ 4, 2, 1, 5 ],
[ -1, 10, 0, 0 ],
[ 2, -4, 7, 0 ] ]
Вычислим определитель этой матрицы:
gap> DeterminantMat(A);
-932
Т.о., система линейных уравнений с данной матрицей должна иметь единственное решение. Для его поиска применим функцию SolutionMat( mat, vec ), которая возвращает вектор-строку x такую, что x * mat = vec (здесь умножается строка на матрицу, а не матрица на столбец!). Пусть, например, vec=[1,-1,0,3], тогда
gap> v:=SolutionMat(A,[1,-1,0,3]);
[ 519/932, 36/233, -323/932, -243/932 ]
Проверим, что нами действительно найдено решение системы:
gap> v*A;
[ 1, -1, 0, 3 ]
Теперь приведем несколько примеров работы с подстановками и группами подстановок (знак # в GAP означает начало комментариев):
gap> (1,2,3); # задали подстановку
(1,2,3)
gap> (1,2,3) * (1,2); # нашли произведение подстановок
(2,3)
gap> (1,2,3)^-1; # нашли обратную подстановку
(1,3,2)
gap> 2^(1,2,3); # нашли образ точки под действием подстановки
3
gap> (1,2,3)^(1,2); # нашли подстановку, сопряженную с данной
(1,3,2)
При этом в GAP умножение подстановок выполняется справа налево в связи с тем, что в GAP образ точки x под действием подстановки s равен x^s, и тогда x^(s1*s2)=(x^s1)^s2 эквивалентно тому, что (s1*s2)(x) = s1(s2(x)).
Теперь зададим группу, порождаемую двумя подстановками:
gap> s8 := Group( (1,2), (1,2,3,4,5,6,7,8) );
Group( [ (1,2), (1,2,3,4,5,6,7,8) ] )
Как известно, это - симметрическая группа подстановок 8-й степени. Теперь вычислим ее коммутант, найдем его порядок и проверим коммутативность:
gap> a8 := DerivedSubgroup( s8 );
Group([(1,2,3),(2,3,4),(2,4)(3,5),(2,6,4),(2,4)(5,7),
(2,8,6,4)(3,5)])
gap> Size( a8 ); IsAbelian( a8 );
20160
false
Приведем теперь пример программы на языке GAP для умножения подстановок, заданных в виде произведения независимых циклов в формате [[a1,a2,...,ai],[b1,b2,...,bj],...,[z1,z2,...,zk]], умножая их справа налево (мы вводим свою запись подстановок, отличную от принятой в GAP, только для изучения трудного для студентов 1-го курса правила умножения подстановок):
ProductOfTwoPermutations:=function( s1, s2 )
local c, i, p, points, pos, s, t, x;
s := Concatenation( s1, s2 ); t := [];
points := Set( Flat( s ) );
while Length(points) > 0 do
c := []; p := Minimum( points );
Add( c, p );
repeat
for i in [ Length(s), Length(s)-1 .. 1 ] do
if p in s[i] then
pos := Position( s[i], p );
if pos = Length( s[i] ) then
p := s[i][1];
else
p := s[i][pos+1];
fi;
fi;
od;
if p <> c[1] then
Add( c, p );
fi;
until p = c[1];
Add( t, c ); SubtractSet( points, c );
od;
return Filtered( t, x -> Length( x ) > 1 );
end;
В разделе "Изучаем алгебру с GAP" сайта Украинской группы пользователей GAP (см. ниже) помещен расширенный вариант данной программы с комментариями и промежуточной печатью, работающий так:
gap> ProductOfTwoPermutations([[2,3,5,4],[1,6]], [[1,3,5]]);
Starting from 1
( 1
cycle 3 : 1 -> 3
cycle 1 : 3 -> 5
( 1 5
cycle 3 : 5 -> 1
cycle 2 : 1 -> 6
( 1 5 6
cycle 2 : 6 -> 1
( 1 5 6 )
Starting from 2
( 1 5 6 )( 2
cycle 1 : 2 -> 3
( 1 5 6 )( 2 3
cycle 3 : 3 -> 5
cycle 1 : 5 -> 4
( 1 5 6 )( 2 3 4
cycle 1 : 4 -> 2
( 1 5 6 )( 2 3 4 )
[ [ 1, 5, 6 ], [ 2, 3, 4 ] ]
4. Система GAP в Запорожском государственном университете
В Запорожском государственном университете применение системы GAP в научных исследованиях и ее внедрение в учебный процесс было начато в 1998 г. Всего в течение 1998-2004 гг. было подготовлено почти 30 публикаций, более 20 выступлений на конференциях и семинарах, а также более 30 квалификационных и более 20 курсовых работ, связанных с системой GAP (полный список см. на личной странице первого из авторов http://www.zsu.zp.ua/ppages/konoval/konov.htm). Одна из основных научных разработок - пакет LAGUNA [1], расширяющий возможности системы GAP для работы с групповыми кольцами, и используемый как для исследований в данной области, так и для преподавания специального курса “групповые кольца” студентам старших курсов. Для подготовки студентов к научной работе с применением системы GAP студентам 3-го курса специализации "алгебра и теория чисел" излагается специальный курс на основе методического пособия [2]. Примерами работы в GAP также сопровождается изложение основного курса алгебры и теории чисел, других специальных курсов по алгебре.
Используя GAP, студенты могут изучать алгебраические объекты в интерактивном режиме, решать стандартные задачи курса алгебры и теории чисел. Это приводит к более глубокому пониманию и усвоению материала, развивает практический опыт работы с системой и готовит их к участию в научных исследованиях на старших курсах. В итоге выпускаются специалисты с более высоким качеством подготовки и навыками применения информационных технологий для решения исследовательских задач.
Дальнейшая информация о системе может быть найдена на сайте Украинской группы пользователей GAP (http://www.zsu.zp.ua/UkrGAP/, http://ukrgap.exponenta.ru/), а также в рассылке новостей сайта (http://subscribe.ru/catalog/science.exact.gap/). На этом же сайте размещен дистрибутив системы GAP, который также можно свободно загрузить с сайта http://www.gap-system.org, или найти на CD-приложении к журналу “ЧИП Украина“ № 9/2004 [3]. Кроме того, в разделе "Изучаем алгебру с GAP" этого сайта содержится постоянно пополняемая серия примеров к курсу алгебры и теории чисел, иллюстрирующих учебный материал и демонстрирующих приемы решения некоторых стандартных задач. В настоящее время она охватывает такие темы, как основы математической логики и теории множеств, бинарные отношения и соответствия, бинарные операции и алгебраические системы, деление целых чисел с остатком, алгоритм Евклида, сравнения в кольце целых чисел, теорию многочленов и др. разделы.
Ссылки:
-
V. Bovdi, A. Konovalov, R. Rossmanith and C. Schneider. LAGUNA —- Lie AlGebras and UNits of group Algebras, Version 3.2.2; 2004 (http://ukrgap.exponenta.ru/laguna.htm).
-
Коновалов А.Б. Система компьютерной алгебры GAP. Методические указания. Запорожье, Запорожский государственный университет, 1999. - 42 с. (http://ukrgap.exponenta.ru/Papers/MetGAP43.htm).
-
Коновалов А.Б. Система компьютерной алгебры GAP 4.4.3 на CHIP-CD 9/2004. Сопроводительная статья к дистрибутиву системы GAP 4.4.3 на CD-приложении к журналу "CHIP" (http://chip.ua/), сентябрь 2004 г.
|