Отправляет email-рассылки с помощью сервиса Sendsay

Система компьютерной алгебры GAP

Подписаться Бесплатная «Серебряная» новостная рассылка . Временно не выходит ,возобновит выход - нет информации Подписчиков 783 RSS
←   Июнь 2003   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Сайт рассылки: http://www.gap-system.org/ukrgap/
Открыта: 05-02-2002

Автор
Александр Борисович Коновалов

Статистика

783 подписчиков
0 за неделю
←   Все выпуски   →

Система компьютерной алгебры GAP - # 24 (30-06-03)


Информационный Канал Subscribe.Ru
Рассылка "Система компьютерной алгебры GAP"
ведущий рассылки А.Б.Коновалов, a_konovalov@hotmail.com
выпуск 24 от 30 июня 2003 г.

Здравствуйте, уважаемые читатели!

Последнее время наша рассылка выходила один раз в месяц. Конец семестра, экзамены, защита дипломных работ - все это приводило к увеличению интервала между выпусками рассылки. Надеемся, что ожидание нового выпуска рассылки компенсируется обилием полученных Вами сегодня материалов.

Несмотря на небольшой перерыв, количество подписчиков продолжало неуклонно возрастать, и 6 июня 2003 г., спустя ровно 16 месяцев после открытия рассылки, оно впервые превысило 1000! Мы приветствуем новых читателей, и для тех, кто ранее не был знаком с системой GAP, публикуем материал вводного характера по ее применению для изучения начальных тем университетского курса алгебры и теории чисел, опубликованный недавно на нашем сайте http://ukrgap.exponenta.ru/.

Хотелось бы также обратить внимание на связь между проблемами, обсуждаемыми на Международном симпозиуме по изображению графов (GD2003), и построением графа группы, которое описано в примере, следующем ниже.

 С уважением, Коновалов А.Б.

СОДЕРЖАНИЕ ВЫПУСКА:
  1. Выход пятого обновления (bugfix 5) к системе GAP 4.3
  2. Новая версия пакета LAGUNA для работы с групповыми кольцами
  3. Элементы математической логики и теории множеств с системой GAP
  4. Графы конечных групп
  5. Летняя школа по представлениям групп (Португалия, июль 2003 г.)
  6. Международный симпозиум по изображению графов (Италия, сентябрь 2003 г.)
24 июня 2003 г.
Bugfix 4 для GAP 4.3

24 июня 2003 г. объявлено о выпуске нового, пятого обновления для GAP версии 4.3. Предыдущее обновление было выпущено в декабре 2002 г.

Данное обновление применяется только к версии 4.3, и не может быть применено к GAP 4.2 и более ранним версиям системы. Если Вы пользуетесь предыдущими версиями, настоятельно рекомендуем обновить Вашу систему до GAP 4.3 с обновлением номер пять.

Система обновлений кумулятивная, т.е. накопительная, что означает, что если Вы пользуетесь версией 4.3 и не воспользовались предыдущими ее обновлениями, то достаточно сразу применить последнее, без первоначального применения предыдущих.

Особо обращаем Ваше внимание на то, что предыдущее, четвертое обновление затрагивало также интерфейс двух программ (packages), а именно AutPGrp и ANUPQ. Если Вы пользуетесь этими программами, их также следовало обновить (см.ниже).

Обновление исправляет 18 проблем различного рода, которые могут приводить к сообщениям об ошибках или неверным результатам.

GAP Group благодарит за сообщения о проблемах следющих пользователей GAP: Edgar Fuss, J"urgen M"uller, Dima Pasechnik, Luc Teirlinck, Leonard Soicher, Ignat Soroko, Peter M"uller, Kimball Martin, Rafael Villarroel Flores.

Для инсталляции обновления загрузите архив fix4r3n5.zoo' со страницы

http://www-gap.dcs.st-and.ac.uk/~gap/Info4/bugfixes.html

или из каталога bugfixes' дистрибутива GAP4 на ftp-сервере.

Разархивируйте этот файл в корневой каталог Вашей системы GAP (т.е. каталог, содержащий подкаталоги lib' и grp') с помощью команды unzoo -x fix4r3n5.zoo', отвечая Y)es или A)ll на вопросы, заменять ли существующие файлы. Версии обновления в архивах форматов zip, tar.gz и tar.bz2 также доступны, а их установка происходит аналогичным образом.

Поскольку данное обновление меняет ядро системы, то нужно перекомпилировать ядро после распаковки обновления. Для этого выполните следующую последовательность команд из корневого каталога GAP:

make clean
./configure
make

 Пользователи Windows могут найти новый исполнимый файл в архиве wbin4r3n5.zoo ' в каталоге bugfixes'. Распакуйте его в том же каталоге, что и обновление, для того, чтобы получить новый файл bin/gapw95.exe'. Пользователи Macintosh должны загрузить один из файлов 'bin4r3n5-PPC.sit' или 'bin4r3n5-68k.sit ' в зависимости от архитектуры машины, из того же каталога 'bugfixes '.

После инсталляции обновления вы можете проверить корректность установки, запустив систему из каталога gap4r3' и выполнив команду ReadTest("tst/bugfix.tst");

 gap> ReadTest("tst/bugfix.tst");
+ bugfixes test
+ GAP4stones: 6220
true

Если установка была успешной, вывод должен быть подобен указанному выше. Параметр GAP4stones может отличаться в зависимости от производительности Вашей системы. Запуск теста не является необходимой частью процедуры инсталляции, а его выполнение может занять продолжительное время.
23 июня 2003 г.
Новая версия пакета LAGUNA для вычислений в групповых кольцах

Выпущена версия 3.1 пакета LAGUNA, расширяющего функциональность системы GAP для вычислений в групповых кольцах. Название пакета расшифровывается как "Lie AlGebras and UNits of group Algebras". Кроме определения некоторых общих характеристик групповых колец и их элементов, LAGUNA позволяет исследовать Лиевские свойства группового кольца конечной группы и вычислять нормированную мультипликативную группу модулярной групповой алгебры конечной р-группы над полем из р элементов.

Основное отличие новой версии от предыдущей - принятие пакета Советом GAP и присвоение ему статуса "accepted package". Кроме того, в новой версии уточнена документация, добавлены функции для проверки симметричности и унитарности элемента группового кольца относительно классической инволюции, ускорено вычисление суммы коэффициентов элемента группового кольца. Выход следующей версии 3.2, адаптированной для работы с ожидаемым вскоре новым релизом GAP 4.4, запланирован на июль 2003 г. Дальнейшая информация и дистрибутив пакета находятся на странице пакета LAGUNA. Пример работы с пакетом можно найти также в разделе "Изучаем алгебру с GAP".
Элементы математической логики
и теории множеств с системой GAP
(материал разработан с участием студентки ЗГУ О.Ганюк)

Запуск GAP и выход из системы

Запуск GAP в ОС Windows осуществляется с помощью командного файла gap.bat, который Вы можете найти в подкаталоге "bin" каталога, содержащем GAP (например, "С:\gap4r3\"). При успешном запуске 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.3fix4 of December 20, 2002, i686-pc-cygwin-gcc
Components: small, small2, small3, small4, small5, small6, small7,
small8, id2, id3, id4, id5, id6, trans, prim loaded.
Packages: tomlib, crisp, cryst, polycyclic, crystcat, ctbllib,
EDIM, GAPDoc, factint, laguna loaded.

Приглашение системы (командная строка) имеет следующий вид:
gap>
Для выхода из системы применяется команда
quit;
Заметим, что любая команда завершается точкой с запятой, после чего нужно нажать <Enter>.

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

Простейшие вычисления в GAP

После приглашения системы (gap>) вы можете использовать ее в качестве обыкновенного калькулятора:
gap> (4+130)*(5-17);
-1608
gap> 1235/67890;
247/13578
gap> 2^65;
36893488147419103232
Для удобства вычислений и написания формул в процессе диалога можно вводить переменные, например:
gap> a:=100;
100
gap> b:=25;
25
gap> (a+50)/b;
6

Элементы математической логики

В GAP имеются две логические константы - true (истина) и false (ложь). Их значения можно присваивать переменным:
gap> A:=true;
true
gap> B:=false;
false
Система GAP позволяет определять истинность тех или иных выражений:
gap> 2+2=5;
false
gap> 1/2 in Integers; # 1/2 не содержится в множестве целых чисел
false
gap> 15 mod 5 = 3; # остаток от деления 15 на 5 не равен 3
false
gap> 16 mod 5 = 1; # остаток от деления 16 на 5 равен 1
true
gap> 1+(1/10000) > 1;
true
Над логическими константами можно выполнять операции отрицания, конъюнкции и дизъюнкции. Рассмотрим примеры вычисления для заданных выше переменных А и В, равных соответственно true и false.
gap> A or B;
true
gap> A and B;
false
gap> not A;
false
gap> not B;
true
Для более сложного логического выражения зададим переменную С со значением true:
gap> C:=true;
true
gap> (A and B) or C;
true
Построим таблицу истинности для логических операторов and и or. Сначала зададим список h, состоящий из всевозможных комбинаций true и false, следующим образом:
gap> h:=[[true,true],[true,false],[false,true],[false,false]];
[ [ true, true ], [ true, false ], [ false, true ], [ false, false ] ]
Теперь будем перебирать все пары из этого списка с помощью цикла for … od. Для каждой пары (x1,x2) выведем на печать значение высказываний "А и В", "А или В", "не А", "не В" :
gap> for x in h do
> Print(x, " ", x[1] and x[2], " ", x[1] or x[2], "\n");
> od;
[ true, true ] true true
[ true, false ] false true
[ false, true ] false true
[ false, false ] false false
Аналогичным образом построим таблицу истинности для импликации, с учетом логического закона, выражающего ее с помощью отрицания и дизъюнкции :
gap> for x in h do
> Print(x, " ", not x[1] or x[2], "\n");
> od;
[ true, true ] true
[ true, false ] false
[ false, true ] true
[ false, false ] true
Следующие команды выводят на экран таблицу истинности для эквиваленции:
gap> for x in h do
> Print(x, " ", (not x[1] or x[2]) and (not x[2] or x[1]), "\n");
> od;
[ true, true ] true
[ true, false ] false
[ false, true ] false
[ false, false ] true
Перебрать всевозможные значения элементарных высказываний, входящих в логическую формулу, можно было бы более эффективно с использованием функции Tuples(list, k), которая возвращает список всевозможных упорядоченных наборов длины k из элементов списка list.

Например, список h в предыдущем примере можно было создать следующим образом:
gap> Tuples([true,false],2);
[ [ true, true ], [ true, false ], [ false, true ], [ false, false ] ]
Если в логическую формулу входят три элементарных высказывания, то нужно создать список, состоящий из всевозможных упорядоченных троек, элементами которых являются true и false:
gap> s:=Tuples([true,false],3);
[ [ true, true, true ], [ true, true, false ], [ true, false, true ],
[ true, false, false ], [ false, true, true ], [ false, true, false ],
[ false, false, true ], [ false, false, false ] ]
Проверим, что элементов списка действительно 8:
gap> Length(s);
8
С помощью этого списка проверим, например, истинность одного из законов де Моргана. Для этого отдельно вычислим левую и правую части соответствующего высказывания, и проверим, что их значения совпадают при любых значениях A, B и C:
gap> for x in s do
> Print(x, " ", (x[1] or x[2]) and x[3], " " ,
> (x[1] and x[3]) or (x[2] and x[3]), "\n");
> od;
[ true, true, true ] true true
[ true, true, false ] false false
[ true, false, true ] true true
[ true, false, false ] false false
[ false, true, true ] true true
[ false, true, false ] false false
[ false, false, true ] false false
[ false, false, false ] false false
В GAP есть также функции ForAll и ForAny, позволяющие записывать высказывания для с применением кванторов, если множество допустимых значений соответствующих переменных конечно. Например, составим список primes, состоящий из первых восьми простых чисел:
gap> primes:=[2,3,5,7,11,13,17,19];
[ 2, 3, 5, 7, 11, 13, 17, 19 ]
Теперь мы можем проверить:
а) действительно ли каждый элемент списка primes является простым числом, применив функцию IsPrime:
gap> ForAll(primes, IsPrime);
true
b) есть ли в списке элемент, остаток от деления которого на 2 равен 0 (т.е. элемент, делящийся на 2):
gap> ForAny(primes, x -> x mod 2 = 0);
true
с) все ли элементы списка не делятся на 2:
gap> ForAll(primes, x -> x mod 2 <> 0);
false
d) есть ли в списке элементы, которые превосходят 20:
gap> ForAny(primes, x -> x > 20);
false

Элементы теории множеств

В предыдущем разделе Вы уже видели примеры использования списков в GAP. Список можно рассматривать как аналог массивов, используемых в некоторых других языках программирования, однако, в отличие от них, в GAP список может состоять из элементов различных типов, включая даже другие списки:
gap> list:=[1,2,true];
[ 1, 2, true ]
gap> list2:=[10,true,12,list,13];
[ 10, true, 12, [ 1, 2, true ], 13 ]
и даже может содержать пустые элементы:
gap> list[10]:=15;
15
gap> list;
[ 1, 2, true,,,,,,, 15 ]
Множества в GAP являются частными случаями списков, и не должны содержать пустых и повторяющихся элементов. Проверить, является ли список множеством в соответствии с этим требованием, можно с помощью функции IsSet:
gap> list:=[1,2,3,4,5,6,7,8,9,10];
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
gap> IsSet(list);
true
gap> list1:=[1,2,2,2,5,6,7,8,9,10];
[ 1, 2, 2, 2, 5, 6, 7, 8, 9, 10 ]
gap> IsSet(list1);
false
Кроме того, любой список можно преобразовать в множество, удалив из него пустые и повторяющиеся элементы, с помощью функции Set:
gap> Set(list1);
[ 1, 2, 5, 6, 7, 8, 9, 10 ]
gap> list2:=[1,1,true,4,true, false];
[ 1, 1, true, 4, true, false ]
gap> Set(list2);
[ 1, 4, true, false ]
Над множествами можно выполнять стандартные операции. Например, зададим множества А и В:
gap> A:=[2,5,7,9];
[ 2, 5, 7, 9 ]
gap> B:=[1,5,7,12];
[ 1, 5, 7, 12 ]
Эти множества не равны:
gap> IsEqualSet(A,B);
false
Множество А не является подмножеством В:
gap> IsSubsetSet(A,B);
false
Мы можем очевидным образом вычислить:
а) пересечение множеств:
gap> IntersectionSet(A,B);
[ 5, 7 ]
в) объединение множеств:
gap> UnionSet(A,B);
[ 1, 2, 5, 7, 9, 12 ]
с) разность множеств:
gap> Difference(A,B);
[ 2, 9 ]
d) симметрическую разность множеств:
gap> UnionSet(Difference(A,B),Difference(B,A));
[ 1, 2, 9, 12 ]
С помощью функции Cartesian мы можем вычислить декартово произведение множеств А и В:
gap> Cartesian(A,B);
[ [ 2, 1 ], [ 2, 5 ], [ 2, 7 ], [ 2, 12 ], [ 5, 1 ], [ 5, 5 ], [ 5, 7 ],
[ 5, 12 ], [ 7, 1 ], [ 7, 5 ], [ 7, 7 ], [ 7, 12 ], [ 9, 1 ], [ 9, 5 ],
[ 9, 7 ], [ 9, 12 ] ]
Заметим, что для вычисления декартова произведения не требуетя, чтобы оба множества состояли из элементов одинакового типа. Например, мы можем вычислить декартово произведение числового множества на множество, состоящее из логических констант. gap> N:=[2,5,7,9];
[ 2, 5, 7, 9 ]
gap> M:=[true, false];
[ true, false ]
gap> Cartesian(N,M);
[ [ 2, true ], [ 2, false ], [ 5, true ], [ 5, false ],
[ 7, true ], [ 7, false ], [ 9, true ], [ 9, false ] ]

Граф группы

Граф группы [1, стр. 63] является одним из способов ее наглядного изображения, он может дать возможность мысленно представить группу, подсказать более эффективное доказательство требуемого результата. Для конечных групп малого порядка он может быть использован для задания группы вместо таблицы Кэли, так как содержит ту же информацию, но в более наглядной форме.

Дадим интуитивное описание графа группы в соответствии с [1]. Пусть G - группа. Для простоты будем считать, что она имеет представление с двумя образующими элементами a и b. Установим взаимно однозначное соответствие между элементами g группы G и вершинами Pg графа группы G. Теперь соединим вершины графа ориентированными ребрами двух различных типов, соответствующих образующим элементам a и b (например, ребрами двух различных цветов Ca и Cb), по следующему правилу: если

g a = s, g a-1 = t, g b = u, g b-1 = v,

то проводим:

  • ориентированные ребра цвета Ca :
    • от вершины Pg к вершине Ps;
    • от вершины Pt к вершине Pg;
  • ориентированные ребра цвета Cb :
    • от вершины Pg к вершине Pu;
    • от вершины Pv к вершине Pg.

Таким образом, в каждой вершине графа будет начинаться в точности одно ориентированное ребро каждого цвета и будет заканчиваться в точности одно ориентированное ребро каждого цвета. Построенная конструкция обычно и называется графом группы G с образующими a и b. В литературе также можно встретить названия "групповая диаграмма", "диаграмма Кэли", "цветная группа".

К сожалению, в настоящее время в системе GAP отстутствуют инструменты для графического изображения графа группы (см. ниже), однако несложно получить его численное описание. Для этого создадим сначала две следующие функции. Первая функция сначала вычисляет списки всех элементов группы и ее порождающих элементов, а затем получает описание графа в виде списка, элементами которого являются тройки чисел вида [i, j, k], означающие, что от вершины с номером i к вершине с номером j проведено ориентированное ребро цвета с номером k.

Graph:=function(G)
local elms, # список всех элементов группы
gens, # список порождающих эл-тов группы
graph,# описание графа группы
i, # индекс эл-тов группы
k, # номер цвета (порожд. эл-та группы)
j; # номер конца ребра цвета k с началом в вершине i
elms:=AsSSortedList(G);
gens:=GeneratorsOfGroup(G);
graph:=[];
for i in [1 .. Length(elms)] do
for k in [1 .. Length(gens)] do
j:=Position(elms, elms[i]*gens[k]);
Append(graph, [[i,j,k]]);
od;
od;
return graph;
end;

Вторая функция представляет полученный с помощью первой функции список в виде квадратной матрицы порядка |G|, в которой элемент aij равен k, если от вершины с номером i к вершине с номером j проведено ориентированное ребро цвета k, и нулю в противном случае. Заметим, что это менее экономичное хранение информации о графе группы, так как такая матрица содержит довольно много нулевых элементов.

Mat:=function(graph)
local l, n, mat, i,j, x;
l:=List(graph, x -> x[1]);
Append(l, List(graph, x -> x[2]));
n:=Maximum(l);
mat:=[];
for i in [1..n] do
mat[i]:=[];
for j in [1..n] do
mat[i][j]:=0;
od;
od;
for x in graph do
mat[x[1]][x[2]]:=x[3];
od;
return(mat);
end;

Получим теперь с помощью этих функций описание графа симметрической группы подстановок третьей степени. Сначала зададим эту группу:

gap> S:=SymmetricGroup(3);
Sym( [ 1 .. 3 ] )

Хотя список порождающих элементов и элементов всей группы независимо будут получены в процессе работы программы, выведем их на экран, чтобы уточнять в дальнейшем, какой элемент группы соответствует вершине графа с соответствующим номером:

gap> GeneratorsOfGroup(S);
[ (1,2,3), (1,2) ]
gap> AsSSortedList(S);
[ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ]

Теперь мы можем получить описание графа группы в виде списка:

gap> t:=Graph(S);
[ [ 1, 4, 1 ], [ 1, 3, 2 ], [ 2, 3, 1 ], [ 2, 4, 2 ], [ 3, 6, 1 ],
[ 3, 1, 2 ], [ 4, 5, 1 ], [ 4, 2, 2 ], [ 5, 1, 1 ], [ 5, 6, 2 ],
[ 6, 2, 1 ], [ 6, 5, 2 ] ]

а также в виде матрицы, которую удобно изобразить с помощью функции Display:

gap> m:=Mat(t);
[ [ 0, 0, 2, 1, 0, 0 ], [ 0, 0, 1, 2, 0, 0 ], [ 2, 0, 0, 0, 0, 1 ],
[ 0, 2, 0, 0, 1, 0 ], [ 1, 0, 0, 0, 0, 2 ], [ 0, 1, 0, 0, 2, 0 ] ]
gap> Display(m);
[ [ 0, 0, 2, 1, 0, 0 ],
[ 0, 0, 1, 2, 0, 0 ],
[ 2, 0, 0, 0, 0, 1 ],
[ 0, 2, 0, 0, 1, 0 ],
[ 1, 0, 0, 0, 0, 2 ],
[ 0, 1, 0, 0, 2, 0 ] ]

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

[1] В.Магнус, А.Каррас, Д.Солитэр. Комбинаторная теория групп. М., Наука, 1974. 456 стр.

ЛЕТНЯЯ ШКОЛА ПО ПРЕДСТАВЛЕНИЯМ ГРУПП
 Лиссабон, Португалия, 21-25 июля 2003 г.
 http://hermite.cii.fc.ul.pt/sschool/
XI МЕЖДУНАРОДНЫЙ СИМПОЗИУМ ПО ИЗОБРАЖЕНИЮ ГРАФОВ (GD 2003)
Перуджа, Италия, 21-24 сентября 2003 г.
http://www.gd2003.org/
Прием статей, презентаций и постеров завершен до 31 мая 2003 г.
Прием заявок на участие в конкурсе "Graph Drawing Contest" до 15 августа 2003 г.
С уважением,
 Коновалов Александр Борисович , председатель Украинской группы пользователей GAP ,
 доцент кафедры алгебры и геометрии Запорожского государственного университета










http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное