Все на одній сторінці

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

Останнє оновлення 2026-05-06 | Редагувати цю сторінку

Приблизний час: 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.

Content from Ще декілька типів об’єктів GAP

Останнє оновлення 2026-05-06 | Редагувати цю сторінку

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

Огляд

Питання

  • Подальші приклади об’єктів і операцій з ними

Цілі

  • Ознайомитися із деякими типами обʼєктів, які є в GAP, але можуть бути відсутні в інших системах
  • Розглянути більше прикладів роботи зі списками

Наразі ми познайомилися з трьома типами обʼєктів у GAP:

  • простими об’єктами (наприклад, цілі числа, раціональні числа, булеві значення, перестановки тощо);

  • складеними об’єктами (наприклад списки);

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

У цьому розділі ми продемонструємо деякі інші приклади базових об’єктів, які існують у GAP. Більш того, у GAP можна самостійно вводити нові типи об’єктів, але це виходить за рамки цього уроку.

Ще декілька типів простих об’єктів у GAP - це числа з плаваючою комою, циклотомічні числа та елементи скінченних полів:

GAP 

1.15; Float(1232/3456567);

ВИХІД 

1.15
0.000356423

GAP 

E(4); E(4)^2; E(6);

ВИХІД 

E(4)
-1
-E(3)^2

GAP 

AsList(GF(2)); Z(5); Z(5)^4;

ВИХІД 

[ 0*Z(2), Z(2)^0 ]
Z(5)
Z(5)^0

Ви вже знаєте про списки. Іншим типом складених об’єктів є записи. У той час як список містить підоб’єкти, проіндексовані за їх позиціями в списку, запис містить підоб’єкти, які називаються компонентами запису та індексуються за своїми іменами. Елементи запису доступні за допомогою символу . (крапка).

GAP 

date:= rec(year:= 2015, month:= "Nov", day:= 17);

ВИХІД 

rec( day := 17, month := "Nov", year := 2015 )

GAP 

date.year;

ВИХІД 

2015

GAP 

date.time:= rec(hour:= 14, minute:= 55, second:= 12);

ВИХІД 

rec( hour := 14, minute := 55, second := 12 )

GAP 

date;

ВИХІД 

rec( day := 17, month := "Nov",
  time := rec( hour := 14, minute := 55, second := 12 ), year := 2015 )

GAP 

RecNames(date);

ВИХІД 

[ "time", "year", "month", "day" ]

Далі, GAP має рядки та символи. Хоча GAP друкує рядки спеціальним чином, насправді рядок — це лише список символів, і будь-яка функція, яка приймає список, також прийматиме рядок. Навпаки, символи є такими ж простими об’єктами, як, наприклад, цілі числа.

GAP 

gap> w:="supercalifragilisticexpialidocious"; Length(w);

ВИХІД 

"supercalifragilisticexpialidocious"
34

Рядки позначаються подвійними лапками, а символи одинарними.

GAP 

gap> "s" in w; 's' in w; IsSubset(w,"s");  IsSubset(w,['s','f']); ['c','a','t'] = "cat";

ВИХІД 

false
true
true
true
true

Зауважте, що

GAP 

gap> PositionSublist(w,"sf"); PositionSublist(w,"fr");

ВИХІД 

fail
10

Будьте обережні! Деякі операції можуть створити новий список, тоді як інші є деструктивними. Наприклад:

GAP 

gap> SortedList(w); w;

ВИХІД 

"aaacccdeefgiiiiiiillloopprrssstuux"
"supercalifragilisticexpialidocious"

але

GAP 

gap> Sort(w); w;

ВИХІД 

"aaacccdeefgiiiiiiillloopprrssstuux"

Яка літера зустрічається у “supercalifragilisticexpialidocious” найчастіше?

GAP 

gap> c := Collected(w);

ВИХІД 

[ [ 'a', 3 ], [ 'c', 3 ], [ 'd', 1 ], [ 'e', 2 ], [ 'f', 1 ], [ 'g', 1 ],
  [ 'i', 7 ], [ 'l', 3 ], [ 'o', 2 ], [ 'p', 2 ], [ 'r', 2 ], [ 's', 3 ],
  [ 't', 1 ], [ 'u', 2 ], [ 'x', 1 ] ]

GAP 

gap> k := Maximum( List( c, v -> v[2] ) ); Filtered( c, v -> v[2] = 7 );

ВИХІД 

7
[ [ 'i', 7 ] ]
Обговорення

Пошук букв, які найчастіше зустрічаються у списку, за допомогою лише одного повного перебору

Команда

k := Maximum( List( c, v -> v[2] ) ); Filtered( c, v -> v[2] = 7 );

двічі перебирає список c (спочатку у List, а потім у Filtered), а також перебирає інший список такої ж довжини, що й список c під час виклику Maximum. Якщо список довгий, це може зайняти більше часу та потребує більше пам’яті. Спробуйте написати код, який знаходить літери, які найчастіше зустрічаються в рядку c, не створюючи проміжного списку.

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

Content from Функції в GAP

Останнє оновлення 2026-05-16 | Редагувати цю сторінку

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

Огляд

Питання

  • Функції як спосіб повторного використання коду

Цілі

  • Використання командного рядка для прототипування
  • Створення функцій
  • Читання GAP-коду з файлу

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

Ми почнемо з дуже прямого підходу, перебираючи всі елементи групи, з якою ми працюємо:

GAP 

S:=SymmetricGroup(10);

ВИХІД 

Sym( [ 1 .. 10 ] )

GAP 

sum:=0;

ВИХІД 

0

GAP 

for g in S do
  sum := sum + Order(g);
od;
sum/Size(S);

ВИХІД 

39020911/3628800

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

GAP 

sum:=0;; for g in S do sum := sum + Order(g); od; sum/Size(S);

ВИХІД 

39020911/3628800

Тепер ми можемо легко скопіювати та вставити його в командний рядок GAP наступного разу, коли він нам знадобиться. Але тут ми бачимо першу незручність: код очікує, що група, про яку йде мова, має бути збережена в змінній з іменем S, тому або ми повинні визначати S знов кожного разу, або редагувати код, змінюючи імʼя групи:

GAP 

S:=AlternatingGroup(10);

ВИХІД 

Alt( [ 1 .. 10 ] )

GAP 

sum:=0;; for g in S do sum := sum + Order(g); od; sum/Size(S);

ВИХІД 

2587393/259200
Виноска

Це працює лише для швидкого прототипування

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

Ось чому нам потрібно надати нашому коду GAP більше структури, організувавши його у функції:

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

Наступна функція приймає аргумент G і обчислює середній порядок елементів з G:

GAP 

AvgOrdOfGroup := function(G)
local sum, g;
sum := 0;
for g in G do
  sum := sum + Order(g);
od;
return sum/Size(G);
end;

ВИХІД 

function( G ) ... end

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

GAP 

A:=AlternatingGroup(10); AvgOrdOfGroup(A); time;

ВИХІД 

Alt( [ 1 .. 10 ] )
2587393/259200
837

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

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

Використовуючи текстовий редактор (наприклад, той, з яким ви, можливо, працювали на попередніх уроках Software Carpentry), створіть текстовий файл під назвою avgord.g, що містить наступний код функції та коментарі (хороший шанс звернути увагу на на коментування коду):

GAP 

#####################################################################
#
# AvgOrdOfGroup(G)
#
# Calculating the average order of an element of G, where G meant to
# be a group but in fact may be any collection of objects having
# multiplicative order
#
AvgOrdOfGroup := function(G)
local sum, g;
sum := 0;
for g in G do
  sum := sum + Order(g);
od;
return sum/Size(G);
end;

Тепер почніть новий сеанс роботи з GAP і створіть іншу групу, наприклад, MathieuGroup(11):

GAP 

M11:=MathieuGroup(11);

ВИХІД 

Group([ (1,2,3,4,5,6,7,8,9,10,11), (3,7,11,8)(4,10,5,6) ])

Очевидно, що функція AvgOrdOfGroup не визначена в цьому сеансі, тому спроба викликати її призводить до помилки:

GAP 

AvgOrdOfGroup(M11);

ПОМИЛКА 

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

Щоб ця функція була доступною, її потрібно спочатку завантажити за допомогою функції Read. Нижче ми припускаємо, що файл avgord.g знаходиться в поточному каталозі, тому шлях до нього не потрібен.

GAP 

Read("avgord.g");

Це завантажує у GAP код з файлу, і тепер функція AvgOrdOfGroup вже доступна:

GAP 

AvgOrdOfGroup(M11);

ВИХІД 

53131/7920

У цьому приклад використання Read було розпочато новий сеанс GAP для того, щоб було зрозуміло, що функція AvgOrdOfGroup не існувала до виклику Read і була завантажена з файлу. Однак файл із такою функцією можна прочитати кілька разів під час одного сеансу GAP (пізніше ви побачите випадки, коли повторне читання файлу є складнішим). Повторний виклик Read виконує весь код у файлі, що зчитується. Це означає, що якщо код функції було змінено і в ньому немає помилок (але, можливо, є попередження), функція буде перезаписана. Ніколи не ігноруйте попередження!

Наприклад, давайте відредагуємо файл і замінимо рядок

GAP 

return sum/Size(G);

рядком із навмисною синтаксичною помилкою:

GAP 

return Float(sum/Size(G);

Тепер прочитайте цей файл

GAP 

Read("avgord.g");

та зверніть увагу на повідомлення про помилку:

ПОМИЛКА 

Syntax error: ) expected in avgord.g line 7
return Float(sum/Size(G);
                        ^

Оскільки сталася помилка, функція AvgOrdOfGroup у нашому сеансі не була перевизначена та залишається такою ж, як і минулого разу, коли вона була успішно прочитана:

GAP 

Print(AvgOrdOfGroup);

ВИХІД 

function ( G )
    for g  in G  do
        sum := sum + Order( g );
    od;
    return sum / Size( G );
end

Тепер виправте помилку, додавши відсутню закриваючу дужку, прочитайте файл ще раз і обчисліть знов середній порядок елемента для M11:

GAP 

Read("avgord.g");
AvgOrdOfGroup(M11);

ВИХІД 

6.70846

Тепер давайте розглянемо приклад попередження. Оскільки це лише попередження, читання коду призведе до перевизначення функції, і це може призвести до несподіваного результату. Щоб побачити, що може статися, спочатку відредагуйте файл, щоб відкотити зміни в типі результату (тобто щоб повертати раціональне значення замість числа з плаваючою комою), а потім закоментуйте два рядки наступним чином:

GAP 

AvgOrdOfGroup := function(G)
# local sum, g;
# sum := 0;
for g in G do
  sum := sum + Order(g);
od;
return sum/Size(G);
end;

Тепер, коли ви прочитаєте файл, ви побачите попередження:

GAP 

Read("avgord.g");

ПОМИЛКА 

Syntax error: warning: unbound global variable in avgord.g line 4
for g in G do
       ^
Syntax error: warning: unbound global variable in avgord.g line 5
  sum := sum + Order(g);
       ^
Syntax error: warning: unbound global variable in avgord.g line 5
  sum := sum + Order(g);
             ^
Syntax error: warning: unbound global variable in avgord.g line 7
return sum/Size(G);
          ^

Ці попередження означають, що оскільки g та sum не оголошено як local (локальні) змінні, GAP очікує, що вони будуть глобальними змінними під час виклику функції. Оскільки вони не існували під час виклику Read, було видано попередження. Однак, якби вони вже існували на цей момент, то попередження не було б, і будь-який виклик AvgOrdOfGroup перезаписав би їх! Це показує, наскільки важливим є оголошення локальних змінних. Давайте розберемося трохи детальніше, що сталося:

Функцію тепер перевизначено (як ми бачимо з її виводу, або можемо перевірити за допомогою PageSource(AvgOrdOfGroup), що також відображатиме будь-які коментарі, якщо вони присутні у коді функції у файлі):

GAP 

Print(AvgOrdOfGroup);

ВИХІД 

function ( G )
    for g in G  do
        sum := sum + Order( g );
    od;
    return sum / Size( G );
end

але спроба викликати цю функції призводить до помилки:

GAP 

AvgOrdOfGroup(M11);

ПОМИЛКА 

Error, Variable: 'sum' must have an assigned value in
  sum := sum + Order( g ); called from
<function "AvgOrdOfGroup">( <arguments> )
 called from read-eval loop at line 24 of *stdin*
you can 'return;' after assigning a value
brk>

Це стан, у якому GAP виводить запрошення brk>. У ньому ви можете, наприклад, перевірити поточні значення змінних, щоб краще зрозуміти помилку. Щоб вийти з цього стану до головної сесії GAP треба ввести команду quit;.

Те, що відбувається далі, демонструє, як все може піти не так:

GAP 

sum:=2^64; g:=[1];

ВИХІД 

18446744073709551616
[ 1 ]

GAP 

AvgOrdOfGroup(M11);

ВИХІД 

18446744073709604747/7920

GAP 

sum; g;

ВИХІД 

18446744073709604747
(1,2)(3,10,5,6,8,9)(4,7,11)

Тепер, перш ніж перейти до наступного епізоду, будь ласка, скасуйте останню зміну, розкоментувавши два рядки з коментарями, щоб у вас знову була коректна версія AvgOrdOfGroup у файлі avgord.g:

GAP 

AvgOrdOfGroup := function(G)
local sum, g;
sum := 0;
for g in G do
  sum := sum + Order(g);
od;
return sum/Size(G);
end;
Виноска

Шляхи

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

  • Корисно знати, що завершення шляху та імені файлу активується натисканням клавіші Esc два або чотири рази.

Ключові моменти
  • Командний рядок добре підходить для прототипування; функції підходять для повторюваних дій.
  • Інформативні назви функцій і коментарі зроблять код більш читабельним для вас та інших.
  • Остерігайтеся неоголошених локальних змінних!

Content from Використання регресійних тестів

Останнє оновлення 2026-05-16 | Редагувати цю сторінку

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

Огляд

Питання

  • Тестова розробка

Цілі

  • Вміти створювати та запускати тестові файли
  • Зрозуміти, як розбіжності у тестах і зміни у швидкості обчислень можна ідентифікувати та інтерпретувати
  • Зрозуміти, як створювати тести для перевірки рандомізованих алгоритмів
  • Засвоїти концепцію “Спочатку зробіть правильно, а потім швидко”

Код AvgOrdOfGroup дуже простий, і з ним нічого не може піти не так. Перебираючи групу замість створення списку її елементів, це дозволяє уникнути нестачі пам’яті (виклик AsList(SymmetricGroup(11)) вже призводить до перевищення дозволеної пам’яті). Тим не менш, обчислення все одно займає час, кілька хвилин необхідні для розрахунку середнього порядку елемента SymmetricGroup(11). Але принаймні ми впевнені, що це правильно.

Тепер ми хотіли б написати кращу версію цієї функції, використовуючи деякі теоретичні факти, відомі нам із теорії груп. Ми можемо поставити avgord.g під контроль версій, щоб скасувати зміни, якщо потрібно; ми можемо створити нову функцію, щоб зберегти стару версію й порівняти результати обох; але це можна зробити ще ефективнішим, якщо ми використаємо regression testing: це термін для тестування на основі повторних запусків раніше завершених тестів, щоб переконатися, що нові зміни не вплинуть на їх коректність або не погіршать їх роботу.

Для початку нам потрібно створити тестовий файл. Тестовий файл виглядає точно так само, як сеанс GAP, тому його легко створити, скопіювавши та вставивши сеанс GAP з усіма підказками, входами та виходами GAP у текстовий файл (тестовий файл також можна створити з файлу журналу із сеансом GAP, записаним за допомогою LogTo). Під час тестування GAP виконуватиме всі вхідні дані з тестового файлу, порівнюватиме результати з тими, що містяться в тестовому файлі, і повідомлятиме про будь-які відмінності.

Тестові файли GAP — це просто текстові файли, але загальноприйнятою практикою є назвати їх із розширенням .tst. Тепер створіть файл avgord.tst у поточному каталозі (щоб вводити повний шлях) з наступним вмістом:

GAP 

# tests for average order of a group element

# permutation group
gap> S:=SymmetricGroup(9);
Sym( [ 1 .. 9 ] )
gap> AvgOrdOfGroup(S);
3291487/362880

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

Щоб запустити тест, слід використовувати функцію Test, як описано в документації тут. Наприклад (за умови, що функція AvgOrdOfGroup вже завантажена):

GAP 

Test("avgord.tst");

ВИХІД 

true

У цьому випадку Test не повідомив про відсутність розбіжностей і повернув true, тому ми робимо висновок, що перевірку пройдено.

Ми не розглядатимемо тут тему написання гарного та комплексного набору тестів, а також не будемо розглядати різні параметри функції Test, що дозволяє нам, наприклад, ігнорувати відмінності у форматуванні виводу або відображати хід виконання тесту, як це описано в його документації.

Замість цього ми додамо більше груп до avgord.tst, щоб продемонструвати, що код також працює з іншими типами груп, і показати різні способи поєднання команд у тестовому файлі:

GAP 

# tests for average order of a group element

# permutation group
gap> S:=SymmetricGroup(9);
Sym( [ 1 .. 9 ] )
gap> AvgOrdOfGroup(S);
3291487/362880

# pc group
gap> D:=DihedralGroup(512);
<pc group of size 512 with 9 generators>
gap> AvgOrdOfGroup(D);
44203/512
gap> G:=TrivialGroup();; # suppress output
gap> AvgOrdOfGroup(G);
1

# fp group
gap> F:=FreeGroup("a","b");
<free group on the generators [ a, b ]>
gap> G:=F/ParseRelators(GeneratorsOfGroup(F),"a^8=b^2=1, b^-1ab=a^-1");
<fp group on the generators [ a, b ]>
gap> IsFinite(G);
true
gap> AvgOrdOfGroup(G);
59/16

# finite matrix group over integers
gap> AvgOrdOfGroup( Group( [[0,-1],[1,0]] ) );
11/4

# matrix group over a finite field
gap> AvgOrdOfGroup(SL(2,5));
221/40

Давайте ще раз протестуємо розширену версію тесту та перевіримо, чи вона працює:

GAP 

Test("avgord.tst");

ВИХІД 

true

Зараз ми будемо працювати над кращою реалізацією. Звичайно, порядок елемента є інваріантом класу спряженості елементів групи, тому нам потрібно лише знати порядки класів спряженості елементів та їх представників. Наступний код, який ми додаємо до avgord.g, зчитує GAP і перевизначає AvgOrdOfGroup без синтаксичних помилок:

GAP 

AvgOrdOfGroup := function(G)
local cc, sum, c;
cc:=ConjugacyClasses(G);
sum:=0;
for c in cc do
  sum := sum + Order( Representative(c) ) * Size(cc);
od;
return sum/Size(G);
end;

але коли ми запускаємо тест, ось сюрприз!

GAP 

Read("avgord.g");
Test("avgord.tst");

ВИХІД 

########> Diff in avgord.tst, line 6:
# Input is:
AvgOrdOfGroup(S);
# Expected output:
3291487/362880
# But found:
11/672
########
########> Diff in avgord.tst, line 12:
# Input is:
AvgOrdOfGroup(D);
# Expected output:
44203/512
# But found:
2862481/512
########
########> Diff in avgord.tst, line 23:
# Input is:
AvgOrdOfGroup(G);
# Expected output:
59/16
# But found:
189/16
########
########> Diff in avgord.tst, line 29:
# Input is:
AvgOrdOfGroup(SL(2,5));
# Expected output:
221/40
# But found:
69/20
########
false

Дійсно, ми допустили помилку (навмисно) і замінили Size(c) на Size(cc). Правильний варіант курсу має виглядати так:

GAP 

AvgOrdOfGroup := function(G)
local cc, sum, c;
cc:=ConjugacyClasses(G);
sum:=0;
for c in cc do
  sum := sum + Order( Representative(c) ) * Size(c);
od;
return sum/Size(G);
end;

Тепер ми виправимо це в avgord.g, прочитаємо та протестуємо його знову, щоб перевірити, чи тести виконуються правильно.

GAP 

Read("avgord.g");
Test("avgord.tst");

ВИХІД 

true

Таким чином, підхід “Спочатку зробіть правильно, а потім швидко” допоміг виявити помилку відразу після її появи.

Ключові моменти
  • Легко створити тестовий файл, скопіювавши та вставивши сеанс GAP.
  • Написання хорошого та комплексного набору тестів вимагає певних зусиль.
  • Зробіть спочатку правильно, а потім швидко!

Content from Пошук малих груп

Останнє оновлення 2026-05-03 | Редагувати цю сторінку

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

Огляд

Питання

  • Модульне програмування: поєднання функцій разом
  • Як перевірити деяку гіпотезу для всіх груп заданого порядку

Цілі

  • Використовуючи Small Groups Library
  • Розробка системи функцій, яка сумісна

У цьому розділі ми хочемо відкрити деякі нетривіальні групи з цікавою властивістю, а саме, що середній порядок їхніх елементів є цілим числом.

Дистрибутив GAP включає низку бібліотек даних (див. огляд тут). Однією з них є Small Groups Library Ганса Ульріха Беше, Беттіни Айк та Імона О’Брайена.

Ця бібліотека надає різні утиліти для визначення того, яка інформація там зберігається, і надсилання запитів для пошуку груп із потрібними властивостями. Ключовими функціями є SmallGroup, AllSmallGroups, NrSmallGroups, SmallGroupsInformation та IdGroup. Наприклад:

ВИХІД 

gap> NrSmallGroups(64);
267
gap> SmallGroupsInformation(64);

  There are 267 groups of order 64.
  They are sorted by their ranks.
     1 is cyclic.
     2 - 54 have rank 2.
     55 - 191 have rank 3.
     192 - 259 have rank 4.
     260 - 266 have rank 5.
     267 is elementary abelian.

  For the selection functions the values of the following attributes
  are precomputed and stored:
     IsAbelian, PClassPGroup, RankPGroup, FrattinifactorSize and
     FrattinifactorId.

  This size belongs to layer 2 of the SmallGroups library.
  IdSmallGroup is available for this size.

gap> G:=SmallGroup(64,2);

gap> AllSmallGroups(Size,64,NilpotencyClassOfGroup,5);
[  ,  ,
   ]
gap> List(last,IdGroup);
[ [ 64, 52 ], [ 64, 53 ], [ 64, 54 ] ]

Ми хотіли б використати нашу власну функцію тестування, яку ми створимо тут, використовуючи вбудовану нотацію (доступну для функцій з одним аргументом):

GAP 

TestOneGroup := G -> IsInt( AvgOrdOfGroup(G) );

Тепер спробуйте, наприклад,

GAP 

List([TrivialGroup(),Group((1,2))],TestOneGroup);

ВИХІД 

[ true, false ]

GAP 

gap> AllSmallGroups(Size,24,TestOneGroup,true);

ВИХІД 

[ ]
Виноска

Тут починається модульне програмування

Чому повернення логічних значень є хорошим проєктним рішенням для таких функцій, замість того, щоб просто друкувати інформацію чи повертати рядок, наприклад "YES"?

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

GAP 

TestOneOrderEasy := function(n)
local i;
for i in [1..NrSmallGroups(n)] do
  if TestOneGroup( SmallGroup( n, i ) ) then
    return [n,i];
  fi;
od;
return fail;
end;

Наприклад,

GAP 

TestOneOrderEasy(1);

ВИХІД 

[ 1, 1 ]

GAP 

TestOneOrderEasy(24);

ВИХІД 

fail
Виноска

AllSmallGroups не вистачає пам’яті - що робити?

  • Використовуйте ітерацію над [1..NrSmallGroups(n)], як показано у функції вище
  • Використовуйте IdsOfAllSmallGroups, яка приймає ті самі аргументи, що й AllSmallGroups, але повертає ідентифікатори замість груп.

Ітерація над [1..NrSmallGroups(n)] дає вам більше гнучкості, якщо вам потрібно більше контролювати хід обчислення. Наприклад, наступна версія нашої функції тестування друкує додаткову інформацію про номер групи, що тестується. Він також надає функцію тестування як аргумент (чому ви думаєте, що це краще?).

GAP 

TestOneOrder := function(f,n)
local i, G;
for i in [1..NrSmallGroups(n)] do
  Print(n, ":", i, "/", NrSmallGroups(n), "\r");
  G := SmallGroup( n, i );
  if f(G) then
    Print("\n");
    return [n,i];
  fi;
od;
Print("\n");
return fail;
end;

Наприклад,

GAP 

TestOneOrder(TestOneGroup,64);

відобразить змінний лічильник під час обчислення, а потім поверне fail:

ВИХІД 

64:267/267
fail

Наступним кроком є інтеграція TestOneOrder у функцію, яка перевірить усі порядки від 2 до n і зупиниться, щойно знайде приклад групи, середній порядок елемента якого є цілим числом:

GAP 

TestAllOrders:=function(f,n)
local i, res;
for i in [2..n] do
  res:=TestOneOrder(f,i);
  if res <> fail then
    return res;
  fi;
od;
return fail;
end;

Ми бачимо, що існує така група порядку 105:

GAP 

TestAllOrders(TestOneGroup,128);

ВИХІД 

2:1/1
3:1/1
4:2/2
5:1/1
6:2/2
7:1/1
8:5/5
...
...
...
100:16/16
101:1/1
102:4/4
103:1/1
104:14/14
105:1/2
[ 105, 1 ]

Щоб дослідити її далі, ми можемо отримати її StructureDescription (див. тут для пояснення нотації, яку використано):

GAP 

G:=SmallGroup(105,1); AvgOrdOfGroup(G); StructureDescription(G);

ВИХІД 

17
"C5 x (C7 : C3)"

а потім перетворити її на скінченно представлену групу, щоб побачити її твірні та співвідношення:

GAP 

H:=SimplifiedFpGroup(Image(IsomorphismFpGroup(G)));
RelatorsOfFpGroup(H);

ВИХІД 

[ F1^3, F2^-1*F1^-1*F2*F1, F3^-1*F2^-1*F3*F2, F3^-1*F1^-1*F3*F1*F3^-1, F2^5,
F3^7 ]

Тепер ми хочемо спробувати більші групи, починаючи з порядку 106 (ми перевіряємо, що інша група порядку 105 не має такої властивості)

GAP 

List(AllSmallGroups(105),AvgOrdOfGroup);

ВИХІД 

[ 17, 301/5 ]

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

GAP 

TestRangeOfOrders:=function(f,n1,n2)
local n, res;
for n in [n1..n2] do
  res:=TestOneOrder(f,n);
  if res <> fail then
    return res;
  fi;
od;
return fail;
end;

Але тепер ми викликаємо

GAP 

TestRangeOfOrders(TestOneGroup,106,256);

і виявляємо, що тестування 2328 груп порядку 128 і додатково 56092 груп порядку 256 вже займає занадто багато часу.

Виноска

Не панікувати!

Ви можете перервати GAP, натиснувши Ctrl-C один раз. Після цього GAP увійде в цикл розриву, позначений підказкою розриву brk>. Ви можете вийти з нього, ввівши quit; (стережіться натискання Ctrl-C двічі протягом секунди – це повністю завершить сеанс GAP).

Це ще одна ситуація, коли теоретичні знання допомагають набагато більше, ніж підхід грубої сили. Якщо група є p-групою, то порядок кожного класу спряженості нетотожного елемента групи ділиться на p; отже, середній порядок елемента групи може не бути цілим числом. Тому p-групи можна виключити з розрахунку. Отже, нова версія коду є

GAP 

TestRangeOfOrders:=function(f,n1,n2)
local n, res;
for n in [n1..n2] do
  if not IsPrimePowerInt(n) then
     res:=TestOneOrder(f,n);
     if res <> fail then
       return res;
     fi;
   fi;
od;
return fail;
end;

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

GAP 

gap> TestRangeOfOrders(TestOneGroup,106,512);

ВИХІД 

106:2/2
108:45/45
...
350:10/10
351:14/14
352:195/195
354:4/4
355:2/2
356:5/5
357:1/2
[ 357, 1 ]

Наступна функція демонструє ще більшу гнучкість: вона є варіативною, тобто вона може приймати два або більше аргументів, перші два з яких будуть призначені змінним f і n, а решта буде доступна в список r (це позначено ... після r). Перший аргумент — функція перевірки, другий — порядок перевірки, третій і четвертий — номери першої та останньої груп цього порядку, які потрібно перевірити. За замовчуванням останні два дорівнюють 1 і NrSmallGroups(n) відповідно. Ця функція також показує, як перевірити вхідні дані та створювати зручні повідомлення про помилки у випадку неприпустимих аргументів.

Крім того, ця функція демонструє, як використовувати повідомлення Info, які можна вмикати та вимикати, встановивши відповідний рівень Info. Потреба, яку ми тут розглядаємо, полягає в тому, щоб мати можливість перемикати рівні багатослівності виводу без підходу, схильного до помилок, проходження коду та коментування інструкцій Print. Це досягається шляхом створення інформаційного класу:

GAP 

gap> InfoSmallGroupsSearch := NewInfoClass("InfoSmallGroupsSearch");

ВИХІД 

InfoSmallGroupsSearch

Тепер замість Print("something"); можна використовувати Info( InfoSmallGroupsSearch, infolevel, "something");, де infolevel є додатним цілим числом, що визначає рівень докладності. Цей рівень можна змінити на n за допомогою команди SetInfoLevel( InfoSmallGroupsSearch, n);. Перегляньте фактичні виклики Info у коді нижче:

GAP 

TestOneOrderVariadic := function(f,n,r...)
local n1, n2, i;

if not Length(r) in [0..2] then
  Error("The number of arguments must be 2,3 or 4\n" );
fi;

if not IsFunction( f ) then
  Error("The first argument must be a function\n" );
fi;

if not IsPosInt( n ) then
  Error("The second argument must be a positive integer\n" );
fi;

if IsBound(r[1]) then
  n1:=r[1];
  if not n1 in [1..NrSmallGroups(n)] then
    Error("The 3rd argument, if present, must belong to ", [1..NrSmallGroups(n)], "\n" );
  fi;
else
  n1:=1;
fi;

if IsBound(r[2]) then
  n2:=r[2];
  if not n2 in [1..NrSmallGroups(n)] then
    Error("The 4th argument, if present, must belong to ", [1..NrSmallGroups(n)], "\n" );
  elif n2 < n1 then
    Error("The 4th argument, if present, must be greater or equal to the 3rd \n" );
  fi;
else
  n2:=NrSmallGroups(n);
fi;

Info( InfoSmallGroupsSearch, 1,
      "Checking groups ", n1, " ... ", n2, " of order ", n );
for i in [n1..n2] do
  if InfoLevel( InfoSmallGroupsSearch ) > 1 then
    Print(i, "/", NrSmallGroups(n), "\r");
  fi;
  if f(SmallGroup(n,i)) then
    Info( InfoSmallGroupsSearch, 1,
          "Discovered counterexample: SmallGroup( ", n, ", ", i, " )" );
    return [n,i];
  fi;
od;
Info( InfoSmallGroupsSearch, 1,
      "Search completed - no counterexample discovered" );
return fail;
end;

У наступному прикладі показано, як тепер можна керувати виводом, перемикаючи рівень інформації для InfoSmallGroupsSearch:

ВИХІД 

gap> TestOneOrderVariadic(IsIntegerAverageOrder,24);
fail
gap> SetInfoLevel( InfoSmallGroupsSearch, 1 );
gap> TestOneOrderVariadic(IsIntegerAverageOrder,24);
#I  Checking groups 1 ... 15 of order 24
#I  Search completed - no counterexample discovered
fail
gap> TestOneOrderVariadic(IsIntegerAverageOrder,357);
#I  Checking groups 1 ... 2 of order 357
#I  Discovered counterexample: SmallGroup( 357, 1 )
[ 357, 1 ]
gap> SetInfoLevel( InfoSmallGroupsSearch, 0);
gap> TestOneOrderVariadic(IsIntegerAverageOrder,357);
[ 357, 1 ]

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

ВИХІД 

# Finding groups with integer average order
gap> INFO_SSS:=InfoLevel(InfoSmallGroupsSearch);;
gap> SetInfoLevel( InfoSmallGroupsSearch, 0);
gap> res:=[];;
gap> for n in [1..360] do
>      if not IsPrimePowerInt(n) then
>        t := TestOneOrderVariadic( IsIntegerAverageOrder,n,1,NrSmallGroups(n) );
>        if t <> fail then
>          Add(res,t);
>        fi;
>      fi;
>    od;
gap> res;
[ [ 1, 1 ], [ 105, 1 ], [ 357, 1 ] ]
gap> SetInfoLevel( InfoSmallGroupsSearch, INFO_SSS);
Обговорення

Чи містить бібліотека Small Groups Library іншу групу з цією властивістю?

  • Що Ви можете сказати про порядок груп із цією властивістю?

  • Чи можете Ви оцінити, скільки часу може зайняти перевірка всіх 408641062 груп порядку 1536?

  • Скільки груп порядку не вище 2000 Ви могли б перевірити, за винятком p-груп і груп порядку 1536?

  • Чи можете Ви знайти іншу групу з цією властивістю в бібліотеці Small Groups Library (порядок не дорівнює 1536)?

Ключові моменти
  • Організуйте код у функції.
  • Створюйте малі групи одну за одною замість того, щоб створювати їх величезний список.
  • Використання SmallGroupsInformation може допомогти зменшити простір пошуку.
  • GAP не є чарівним інструментом: теоретичні знання можуть допомогти набагато більше, ніж підхід грубої сили.

Content from Атрибути та методи

Останнє оновлення 2026-04-28 | Редагувати цю сторінку

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

Огляд

Питання

  • Як записати інформацію в об’єкти GAP

Цілі

  • Оголошення атрибута
  • Встановлення методу
  • Розуміння вибору методу
  • Використання інструментів для налагодження
Виноска

Яка функція швидше?

Спробуйте неодноразово обчислити AvgOrdOfGroup(M11) та AvgOrdOfCollection(M11) і порівняти час виконання. Зробіть це для нової копії M11 і для тієї, для якої цей параметр уже спостерігався. Що ви спостерігаєте?

Звичайно, для будь-якої даної групи середній порядок її елементів потрібно обчислити лише один раз, оскільки наступного разу він поверне те саме значення. Однак, як ми бачимо з часу виконання нижче, кожен новий виклик AvgOrdOfGroup повторюватиме те саме обчислення знову, дещо змінюючи час виконання:

GAP 

A:=AlternatingGroup(10);

ВИХІД 

Alt( [ 1 .. 10 ] )

GAP 

AvgOrdOfCollection(A); time; AvgOrdOfCollection(A); time;

ВИХІД 

2587393/259200
8226
2587393/259200
8118

В останньому прикладі група, про яку йде мова, була такою самою – ми не створили іншу копію AlternatingGroup(10); однак результат обчислення не було збережено в A.

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

GAP 

G:=Group([ (1,2,3,4,5,6,7,8,9,10,11), (3,7,11,8)(4,10,5,6) ]);
gap> NrConjugacyClasses(G);time;NrConjugacyClasses(G);time;

ВИХІД 

Group([ (1,2,3,4,5,6,7,8,9,10,11), (3,7,11,8)(4,10,5,6) ])
10
39
10
0

У цьому випадку група G має 10 класів спряженості, і знадобилося 39 мс, щоб встановити це під час першого виклику. Другий виклик має нульову вартість, оскільки результат було збережено в G, і тому, що NrConjugacyClasses є атрибутом:

GAP 

NrConjugacyClasses;

ВИХІД 

<Attribute "NrConjugacyClasses">

Зараз наша мета — навчитися створювати власні атрибути.

Оскільки у нас вже є функція AvgOrdOfCollection, яка виконує обчислення, найпростішим способом перетворити її на атрибут є наступний:

GAP 

AverageOrder := NewAttribute("AverageOrder", IsCollection);
InstallMethod( AverageOrder, "for a collection", [IsCollection], AvgOrdOfCollection);

У цьому прикладі спочатку ми оголосили атрибут AverageOrder для об’єктів у категорії IsCollection, а потім встановили функцію AvgOrdOfCollection як метод для цього атрибута. Замість виклику функції AvgOrdOfCollection, тепер ми можемо викликати AverageOrder.

Тепер ми можемо перевірити, що наступні виклики AverageOrder з тим самим аргументом виконуються без витрат часу. У цьому прикладі час скорочено з більш ніж 16 секунд до нуля:

GAP 

S:=SymmetricGroup(10);; AverageOrder(S); time; AverageOrder(S); time;

ВИХІД 

39020911/3628800
16445
39020911/3628800
0

Ви можете запитати, чому ми оголосили операцію для колекції, а не лише для групи, і чому ми встановили неефективний AvgOrdOfCollection. Зрештою, ми вже розробили набагато ефективнішу функцію AvgOrdOfGroup.

Уявіть, що Ви хочете мати можливість обчислити середній порядок як для групи, так і для списку, який складається з об’єктів, що мають мультиплікативний порядок. Ви можете мати спеціальну функцію для кожного випадку, як у нас. Якщо може трапитися так, що Ви не знаєте наперед тип об’єкта, про який йде мова, Ви можете додати перевірки в код і відправити до відповідної функції. Це може швидко стати складним, якщо у вас є кілька різних функцій для різних типів об’єктів. Натомість атрибути — це групи функцій, які називаються method, а вибір методу в GAP вибере найефективніший метод на основі типу всіх аргументів.

Щоб проілюструвати це, зараз ми встановимо метод для AverageOrder для групи:

GAP 

InstallMethod( AverageOrder, [IsGroup], AvgOrdOfGroup);

Якщо ви застосуєте його до групи, для якої AverageOrder вже обчислено, нічого не станеться, оскільки GAP використовуватиме збережене значення. Однак для новоствореної групи цей новий метод буде називатися:

GAP 

S:=SymmetricGroup(10);; AverageOrder(S); time; AverageOrder(S); time;

ВИХІД 

39020911/3628800
26
39020911/3628800
0
Виноска

Який метод викликається

  • Try to call AverageOrder for a collection which is not a group (a list of group elements and/or a conjugacy class of group elements).

  • Debugging tools like TraceMethods may help you see which method is being called.

  • ApplicableMethod in combination with PageSource may point you to the source code with all the comments.

Property є атрибутом із логічним значенням. Його можна створити, використовуючи NewProperty

GAP 

IsIntegerAverageOrder := NewProperty("IsIntegerAverageOrder", IsCollection);

Тепер ми встановимо метод для IsIntegerAverageOrder для колекції. Зауважте, що ніколи не потрібно спочатку створювати функцію, а потім встановлювати її як метод. Наступне встановлення методу натомість створює нову функцію як один із своїх аргументів:

GAP 

InstallMethod( IsIntegerAverageOrder,
  "for a collection",
  [IsCollection],
  coll -> IsInt( AverageOrder( coll ) )
);

Зауважте, що оскільки AverageOrder є атрибутом, він подбає про вибір найбільш прийнятного методу.

Виноска

Чи завжди такий метод існує?

Ні. “No-method-found” є особливим видом помилки, і існують інструменти для дослідження таких помилок: див. ?ShowArguments, ?ShowDetails, ?ShowMethods> та ?ShowOtherMethods.

Наступні обчислення показують, що, незважаючи на наш успіх з обчисленням середнього порядку для великих груп перестановок через класи спряженості елементів, для pc груп із бібліотеки Small Groups Library можна було б швидше перебирати їх елементи, ніж обчислювати класи спряженості:

GAP 

l:=List([1..1000],i->SmallGroup(1536,i));; List(l,AvgOrdOfGroup);;time;

ВИХІД 

56231

GAP 

l:=List([1..1000],i->SmallGroup(1536,i));; List(l,AvgOrdOfCollection);;time;

ВИХІД 

9141
Обговорення

Не панікуйте!

  • Установіть метод для IsPcGroup, який повторює елементи групи замість обчислень її класів спряженості.

  • Оцініть практичні межі його можливості. Чи можете ви знайти приклад pc групи, де ітерація повільніша, ніж обчислення класів спряженості?

Ключові моменти
  • Позиційні об’єкти можуть накопичувати інформацію про себе протягом життя.
  • Це означає, що наступного разу збережену інформацію можна буде відновити без жодних витрат.
  • Методи — це групи функцій; Вибір методів GAP вибере найефективніший метод на основі типу всіх аргументів.
  • ‘Метод не знайдено’ — це особливий вид помилки з корисними інструментами налагодження, які допомагають її зрозуміти.