Перша сесія з GAP

Приблизний час: 40 хвилин

Огляд

Питання

• Робота з командним рядком GAP

Цілі

• Поради та підказки, які заощадять час
• Використання довідкової системи GAP
• Базові об’єкти та конструкції в мові GAP

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

ВИХІД

 ┌───────┐   GAP 4.9.2 of 04-Jul-2018
 │  GAP  │   https://www.gap-system.org
 └───────┘   Architecture: x86_64-apple-darwin16.7.0-default64
 Configuration:  gmp 6.1.2, readline
 Loading the library and packages ...
 Packages:   AClib 1.3, Alnuth 3.1.0, AtlasRep 1.5.1, AutPGrp 1.9,
             Browse 1.8.8, CRISP 1.4.4, Cryst 4.1.17, CrystCat 1.1.8,
             CTblLib 1.2.2, FactInt 1.6.2, FGA 1.4.0, GAPDoc 1.6.1, IO 4.5.1,
             IRREDSOL 1.4, LAGUNA 3.9.0, Polenta 1.3.8, Polycyclic 2.14,
             PrimGrp 3.3.1, RadiRoot 2.8, ResClasses 4.7.1, SmallGrp 1.3,
             Sophus 1.24, SpinSym 1.5, TomLib 1.2.6, TransGrp 2.0.2,
             utils 0.54
 Try '??help' for help. See also '?copyright', '?cite' and '?authors'
gap>

Щоб вийти з GAP, введіть quit; у командному рядку GAP. Пам’ятайте, що всі команди GAP, включно з цією, мають закінчуватися крапкою з комою! Потренуйтеся вводити quit;, щоб вийти з GAP, а потім почати новий сеанс GAP. Перш ніж продовжити, ви можливо забажаєте ввести наступну команду, щоб відображати запрошення GAP та команди, введені користувачем у різних кольорах:

GAP

 ColorPrompt(true);

Найпростіший шлях розпочати роботу з GAP - це використовувати GAP як калькулятор:

GAP

( 1 + 2^32 ) / (1 - 2*3*107 );

ВИХІД

-6700417

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

GAP

LogTo("gap-intro.log");

Це створить у поточному каталозі файл gap-intro.log, який містить всі подальші вхідні та вихідні дані, які з’являтимуться у вашому терміналі. Щоб припинити ведення журналу, ви можете викликати LogTo без аргументів, тобто LogTo();, або вийти з GAP. Зауважте, що LogTo очищає файл перед запуском, якщо він уже існує!

Може бути корисним залишити кілька коментарів у файлі журналу на випадок, якщо ви повернетеся до нього в майбутньому. Коментар у GAP починається з символу # та продовжується до кінця рядка. Ви можете ввести наступне після запрошення GAP:

GAP

# Урок з GAP у форматі Software Carpentry

Тоді після натискання клавіші Return GAP відобразить нове запрошення, але коментар буде записано до файлу журналу.

Файл журналу записує всю взаємодію з GAP, яка відбувається після виклику LogTo, але не раніше. Ми можемо повторити наші обчислення вище, якщо також хочемо їх записати. Замість того, щоб вводити їх повторно, ми будемо використовувати клавіші зі стрілками вгору та вниз для перегляду історії командного рядка. Натискайте ці клавіші, щоб побачити попередні команди. Коли побачите потрібну формулу, натисніть Return (розташування курсору в командному рядку не має значення):

GAP

( 1 + 2^32 ) / (1 - 2*3*107 );

ВИХІД

-6700417

Ви також можете редагувати команди, які були використані раніше. Натисніть клавішу зі стрілкою вгору ще раз, а потім використовуйте клавіші зі стрілками вліво та вправо, Delete або Backspace, щоб відредагувати цю команду та замінити 32 на 64. Іншими корисними комбінаціями клавіш є Ctrl-A та Ctrl-E, які переміщують курсор на початок і кінець рядку, відповідно. Тепер натисніть клавішу Return (у будь-якій позиції курсору в командному рядку):

GAP

( 1 + 2^64 ) / (1 - 2*3*107 );

ВИХІД

-18446744073709551617/641

Якщо історія командного рядка велика, можна виконати частковий пошук, ввівши початкову частину команди, а потім використовуючи клавіші зі стрілками вгору та вниз, переглянути лише ті рядки, які починаються з введених символів.

Якщо ви бажаєте зберегти значення для подальшого використання, цьому значенню можна присвоїти ім’я за допомогою :=

GAP

universe := 6*7;

Виноска

Оператори :=, = та <>

• В інших мовах ви можете частіше зустріти використання = для присвоєння значення змінним, але GAP для цього використовує :=.

• GAP використовує = для перевірки, чи два об’єкти дорівнюють один одному (інші мови можуть використовувати для цього ==).

• Нарешті, GAP використовує <>, щоб перевірити, що два об’єкти не рівні (замість оператора !=, який ви могли бачити в інших мовах програмування).

Недруковані символи (наприклад, пробіли, табуляції та символи переводу рядка) не мають значення в GAP, за винятком випадків, коли вони знаходяться всередині рядка. Наприклад, попередню команду можна ввести без пробілів:

GAP

(1+2^64)/(1-2*3*107);

ВИХІД

-18446744073709551617/641

Пробіли часто використовуються для форматування більш складних команд для кращої читабельності. Наприклад, наступна команда створює матрицю 3×3:

GAP

m:=[[1,2,3],[4,5,6],[7,8,9]];

ВИХІД

[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]

Замість цього ми можемо записати нашу матрицю в 3 рядки. У цьому випадку замість повного запрошення gap> відображатиметься часткове запрошення >, доки користувач не завершить введення крапкою з комою:

GAP

gap> m:=[[ 1, 2, 3 ],
>        [ 4, 5, 6 ],
>        [ 7, 8, 9 ]];

ВИХІД

[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]

Ви можете використовувати Display для відформатованого друку змінних, включаючи цю матрицю:

GAP

Display(m);

ВИХІД

[ [  1,  2,  3 ],
  [  4,  5,  6 ],
  [  7,  8,  9 ] ]

Загалом функції GAP, як наприклад LogTo і Display, викликаються за допомогою дужок, які містять (можливо, порожній) список аргументів.

Виноска

Функції - це також об’єкти у GAP

Перевірте, що станеться, якщо ви забудете додати дужки, наприклад, надрукуєте LogTo; або Factorial;. Пізніше ми пояснимо відмінності в цих результатах.

Нижче наведені декілька прикладів виклику інших функцій GAP:

GAP

Factorial(100);

ВИХІД

93326215443944152681699238856266700490715968264381621468\
59296389521759999322991560894146397615651828625369792082\
7223758251185210916864000000000000000000000000

(точна ширина виводу залежатиме від налаштувань вашого терміналу),

GAP

Determinant(m);

ВИХІД

0

та

GAP

Factors(2^64-1);

ВИХІД

[ 3, 5, 17, 257, 641, 65537, 6700417 ]

Функції можна комбінувати різними способами та використовувати як аргументи інших функцій. Наприклад, функція Filtered сприймає список і функцію, повертаючи всі елементи списку, які задовольняють цю функцію. Наприклад, функція IsEvenInt (“Is Even Integer” з англ. “чи є ціле число парним”) перевіряє, чи є ціле число парним:

GAP

Filtered( [2,9,6,3,4,5], IsEvenInt);

ВИХІД

[ 2, 6, 4 ]

Корисною функцією інтерфейсу командного рядка GAP, яка економить час, є автодоповнення ідентифікаторів під час натискання клавіші Tab. Наприклад, введіть Fib, а потім натисніть клавішу Tab, щоб завершити введений текст до Fibonacci:

GAP

Fibonacci(100);

ВИХІД

354224848179261915075

У випадку, якщо унікальне доповнення неможливе, GAP спробує виконати часткове доповнення, а натискання клавіші Tab вдруге відобразить усі можливі доповнення ідентифікатора. Спробуйте, наприклад, ввести GroupHomomorphismByImages або NaturalHomomorphismByNormalSubgroup за допомогою автодоповнення.

Сподіваємось, те, як функції називаються в GAP, допоможе вам запам’ятовувати або навіть вгадувати назви бібліотечних функцій. Якщо назва змінної складається з кількох слів, то перша літера кожного слова пишеться з великої літери (пам’ятайте, що GAP чутливий до регістру!). Подальші відомості про правила іменування, які використовуються в GAP, задокументовані в документації GAP тут. Функції з назвами У_ВЕРХНЬОМУ_РЕГІСТРІ є внутрішніми функціями, не призначеними для загального використання. Використовуйте їх з особливою обережністю!

Важливо пам’ятати, що GAP чутливий до регістру. Наприклад, наступне введення викликає помилку:

GAP

factorial(100);

ПОМИЛКА

Error, Variable: 'factorial' must have a value
not in any function at line 14 of *stdin*

тому що назва цієї функції GAP – Factorial. Використання малих літер замість великих або навпаки також впливає на автодоповнення назви.

Тепер розглянемо таку задачу: для скінченної групи G обчислити середній порядок її елементів (тобто суму порядків її елементів, поділену на порядок групи). З чого почати?

Введіть ?Group, щоб побачити всі записи довідкової системи, що починаються із Group:

ВИХІД

┌──────────────────────────────────────────────────────────────────────────────┐
│   Choose an entry to view, 'q' for none (or use ?<nr> later):                │
│[1]    AutoDoc (not loaded): @Group                                           │
│[2]    loops (not loaded): group                                              │
│[3]    polycyclic: Group                                                      │
│[4]    RCWA (not loaded): Group                                               │
│[5]    Tutorial: Groups and Homomorphisms                                     │
│[6]    Tutorial: Group Homomorphisms by Images                                │
│[7]    Tutorial: group general mapping                                        │
│[8]    Tutorial: GroupHomomorphismByImages vs. GroupGeneralMappingByImages    │
│[9]    Tutorial: group general mapping single-valued                          │
│[10]   Tutorial: group general mapping total                                  │
│[11]   Reference: Groups                                                      │
│[12]   Reference: Group Elements                                              │
│[13]   Reference: Group Properties                                            │
│[14]   Reference: Group Homomorphisms                                         │
│[15]   Reference: GroupHomomorphismByFunction                                 │
│[16]   Reference: Group Automorphisms                                         │
│[17]   Reference: Groups of Automorphisms                                     │
│[18]   Reference: Group Actions                                               │
│[19]   Reference: Group Products                                              │
│[20]   Reference: Group Libraries                                             │
│ > > >                                                                        │
└─────────────── [ <Up>/<Down> select, <Return> show, q quit ] ────────────────┘

Можна використовувати клавіші зі стрілками для переміщення вгору та вниз по списку, а також відкривати сторінки довідки, натискаючи клавішу Return. Для цієї вправи спочатку відкрийте Tutorial: Groups and Homomorphisms. Зверніть увагу на навігаційні інструкції внизу екрана. Перегляньте перші дві сторінки, потім натисніть q, щоб повернутися до меню вибору. Далі перейдіть до елементу Reference: Groups і відкрийте його. На перших двох сторінках ви знайдете функцію Group та згадку про функцію Order.

Документація GAP доступна у кількох форматах: текстовий формат зручний для перегляду в терміналі, PDF зручний для друку, а HTML (особливо з підтримкою MathJax) дуже ефективний для перегляду за допомогою браузера. Якщо ви використовуєте GAP на власному комп’ютері, ви можете налаштувати GAP так, щоб він відкривав довідку за допомогою вашого браузера за замовчуванням (це навряд чи спрацює, якщо використовується віддалене підключення). Дивіться ?WriteGapIniFile про те, як зробити це налаштування постійним:

GAP

SetHelpViewer("browser");

Після цього викличте довідку знову та побачите різницю!

Давайте тепер скопіюємо наступні вхідні дані з першого прикладу з глави про групи у довідковому посібнику GAP. У ньому показано, як створювати перестановки та присвоювати значення змінним. Це Reference: Groups. Ви можете вибрати його, ввівши ?11, де ви заміните 11 на те значення, яке з’явиться перед Reference: Groups на вашому комп’ютері.

Якщо ви переглядаєте документацію GAP у терміналі, вам може бути корисно відкрити дві копії GAP, одну для читання документації та одну для написання коду!

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

GAP

a:=(1,2,3);;b:=(2,3,4);;

Далі, нехай G - група, утворена за допомогою a та b:

GAP

G:=Group(a,b);

ВИХІД

Group([ (1,2,3), (2,3,4) ])

Ми можемо дослідити деякі властивості групи G та її твірних:

GAP

Size(G); IsAbelian(G); StructureDescription(G); Order(a);

ВИХІД

12
false
"A4"
3

Нашою наступною метою є дізнатися, як отримати список елементів G та їх порядок. Введіть ?elements і перегляньте список тем довідки. Після перевірки, інформація з GAP Tutorial не здається корисною, але вміст розділу у довідковому посібнику (Reference) є актуальним. В цьому розділі також пояснюється різниця між використанням AsSSortedList та AsList. Отже, маємо список елементів G:

GAP

AsList(G);

ВИХІД

[ (), (2,3,4), (2,4,3), (1,2)(3,4), (1,2,3), (1,2,4), (1,3,2), (1,3,4),
  (1,3)(2,4), (1,4,2), (1,4,3), (1,4)(2,3) ]

Повернений об’єкт є списком. Ми хотіли б призначити його змінній для дослідження та повторного використання. Ми забули це зробити, коли створювали цей список перший раз. Звичайно, ми можемо використати історію командного рядка, щоб відновити останню команду, відредагувати її та викликати знову. Але замість цього будемо використовувати спеціальну змінну last, яка містить останній результат, що повернув GAP:

GAP

elts:=last;

ВИХІД

[ (), (2,3,4), (2,4,3), (1,2)(3,4), (1,2,3), (1,2,4), (1,3,2), (1,3,4),
  (1,3)(2,4), (1,4,2), (1,4,3), (1,4)(2,3) ]

Отриманий результат є списком. Списки в GAP індексуються від 1, на відміну від, наприклад, мови Python. Наступні команди (сподіваємося!) не потребують пояснень:

GAP

gap> elts[1]; elts[3]; Length(elts);

ВИХІД

()
(2,4,3)
12

Виноска

Списки — це більше, ніж масиви

• Можуть містити дірки (тобто відсутніх елементів у середині списку) або бути порожніми.

• Можуть динамічно змінювати свою довжину за допомогою, наприклад, Add, Append або прямого призначення.

• Не обов’язково містять об’єкти одного типу.

• Дивіться більше в документації GAP Tutorial: Lists and Records.

Багато функцій у GAP посилаються на множини. Множина у GAP — це список, який не має повторень та дірок, і у якому елементи розташовані у порядку зростання. Ось кілька прикладів:

GAP

gap> IsSet([1,3,5]); IsSet([1,5,3]); IsSet([1,3,3]);

ВИХІД

true
false
false

Розглянемо цікаве обчислення: знаходження середнього порядку елементів групи G. Існує багато різних способів це зробити. Наведемо тут деякі з них.

Цикл for у GAP дозволяє виконати певну дію із кожним елементом колекції (наприклад, списку, множини, групи тощо). Загальна форма циклу for така:

GAP

for val in collection do
  <something with val>
od;

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

GAP

s:=0;;
for g in elts do
  s := s + Order(g);
od;
s/Length(elts);

ВИХІД

31/12

Насправді, ми можемо просто перебирати елементи групи G (загалом GAP дозволяє перебирати елементи більшості типів об’єктів). Нам потрібно використовувати Size замість Length, оскільки групи не мають довжини!

GAP

s:=0;;
for g in G do
  s := s + Order(g);
od;
s/Size(G);

ВИХІД

31/12

Існують також інші способи організації циклів. Наприклад, можемо перебирати цілі числа із відповідного діапазону та розглядати elts як список, який проіндексовано цими числами:

GAP

s:=0;;
for i in [ 1 .. Length(elts) ] do
  s := s + Order( elts[i] );
od;
s/Length(elts);

ВИХІД

31/12

Однак часто існують більш компактні способи виконання тієї ж самої операції. Наведемо коротший шлях отримання цього результату:

GAP

Sum( List( elts, Order ) ) / Length( elts );

ВИХІД

31/12

Далі, розберемо останню частину:

• Order знаходить порядок однієї перестановки;
• List(L,F) створює новий список, де функція F застосовується до кожного елемента списку L;
• Sum(L) знаходить суму усіх елементів списку L.

Виноска

Який підхід найкращий?

Порівняйте ці підходи. Якому із них ви віддасте перевагу?

GAP має дуже корисний інструментарій для роботи зі списками. Наведемо ще кілька прикладів.

Іноді GAP не має саме тієї функції, яка нам потрібна. Наприклад, NrMovedPoints повертає кількість точок, які пересуває перестановка. Що робити, якщо ми хочемо знайти всі перестановки, які пересувають 4 точки? Тоді є корисним позначення “стрілка”. Вираз g -> e створює нову функцію, яка отримує один аргумент g і повертає значення виразу e. Ось деякі приклади:

• знаходження всіх елементів G, які не мають фіксованих точок:

GAP

Filtered( elts, g -> NrMovedPoints(g) = 4 );

ВИХІД

[ (1,2)(3,4), (1,3)(2,4), (1,4)(2,3) ]

• пошук перестановки в групі G, яка переводить перестановку (1,2) в (2,3) за допомогою спряження.

GAP

First( elts, g -> (1,2)^g = (2,3) );

ВИХІД

(1,2,3)

Давайте перевіримо це (пам’ятайте, що в GAP перестановки перемножуються зліва направо!):

GAP

(1,2,3)^-1*(1,2)*(1,2,3)=(2,3);

ВИХІД

true

• перевірка, чи всі елементи G пересувають точку 1 у 2:

GAP

ForAll( elts, g -> 1^g <> 2 );

ВИХІД

false

• перевірка того, чи є елемент у групі G, який переміщує точно дві точки:

GAP

ForAny( elts, g -> NrMovedPoints(g) = 2 );

ВИХІД

false

Обговорення

Використайте операції зі списком, щоб вибрати з elts стабілізатор точки 2 та централізатор перестановки (1,2)

• Filtered( elts, g -> 2^g = 2 );

• Filtered( elts, g -> (1,2)^g = (1,2) );

Ключові моменти

• Пам’ятайте, що GAP чутливий до регістру!
• Не панікуйте, якщо побачите Error, Variable: 'FuncName' must have a value.
• Звертайте увагу на те, які імена ви даєте змінним та функціям.
• Використовуйте редагування командного рядка.
• Використовуйте автодоповнення замість повного введення імен функцій і змінних вручну.
• Використовуйте ? та ??, щоб переглянути сторінки довідки.
• Встановіть HTML формат довідки за замовчуванням за допомогою SetHelpViewer.
• Використовуйте функцію LogTo, щоб зберігати у текстовий файл всі вхідні та вихідні дані, які зʼявляються на екрані під час роботи з GAP.
• Якщо обчислення триває занадто довго, натисніть -C, щоб перервати його.
• Прочитайте розділ “A First Session with GAP”, який міститься у GAP Tutorial.