Отправляет 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
31


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


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

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

Статистика

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

Система компьютерной алгебры GAP - #31, 01-12-03


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

СОДЕРЖАНИЕ ВЫПУСКА:
  1. Бинарные операции, полугруппы и моноиды в системе GAP
  2. ICAI '2004 : 6-я международная конференция по прикладной информатике (г.Эгер, Венгрия, 27-31 января 2004 г.)
На сайте Украинской группы пользователей GAP в разделе "Изучаем алгебру с GAP" опубликован материал по теме "Бинарные операции, полугруппы и моноиды". Его полный текст приводится ниже.

Бинарные операции. Полугруппы и моноиды.

В системе GAP одним из способов задания бинарной операции на конечном множестве M является задание ее с помощью таблицы. При этом бинарная операция полагается мультипликативной. Таблица умножения является квадратной матрицей с натуральными коэффициентами, в которой aij = k, если произведение i-го элемента множества M на его j-й элемент равняется его k-му элементу (заметьте, что задание таблицы умножения попутно вводит отношение порядка на множестве М).

Полученная структура будет являться группоидом [см. Общая алгебра. Т.2 / В.А.Артамонов, В.Н.Салий, Л.А.Скорняков и др. Под общ. ред. Л.А.Скорнякова. - М.:Наука, 1991]. В системе GAP такая структура называется магмой (magma) в соответствии с [N. Bourbaki. Éléments de Mathématique, Algèbre I, volume 1. Hermann, Paris, 1970].

Зададим некоторую таблицу умножения и исследуем свойства бинарной операции, которая ей соответствует. Вначале введем матрицу m:
gap> m:=[[1,1,1,1],[1,2,3,4],[1,3,2,4],[1,4,4,3]];
[ [ 1, 1, 1, 1 ], [ 1, 2, 3, 4 ], [ 1, 3, 2, 4 ], [ 1, 4, 4, 3 ] ]
Чтобы вывести ее на экран в удобочитаемом виде, применим функцию Display:
gap> Display(m);
[ [ 1, 1, 1, 1 ],
[ 1, 2, 3, 4 ],
[ 1, 3, 2, 4 ],
[ 1, 4, 4, 3 ] ]
Теперь мы можем сконструировать группоид M с помощью функции MagmaByMultiplicationTable следующим образом:
gap> M:=MagmaByMultiplicationTable(m);
<magma with 4 generators>
Убедимся, что он состоит из четырех элементов:
gap> AsList(M);
[ m1, m2, m3, m4 ]
Легко заметить, что введенная таблица умножения была симметрична относительно главной диагонали, и поэтому группоид M должен быть коммутативен. GAP также может проверить это:
gap> IsCommutative(M);
true
Немного сложнее с первого взгляда заметить, почему групоид M не является ассоциативным. Однако это на самом деле так:
gap> IsAssociative(M);
false
Чтобы выяснить, почему ассоциативность не имеет места, найдем все тройки элементов группоида M, для которых не выполняется условие ассоциативности. Сначала сформируем список всевозможных упорядоченных наборов по три элемента из M (заметьте, что двойная точка с запятой в конце команды подавляет вывод на экран результата, который в данном случае занял бы очень много места):
gap> t:=Tuples(AsList(M),3);;
Теперь выберем из этого списка с помощью функции Filtered только те тройки, для которых условие ассоциативности не выполняется. Таких троек окажется две:
gap> f:=Filtered(t, x -> (x[1]*x[2])*x[3] <> x[1]*(x[2]*x[3]));
[ [ m3, m4, m4 ], [ m4, m4, m3 ] ]
Проверим теперь условие асоциативности непосредственно для первой из троек. Действительно, в одном случае мы получаем m3, тогда как другой вариант расстановки скобок дает в результате m2:
gap> x:=f[1];
[ m3, m4, m4 ]
gap> (x[1]*x[2])*x[3]; x[1]*(x[2]*x[3]);
m3
m2
Полезными являются функции для определения нейтрального элемента и нулевого элемента групоида M:
gap> MultiplicativeNeutralElement(M);
m2
gap> MultiplicativeZero(M);
m1
Рассмотрим теперь еще один подобный пример, в котором операция уже будет являться ассоциативной:
gap> m:=[[1,1,1,1],[1,2,3,4],[1,3,4,2],[1,4,2,3]];
[ [ 1, 1, 1, 1 ], [ 1, 2, 3, 4 ], [ 1, 3, 4, 2 ], [ 1, 4, 2, 3 ] ]
gap> M:=MagmaByMultiplicationTable(m);
<magma with 4 generators>
gap> IsAssociative(M);
true
gap> IsCommutative(M);
true
gap> MultiplicativeNeutralElement(M);
m2
Таким образом, мы построили группоид с ассоциативной бинарной операцией и нейтральным элементом относительно этой операции. Следовательно, он является моноидом. Однако, как это ни кажется странным на первый взгляд, проверка с помощью функции IsMonoid возвращает противоположный ответ:
gap> IsMonoid(M);
false
На самом же деле (и это описано в документации по системе!), этот ответ не является ошибочным - просто необходимо интерпретировать его правильным образом. Для этого нужно рассмотреть тонкие различия между категориями и свойствами объектов в GAP.

Дело в том, что указанная функция IsMonoid проверяет не то, что объект фактически является моноидом (т.е. его свойство быть моноидом), а только лишь то, был ли создан этот объект как моноид или нет (т.е. проверяет его принадлежность к категории моноидов - см. ниже о понятии категории в GAP). Здесь мы сталкиваемся с некоторыми тонкими вопросами, связанными с особенностями программирования в системе GAP, язык программирования которой является объектно-ориентированным языком.

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

После определения категории объекта может быть произведен дальнейший выбор методов из числа применимых для объектов данной категории на основании набора фильтров, которыми он обладает (так, могут быть свои отдельные методы для определения порядка групп подстановок, матричных групп, и т.п.). Фильтр - это логическая функция, характеризующая соответствующие параметры объекта (например, IsAbelian, IsPrime, IsGroup и т.п.). Строго говоря, категории - это также фильтры, но они характеризуются тем, что определяют, какие операции применимы к объекту, тогда как в общем случае фильтр может описывать и свойства объекта, не влияющие на применимость тех или иных операций. Важно учесть, что категория объекта не может изменяться в процессе работы с ним, тогда как атрибуты и свойства объекта могут изменяться в процессе накопления знаний об объекте.

Как правило, подобные вопросы не возникают, если работа ведется с алгебраическими структурами, лежащими в одной категории. Однако, при переходах от одной категории у другой нужно быть осторожным. Несмотря на что, что из наименования функции вида Is<Имя структуры> нельзя сразу заметить, проверяет ли она свойство или принадлежность к категории, в документации описание функции сопровождается примечанием C или P, означающим соответственно Category или Property.

Если необходимо перевести объект из одной категории в другую, в ряде случаев в GAP это можно сделать с помощью функции вида As<Имя структуры>.Так, в следующем примере таблица умножения фактически задает группу. Однако и IsMagmaWithInverses, и IsGroup проверяют категорию объекта, а не то, что он является соответственно группоидом, в котором каждый элемент обратим (без требования ассоциативности), или группой. Функция же IsMonoid проверяет свойство (а не категорию), и возвращает true, если объект категории групоидов с единицей и заданная на нем операция ассоциативна.
gap> m:=[[1,2,3],[2,3,1],[3,1,2]];
[ [ 1, 2, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ] ]
gap> M:=MagmaWithOneByMultiplicationTable(m); # обратите внимание
# на WithOne в имени функции
<magma-with-one with 3 generators>
gap> IsMonoid(M); # объект является моноидом (свойство)
true
gap> IsMagmaWithInverses(M); # но не является групоидом
false # с обратимыми элементами (категория)
gap> M:=MagmaWithInversesByMultiplicationTable(m);
<magma-with-inverses with 3 generators>
gap> IsMagmaWithInverses(M); # теперь мы имеем групоид
true # с обратимыми элементами (категория),
gap> IsGroup(M); # но он не лежит в категории групп
false
gap> G:=AsGroup(M); # только теперь мы рассматриваем
<group of size 3 with 1 generators> # его как группу,
gap> AsList(G); # состоящую из трех элементов
[ m1, m2, m3 ]
gap> IsGroup(G);
true
В следующем примере мы пытаемся задать группу и полугруппу. Функция IsSemigroup проверяет свойство (а не категорию), и возвращает true, если объект является групоидом с ассоциативной операцией. Мы видим, что результат ее применения не зависит от того, был ли задан объект как групоид или групоид с нейтральным элементом:
gap> m:=[[1,1,1,1],[1,2,3,4],[1,3,4,2],[1,4,2,3]];
[ [ 1, 1, 1, 1 ], [ 1, 2, 3, 4 ], [ 1, 3, 4, 2 ], [ 1, 4, 2, 3 ] ]
gap> M:=MagmaWithInversesByMultiplicationTable(m);
fail # так как не каждый элемент является обратимым
gap> M:=MagmaWithOneByMultiplicationTable(m);
<magma-with-one with 4 generators>
gap> IsAssociative(M);
true
gap> IsSemigroup(M);
true # получили полугруппу
gap> M:=MagmaByMultiplicationTable(m);
<magma with 4 generators>
gap> IsAssociative(M);
true
gap> IsSemigroup(M);
true # также получили полугруппу
В заключение напомним, что, как уже говорилось выше, задание таблицы умножения упорядочивает множество M. Поэтому к элементам из групоида M можно обращаться по их порядковому номеру в соответствии с таблицей умножения:
gap> MultiplicationTable(AsList(M));
[ [ 1, 1, 1, 1 ], [ 1, 2, 3, 4 ], [ 1, 3, 4, 2 ], [ 1, 4, 2, 3 ] ]
gap> Display(last);
[ [ 1, 1, 1, 1 ],
[ 1, 2, 3, 4 ],
[ 1, 3, 4, 2 ],
[ 1, 4, 2, 3 ] ]
gap> elm:=MagmaElement(M,2);
m2
С помощью функции Inverse можно находить обратный элемент, если он существует (при этом не обязательно, чтобы M было задано в категории моноидов - в последнем примере мы создали его с помощью функции MagmaByMultiplicationTable):
gap> Inverse(elm);
m2
gap> Inverse(MagmaElement(M,3));
m4
gap> Inverse(MagmaElement(M,1));
fail # элемент не имеет обратного
ICAI '2004 : 6-я международная конференция по прикладной информатике
г.Эгер, Венгрия, 27-31 января 2004 г.

Основная тематика конференции:
  • Компьютерная алгебра
  • Базы данных
  • Компьютерная графика
  • Образование и другие применения прикладной информатики
Регистрация и прием тезисов до 10 января 2004 г.
С уважением,
Коновалов Александр Борисович , председатель Украинской группы пользователей GAP ,
доцент кафедры алгебры и геометрии Запорожского государственного университета


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