Лабораторна робота № 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);3gap> s:=(1,2);(1,2)gap> Nrmovedpoints(s);2gap> t:=(1,2,3);(1,2,3)gap> Nrmovedpoints(t);3Тепер завдання стало яснішим, і можна розробити наступну функцію:

 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 .. 30 ] )gap> Size(G);265252859812191058636308480000000gap> 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 комутує з підстановкою ( 1 2 ).

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

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

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

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

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

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

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

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

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