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

При повній інсталяції системи каталог gap4r4/doc також містить документацію і в інших форматах. Зокрема, він містить інші підкаталоги, найменування яких відповідають п'яти основним розділам документація, в якій можна знайти ці розділи у форматі PDF, зручнішому при друці документації (врахуйте, що центральний розділ документації - Reference Manual - займає у форматі PDF 887 сторінок!).

11. Альтернативним варіантом використання документації є підрядкова довідка, яку можна викликати прямо з командного рядка GAP. Це зручно, якщо надалі не передбачається активне переміщення по гіперпосиланнях в документації, а також може бути корисно при видаленому підключенні або у разі, коли ресурси комп'ютера обмежені. Наприклад, наберіть в командному рядку ?Factorial (без крапки з комою) для відображення довідки по даній функції.

Якщо ввести два знаки питання, то проводиться повний пошук по документацію і вовзращаєтся список всіх входжень даного терміну в неї. Наприклад, наберіть ??Sum для виведення списку що всіх мають відношення до запиту розділів, а потім наберіть ?1 для переходу до першого із запропонованих розділів.

12. Зручною властивістю системи є автодоповнення імен змінних при їх введенні. Це означає, що якщо по перших буквах введеного імені змінної (в т. ч. імені функції) можна однозначно визначити його закінчення, то при натисненні клавіші <Tab> це закінчення буде додано автоматично. Якщо ж однозначності немає, то при повторному натисненні клавіші <Tab> буде запропонований список всіх можливих варіантів. Наприклад, наберіть в командній терміні Fib і натисніть <Tab>. Обчислите тепер 100й елемент послідовності Фібоначчі, вказавши 100 в дужках як аргумент. Потім наберіть в командному рядку Factori і натисніть <Tab> двічі для виводу на екран імен всіх змінних, що починаються з цього поєднання букв.

13. Історію роботи з системою можна зберегти в текстовому файлі (т. наз. файлі протоколу). Виберіть одне з вікон GAP, робота в якому Вам здалася зручнішою - вікно MS-DOS або вікно RXVT. Введіть команду
Logto("logfile.txt");

Після цього всі введені Вами команди і результати їх роботи, що відображаються на екрані, дублюватимуться у файлі з ім'ям logfile.txt, який міститься у Вашому робочому каталозі.

Тепер виконаєте наступні обчислення: задайте спочатку змінну n, в якій збережете номер свого варіанту, наприклад:

n:=20;

Потім послідовно введіть наступні команди:
a:=2^(n+1)-1;
Isprime(a);
Factors(a);
x:=n+10;
Factors(Factorial(x));
Phi(x);
Sigma(x);
Tau(x);

Тепер закрийте файл протоколу за допомогою команди
Logto();

і проглянете його за допомогою, наприклад, FAR або Провідника.

Лабораторна робота № 2
Списки. Цілі числа

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

Докладні відомості по даних темах містяться:
- в розділі "Структури даних" <file:///e:\document\alex\web-site\papers\metgap43\3-data. htm> даної методичної допомоги;
- в розділі "Цілі числа, алгоритм Евкліда і розкладання на множники" <file:///e:\document\alex\web-site\examples\integers. htm> учбових матеріалів до курсу алгебри і теорії чисел;
- в розділі "Lists and Records" введення в систему GAP <file:///d:\ Комп'ютерна%20алгебра\metgap43\tppmsgs\msgs0.htm>;
- в розділах "Integers", "Number theory" і "Lists" довідкового керівництва за системою GAP <file:///d:\ Комп'ютерна%20алгебра\metgap43\tppmsgs\msgs0.htm>.

Завдання лабораторної роботи є реальними завданнями з наступного видання: В. У.Грібанов, П. І.Тітов, Збірка вправ по теорії чисел, М., Освіта, 1964 (далі - ГТ), і після номера варіанту вказаний номер відповідного завдання в [ГТ]. Студентам рекомендується ознайомитися з приведеним в [ГТ] вирішенням даних завдань, щоб побачити, що теоретичне їх рішення ефективніше, ніж простий перебір, виконаний ними в учбових цілях в даній лабораторній роботі.

Залежно від конкретного завдання, при виконанні роботи корисними можуть опинитися наступні функції і операції (детальний їх опис див. в документації):Collected(list)Повертає новий список newlist, який для кожного елементу x початкового списку list містить відповідний йому список з двох елементів, перший з яких є самим елементом x, а другою показує кратність його входження в список list, наприклад: gap> Collected([ 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 5, 5, 7 ]); [ [ 2, 8 ], [ 3, 4 ], [ 5, 2 ], [ 7, 1 ] ]

Combinations( list [, до ] )Повертає безліч всіляких комбінацій (неврегульованих наборів без повторень), складених з до елементів списку list (який може навіть містити однакові елементи кілька разів). Якщо до не вказано, повертаються всі можливі комбінації, складені з елементів списку list, наприклад: gap> Combinations( [1,2,2,3] ); [ [ ], [ 1 ], [ 1, 2 ], [ 1, 2, 2 ], [ 1, 2, 2, 3 ], [ 1, 2, 3 ], [ 1, 3 ], [ 2 ], [ 2, 2 ], [ 2, 2, 3 ], [ 2, 3 ], [ 3 ] ]

Divisorsint(n)Повертає список натуральних дільників цілого числа n

Factorsint(n)Повертає розкладання цілого числа n на прості множники у вигляді їх списку

Filtered(list, x -> f(x))Повертає список тих елементів x із списку list, для яких виконується умова f(x)=true

Forall(list, x -> f(x))Перевіряє, що для кожного елементу x із списку list виконується умова f(x)=true

Forany(list, x -> f(x))Перевіряє, що існує хоч би один елемент x із списку list, для якого виконується умова f(x)=true

Gcd(a1, a2 ...) Gcd(list)Обчислює найбільшого загального дільника цілих чисел a1, a2 ... або цілих чисел із списку list

Length(list)Визначає довжину списку list

а mod bа mod b повертає залишок від ділення а на b

Phi(n) Обчислює функцію Ейлера \Phi( n )

Product(list)Обчислює твір всіх елементів списку list

Sum(list)Обчислює суму всіх елементів списку list

Приклад (ГТ 77): Скільки чисел в інтервалі від 1 до 120 ділиться на одне і лише одне з чисел 2, 3 або 5 ?

Спочатку ми отримаємо список цих чисел, а потім визначимо їх кількість:
gap> l := Filtered( [ 1], i ->
> Length( Filtered( [2,3,5], j -> i mod j = 0 ))= 1 );
[ 2, 3, 4, 5, 8, 9, 14, 16, 21, 22, 25, 26, 27, 28, 32, 33, 34, 35, 38, 39, 44, 46, 51, 52,
55, 56, 57, 58, 62, 63, 64, 65, 68, 69, 74, 76, 81, 82, 85, 86, 87, 88, 92, 93, 94, 95, 98,
99, 104, 106, 111, 112, 115, 116, 117, 118 ]
gap> Length(l);
56

Цей же результат можна було б отримати і за допомогою однієї команди:
gap> Length( Filtered( [ 1], i ->
> Length( Filtered( [2,3,5], j -> i mod j = 0 ))= 1 ));
56

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

Варіант 1 (ГТ 65). Знайти показник ступеня числа 3 в канонічному розкладанні числа 100!.

Варіант 2 (ГТ 66). Знайти показник ступеня числа 11 в канонічному розкладанні числа 1000!.
Варіант 3 (ГТ 67). Скількома нулями закінчується число 100! (запропонувати два способи рішення даної задачі, що не зводяться до виводу 100! на екран і ручному підрахунку нулів) ?
Варіант 4 (ГТ 68). Розкласти на прості множники числа 10!, 15!, 20!, 25!, 30!.
Варіант 5 (ГТ 69). Знайти кількість цілих позитивних чисел, що не перевершують 180 і що не діляться ні на одне з простих чисел 5, 7, 11.
Варіант 6 (ГТ 70). Знайти кількість цілих позитивних чисел, що не перевершують 2311 і що не діляться ні на одне з простих чисел 5, 7, 11, 13.
Варіант 7 (ГТ 71). Знайти кількість цілих позитивних чисел, що не перевершують 100 і взаємно простих з 36.
Варіант 8 (ГТ 72). Знайти кількість цілих позитивних чисел, що не перевершують 12317 і взаємно простих з 1575.
Варіант 9 (ГТ 73). Знайти кількість цілих позитивних чисел, що не перевершують 1000 і не взаємно простих з 363.
Варіант 10 (ГТ 74). У ряді натуральних чисел 1 ..., 1800, починаючи з одиниці, викреслюється кожне п'яте, кожне восьме і кожне дев'яте число. Скільки чисел не буде викреслено?
Варіант 11 (ГТ 78). У урні 5000 куль, перенумерованих від 1 до 5000. Яка вірогідність того, що вийнята наугад куля матиме номер, кратний якому-небудь з чисел 14, 21, 10 ?

Варіант 12 (ГТ 84). Знайти всіх дільників чисел 360, 375, 957, 988 (запропонувати два способи рішення, порівняти результати).
Варіант 13 (ГТ 85). Знайти ціле позитивне число, знаючи, що воно має тільки двох простих дільників, число всіх дільників дорівнює 6, а сума всіх дільників дорівнює 28.
Варіант 14 (ГТ 91). Знайти ціле позитивне число, твір всіх дільників якого дорівнює 5832.
Варіант 15 (ГТ 101). Скільки чисел в інтервалі від 1 до 120, не взаємно простих з 30 (запропонувати два способи рішення, порівняти результати)?
Варіант 16 (ГТ 113). Знайти кількість натуральних чисел, менших числа 300 і що мають з ним найбільшим загальним дільником число 20.
Варіант 17 (ГТ 114). Знайти кількість натуральних чисел, менших числа 1665 і що мають з ним найбільшим загальним дільником число 37.
Варіант 18 (ГТ 115). Знайти кількість натуральних чисел, менших числа 1476 і що мають з ним найбільшим загальним дільником число 41.[Попередній розділ <file:///d:\ Комп'ютерна%20алгебра\metgap43\b-funct. htm>][Зміст <file:///d:\ Комп'ютерна%20алгебра\metgap43\metgap43.htm>][Список лабораторних робіт <file:///d:\ Комп'ютерна%20алгебра\metgap43\c-labrab. htm>][Наступний розділ]

Лабораторна робота № 3.
Лінійні програми. Вектори і матриці

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

Докладні відомості по даних темах містяться:
- в розділі "Структури даних" <file:///d:\ Комп'ютерна%20алгебра\metgap43\3-data. htm> даної методичної допомоги (про матриці і вектори);
- в додатку А <file:///d:\ Комп'ютерна%20алгебра\metgap43\a-prog. htm> до даної методичної допомоги (про створення і запуск програм);
- в розділі "Lists and Records" введення в систему GAP <file:///d:\ Комп'ютерна%20алгебра\metgap43\tppmsgs\msgs0.htm>;
- в розділах "Row vectors" і "Matrices" довідкового керівництва за системою GAP <file:///d:\ Комп'ютерна%20алгебра\metgap43\tppmsgs\msgs0.htm>.

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

Для цього створимо в робочому каталозі (створеному відповідно до інструкцій лабораторної роботи №1) файл lab3.g наступного змісту:

Sumdiag:=function(A)
local s;
s := A[1][3]+ A[2][2]+ A[3][1];
return s;
end;

Тепер прочитаємо його за допомогою наступної команди (якщо система GAP запущена з іншого каталога, то потрібно буде вказати повний шлях до файлу):
Read("lab3.g");

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

gap> M:=[[1,2,3],[-1,-2,-3],[1,1,1]];
[ [ 1, 2, 3 ], [ -1, -2, -3 ], [ 1, 1, 1 ] ]
gap> Sumdiag(M);
2

Дану функцію можна було б розробити і більш універсальним чином для роботи з матрицями будь-якого порядку (її доопрацювання для перевірки того, що матриця є квадратною, ми залишаємо читачеві):
Bettersumdiag:=function(A)
local i, nrows, ncols;
nrows := Length( A ); # кількість рядків
ncols := Length( A[1]); # кількість стовпців
return Sum( List( [ 1 .. nrows ], i -> A[i][ncols-i+1]));
end;

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

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

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

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

Варіант 3.
Розробити функцію для обчислення визначника матриці A другого порядку, вхідним параметром якої є матриця A, а вихідним - її визначник, обчислений за формулою det A = a11 a22 - a12 a21.