- •Р.М.Літнарович, ю.Г.Лотюк комп’ютерна алгебра навчально-методичний посібник
- •© Літнарович р.М., Лотюк ю.Г.,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 Рівне , Україна
Лабораторна робота № 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 комутує з підстановкою ( 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, якщо такого числа до не існує.