Перейти к главе: Начало 1 2 3 4 A B C Bib Ind
 [Начало книги]  [Содержание]   [Предыдущая глава]   [Следующая глава] 

1 Введение
 1.1 Краткая характеристика и история системы GAP
 1.2 Обзор возможностей GAP
 1.3 Инсталляция и запуск системы
 1.4 Первые шаги в GAP

1 Введение

1.1 Краткая характеристика и история системы GAP

Разработка системы компьютерной алгебры GAP (http://www.gap-system.org), название которой расшифровывается как "Groups, Algorithms and Programming", была начата в 1986 г. в г.Аахен, Германия (http://www.math.rwth-aachen.de/LDFM/). В 1997 г. центр координации разработки и технической поддержки пользователей переместился в Университет г.Сент-Эндрюс, Шотландия (http://www-circa.mcs.st-and.ac.uk/). В настоящее время GAP является уникальным всемирным совместным научным проектом, объединяющим специалистов в области алгебры, теории чисел, математической логики, информатики и др. наук из различных стран мира. Основные центры разработки системы находятся в университетах г.Сент-Эндрюс (Шотландия), гг. Аахен, Брауншвейг (Германия) и Университете штата Колорадо (США). Текущая версия системы - GAP 4.4.10 - была выпущена в октябре 2007 г.

Изначально система GAP разрабатывалась под Unix, а затем была портирована для работы в других операционных системах. В настоящее время она работает в разнообразных версиях Unix/Linux, а также в Windows и Mac OS. Заметим, что ряд пакетов, расширяющих функциональность системы, работает только в среде Unix/Linux.

GAP является свободно распространяемой, открытой и расширяемой системой. Она распространяется в соответствии с GNU Public License (cм. http://www.gap-system.org/Download/copyright.html). Cистема поставляется вместе с исходными текстами, которые написаны на двух языках: ядро системы написано на Си, а библиотека функций - на специальном языке, также называемом GAP, который по синтаксису напоминает Pascal, однако является объектно-ориентированным языком. Пользователи могут создавать свои собственные программы на этом языке, и здесь исходные тексты являются незаменимым наглядным пособием. Наконец, разработчики программ для GAP могут оформить свои разработки в виде пакета для системы GAP и представить их на рассмотрение в Совет GAP. После прохождения процедуры рецензирования и одобрения советом GAP такой пакет включается в приложение к дистрибутиву GAP и распространяется вместе с ним. Процедура рецензирования позволяет приравнивать принятые Советом GAP пакеты к научной публикации, и ссылаться на них наравне с другими источниками.

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

1.2 Обзор возможностей GAP

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

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

Группы могут быть заданы в различной форме, например, как группы подстановок, матричные группы, группы, заданные порождающими элементами и определяющими соотношениями. Более того, построив, например, групповую алгебру, можно вычислить ее мультипликативную группу, и даже задать ее подгруппу, порожденную конкретными обратимыми элементами групповой алгебры. Ряд групп может быть задан непосредственным обращением к библиотечным функциям (например, симметрическая и знакопеременная группы, группа диэдра, циклическая группа и др.).

Функции для работы с группами включают определение порядка группы, вычисление классов сопряженных элементов, центра и коммутанта группы, верхнего и нижнего центрального рядов, ряда коммутантов, Силовских подгрупп, максимальных подгрупп, нормальных подгрупп, решеток подгрупп, групп автоморфизмов, и т.д. Для ряда конечных групп доступно определение их типа изоморфизма.

Теория представлений групп также входит в область применения системы GAP. Здесь имеются инструменты для вычисления таблиц характеров конкретных групп, действий над характерами и интерактивного построения таблиц характеров, определения теоретико-групповых свойств на основании свойств таблицы характеров группы. Модулярные представления групп (т.е. представления над полем, характеристика которого делит порядок группы) также могут быть исследованы с помощью GAP.

В версии 4.3 были существенным образом расширены возможности для работы с векторными пространствами, алгебрами и модулями. В системе могут быть определены векторные пространства над всеми доступными полями и модули над всеми доступными кольцами. Имеются алгоритмы для вычисления структуры конечномерных алгебр Ли, которые могут быть, например, заданы структурными константами или порождающими элементами, вычисления различных их Лиевских подалгебр и идеалов.

Версия 4.4, заменившая версию 4.3, содержит множество новых особенностей, усовершенствованных алгоритмов и средств программирования, и поэтому мы рекомендуем ее установку всем пользователям предыдущих версий. В частности, в GAP 4.4 появились новые алгоритмы и функции для работы с базисами Гребнера, алгебраическими расширениями полей, группами Галуа, таблицами характеров, векторными пространствами; новые методы для вычисления минимальных нормальных подгрупп конечной группы и цоколя конечной группы; быстрый метод для определения, является ли заданная группа подстановок симметрической или знакопеременной группой в их естественном представлении; разнообразные функции для вычислений с целочисленными матрицами, и др. нововведения.

Кроме новых алгоритмов и функций, в GAP 4.4 усовершенствована производительность многих уже существовавших ранее алгоритмов, в т.ч. для вычисления неприводимых представлений и их характеров, вычисления нормализаторов и сопряженных подгрупп в симметрических группах подстановок, вычисления системы представителей смежных классов в группах подстановок. Разложение подстановки в произведение порождающих элементов теперь вовзращает существенно более короткие слова (например, длины около 100 для группы кубика Рубика). Усовершенствования также коснулись списков, многочленов, матриц и матричных групп, расширений конечных групп, конечномерных алгебр.

В вышедшей в мае 2005 г. версии GAP 4.4.5, в библиотеку конечных групп добавлены:

Также в ней была введена новая функция StructureDescription для вычисления структурных описаний конечных групп, например:


gap> l := AllSmallGroups( Size, 8 );;
gap> List( l, StructureDescription );
[ "C8", "C4 x C2", "D8", "Q8", "C2 x C2 x C2" ]

Вместе с системой распространяется множество новых версий пакетов для GAP. При этом изменился механизм загрузки пакетов. Для загрузки каждый пакет должен содержать файл PackageInfo.g с мета-информацией о нем (все пакеты для GAP 4.4 такие файлы уже содержат). За исключением этой особенности, имеется только несколько незначительных изменений (например, тривиальная группа теперь не является простой), не совместимых с GAP 4.3.

Среди других областей применения системы - теория графов и их автоморфизмов, теория кодирования, теория полугрупп, кристаллография, и многое другое. Существует графический интерфейс XGAP (http://www.math.rwth-aachen.de/~Max.Neunhoeffer/xgap4), который работает в среде Unix/Linux и позволяет, например, графически изобразить решетку подгрупп группы (см. пример здесь: http://www.gap-system.org/ukrgap/Examples/Lattice.htm). Информация о существующих разработках для применения в той или проблемной области может быть найдена на сайте GAP (http://www.gap-system.org/).

1.3 Инсталляция и запуск системы

При успешном запуске GAP на экране появится эмблема GAP. После нее будет напечатана дополнительная информация о версии системы и установленных компонентах, например:


            #########           ######         ###########           ###  
         #############          ######         ############         ####  
        ##############         ########        #############       #####  
       ###############         ########        #####   ######      #####  
      ######         #         #########       #####    #####     ######  
     ######                   ##########       #####    #####    #######  
     #####                    ##### ####       #####   ######   ########  
     ####                    #####  #####      #############   ###  ####  
     #####     #######       ####    ####      ###########    ####  ####  
     #####     #######      #####    #####     ######        ####   ####  
     #####     #######      #####    #####     #####         #############
      #####      #####     ################    #####         #############
      ######     #####     ################    #####         #############
      ################    ##################   #####                ####  
       ###############    #####        #####   #####                ####  
         #############    #####        #####   #####                ####  
          #########      #####          #####  #####                ####  
                                                                          
     Information at:  http://www.gap-system.org
     Try '?help' for help. See also  '?copyright' and  '?authors'
    
   Loading the library. Please be patient, this may take a while.
GAP4, Version: 4.4.10 of 02-Oct-2007, i686-apple-darwin9.1.0-gcc
Components:  small 2.1, small2 2.0, small3 2.0, small4 1.0, small5 1.0, 
             small6 1.0, small7 1.0, small8 1.0, small9 1.0, small10 0.2, 
             id2 3.0, id3 2.1, id4 1.0, id5 1.0, id6 1.0, id9 1.0, id10 0.1, 
             trans 1.0, prim 2.1  loaded.
Packages:    openmath 06.03.02, GAPDoc 1.1, IO 2.3, AClib 1.1, Polycyclic 2.2, 
             Alnuth 2.2.5, CrystCat 1.1.2, Cryst 4.1.5, Carat 2.0.2, 
             AutPGrp 1.2, CRISP 1.3.1, CTblLib 1.1.3, TomLib 1.1.2, 
             FactInt 1.5.2, FGA 1.1.0.1, HAP 1.8.2, Homology 1.4.2, EDIM 1.2.3, 
             IRREDSOL 1.1.2, LAGUNA 3.4, Sophus 1.23, Polenta 1.2.7, 
             ResClasses 2.5.3  loaded.

Точный вид этого сообщения будет зависеть от набора установленных пакетов и их совместимости с операционной системой.

Приглашение системы (командная строка) имеет следующий вид:


gap>

Для выхода из системы применяется команда quit; (заметим, что ввод любой команды завершается точкой с запятой и нажатием клавиши Enter.

Примечание. Для дублирования введенных команд и выводимых на экран результатов в текстовом файле используется команда LogTo("filename.log");. Ведение файла протокола может быть остановлено командой LogTo(); (например, чтобы просмотреть его содержимое в другом окне Windows, не прерывая сеанса работы с GAP).

1.4 Первые шаги в GAP

Если Вы впервые работаете с системой, Вы можете попробовать начать читать и вводить (в т.ч. через копирование и вставку) примеры из первых глав "Введения в GAP" (GAP Tutorial) с сайта GAP в формате HTML или PDF. В частности, там рассказывается, как пользоваться обширнейшей документацией по системе. См. также лабораторную работу "Основы работы с системой GAP в MS Windows" (Приложение C.1).

Вы можете попробовать, например, использовать GAP как простейший калькулятор:


gap> (9 - 7) * (5 + 6); 
22 
gap> 3^132; 
955004950796825236893190701774414011919935138974343129836853841 
gap>

Определить последние пять из 12978189 цифр 45-го числа Мерсенна 2^43112609-1, найденного в августе 2008 г. в ходе проекта GIMPS (Great Internet Mersenne Prime Search, см. http://www.mersenne.org), и являющегося на сегодня самым большим из известных науке простых чисел:


gap> a:=2^43112609-1;
<integer 316...511 (12978189 digits)>
gap> a mod 100000;
52511

Вычислить наибольший общий делитель двух целых чисел и найти его линейное представление:


gap> Gcd(100, 48);
4
gap> Gcdex(100, 48);
rec( coeff1 := 1, coeff2 := -2, coeff3 := -12, coeff4 := 25, gcd := 4 )
gap> 100*1+48*-2;
4
gap> 100*-12+48*25;
0

Разложить целое число на множители с помощью функции FactorsInt:


gap> FactorsInt(2^64-1);
[ 3, 5, 17, 257, 641, 65537, 6700417 ]
gap> FactorsInt(2^128-1);
[ 3, 5, 17, 257, 641, 65537, 274177, 6700417, 67280421310721 ]
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 ]

GAP предоставляет разнообразные возможности для работы с множествами, списками, матрицами. Например, список квадратов натуральных чисел от 1 до 10 можно получить так:


gap> List([1..10], x -> x^2);
[ 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 ]

А список натуральных чисел, не превосходящих 100 и являющихся произведением трех простых чисел (не обязательно различных), можно получить следующим образом:


gap> Filtered([1..100], x -> Length(Factors(x))=3 );
[ 8, 12, 18, 20, 27, 28, 30, 42, 44, 45, 50, 52, 63, 66, 68, 70, 75, 76, 78,
  92, 98, 99 ]

Теперь зададим матрицу следующим образом:


gap> A:=[[1,2,3,4],[4,2,1,5],[-1,10,0,0],[2,-4,7,0]];
[ [ 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> (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> 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 описаны в следующих разделах данного методического пособия, а также в документации на английском языке, которая не только является частью системы (см. каталог gap4r4/doc), но и доступна для просмотра и загрузки в форматах HTML и PDF на сайте системы по адресу http://www.gap-system.org/Doc/manuals.html. Кроме того, в разделе "Изучаем алгебру с GAP" сайта Украинской группы пользователей GAP (http://www.gap-system.org/ukrgap/) содержится серия примеров к курсу алгебры и теории чисел.

Для получения новостей о GAP рекомендуем подписаться на GAP Forum (http://mail.gap-system.org/mailman/listinfo/forum) - англоязычный форум для обсуждения связанных с GAP вопросов, сообщений об обновлениях, новых версиях, пакетах, конференциях и др. связанных с GAP событиях.

Желаем Вам приятной работы с системой GAP!

 [Начало книги]  [Содержание]   [Предыдущая глава]   [Следующая глава] 
Перейти к главе: Начало 1 2 3 4 A B C Bib Ind

generated by GAPDoc2HTML