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

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

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

Огляд

Питання

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

Цілі

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

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

ВИВІД 

 ┌───────┐   GAP 4.15.1 of 2025-10-18
 │  GAP  │   https://www.gap-system.org
 └───────┘   Architecture: aarch64-apple-darwin25-default64-kv10
 Configuration:  gmp 6.3.0, GASMAN, readline
 Loading the library and packages ...
 Packages:   AClib 1.3.3, Alnuth 3.2.1, AtlasRep 2.1.9, AutoDoc 2025.10.16,
             AutPGrp 1.11.1, Browse 1.8.21, CaratInterface 2.3.7, CRISP 1.4.8,
             Cryst 4.1.30, CrystCat 1.1.10, CTblLib 1.3.11,
             curlInterface 2.4.2, FactInt 1.6.3, FGA 1.5.0, Forms 1.2.13,
             GAPDoc 1.6.7, genss 1.6.9, IO 4.9.3, IRREDSOL 1.4.4,
             LAGUNA 3.9.7, orb 5.0.1, PackageManager 1.6.3, Polenta 1.3.11,
             Polycyclic 2.17, PrimGrp 4.0.1, RadiRoot 2.9, recog 1.4.4,
             ResClasses 4.7.4, SmallGrp 1.5.4, Sophus 1.27, SpinSym 1.5.2,
             StandardFF 1.0, TomLib 1.2.11, TransGrp 3.6.5, utils 0.92
 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, щоб перервати його. Потім введіть quit; щоб повернутись до головної сесії GAP.
  • Прочитайте розділ “A First Session with GAP”, який міститься у GAP Tutorial.

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

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

Огляд

Питання

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

Цілі

  • Ознайомитися із деякими типами обʼєктів, які є в 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-06-16 | Редагувати цю сторінку

Огляд

Питання

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

Цілі

  • Використання командного рядка для прототипування
  • Створення функцій
  • Завантаження 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

У цьому прикладі ми навмисно розпочали новий сеанс 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-06-16 | Редагувати цю сторінку

Огляд

Питання

  • Регресійні тести

Цілі

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

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

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

Спочатку нам треба створити тестовий файл. Тестовий файл виглядає точно так само, як сеанс 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 друкує у відповідь на введену команду.

Щоб запустити тест, слід використовувати функцію 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 := 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-06-16 | Редагувати цю сторінку

Огляд

Питання

  • Модульне програмування
  • Пошук прикладів та контрприкладів серед груп заданого порядку

Цілі

  • Використання бібліотеки груп малих порядків (Small Groups Library)
  • Створення взаємоповʼязаних функцій

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

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

Бібліотека 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 не вистачає пам’яті - що робити?

  • Використовуйте цикл, як показано у функції вище, щоб створювати тільки одну групу на кожній ітерації
  • Використовуйте функцію 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 (див. документацію для пояснення нотації, яку використано у 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>. Ви можете перевірити поточні значення змінних, щоб краще зрозуміти контекст виконання. Для того, щоб вийти до головної сесії GAP, треба ввести 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. Це досягається шляхом створення інформаційного класу (Info class):

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-06-16 | Редагувати цю сторінку

Огляд

Питання

  • Як зберігати інформацію в об’єктах 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 є таке поняття як атрибут – структура даних, яка використовується для накопичення інформації, яку об’єкт “дізнається про себе протягом свого життя” (learns about itself during its lifetime). Розгляньмо наступний приклад:

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.

Уявіть, що ми хочемо мати можливість обчислити середній порядок як для групи, так і для списку, який складається з об’єктів, що мають мультиплікативний порядок. Можна мати окрему функцію для кожного випадку, наприклад, як ми маємо зараз. Щоб зробити код більш універсальним, до нього можна додати перевірку типу обʼєкту, що розглядається, для виклику відповідної функції. Це може швидко стати складним, якщо у вас є кілька різних функцій для різних типів об’єктів. Натомість атрибути — це групи функцій, які називаються методами, а вибір методу в 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
Примітка

Як зрозуміти, який метод викликається

  • Спробуйте викликати AverageOrder для колекції, яка не є групою (список елементів групи та/або клас спряжених елементів групи).

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

  • Функція ApplicableMethod в комбінації з PageSource може вказати на конкретні рядки у вихідному коді разом з коментарями.

Спеціальним видом атрибуту є властивість (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 групи, де перебір елементів повільніший, ніж обчислення класів спряженості?

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