Изучение алгебры и теории чисел с помощью системы компьютерной алгебры gap

Вид материала

Документы

Содержание 2. Краткая характеристика системы GAP GAP является свободно распространяемой, открытой и расширяемой системой 3. Простейшие примеры работы с системой GAP Display: gap> Display(A) SolutionMat( mat, vec ) ProductOfTwoPermutations:=function( s1, s2 ) 4. Система GAP в Запорожском государственном университете

Подобный материал:

• Некоммутативная геометрия, 36.84kb.
• Рабочая учебная программа по курсу по выбору «Алгебры с делением над полем действительных, 179.95kb.
• Системные технологии, 129.7kb.
• Специальная (частная) методика алгебры, алгебры и начал анализа, 264.95kb.
• «многочлены с одной переменной», рекомендованная для углубленного изучения математики, 13.08kb.
• Методика преподавания математики в основной школе Курс лекций, 1273.88kb.
• Рабочая учебная программа по дисциплине «Алгебра», 320.51kb.
• Функции алгебры логики, 47.25kb.
• И. Б. Щенков из истории развития и применения компьютерной алгебры в институте прикладной, 1005.41kb.
• Diskrētā matemātika Discrete mathematics Дискретная математика, 300.73kb.

УДК 519.725

ИЗУЧЕНИЕ АЛГЕБРЫ И ТЕОРИИ ЧИСЕЛ

С ПОМОЩЬЮ СИСТЕМЫ КОМПЬЮТЕРНОЙ АЛГЕБРЫ GAP


Коновалов А. Б., к.ф.-м.н., доц. (Запорожский государственный университет)

Лысенко Д.А., асс. (Запорожская государственная инженерная академия)


1. Компьютерная алгебра как область науки

Компьютерная алгебра – современная область науки, возникшая на стыке математики и информационных технологий. Ее предметом является осуществление символьных вычислений с помощью ЭВМ (например, разложение многочлена на множители, аналитическое интегрирование и дифференцирование, разнообразные задачи дискретной математики, в т.ч. проверка изоморфизма графов, сборка Кубика Рубика и др.).

Технический прогресс привел к появлению различных программных продуктов для символьных вычислений – т.наз. систем компьютерной алгебры. Наиболее известны из них свободно распространяемые системы GAP, KANT, Singular, коммерческие системы MAGMA, Maple, Mathematica, Statistica, MathCAD, MathLab, и др. Каждая из них в той или иной степени адаптирована для решения задач в конкретных областях науки. Так, системы компьютерной алгебры нашли применение в исследованиях в области дискретной математики, геометрии, механики, кристаллографии, криптографии и др. наук. Для решения вычислительных задач в области абстрактной алгебры наиболее подходящими и развитыми системами на сегодняшний день являются GAP и MAGMA.


^ 2. Краткая характеристика системы GAP

Система компьютерной алгебры GAP (ystem.org/), название которой расшифровывается как "Groups, Algorithms and Programming", была задумана около 18 лет назад как инструмент комбинаторной теории групп — раздела алгебры, изучающего группы, заданные порождающими элементами и определяющими соотношениями. Разработка системы была начата в 1986 г. в г.Аахен, Германия (rwth-aachen.de/LDFM/). Впоследствии система была расширена и на другие разделы алгебры. В 1997 г. центр координации разработки и технической поддержки пользователей переместился в Университет г.Сент-Эндрюс, Шотландия (.mcs.st-and.ac.uk/). Сегодня GAP является уникальным всемирным совместным научным проектом, объединяющим специалистов в области алгебры, теории чисел, математической логики, информатики и др. наук из различных стран мира. Текущая версия системы GAP 4.4.3 была выпущена в мае 2004 г.

Система GAP работает в разнообразных версиях ОС Unix/Linux, а также в Windows и MacOS. Максимальная производительность достигается в Unix/Linux-системах, а некоторые пакеты (например, графический интерфейс XGAP, см. rwth-aachen.de/~Max.Neunhoeffer/xgap4) вообще работают только в ОС семейства Unix/Linux.

^ GAP является свободно распространяемой, открытой и расширяемой системой. Она распространяется в соответствии с GNU Public License (cм. ystem.org/Download/copyright.php). Cистема поставляется вместе с исходными текстами, которые написаны на двух языках: ядро системы – на С, а библиотека функций – на специальном языке, также называемом GAP. Пользователи могут создавать свои собственные программы на этом языке, используя в качестве образца исходные тексты. Они также могут оформить свои разработки в виде пакета для системы GAP и представить их на рассмотрение в Совет GAP. После рецензирования и одобрения советом GAP такой пакет рассматривается как научная публикация, на которую можно ссылаться наравне с другими источниками.

Помимо уже упомянутых пакетов, система состоит из следующих четырех основных компонент:

• ядра системы, обеспечивающего интерпретацию языка GAP, работу с системой в программном и интерактивном режиме;
  
• библиотеки функций, в которой реализованы разнообразные алгебраические алгоритмы (более 4000 пользовательских функций, более 140000 строк программ на языке GAP);
  
• библиотеки данных, включая, например, библиотеку всех групп порядка не более 2000 (за исключением 49487365422 групп порядка 1024, количество которых также было определено с помощью системы GAP!), библиотеку примитивных групп подстановок, таблицы характеров конечных групп и др. эффективные средства для выдвижения и тестирования гипотез;
  
• обширной (около 1500 страниц) документации, доступной в разнообразных форматах (tex, ps, pdf, html), а также через Интернет.
  

GAP работает с гигантскими целыми и рациональными числами, которые ограничены только объемом доступной памяти, с конечными и циклотомическими полями, р-адическими числами, многочленами от многих переменных, рациональными функциями, векторами и матрицами. Имеются различные комбинаторные функции, элементарные теоретико-числовые функции, разнообразные функции для работы с множествами и списками.

Группы могут быть заданы как группы подстановок, матричные группы, а также с помощью порождающих элементов и определяющих соотношений. Есть функции для задания стандартных групп (например, симметрических и знакопеременных, циклических, и т.д.). Функции для работы с группами позволяют определить порядок группы, вычислить классы сопряженных элементов, центр и коммутант группы, ее различные подгруппы, группу автоморфизмов, и т.д. Для конечных групп малых порядков доступно определение их типа изоморфизма. Эффективность теоретико-групповых алгоритмов демонстрирует пример на сайте GAP, в котором строится группа подстановок, описывающая кубик Рубика, а затем определяется, что он имеет 43252003274489856000 различных состояний, и демонстрируется его сборка из произвольного начального состояния в среднем за 100 ходов.

Среди других областей применения системы – линейная алгебра, теория графов и их автоморфизмов, теория кодирования, теория полугрупп, кристаллография, и многое другое (см. ystem.org/).


^ 3. Простейшие примеры работы с системой GAP

После запуска системы Вы увидите строку с приглашением gap> для ввода команд. Например, Вы можете использовать GAP как калькулятор:

gap> (9 - 7) * (5 + 6);

22

gap> 2^64;

18446744073709551616

Теперь определим, например, последние пять из 6320430 цифр 40-го числа Мерсенна 2^20996011-1, найденного в ноябре 2003 г. в ходе проекта GIMPS (Great Internet Mersenne Prime Search, см. nne.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 эквивалентно тому, что (s₁*s₂)(x) = s₁(s₂(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 для умножения подстановок, заданных в виде произведения независимых циклов в формате [[a₁,a₂,...,a_i],[b₁,b₂,...,b_j],...,[z₁,z₂,...,z_k]], умножая их справа налево (мы вводим свою запись подстановок, отличную от принятой в 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 (полный список см. на личной странице первого из авторов p.ua/ppages/konoval/konov.htm). Одна из основных научных разработок - пакет LAGUNA [1], расширяющий возможности системы GAP для работы с групповыми кольцами, и используемый как для исследований в данной области, так и для преподавания специального курса “групповые кольца” студентам старших курсов. Для подготовки студентов к научной работе с применением системы GAP студентам 3-го курса специализации "алгебра и теория чисел" излагается специальный курс на основе методического пособия [2]. Примерами работы в GAP также сопровождается изложение основного курса алгебры и теории чисел, других специальных курсов по алгебре.

Используя GAP, студенты могут изучать алгебраические объекты в интерактивном режиме, решать стандартные задачи курса алгебры и теории чисел. Это приводит к более глубокому пониманию и усвоению материала, развивает практический опыт работы с системой и готовит их к участию в научных исследованиях на старших курсах. В итоге выпускаются специалисты с более высоким качеством подготовки и навыками применения информационных технологий для решения исследовательских задач.

Дальнейшая информация о системе может быть найдена на сайте Украинской группы пользователей GAP (p.ua/UkrGAP/, ponenta.ru/), а также в рассылке новостей сайта (.ru/catalog/science.exact.gap/). На этом же сайте размещен дистрибутив системы GAP, который также можно свободно загрузить с сайта ystem.org, или найти на CD-приложении к журналу “ЧИП Украина“ № 9/2004 [3]. Кроме того, в разделе "Изучаем алгебру с GAP" этого сайта содержится постоянно пополняемая серия примеров к курсу алгебры и теории чисел, иллюстрирующих учебный материал и демонстрирующих приемы решения некоторых стандартных задач. В настоящее время она охватывает такие темы, как основы математической логики и теории множеств, бинарные отношения и соответствия, бинарные операции и алгебраические системы, деление целых чисел с остатком, алгоритм Евклида, сравнения в кольце целых чисел, теорию многочленов и др. разделы.


Ссылки:

1. V. Bovdi, A. Konovalov, R. Rossmanith and C. Schneider. LAGUNA —- Lie AlGebras and UNits of group Algebras, Version 3.2.2; 2004 (ponenta.ru/laguna.htm).
   
2. Коновалов А.Б. Система компьютерной алгебры GAP. Методические указания. Запорожье, Запорожский государственный университет, 1999. - 42 с. (ponenta.ru/Papers/MetGAP43.htm).
   
3. Коновалов А.Б. Система компьютерной алгебры GAP 4.4.3 на CHIP-CD 9/2004. Сопроводительная статья к дистрибутиву системы GAP 4.4.3 на CD-приложении к журналу "CHIP" (, сентябрь 2004 г.