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

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

Подписаться Бесплатная «Серебряная» новостная рассылка . Временно не выходит ,возобновит выход - нет информации Подписчиков 783 RSS
←   Декабрь 2004   →
 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 - # 45, 13-12-04 (Алгоритм умножения подстановок)


Информационный Канал Subscribe.Ru
Рассылка "Система компьютерной алгебры GAP"
http://subscribe.ru/catalog/science.exact.gap/
ведущий рассылки А.Б.Коновалов, a_konovalov@hotmail.com
выпуск 45 от 13 декабря 2004 г.
Алгоритм умножения подстановок
На сайте Украинской группы пользователей GAP (http://ukrgap.exponenta.ru/) в разделе "Изучаем алгебру с GAP" помещен новый материал по теме "Алгоритм умножения подстановок". В связи с тем, что 13 декабря этот выпуск вышел с нарушениями кодировки, мы повторяем его и приносим извинения за неудобства.
Напомним, что взаимно однозначное отображение множества M первых n натуральных чисел на себя называется подстановкой n-й степени. Если x - элемент множества M, и s - подстановка, то образ элемента x под действием подстановки s обозначается s(x). Тогда умножение подстановок определяется как композиция отображений:
(s1*s2)(x) = s1(s2(x)).

Подстановки являются стандартными объектами в системе GAP. Они задаются в виде произведения независимых циклов. При этом умножение подстановок выполняется слева направо, а не справа налево. Это связано с тем, что для образа точки i под действием подстановки p можно использовать как обозначение p(i), так и обозначение ip. В GAP принят за основу второй вариант записи (поскольку запись p(i) интерпретировалась бы как обращение к функции p с аргументом i), и ip записывается как i^p. Тогда выполняется соотношение i^(p1*p2)=(i^p1)^p2, соответствующее правилу (p1*p2)(i) = p1(p2(i)).

Для изучения алгоритма умножения подстановок справа налево приведем пример программы на языке GAP. Эта программа работает с подстановками, заданными в виде произведения независимых циклов в формате [[a1,a2,...,ai],[b1,b2,...,bj],...,[z1,z2,...,zk]]. Мы вводим свою запись подстановок, отличную от принятой в GAP, специально для изучения правила умножения подстановок, и ни в коем случае не для практического применения в научных целях, так как в системе GAP уже имеется намного более эффективная возможность работы с подстановками. Данная программа также дает понятие о языке программирования GAP, так как содержит примеры его основных конструкций: условные переходы и три различных вида циклов - for, while и until.

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

ProductOfTwoPermutations:=function( s1, s2 )
local c, i, p, points, pos, s, t, x;
s := Concatenation( s1, s2 );
if ForAny(s, x -> Length( x ) <> Length( Set( x ) ) ) then
Error("An argument do not represent a permutation !!!");
fi;
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> ProductOfTwoPermutations([[2,3,5,4],[1,6]], [[1,3,5]]);
[ [ 1, 5, 6 ], [ 2, 3, 4 ] ]

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

ProductOfTwoPermutations:=function( s1, s2 )
# Используемые переменные:
local t, # результирующий список независимых циклов
s, # объединенный список независимых циклов из разложений
# подстановок s1 и s2 (сначала перечисляются циклы из
# разложения подстановки s1, потом подстановки s2)
points, # множество точек, которые входят в запись s1 и s2
p, # текущая точка
i, # счетчик циклов в списке s
pos, # позиция текущей точки в текущем цикле s[i]
c, # текущий формируемый цикл, который после окончания
# его формирования добавляется к списку t
x; # служебная переменная (элемент списка при его переборе)
#
# Шаг 1. Соединяем первый и второй аргументы в один список
# (т.е. записываем вторую подстановку после первой)
s := Concatenation( s1, s2 );
#
# Проверяем, что каждый цикл не содержит повторяющихся элементов
# (в данной программе не проверяется, что циклы независимы)
if ForAny(s, x -> Length( x ) <> Length( Set( x ) ) ) then
Error("An argument do not represent a permutation !!!");
fi;
#
# Шаг 2. Создаем пустой список, в который в процессе расчета
# будут добавляться списки, соответствующие независимым циклам
# из разложения итоговой подстановки
t := [];
#
# Шаг 3. Формируем множество точек, входящих в заданные подстановки
# (другие точки мы не рассматриваем). Оно будет нужно нам для
# выбора точек, которые еще не были нами рассмотрены, т.е. не входят
# в уже сформированные циклы результирующей подстановки t.
points := Set( Flat( s ) );
#
# Шаг 4. Последовательный выбор точки p из множества еще не входящих
# в запись s1*s2 точек. С выбранной точки p начинается формирование
# нового цикла (его запись можно начинать с любой точки, но для
# удобства мы выбираем в качестве р минимальную из таких точек).
while Length(points) > 0 do
# Шаг 4.1.
# создаем пустой список c, в который будем записывать точки цикла
# (иными словами, открываем левую скобку)
c := [];
# Выбор минимального p, еще не входящего в запись s1*s2
p := Minimum( points );
# записываем р в список c - это первый элемент нашего цикла
Add( c, p );
# Шаг 4.2. Продолжение формирование цикла c: если на некотором шаге
# его последний элемент - точка p, то добавляем к циклу c образ
# точки p под действием подстановки s1*s2. Процесс продолжаем
# до тех пор, пока цикл не замкнется, т.е. пока не получим первый
# элемент цикла c.
repeat
# Шаг 4.3. Перебор циклов из списка s в обратном порядке
# для определения образа точки p
for i in [ Length(s), Length(s)-1 .. 1 ] do
# если текущий цикл s[i] не содержит p, мы его пропускаем
if p in s[i] then
# иначе определяем номер точки p в цикле s[i]
pos := Position( s[i], p );
if pos = Length( s[i] ) then
# если точка р - последняя в цикле s[i], то она
# переходит в первый его элемент
p := s[i][1];
else
# в противном случае она переходит в элемент цикла
# с номером, на единицу большим, т.е. следующий за ней
p := s[i][pos+1];
fi;
fi;
# если i не равняется единице, то возвращаемся на шаг 4.2,
# уменьшая i на единицу (т.к. перебираем циклы справа налево)
od;
# в результате после шага 4.3 вместо исходного значения р
# мы получили его образ под действием подстановки s1*s2. Если
# этот образ совпадает с первым элементом формируемого цикла,
# то цикл замкнулся (ставим правую скобку). В противном случае
# добавляем этот элемент к циклу и вовзращаемся на шаг 4.2
if p <> c[1] then
Add( c, p );
fi;
until p = c[1];
# Добавляем полученный цикл к результирующему списку t
Add( t, c );
# Теперь удаляем из списка points все точки, входящие в цикл c,
# для того, чтобы затем определить, какие еще точки не были учтены
SubtractSet( points, c );
# Если после этого список points еще не пуст, то возвращаемся
# на шаг 4 и начинаем формирование следующего цикла
od;
# если же перебрали уже все возможные точки, то удаляем из
# списка t циклы единичной длины, а затем возвращаем результат
return Filtered( t, x -> Length( x ) > 1 );
end;
Блок-схема
Блок-схема данной программы находится здесь.

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

DeclareInfoClass("MyInfo");

Эта команда определяет так называемый InfoClass под именем "MyInfo". Ему соответствует уровень вывода информации, который называется InfoLevel. По умолчанию InfoLevel для вновь созданного класса равен нулю, и никакие информационные сообщения не печатаются. Далее, для печати информационных сообщений в программу включаются строки вида

Info( MyInfo, i, "text", variable );

Если теперь ввести, например, команду

SetInfoLevel(MyInfo,1);

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

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

gap> Read("prodperm.g");

для включения режима печати информационных сообщений нужно ввести команду

gap> SetInfoLevel(MyInfo,1);

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

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 ] ]

Диаграмма Эти информационные сообщения показывают следующую информацию:
  • с какой точки начинается запись текущего цикла;
  • как выглядит уже записанный текст на текущем шаге алгоритма;
  • как определяется элемент, который нужно записывать следующим (в т.ч. какие циклы и каким образом участвуют в его определении).
Полезным упражнением будет изучение текста программы prodperm.g и сопоставление шаго алгоритма и выводимых на печать информационных сообщений.

Для изучения алгоритма умножения подстановок в виде произведения циклов предлагаем ознакомиться также с презентацией в MS PowerPoint, показывающую его на примере. Вы можете загрузить презентацию здесь. Если же у Вас не установлен MS PowerPoint, то Вы можете загрузить изображение в формате WMF здесь.

В заключение отметим, что при сверке студентами результатов расчетов с ответами в учебнике следует быть внимательным, так как в некоторых изданиях принято умножать подстановки слева направо. В этом случае для совпадения ответа их порядок должен быть изменен на противоположный.
С уважением,
Александр Борисович Коновалов
председатель Украинской группы пользователей GAP (http://ukrgap.exponenta.ru/)
доцент кафедры алгебры и геометрии Запорожского государственного университета
E-mail: a_konovalov (at) hotmail.com

http://subscribe.ru/
http://subscribe.ru/feedback/		 Подписан адрес:
Код этой рассылки: science.exact.gap		 Отписаться
В избранное