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

Після введення даної програми задамо випадковим чином бінарне відношення на множині з п'яти елементів:
gap> r:=randombinaryrelationonpoints(5);
Binary Relation on 5 points

Отримаємо його опис за допомогою функції Successors:

gap> Successors(r);
[ [ 1, 2, 4 ], [ 1, 3, 4, 5 ], [ 3, 5 ], [ 2, 4, 5 ], [ 2, 3, 4 ] ]

Тепер обчислимо його матрицю суміжності і переконаємося в правильності отриманого результату, зіставивши номери рядків і стовпців, в яких знаходяться одиниці, з результатом Successors(r):

gap> Display( Matrixofbinaryrelation( r ));
[ [ 1, 1, 0, 1, 0 ],
[ 1, 0, 1, 1, 1 ],
[ 0, 0, 1, 0, 1 ],
[ 0, 1, 0, 1, 1 ],
[ 0, 1, 1, 1, 0 ] ]

Обчислимо матрицю суміжності для мінімального симетричного бінарного відношення, що містить задане, і переконаємося в її симетричності щодо головної діагоналі:
gap> Display( Matrixofbinaryrelation( Symmetricclosurebinaryrelation( r )));
[ [ 1, 1, 0, 1, 0 ],
[ 1, 0, 1, 1, 1 ],
[ 0, 1, 1, 0, 1 ],
[ 1, 1, 0, 1, 1 ],
[ 0, 1, 1, 1, 0 ] ]

Обчислимо матрицю суміжності для мінімального симетричного бінарного відношення, що містить задане, і переконаємося в тому, що всі елементи на її головній діагоналі дорівнюють одиниці:
gap> Display( Matrixofbinaryrelation( Reflexiveclosurebinaryrelation( r )));
[ [ 1, 1, 0, 1, 0 ],
[ 1, 1, 1, 1, 1 ],
[ 0, 0, 1, 0, 1 ],
[ 0, 1, 0, 1, 1 ],
[ 0, 1, 1, 1, 1 ] ]

Тепер перевіримо, що матриця відношення тотожності є одиничною:
gap> Display( Matrixofbinaryrelation( Identitybinaryrelation;
[ [ 1, 0, 0, 0, 0 ],
[ 0, 1, 0, 0, 0 ],
[ 0, 0, 1, 0, 0 ],
[ 0, 0, 0, 1, 0 ],
[ 0, 0, 0, 0, 1 ] ]

Таким чином, розроблена функція працює коректно.
Завдання для лабораторної роботи № 5

Варіант 1.
Розробити функцію, яка для заданого бінарного відношення повертає бінарне відношення, що є його запереченням.

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

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

Варіант 4.
Розробити функцію, яка для двох заданих бінарних стосунків повертає бінарне відношення, що є різницею першого і другого стосунків.

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

Варіант 6.
Розробити функцію, яка для заданого бінарного відношення повертає зворотне до нього бінарне відношення.

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

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

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

Варіант 10.
Розробити функцію, яка для заданого бінарного відношення r повертає список елементів x, для яких виконується умова x r x.

Варіант 11.
Розробити функцію, яка для заданого бінарного відношення r повертає список всіх впорядкованих пар елементів (x, y), для яких одночасно виконуються умови x r у і у r x.

Варіант 12.
Розробити функцію, яка для заданого бінарного відношення r повертає список всіх впорядкованих пар елементів (x,y), таких що яких виконується умова x r у, але не виконується умова у r x.

Варіант 13.
Розробити функцію, яка для заданого бінарного відношення r повертає список всіх впорядкованих пар елементів (x,y), таких що яких виконується умова x r у, і елементи x і у не збігаються.

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

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

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

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

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

Лабораторна робота № 6.
Циклічні програми (цикл WHILE). Підстановки

Дана лабораторна робота призначена для вивчення оператора циклу WHILE на прикладі роботи з підстановками.

Докладні відомості по даних темах містяться:
- в розділі "Мова програмування GAP" <file:///d:\ Комп'ютерна%20алгебра\metgap43\2-lang. htm> даної методичної допомоги (див. п.2.11);
- в розділах "Підстановки в системі GAP" <file:///d:\ Комп'ютерна%20алгебра\metgap43\tppmsgs\msgs0.htm> і "Алгоритм множення підстановок" <file:///d:\ Комп'ютерна%20алгебра\metgap43\tppmsgs\msgs0.htm> учбових матеріалів до курсу алгебри і теорії чисел;
- в розділі "Permutations" довідкового керівництва за системою GAP <file:///d:\ Комп'ютерна%20алгебра\metgap43\tppmsgs\msgs0.htm>.

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

Дане завдання вирішується за допомогою наступної функції:
Orderofpermutation:=function(s)
local до, t;
k:=1;
t:=s;
while t <> () do
t:=t*s;
k:=k+1;
od;
return до;
end;

Ім'я функції Orderofpermutation було вибране так, щоб воно не збігалося з ім'ям наявною в GAP стандартної функції Orderperm - інакше при її введенні було б отримано повідомлення про помилку, оскільки бібліотечні функції захищені від перевизначення користувачем.

Після введення даної програми протестуємо її на різних підстановках:
gap> Orderofpermutation( () );
1
gap> Orderofpermutation( (1,2) );
2
gap> Orderofpermutation( (1,2,3) );
3
gap> Orderofpermutation( (1,2,3)(4,5) );
6

Відмітимо, що порядок підстановки дорівнює найменшому загальному кратному довжин незалежних циклів в її розкладанні (див. останній приклад), і використання цього факту дозволило б ефективніше знайти порядок підстановки, уникнувши її піднесення до ступеня. Тому даний приклад застосовний тільки в учбових цілях. Порівняємо швидкодію нашої функції із стандартною:
gap> for i in [1..1000] do
> k:=orderperm( (1,2,3,4,5)(6,7,8)(9,10)(11,12,13,14,15)(16,17,18) );
> od;
gap> time;
384
gap> for i in [1..1000] do
> k:=orderofpermutation( (1,2,3,4,5)(6,7,8)(9,10)(11,12,13,14,15)(16,17,18) );
> od;
gap> time;
743

Таким чином, ми бачимо, що стандартна функція ефективніша.

Отримаємо за допомогою нашої функції список порядків всіх елементів симетричної групи підстановок третього ступеня:
gap> List( Symmetricgroup(3), Orderofpermutation );
[ 1, 2, 3, 2, 3, 2 ]

Повторимо те ж саме для симетричної групи підстановок п'ятого ступеня, згрупувавши результати:

gap> Collected( List( Symmetricgroup(5), Orderofpermutation ));
[ [ 1, 1 ], [ 2, 25 ], [ 3, 20 ], [ 4, 30 ], [ 5, 24 ], [ 6, 20 ] ]

Таким чином, в ній 25 елементів другого порядку, 20 - третього, 30 - четвертого, 24 - п'ятого, і 20 - шостого порядку.
Завдання для лабораторної роботи № 6

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

Варіант 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, якщо такого числа до не існує.

Лабораторна робота № 7.
Циклічні програми (цикл REPEAT). Групи підстановок

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

Докладні відомості по даних темах містяться:
- в розділі "Мова програмування GAP" <file:///d:\ Комп'ютерна%20алгебра\metgap43\2-lang. htm> даної методичної допомоги (див. п.2.12);
- в розділах "Підстановки в системі GAP" <file:///d:\ Комп'ютерна%20алгебра\metgap43\tppmsgs\msgs0.htm>, "Побудова таблиці множення для кінцевої групи підстановок" <file:///e:\document\alex\web-site\examples\cayley. htm> і "Алгоритм множення підстановок" <file:///d:\ Комп'ютерна%20алгебра\metgap43\tppmsgs\msgs0.htm> учбових матеріалів до курсу алгебри і теорії чисел;
- в розділі "Permutations" і "Permutation groups" довідкового керівництва за системою GAP <file:///d:\ Комп'ютерна%20алгебра\metgap43\tppmsgs\msgs0.htm>.

Приклад: Розробити функцію, яка вибирає випадковим чином елемент заданої групи підстановок, M, що діє на множині = {1...,n}, до тих пір, поки не виявить підстановку, яка переставляє всі точки безлічі M, і повертає знайдену підстановку.

Спочатку потрібно зрозуміти, як визначити порядок безлічі M, і як зрозуміти, що задана підстановка не має нерухомих крапок. Для цього поекспериментуємо в діалоговому режимі з деякими функціями з розділу "Підстановки в системі GAP" <file:///e:\document\alex\web-site\examples\permutat. htm>:

gap> G:=symmetricgroup(3);
Sym( [ 1 .. 3 ] )
gap> Largestmovedpoint(G);
3
gap> s:=(1,2);
(1,2)
gap> Nrmovedpoints(s);
2
gap> t:=(1,2,3);
(1,2,3)
gap> Nrmovedpoints(t);
3

Тепер завдання стало яснішим, і можна розробити наступну функцію: