Комп’ютерна алгебра (стр. 15 )

Findfixedpointfreepermutation:=function(G)
local n, s;
n:=largestmovedpoint(G);
repeat
s := Random(G);
until Nrmovedpoints(s)= n;
return s;
end;

Протестуємо її на різних групах:

gap> G:=symmetricgroup(3);
Sym( [ 1 .. 3 ] )
gap> Findfixedpointfreepermutation(G);
(1,3,2)
gap> Findfixedpointfreepermutation(Alternatinggroup(4));
(1,2)(3,4)
gap> Findfixedpointfreepermutation(Alternatinggroup(5));
(1,3,5,4,2)
gap> G:=symmetricgroup(30);
Sym( [ 1] )
gap> Size(G);

gap> Findfixedpointfreepermutation(G);
(1,23)(2,19,10,8,3)(4,12,5,28,6,13,14,29,11,21,20,24,26,18,16,17)(7,27,15,9,25,30,22)

Відмітимо, що умова M={1...,n} в постановці завдання істотно, оскільки програма зациклюється в наступному прикладі:

gap> G:=group((2,3));
Group([ (2,3) ])
gap> Findfixedpointfreepermutation(G);

Така поведінка пояснюється тим, що в цьому випадку Largestmovedpoint(G) повертає 3. Природно, що ніяка підстановка з групи G не переміщає три крапки, і тому потрібна умова ніколи не досягається. З іншого боку, функція Nrmovedpoints(G) повертає 2, і потрібно використовувати саме її. Тому для більшої універсальності нашу функцію потрібно модифікувати таким чином:

Findfixedpointfreepermutation:=function(G)
local n, s;
n:=nrmovedpoints(G);
repeat
s := Random(G);
until Nrmovedpoints(s)= n;
return s;
end;

Перевіримо тепер її роботу:
gap> G:=group((2,3));
Group([ (2,3) ])
gap> Findfixedpointfreepermutation(G);
(2,3)
gap> Findfixedpointfreepermutation(Symmetricgroup(10));
(1,2)(3,5,9,8)(4,10)(6,7)
gap> Findfixedpointfreepermutation(Symmetricgroup(100));
(1,11,24,8,37,73,62,38,97,54,88,47,2,60,50,56,19,84,67,65,32,69,14,4,10,6,33,
52,83,70,5,29,91,86,77,78,43,61,35,3,22,57,95,85,23)(7,98,16,28,34,13,48,39,
46,90,45,40,21,42,36,18,17,58,76,74)(9,96,92,15,89,41,93,59,75)(12,79,30,94,
99,51,53,31,81,63,44,55)(20,82,71)(25,80,49,68,26,87,64,100,27,72,66)

Ми бачимо, що вона працює коректно як з групами, що залишають одиницю на місці, так і з симетричними групами підстановок.

Іноді при тестуванні гіпотез цікаво отбражать динаміку розрахунку на екрані і прослідкувати, скільки спроб вибору випадкового елементу з групи було зроблено, перш ніж був знайдений елемент з необхідними властивостями. Для цього можна вставити у функцію лічильник і відображати його поточне значення на екрані. При цьому рядок "\r", що управляє, використовується для стирання результату попереднього виводу на екран і друк нової інформації в тому ж рядку:
Findfixedpointfreepermutation:=function(G)
local n,s,k;
n:=nrmovedpoints(G);
k:=0;
repeat
s := Random(G);
до := k+1;
Print(до, "\r");
until Nrmovedpoints(s)= n;
Print("\n");
return s;
end;

Тепер скопіюйте у вікно GAP останній варіант нашої функції і звернетеся до неї кілька разів для якої-небудь досить великої групи. Подивитеся, скільки кроків в середньому потрібно для знаходження потрібної підстановки.

Завдання для лабораторної роботи № 7

У даній лабораторній роботі Вам необхідно вирішити ту ж задачу, що і в роботі № 6, але тільки із застосуванням циклу REPEAT замість циклу WHILE. Крім того, при тестуванні розробленої Вами функції Ви винні замість безпосереднього завдання підстановки спочатку задати деяку групу підстановок (наприклад, симетричну, знакозмінну, або породжену вказаним Вами списком підстановок), після чого вибрати випадковим чином її елемент(ы) для використання як аргумент Вашої функції.

Варіант 1.
Розробити функцію, яка для заданої підстановки s визначає мінімальне натуральне число до, таке що sk комутує із заданою підстановкою t.

Варіант 2. Розробити функцію, яка для заданої підстановки s визначає мінімальне натуральне число до, таке що sk переводить задане натуральне число n в задане натуральне число m, і повертає fail, якщо такого числа до не існує.

Варіант 3.
Розробити функцію, яка для заданої підстановки s визначає мінімальне натуральне число до, яке вона залишає на місці.

Варіант 4.
Розробити функцію, яка для заданої підстановки s визначає мінімальне натуральне число до, таке що sk залишає на місці задане натуральне число n.

Варіант 5.
Розробити функцію, яка для заданої підстановки s визначає мінімальне натуральне число до, таке що кількість натуральних чисел, переміщуваних підстановкою sk, не перевершує заданого натурального числа n.

Варіант 6.
Розробити функцію, яка для заданої підстановки s визначає мінімальне натуральне число до, таке що sk залишає на місці одиницю.

Варіант 7.
Розробити функцію, яка для заданої підстановки s визначає мінімальне натуральне число до, таке що sk комутує з підстановкою

Варіант 8.
Розробити функцію, яка для заданої підстановки s визначає мінімальне натуральне число до, таке що sk переводить 1 в 2, і повертає fail, якщо такого числа до не існує.

Варіант 9.
Розробити функцію, яка для заданої підстановки s обчислює орбіту числа 1, тобто безліч всіх чисел, в які одиницю можна перевести за допомогою деякої міри sk початкової підстановки.

Варіант 10.
Розробити функцію, яка для заданої підстановки s визначає мінімальне натуральне число до, таке що кількість натуральних чисел, переміщуваних підстановкою sk, не перевершує 5.

Варіант 11.
Розробити функцію, яка для заданої підстановки s визначає мінімальне натуральне число до, таке що sk залишає на місці найбільше число, переміщуване даною постановкою.

Варіант 12.
Розробити функцію, яка для заданої підстановки s визначає максимальне натуральне число до, таке що sk не комутує з підстановкою

Варіант 13.
Розробити функцію, яка для заданої підстановки s визначає максимальне натуральне число до, таке що кількість натуральних чисел, переміщуваних підстановкою sk, перевершує задане натуральне число n, і повертає fail, якщо такого числа до не існує.

Варіант 14.
Розробити функцію, яка для заданої підстановки s обчислює орбіту найменшого числа, переміщуваного даною підстановкою, тобто безліч всіх чисел, в які його можна перевести за допомогою деякої міри sk початкової підстановки.

Варіант 15.
Розробити функцію, яка для заданої підстановки s повертає безліч орбіт чисел, переміщуваних даною підстановкою.

Варіант 16.
Розробити функцію, яка для заданої підстановки s визначає мінімальне натуральне число до, таке що sk залишає на місці найменше число, переміщуване даною постановкою.

Варіант 17.
Розробити функцію, яка для заданої підстановки s обчислює орбіту найбільшого числа, переміщуваного даною підстановкою, тобто безліч всіх чисел, в які його можна перевести за допомогою деякої міри sk початкової підстановки.

Варіант 18.
Розробити функцію, яка для заданої підстановки s визначає максимальне натуральне число до, таке що кількість натуральних чисел, переміщуваних підстановкою sk, перевершує 5, і повертає fail, якщо такого числа до не

Лабораторна робота № 8.
Вивчення властивостей елементів групи

Дана лабораторна робота призначена для вивчення деяких прийомів роботи з елементами груп.

Докладні відомості по даних темах містяться:
- в розділі "Операції над групами і їх елементами" <file:///d:\ Комп'ютерна%20алгебра\metgap43\4-groups. htm> і Додатку B <file:///d:\ Комп'ютерна%20алгебра\metgap43\b-funct. htm> (деякі функції GAP для роботи з групами) даної методичної допомоги;
- в розділі "Groups" довідкового керівництва за системою GAP <file:///d:\ Комп'ютерна%20алгебра\metgap43\tppmsgs\msgs0.htm> і інших відповідних його розділах.

Приклад: Знайти всі 2-елементні множини, що породжують симетричну групу S3.

У інтерактивному режимі цю задачу можна вирішити таким чином:

gap> S:=symmetricgroup(3); # початкова група
Sym( [ 1 .. 3 ] )
gap> g:=aslist(S); # список її елементів
[ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ]
gap> m:=combinations(g,2); # всілякі неврегульовані пари
[ [ (), (2,3) ], [ (), (1,2) ], [ (), (1,2,3) ], [ (), (1,3,2) ],
[ (), (1,3) ], [ (2,3), (1,2) ], [ (2,3), (1,2,3) ], [ (2,3), (1,3,2) ],
[ (2,3), (1,3) ], [ (1,2), (1,2,3) ], [ (1,2), (1,3,2) ], [ (1,2), (1,3) ],
[ (1,2,3), (1,3,2) ], [ (1,2,3), (1,3) ], [ (1,3,2), (1,3) ] ]
gap> Length(m); # всього 15 пар елементів
15
gap> Filtered(m, t -> S=subgroup(S,t)); # відбираємо ті пари, які породжують всю групу
[ [ (2,3), (1,2) ], [ (2,3), (1,2,3) ], [ (2,3), (1,3,2) ], [ (2,3), (1,3) ],
[ (1,2), (1,2,3) ], [ (1,2), (1,3,2) ], [ (1,2), (1,3) ],
[ (1,2,3), (1,3) ], [ (1,3,2), (1,3) ] ]
gap> Length(last); # залишилося тільки 9 пар елементів
9

При розробці функції аналогічного призначення можна організувати подвійний перебір елементів групи для того, щоб більш оптимально витрачати пам'ять і не тримати в ній одночасно весь список всіх неврегульованих пар елементів групи (ще одне спрощення може бути отримане виключенням з розгляду нейтрального елементу групи - зробіть це самостійно). Така функція виглядатиме таким чином:
Findgeneratingpairs:=function(G)
local g, n, i, j, s;
g := Aslist( G );
n := Size( G );
s := [ ];
for i in [ 1 .. n-1 ] do
for j in [ in ] do
if G = Subgroup( G [ g[i], g[j]] ) then
Add(s [ g[i], g[j]]);
fi;
od;
od;
return s;
end;

Протестуємо її і перевіримо, що результат збігається з отриманим раніше:

gap> S:=symmetricgroup(3);
Sym( [ 1 .. 3 ] )
gap> Findgeneratingpairs(S);
[ [ (2,3), (1,2) ], [ (2,3), (1,2,3) ], [ (2,3), (1,3,2) ], [ (2,3), (1,3) ],
[ (1,2), (1,2,3) ], [ (1,2), (1,3,2) ], [ (1,2), (1,3) ],
[ (1,2,3), (1,3) ], [ (1,3,2), (1,3) ] ]

Відмітьте, що будь-яка 2-елементна підмножина групи S3, що не рівна {,} і не містить тотожної підстановки, породжує всю групу S3.

Завдання для лабораторної роботи № 7

Варіант 1.
Розробити функцію для безпосередньої перевірки того, що задана група є комутативною, шляхом перемножування всіляких пар її елементів, що породжують.
Вказівка: використовувати функцію Generatorsofgroups

Варіант 2. Розробити функцію для перевірки того, що знакозмінна група An породжується всілякими циклами довжини 3, і перевірити з її допомогою дане твердження для всіх n, що не перевершують 7.

Варіант 3.
Розробити функцію, яка повертає безліч елементів заданої групи, що мають порядок, рівний заданому числу до.
Вказівка: використовувати функції Aslist, Order

Варіант 4.
Розробити функцію, яка повертає безліч порядків елементів заданої групи.
Вказівка: використовувати функції Aslist, Order, Set

Варіант 5.
Перевірити, чи виконується в групі підстановок S3 тотожність ((x,y),z)=1, де (а,b) = a-1b-1ab