- •Р.М.Літнарович, ю.Г.Лотюк комп’ютерна алгебра навчально-методичний посібник
- •© Літнарович р.М., Лотюк ю.Г.,2010 р.
- •1. Програма нормативної дисципліни
- •2. Мета та завдання дисципліни,
- •3. Формування практичних навичків
- •4. Зміст дисципліни
- •4.1.Лекції, найменування тем за їх змістом
- •6.Перелік питань до заліку
- •7.Науково-дослідна робота студентів
- •8. Літературні джерела
- •9.Розподіл балів за один змістовий модуль, присвоюваних студентам
- •10.Шкала оцінювання:
- •11.Зміни та доповнення ,внесені в робочу програму на 201__ рік
- •12.Оцінка навчальної діяльності студента
- •2. Лекційний курс Лекція 1. (2 год.)
- •1.1 Коротка характеристика gap
- •1.2 Можливості для роботи з різними видами об'єктів алгебри
- •1.3 Приклади простих обчислень
- •2 Мова програмування gap
- •2.1 Символи і категорії слів в gap
- •2.2 Ключові слова
- •2.3 Ідентифікатори
- •2.4 Вирази
- •2.5 Звернення до функцій
- •2.6 Порівняння виразів
- •2.7 Арифметичні оператори
- •2.8 Привласнення
- •2.9 Виклик процедури
- •2.10 Команда if
- •2.11 Цикл while
- •2.12 Цикл repeat
- •2.13 Цикл for
- •2.14 Функції
- •3 Структури даних
- •3.1 Константи і оператори
- •3.2 Змінні і привласнення
- •3.3 Функції
- •3.4 Списки
- •3.5 Тотожність і рівність списків
- •3.6 Множини
- •3.7 Вектори і матриці
- •3.8 Записи
- •3.9 Арифметичні прогресії
- •3.10 Використання циклів
- •3.11 Подальші операції із списками
- •3.12 Функції
- •4 Операції над групами і їх елементами
- •4.1 Завдання групи підстановок
- •4.2 Завдання підгрупи групи підстановок
- •4.3 Прості властивості групи. Силовськие підгрупи.
- •4.4 Інші види підгруп
- •4.5 Факторгруппи
- •Список літератури, що рекомендується
- •Додаток а Рекомендації по створенню і запуску програм в системі gap
- •1. Створюємо за допомогою текстового редактора файл "prog.G" наступного змісту:
- •2. Зберігаємо цей файл в каталозі, вибраному з урахуванням рекомендацій параграфа 1.2.
- •3. Запустимо gap і визначимо файл протоколу log.Txt:
- •Лабораторна робота № 1. Основи роботи з системою gap в Windows
- •Лабораторна робота № 2 Списки. Цілі числа
- •Завдання для лабораторної роботи № 2
- •Лабораторна робота № 3. Лінійні програми. Вектори і матриці
- •Завдання для лабораторної роботи № 3
- •Лабораторна робота № 4. Програми, що гілкуються. Многочлени
- •Лабораторна робота № 5. Циклічні програми (цикл for). Бінарні відносини
- •Лабораторна робота № 6. Циклічні програми (цикл while). Підстановки
- •Лабораторна робота № 7. Циклічні програми (цикл repeat). Групи підстановок
- •Завдання для лабораторної роботи № 7
- •Лабораторна робота № 8. Вивчення властивостей елементів групи
- •Завдання для лабораторної роботи № 7
- •Лабораторна робота № 9. Вивчення властивостей підгруп групи.
- •Завдання для лабораторної роботи № 9.
- •Лабораторна робота № 10. Робота з бібліотекою кінцевих груп
- •Додаткові завдання
- •33027 Рівне , Україна
Лабораторна робота № 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 Тепер завдання стало яснішим, і можна розробити наступну функцію:
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); 265252859812191058636308480000000 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 останній варіант нашої функції і звернетеся до неї кілька разів для якої-небудь досить великої групи. Подивитеся, скільки кроків в середньому потрібно для знаходження потрібної підстановки.