All in One View

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

Last updated on 2026-04-27 | Edit this page

Estimated time: 40 minutes

Overview

Questions

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

Objectives

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

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

OUTPUT 

 ┌───────┐   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 );

OUTPUT 

-6700417

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

GAP 

LogTo("gap-intro.log");

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

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

GAP 

# Урок Software Carpentry GAP

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

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

GAP 

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

OUTPUT 

-6700417

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

GAP 

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

OUTPUT 

-18446744073709551617/641

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

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

GAP 

universe := 6*7;
Callout

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

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

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

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

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

GAP 

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

OUTPUT 

-18446744073709551617/641

Пробіли часто використовуються для форматування більш складних команд для кращої читабельності. Наприклад, наступне введення, яке створює матрицю 3×3: For example, the following input which creates a 3×3 matrix:

GAP 

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

OUTPUT 

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

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

GAP 

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

OUTPUT 

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

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

GAP 

Display(m);

OUTPUT 

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

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

Callout

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

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

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

GAP 

Factorial(100);

OUTPUT 

93326215443944152681699238856266700490715968264381621468\
59296389521759999322991560894146397615651828625369792082\
7223758251185210916864000000000000000000000000

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

GAP 

Determinant(m);

OUTPUT 

0

та

GAP 

Factors(2^64-1);

OUTPUT 

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

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

GAP 

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

OUTPUT

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

GAP 

Fibonacci(100);

OUTPUT 

354224848179261915075

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

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

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

GAP 

factorial(100);

ERROR 

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

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

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

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

OUTPUT 

┌──────────────────────────────────────────────────────────────────────────────┐
│   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 на власному комп’ютері, ви можете встановити для перегляду довідки браузер за замовчуванням. If you are running GAP on a remote machine, this (probably) will not work. (see ?WriteGapIniFile on how to make this setting permanent):

GAP 

SetHelpViewer("browser");

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

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

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

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

GAP 

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

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

GAP 

G:=Group(a,b);

OUTPUT 

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

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

GAP 

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

OUTPUT 

12
false
"A4"
3

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

GAP 

AsList(G);

OUTPUT 

[ (), (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;

OUTPUT 

[ (), (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. Наступні команди (сподіваємося!) не потребують пояснень:

GAP 

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

OUTPUT 

()
(2,4,3)
12
Callout

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

  • Може містити дірки або бути порожнім

  • Може динамічно змінювати їх довжину (за допомогою Add, Append або прямого призначення)

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

  • Дивіться більше в GAP Tutorial: Lists and Records

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

GAP 

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

OUTPUT 

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);

OUTPUT 

31/12

Насправді, ми можемо просто перебирати елементи G (загалом GAP дозволить вам перебирати більшість типів об’єктів). Нам потрібно перейти на використання Size замість Length, оскільки групи не мають довжини! We have to switch to using Size instead of Length, as groups don’t have a length!Нам потрібно перейти на використання Size замість Length, оскільки групи не мають довжини!

GAP 

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

OUTPUT 

31/12

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

GAP 

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

OUTPUT 

31/12

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

GAP 

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

OUTPUT 

31/12

Давайте розберемо останню частину:

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

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

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

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

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

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

GAP 

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

OUTPUT 

[ (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) );

OUTPUT 

(1,2,3)

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

GAP 

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

OUTPUT 

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

GAP 

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

OUTPUT 

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

GAP 

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

OUTPUT 

false
Discussion

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

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

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

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

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

Last updated on 2026-04-27 | Edit this page

Estimated time: 20 minutes

Overview

Questions

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

Objectives

  • Перегляньте приклади типів, які вбудовані в GAP, але можуть бути відсутні в інших системах
  • Подивіться приклади арифметики списку

Наразі ми познайомилися з трьома типами GAP:

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

  • такі складені об’єкти, як lists;

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

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

Деякі інші прості об’єкти - це floats, cyclotomics and finite field elements:

GAP 

1.15; Float(1232/3456567);

OUTPUT 

1.15
0.000356423

GAP 

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

OUTPUT 

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

GAP 

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

OUTPUT 

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

Ви вже знаєте про списки. Іншим типом складених об’єктів є записи. У той час як список містить субоб’єкти, проіндексовані за їх позиціями в списку, запис містить субоб’єкти, які називаються компонентами запису, які індексуються за своїми іменами. Elements of a record are accessed with .

GAP 

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

OUTPUT 

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

GAP 

date.year;

OUTPUT 

2015

GAP 

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

OUTPUT 

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

GAP 

date;

OUTPUT 

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

GAP 

RecNames(date);

OUTPUT 

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

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

GAP 

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

OUTPUT 

"supercalifragilisticexpialidocious"
34

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

GAP 

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

OUTPUT 

false
true
true
true
true

Зауважте, що

GAP 

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

OUTPUT 

fail
10

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

GAP 

gap> SortedList(w); w;

OUTPUT 

"aaacccdeefgiiiiiiillloopprrssstuux"
"supercalifragilisticexpialidocious"

але

GAP 

gap> Sort(w); w;

OUTPUT 

"aaacccdeefgiiiiiiillloopprrssstuux"

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

GAP 

gap> c := Collected(w);

OUTPUT 

[ [ '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 );

OUTPUT 

7
[ [ 'i', 7 ] ]
Discussion

Пошук найпоширеніших букв у списку за допомогою лише одного проходу

Команда

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

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

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

Content from Функції в GAP

Last updated on 2026-04-27 | Edit this page

Estimated time: 55 minutes

Overview

Questions

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

Objectives

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

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

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

GAP 

S:=SymmetricGroup(10);

OUTPUT 

Sym( [ 1 .. 10 ] )

GAP 

sum:=0;

OUTPUT 

0

GAP 

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

OUTPUT 

39020911/3628800

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

GAP 

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

OUTPUT 

39020911/3628800

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

GAP 

S:=AlternatingGroup(10);

OUTPUT 

Alt( [ 1 .. 10 ] )

GAP 

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

OUTPUT 

2587393/259200
Callout

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

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

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

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

Наступна функція приймає аргумент 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;

OUTPUT 

function( G ) ... end

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

GAP 

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

OUTPUT 

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);

OUTPUT 

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 

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

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

GAP 

Read("avgord.g");

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

GAP 

AvgOrdOfGroup(M11);

OUTPUT 

53131/7920

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

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

GAP 

return sum/Size(G);

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

GAP 

return Float(sum/Size(G);

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

GAP 

Read("avgord.g");

і Ви побачите повідомлення про помилку:

ERROR 

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

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

GAP 

Print(AvgOrdOfGroup);

OUTPUT 

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

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

GAP 

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

OUTPUT 

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");

ERROR 

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

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

GAP 

Print(AvgOrdOfGroup);

OUTPUT 

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

але спроба запустити його призводить до розриву циклу:

GAP 

AvgOrdOfGroup(M11);

ERROR 

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>

з якого можна вийти за допомогою quit;.

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

GAP 

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

OUTPUT 

18446744073709551616
[ 1 ]

GAP 

AvgOrdOfGroup(M11);

OUTPUT 

18446744073709604747/7920

GAP 

sum; g;

OUTPUT 

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;
Callout

Шляхи

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

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

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

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

Last updated on 2026-04-28 | Edit this page

Estimated time: 50 minutes

Overview

Questions

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

Objectives

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

Код 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");

OUTPUT 

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);

gap> AvgOrdOfGroup(D);
44203/512
gap> G:=TrivialGroup();; # suppress output
gap> AvgOrdOfGroup(G);
1

# fp group
gap> F:=FreeGroup("a","b");

gap> G:=F/ParseRelators(GeneratorsOfGroup(F),"a^8=b^2=1, b^-1ab=a^-1");

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");

OUTPUT 

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");

OUTPUT 

########> 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");

OUTPUT 

true

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

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

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

Last updated on 2026-04-27 | Edit this page

Estimated time: 55 minutes

Overview

Questions

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

Objectives

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

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

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

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

OUTPUT 

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);

OUTPUT 

[ true, false ]

GAP 

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

OUTPUT 

[ ]
Callout

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

Чому повернення логічних значень є хорошим проєктним рішенням для таких функцій, замість того, щоб просто друкувати інформацію чи повертати рядок, наприклад "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);

OUTPUT 

[ 1, 1 ]

GAP 

TestOneOrderEasy(24);

OUTPUT 

fail
Callout

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:

OUTPUT 

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);

OUTPUT 

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);

OUTPUT 

17
"C5 x (C7 : C3)"

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

GAP 

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

OUTPUT 

[ 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);

OUTPUT 

[ 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 вже займає занадто багато часу.

Callout

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

Ви можете перервати 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);

OUTPUT 

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");

OUTPUT 

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:

OUTPUT 

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 з іншим рівнем інформації, ми запам’ятаємо цей рівень інформації, щоб відновити його після тесту:

OUTPUT 

# 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);
Discussion

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

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

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

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

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

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

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

Last updated on 2026-04-28 | Edit this page

Estimated time: 50 minutes

Overview

Questions

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

Objectives

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

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

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

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

GAP 

A:=AlternatingGroup(10);

OUTPUT 

Alt( [ 1 .. 10 ] )

GAP 

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

OUTPUT 

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;

OUTPUT 

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;

OUTPUT 

<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;

OUTPUT 

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;

OUTPUT 

39020911/3628800
26
39020911/3628800
0
Callout

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

  • 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 є атрибутом, він подбає про вибір найбільш прийнятного методу.

Callout

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

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

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

GAP 

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

OUTPUT 

56231

GAP 

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

OUTPUT 

9141
Discussion

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

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

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

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