Перейти к главе: Начало 1 2 3 4 A B C Bib Ind
 [Начало книги]  [Содержание]   [Предыдущая глава]   [Следующая глава] 

C Лабораторные работы
 C.1 Основы работы с системой GAP в MS Windows
 C.2 Списки. Целые числа
 C.3 Линейные программы. Векторы и матрицы
 C.4 Ветвящиеся программы. Многочлены
 C.5 Циклические программы (цикл FOR). Бинарные отношения
 C.6 Циклические программы (цикл WHILE). Подстановки
 C.7 Циклические программы (цикл REPEAT). Группы подстановок
 C.8 Изучение свойств элементов группы
 C.9 Изучение свойств подгрупп группы
 C.10 Работа с библиотекой конечных групп
 C.11 Дополнительные упражнения различной трудности

C Лабораторные работы

C.1 Основы работы с системой GAP в MS Windows

C.1-1 Инструкции по выполнению работы 1

В данной лабораторной работе необходимо последовательно выполнить все этапы.

1. Найдите каталог gap4r4, в котором инсталлирована система GAP на локальном или сетевом диске (например, с помощью FAR или Проводника). Если инсталляция системы GAP не выполнена, то Вы можете произвести ее самостоятельно в соответствии с разделами "Инсталляция" или "GAP для Windows" сайта Украинской группы пользователей GAP. Для учебных целей намного быстрее можно инсталлировать мини-дистрибутив из раздела "Мини-тест" этого же сайта. Адрес сайта - http://www.gap-system.org/ukrgap/.

2. Найдите в каталоге gap4r4\bin командные файлы gap.bat и gaprxvt.bat. Теперь Вы уже можете запускать систему GAP с их помощью. Запустите сначала файл gap.bat для работы в окне командной строки Windows (окне MS-DOS). После появления приглашения вида gap> введите команду quit; для выхода из системы. После этого запустите файл gaprxvt.bat для работы в окне оболочки RXVT. После завершения загрузки системы также выйдите из нее с помощью команды quit; (помните, что команды завершаются точкой с запятой, после чего необходимо нажать клавишу Enter).

3. Простейшие вычисления можно выполнять, запуская систему так, как указано в п.2. Однако, в этом случае при чтении и записи файлов нужно будет указывать полный путь к ним. Эффективнее будет создать рабочий каталог в том разделе диска, где Вы имеете соответствующие права доступа, и скопировать туда файлы gap.bat и gaprxvt.bat. Выполните эти инструкции, создав свой рабочий каталог (который можно назвать, например, gap) и ознакомьтесь с содержанием этих файлов (например, c помощью FAR или Блокнота). В дальнейшем Вы также сможете создать ярлыки для запуска этих файлов и поместить их в главное меню и на рабочий стол.

4. Теперь Вам нужно освоить работу с системой в обоих вариантах - как в окне MS-DOS, так и в окне RXVT. Для этого снова запустите систему, но теперь уже из только что созданного Вами рабочего каталога. Если производительность компьютера позволяет, Вы можете одновременно запустить оба файла gap.bat и gaprxvt.bat. В противном случае нижеследующие пункты нужно будет сначала выполнить в одном окне, а потом повторить в другом.

5. Выполните простейшие вычисления, введя следующие команды:


352/182;
2*(15+256)/17;
2^64;
2^20000 mod 100;
3 in [1,2,3];
2*2 >= 4;

Одна команда может занимать несколько строк, последняя из которых заканчивается точкой с запятой. Таким образом, если Вы забыли поставить точку с запятой в конце строки и уже нажали клавишу Enter, Вы можете поставить точку с запятой в следующей строке, а затем нажать Enter еще раз. Попробуйте ввести следующую многострочную команду:


155/4545+ 
1234*5678+ 
Factorial(100)+  
Sum([1..100]);

Помните при этом, что в GAP имеет значение регистр текста. Например, следующая команда приводит к ошибке:


gap> factorial(100);
Variable: 'factorial' must have a value
gap>

При некоторых ошибках на экран выводится промежуточное приглашение системы вида brk>. Для выхода из него нужно ввести команду quit; (в этом случае она не приводит к завершению работы системы). Например:


gap> Factorial(1/2);
Range: <last> must be an integer less than 2^28 (not a rational) at
return Product( [ 1 .. n ] );
called from
<function>( <arguments> ) called from read-eval-loop
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can replace <last> via 'return <last>;' to continue
brk> quit;
gap>

6. Теперь нужно освоить работу с историей команд. Нажимайте клавиши перемещения курсора вверх и вниз для просмотра истории команд. Теперь наберите в командной строке цифру 2, а затем нажимайте те же клавиши управления курсором. При этом Вы будете видеть только те из ранее введенных команд, которые начинались с цифры 2.

7. Вы можете перемещаться по содержимому командной строки с помощью клавиш перемещения курсора влево и вправо, и можете удалять символы с помощью клавиш Delete и Backspace. Например, наберите в командной строке F и найдите в истории команд ранее введенную строку Factorial(100)+. Теперь переместитесь в конец строки и отредактируйте ее так, чтобы вычислить 500!.

Для быстрого перемещения в конец и начало строки можно также использовать клавиши Home и End в окне MS-DOS, и комбинации клавиш Ctrl-A и Ctrl-B как в окне MS-DOS, так и в окне RXVT (о других полезных при редактировании содержимого командной строки сочетаниях клавиш Вы можете прочитать в документации по системе, для чего введите команду ?options!command line, а затем следуйте выведенным на экран инструкциям).

8. Научитесь выделять, копировать и вставлять текст. Попробуйте выделить в окне браузера (т.е. MS Internet Explorer, Netscape и т.п.) и скопировать в буфер обмена команды, приведенные выше, а затем перейти в окно GAP и вставить их в командную строку (в окне MS-DOS используйте стандартные способы вставки, а в окне RXVT используйте сочетание клавиш Shift-Ins). Затем попробуйте выделить и скопировать текст из окна GAP (в окне MS-DOS используйте стандартные средства, в окне RXVT выделяйте текст мышью, а для копирования используйте Ctrl-Ins) и вставить его в текстовый файл (редактируемый, например, с помощью FAR или Блокнота).

9. Если имеются, используйте полосы прокрутки для просмотра информации, которая в процессе работы с системой переместилась за верхний край экрана.

10. Одной из составных частей системы GAP является ее документация. С помощью Проводника откройте каталог gap4r4/doc. В нем Вы обнаружите подкаталог htm, в котором нужно открыть файл index.htm - это стартовый файл для просмотра документации в HTML-формате. В зависимости от выбранного варианта инсталляции, возможно также наличие каталога htmie - в нем та же документация, оптимизированная для просмотра с помощью MS Internet Explorer). Для быстрого обращения к документации создайте в своем рабочем каталоге ярлык, указывающий на файл index.htm в одном из каталогов htm или htmie, после чего откройте его с помощью данного ярлыка и ознакомьтесь с названиями пяти основных разделов документации. Перейдите в раздел "Индекс" и найдите с его помощью описание функций Factorialи Sum. Вы можете копировать приведенные в документации примеры и выполнять их в GAP так, как это было описано в п.8.

При полной инсталляции системы каталог gap4r4/doc также содержит документацию и в других форматах. В частности, он содержит другие подкаталоги, наименования которых соответствуют пяти основным разделам документации, в которых можно найти эти разделы в формате PDF, более удобном при печати документации (учтите, что центральный раздел документации - Reference Manual - занимает в формате PDF почти тысячу страниц!).

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

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

12. Удобным свойством системы является автодополнение имен переменных при их вводе. Это означает, что если по первым буквам введенного имени переменной (в т.ч. имени функции) можно однозначно определить его окончание, то при нажатии клавиши Tab это окончание будет добавлено автоматически. Если же однозначности нет, то при повторном нажатии клавиши Tab будет предложен список всех возможных вариантов. Например, наберите в командной сроке Fib и нажмите Tab. Вычислите теперь 100-й элемент последовательности Фибоначчи, указав 100 в скобках в качестве аргумента. Затем наберите в командной строке Factor и нажмите Tab дважды для вывода на экран имен всех переменных, начинающихся с этого сочетания букв.

13. Историю работы с системой можно сохранить в текстовом файле (т.наз. файле протокола). Выберите одно из окон GAP, работа в котором Вам показалась более удобной - окно MS-DOS или окно RXVT. Введите команду


LogTo("logfile.txt");

После этого все введенные Вами команды и результаты их работы, отображаемые на экране, будут дублироваться в файле с именем logfile.txt, который содержится в Вашем рабочем каталоге.

Теперь выполните следующие вычисления: задайте сначала переменную n, в которой сохраните номер своего варианта, например:


n:=20;

Затем последовательно введите следующие команды:


a:=2^(n+1)-1;
IsPrime(a);
Factors(a);
x:=n+10;
Factors(Factorial(x));
Phi(x);
Sigma(x);
Tau(x);

Теперь закройте файл протокола с помощью команды


LogTo();

и просмотрите его с помощью, например, FAR или Проводника.

C.2 Списки. Целые числа

C.2-1 Инструкции по выполнению работы 2

Данная лабораторная работа предназначена для изучения приемов работы со списками на примере действий над целыми числами. Подробные сведения по данным темам содержатся:

Задания для лабораторной работы взяты из сборника задач [ГТ64], и после номера варианта указан номер соответствующей задачи в [ГТ64]. Студентам рекомендуется ознакомиться с приведенным в [ГТ64] решением данных задач, чтобы увидеть, что теоретическое их решение более эффективно, чем простой перебор, выполненный ими в учебных целях в данной лабораторной работе.

В зависимости от конкретной задачи, при выполнении работы полезными могут оказаться следующие функции и операции (детальное их описание см. в документации):

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

Сначала мы получим список этих чисел, а затем определим их количество:


gap> l := Filtered( [ 1 .. 120 ],  i -> 
>                   Length( Filtered( [2,3,5], j -> i mod j = 0 )  ) = 1 );
[ 2, 3, 4, 5, 8, 9, 14, 16, 21, 22, 25, 26, 27, 28, 32, 33, 34, 35, 38, 39,
  44, 46, 51, 52, 55, 56, 57, 58, 62, 63, 64, 65, 68, 69, 74, 76, 81, 82, 85,
  86, 87, 88, 92, 93, 94, 95, 98, 99, 104, 106, 111, 112, 115, 116, 117, 118 ]
gap> Length(l);
56

Этот же результат можно было бы получить и с помощью одной команды:


gap> Length( Filtered( [ 1 .. 120 ], i -> 
>                      Length( Filtered( [2,3,5], j -> i mod j = 0  ) ) = 1 ) );  
56

C.2-2 Варианты заданий для лабораторной работы 2

Вариант 1 (ГТ 65). Найти показатель степени числа 3 в каноническом разложении числа 100!.

Вариант (ГТ 66). Найти показатель степени числа 11 в каноническом разложении числа 1000!.

Вариант 3 (ГТ 67). Сколькими нулями оканчивается число 100! (предложить два способа решения данной задачи, не сводящихся к выводу 100! на экран и ручному подсчету нулей) ?

Вариант 4 (ГТ 68). Разложить на простые множители числа 10!, 15!, 20!, 25!, 30!.

Вариант 5 (ГТ 69). Найти количество целых положительных чисел, не превосходящих 180 и не делящихся ни на одно из простых чисел 5, 7, 11.

Вариант 6 (ГТ 70). Найти количество целых положительных чисел, не превосходящих 2311 и не делящихся ни на одно из простых чисел 5, 7, 11, 13.

Вариант 7 (ГТ 71). Найти количество целых положительных чисел, не превосходящих 100 и взаимно простых с 36.

Вариант 8 (ГТ 72). Найти количество целых положительных чисел, не превосходящих 12317 и взаимно простых с 1575.

Вариант 9 (ГТ 73). Найти количество целых положительных чисел, не превосходящих 1000 и не взаимно простых с 363.

Вариант 10 (ГТ 74). В ряду натуральных чисел 1, ... , 1800, начиная с единицы, вычеркивается каждое пятое, каждое восьмое и каждое девятое число. Сколько чисел не будет вычеркнуто?

Вариант 11 (ГТ 78). В урне 5000 шаров, перенумерованных от 1 до 5000. Какова вероятность того, что вынутый наудачу шар будет иметь номер, кратный какому-нибудь из чисел 14, 21, 10 ?

Вариант 12 (ГТ 84). Найти все делители чисел 360, 375, 957, 988 (предложить два способа решения, сравнить результаты).

Вариант 13 (ГТ 85). Найти целое положительное число, зная, что оно имеет только два простых делителя, число всех делителей равно 6, а сумма всех делителей равна 28.

Вариант 14 (ГТ 91). Найти целое положительное число, произведение всех делителей которого равно 5832.

Вариант 15 (ГТ 101). Сколько чисел в интервале от 1 до 120, не взаимно простых с 30 (предложить два способа решения, сравнить результаты)?

Вариант 16 (ГТ 113). Найти количество натуральных чисел, меньших числа 300 и имеющих с ним наибольшим общим делителем число 20.

Вариант 17 (ГТ 114). Найти количество натуральных чисел, меньших числа 1665 и имеющих с ним наибольшим общим делителем число 37.

Вариант 18 (ГТ 115). Найти количество натуральных чисел, меньших числа 1476 и имеющих с ним наибольшим общим делителем число 41.

C.3 Линейные программы. Векторы и матрицы

C.3-1 Инструкции по выполнению работы 3

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

Пример: Разработать функцию для вычисления суммы элементов побочной диагонали матрицы A третьего порядка, входным параметром которой является матрица A, а выходным - указанная сумма.

Для этого создадим в рабочем каталоге (созданном в соответствии с инструкциями лабораторной работы C.1) файл lab3.g следующего содержания:


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

Теперь прочитаем его с помощью следующей команды (если система GAP запущена из другого каталога, то нужно будет указать полный путь к файлу):


Read("lab3.g");

Теперь мы можем обращаться к функции SumDiag, например:


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

Данную функцию можно было бы разработать и более универсальным образом для работы с матрицами любого порядка (ее доработку для проверки того, что матрица является квадратной, мы оставляем читателю):


BetterSumDiag:=function(A)
local i, nrows, ncols;
nrows := Length( A );    # количество строк
ncols := Length( A[1] ); # количество столбцов
return Sum( List( [ 1 .. nrows ], i -> A[i][ncols-i+1] ) );
end;

При разработке функций обратите внимание на следующее:

C.3-2 Варианты заданий для лабораторной работы 3

Вариант 1. Разработать функцию для вычисления объема треугольной пирамиды, заданной координатами своих вершин, с помощью смешанного произведения векторов.

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

Вариант 3. Разработать функцию для вычисления определителя матрицы A второго порядка, входным параметром которой является матрица A, а выходным - ее определитель, вычисленный по формуле det A = a_11 a_22 - a_12 a_21.

Вариант 4. Разработать функцию для вычисления определителя матрицы A третьего порядка, входным параметром которой является матрица A, а выходным - ее определитель, вычисленный по правилу Саррюса.

Вариант 5. Разработать функцию для вычисления векторного произведения двух векторов, заданных своими координатами в ПДСК, входными параметрами которой являются два вектора u и v, а выходным - вектор, являющийся их векторным произведением.

Вариант 6. Разработать функцию для вычисления векторного произведения двух векторов, заданных координатами их начал и концов в ПДСК, входными параметрами которой являются координаты четырех точек пространства, соответствующих началу и концу векторов u и v, а выходным - вектор, являющийся их векторным произведением.

Вариант 7. Разработать функцию для вычисления произведения двух матриц второго порядка непосредственно по определению произведения матриц (т.е. не используя имеющуюся в GAP операцию умножения матриц), входными параметрами которой являются матрицы A и B, а выходным - матрица C = AB.

Вариант 8. Разработать функцию для транспонирования матрицы третьего порядка непосредственно по определению транспонирования матриц (т.е. не используя имеющуюся в GAP операцию транспонирования), входным параметром которой является матрица A, а выходным - матрица A^T.

Вариант 9. Разработать функцию для вычисления скалярного произведения двух векторов, заданных своими координатами в ПДСК (не используя имеющуюся в GAP операцию скалярного умножения векторов), входными параметрами которой являются два вектора u и v, а выходным - их скалярное произведение.

Вариант 10. Разработать функцию для вычисления скалярного произведения двух векторов, заданных координатами их начал и концов в ПДСК (не используя имеющуюся в GAP операцию скалярного умножения векторов), входными параметрами которой являются координаты четырех точек пространства, соответствующих началу и концу векторов u и v, а выходным - их скалярное произведение.

Вариант 11. Разработать функцию для вычисления перманента матрицы A второго порядка, входным параметром которой является матрица A, а выходным - ее перманент, равный a_11 a_22 + a_12 a_21.

Вариант 12. Разработать функцию для вычисления перманента матрицы A третьего порядка, входным параметром которой является матрица A, а выходным - ее перманент, равный сумме шести слагаемых, каждое из которых является произведением трех элементов матрицы A, взятых по одному из каждой строки и каждого столбца.

Вариант 13. Разработать функцию для вычисления следа матрицы второго порядка, входным параметром которой является матрица A, а выходным ее след, равный сумме элементов ее главной диагонали.

Вариант 14. Разработать функцию для вычисления следа матрицы третьего порядка, входным параметром которой является матрица A, а выходным ее след, равный сумме элементов ее главной диагонали.

Вариант 15. Разработать функцию, входным параметром которой являются координаты двух точек плоскости A и B, а выходным - координаты середины отрезка AB.

Вариант 16. Разработать функцию, входным параметром которой являются координаты двух точек пространства A и B,а выходным - координаты середины отрезка AB.

Вариант 17. Разработать функцию для вычисления образа вектора u = ( u_1, u_2, u_3 ) под действием линейного оператора f, заданного матрицей A (не используя имеющуюся в GAP операцию умножения матрицы на вектор), входными параметрами которой являются матрица A и координаты вектора u, а выходным - координаты вектора Au.

Вариант 18. Разработать функцию для вычисления Лиевского коммутатора [A,B] двух квадратных матриц A и B произвольного порядка n, входными параметрами которой являются матрицы A и B, а выходным - матрица D = AB - BA.

C.4 Ветвящиеся программы. Многочлены

C.4-1 Инструкции по выполнению работы 4

Данная лабораторная работа предназначена для изучения оператора условного перехода на примере работы с многочленами от одной переменной.

Подробные сведения по данным темам содержатся:

Пример: Разработать функцию, которая определяет, являются ли коэффициенты заданного многочлена взаимно простыми, и в случае положительного ответа возвращает исходный многочлен, а в случае отрицательного - исходный многочлен, разделенный на НОД своих коэффициентов.

Перед тем, как приступить к разработке функции, попробуем понять схему ее работы в диалоговом режиме. Зададим переменную х и многочлен f от этой переменной, затем получим список коэффициентов многочлена f, найдем их наибольший общий делитель d и разделим на него многочлен f :


gap> x:=Indeterminate(Rationals,"x");
x
gap> f:=20*x^3+15*x^2+10*x+5;
20*x^3+15*x^2+10*x+5
gap> CoefficientsOfUnivariatePolynomial(f);
[ 5, 10, 15, 20 ]
gap> d:=Gcd(last);
5
gap> f/5;
4*x^3+3*x^2+2*x+1

Теперь в рабочем каталоге создадим текстовый файл следующего содержания (подробные инструкции по работе с файлами см. в лабораторной работе C.3):


CoeffCancellation := function( f )
local d;
d := Gcd( CoefficientsOfUnivariatePolynomial( f ) );
if d<>1 then
  return f/d;
else
  return f;
fi;
end;

После чтения данной программы (см. пример из лабораторной работы C.3 мы можем обращаться к функции CoeffCancellation. Для проверки правильности работы обеих алгоритма сначала применим ее к ранее заданному многочлену f, а затем к многочлену g, коэффициенты которого уже являются взаимно простыми:


gap> CoeffCancellation(f);
4*x^3+3*x^2+2*x+1
gap> g:=x^3+x^2+10*x+5;
x^3+x^2+10*x+5
gap> CoeffCancellation(g);
x^3+x^2+10*x+5</C>

Очевидно, что программа работает корректно. При разработке функций обратите внимание на следующее:

C.4-2 Варианты заданий для лабораторной работы 4

Вариант 1. Разработать функцию, которая определяет, имеет ли заданный многочлен f корни кратности выше первой, и в случае отрицательного ответа возвращает исходный многочлен, а в случае положительного - многочлен g, имеющий те же корни, что и исходный, но только первой кратности (при этом для нахождения многочлена g необходимо разделить многочлен f на наибольший общий делитель многочлена f и его производной f' ). Примечание: использовать функции Gcd, Derivative, IsOne.

Вариант 2. Разработать функцию, которая определяет, являются ли два заданных многочлена f и g взаимно простыми, и в случае положительного ответа возвращает их произведение, а в случае отрицательного - их произведение, разделенное на их наибольший общий делитель. Примечание: использовать функции Gcd, IsOne.

Вариант 3. Разработать функцию, которая определяет, имеет ли заданный многочлен f разные знаки на концах заданного интервала [a,b], и в случае положительного ответа возвращает среднее арифметическое значений многочлена на концах интервала, а в случае отрицательного - наибольшее из значений многочлена на концах интервала. Примечание: использовать функции Value, Maximum.

Вариант 4. Разработать функцию, которая определяет, все ли коэффициенты заданного многочлена f являются четными, и в случае отрицательного ответа возвращает исходный многочлен, а в случае положительного - многочлен (1/2)*f.

Вариант 5. Разработать функцию, которая определяет, разлагается ли заданный многочлен f в произведение линейных множителей, и в случае положительного ответа возвращает их произведение, а в случае отрицательного - единицу. Примечание: использовать функции Factors, Degree.

Вариант 6. Разработать функцию, которая определяет, совпадают ли степени двух заданных многочленов f и g, и в случае положительного ответа возвращает их сумму, а в случае отрицатльного - произведение. Примечание: использовать функцию Degree.

Вариант 7. Разработать функцию, которая определяет, имеет ли заданный многочлен f четную степень, и в случае отрицательного ответа возвращает исходный многочлен, а в случае положительного - многочлен x * f. Примечание: использовать функции Degree, IndeterminateOfUnivariateRationalFunction.

Вариант 8. Разработать функцию, которая определяет, равен ли нулю свободный член заданного многочлена, и в случае отрицательного ответа возвращает исходный многочлен, а в случае положительного - многочлен f/x. Примечание: использовать функцию IndeterminateOfUnivariateRationalFunction.

Вариант 9. Разработать функцию, которая определяет, равна ли единице сумма коэффицентов заданного многочлена f, и в случае положительного ответа возвращает исходный многочлен, а в случае отрицательного - многочлен, полученный из многочлена f делением его на сумму своих коэффициентов.

Вариант 10. Разработать функцию, которая определяет, равен ли единице старший коэффициент заданного многочлена f, и в случае положительного ответа возвращает исходный многочлен, а в случае отрицательного - многочлен, полученный из многочлена f делением его на свой старший коэффициент.

Вариант 11. Разработать функцию, которая определяет, равна ли нулю сумма коэффицентов заданного многочлена f, и в случае положительного ответа возвращает исходный многочлен, а в случае отрицательного - многочлен, полученный из многочлена f вычитанием из него суммы своих коэффициентов.

Вариант 12. Разработать функцию, которая определяет, равна ли единице сумма коэффицентов заданного многочлена f, и в случае положительного ответа возвращает исходный многочлен, а в случае отрицательного - многочлен, полученный из многочлена f вычитанием из него суммы своих коэффициентов и прибавлением единицы.

Вариант 13. Разработать функцию, которая определяет, имеет ли заданный многочлен f нечетную степень, и в случае отрицательного ответа возвращает исходный многочлен, а в случае положительного - многочлен x * f. Примечание: использовать функции Degree, IndeterminateOfUnivariateRationalFunction.

Вариант 14. Разработать функцию, которая определяет, равна ли нулю производная заданного многочлена f в заданной точке a, и в случае отрицательного ответа возвращает значение производной многочлена f в точке a, а в случае положительного - значение многочлена f в точке a. Примечание: использовать функции Derivative, Value.

Вариант 15. Разработать функцию, которая определяет, положительно ли значение заданного многочлена f в заданной точке a, и в случае отрицательного ответа возвращает значение производной многочлена f в точке a, а в случае положительного - значение многочлена f в точке a. Примечание: использовать функции Derivative, Value.

Вариант 16. Разработать функцию, которая определяет, отрицательно ли значение заданного многочлена f в заданной точке a, и в случае отрицательного ответа возвращает значение производной многочлена f в точке a, а в случае положительного - значение многочлена f в точке a. Примечание: использовать функции Derivative, Value.

Вариант 17. Разработать функцию, которая определяет, все ли коэффициенты заданного многочлена f делятся на три, и в случае отрицательного ответа возвращает исходный многочлен, а в случае положительного - многочлен f/3.

Вариант 18. Разработать функцию, которая определяет, равен ли единице свободный член заданного многочлена f, и в случае положительного ответа возвращает исходный многочлен, а в случае отрицательного - многочлен, полученный из многочлена f делением его на свой свободный член.

C.5 Циклические программы (цикл FOR). Бинарные отношения

C.5-1 Инструкции по выполнению работы 5

Данная лабораторная работа предназначена для изучения оператора цикла FOR на примере работы с бинарными отношениями. Подробные сведения по данным темам содержатся:

Пример: Разработать функцию, входным параметром которой является бинарное отношение r, заданное на множестве из n элементов, а выходным - квадратная матрица M порядка n × n, в которой m_ij=1, если i и j находятся в бинарном отношении ρ, и m_ij=0 в противном случае (таким образом, M - матрица смежности ориентированного графа, соответствующего бинарному отношению ρ).

Данная задача решается следующим образом. Сначала мы определяем порядок множества N, на котором задано бинарное отношение r, и строим нулевую матрицу m соответствующего размера с помощью функции NullMat. Затем с помощью функции Successors мы получаем список s, i-й элемент которого является списком номеров тех элементов множества N, которые находятся в бинарном отношении ρ c i-м элементом. Для замены нужных элементов нулевой матрицы единицами мы перебираем элементы полученного списка s. При этом i-й элемент списка s определяет, какие элементы i-й строки матрицы m должны быть равны единице - на единицу заменяются те элементы i-й строки матрицы m, которые лежат в столбцах с номерами из списка s[i]:


MatrixOfBinaryRelation:=function(r)
local s, n, m, i, j;
n := DegreeOfBinaryRelation( r );
 m := NullMat( n, n );
s := Successors( r );
for i in [ 1 .. Length(s) ] do
  for j in s[i] do
    m[i][j]:=1;
  od;
od;
return m;
end;

Обратите внимание на форматирование программы (выделение циклов с помощью отступов), а также на то, что перебирать можно не только числа из заданного диапазона (как во внешнем цикле), но и все элементы из заданного списка (как во внутреннем цикле).

После ввода данной программы зададим случайным образом бинарное отношение на множестве из пяти элементов:


gap> r:=RandomBinaryRelationOnPoints(5);
Binary Relation on 5 points

Получим его описание с помощью функции Successors:


gap> Successors(r);
[ [ 1, 2, 4 ], [ 1, 3, 4, 5 ], [ 3, 5 ], [ 2, 4, 5 ], [ 2, 3, 4 ] ]

Теперь вычислим его матрицу смежности и убедимся в правильности полученного результата, сопоставив номера строк и столбцов, в которых находятся единицы, с результатом Successors(r) :


gap> Display( MatrixOfBinaryRelation( r ) );
[ [  1,  1,  0,  1,  0 ],
  [  1,  0,  1,  1,  1 ],
  [  0,  0,  1,  0,  1 ],
  [  0,  1,  0,  1,  1 ],
  [  0,  1,  1,  1,  0 ] ]

Вычислим матрицу смежности для минимального симметричного бинарного отношения, содержащего заданное, и убедимся в ее симметричности относительно главной диагонали:


gap> Display( MatrixOfBinaryRelation( SymmetricClosureBinaryRelation( r ) ) );
[ [  1,  1,  0,  1,  0 ],
  [  1,  0,  1,  1,  1 ],
  [  0,  1,  1,  0,  1 ],
  [  1,  1,  0,  1,  1 ],
  [  0,  1,  1,  1,  0 ] ]

Вычислим матрицу смежности для минимального рефлексивного бинарного отношения, содержащего заданное, и убедимся в том, что все элементы на ее главной диагонали равны единице:


gap> Display( MatrixOfBinaryRelation( ReflexiveClosureBinaryRelation( r ) ) );       
[ [  1,  1,  0,  1,  0 ],
  [  1,  1,  1,  1,  1 ],
  [  0,  0,  1,  0,  1 ],
  [  0,  1,  0,  1,  1 ],
  [  0,  1,  1,  1,  1 ] ]

Теперь проверим, что матрица отношения тождества является единичной:


gap> Display( MatrixOfBinaryRelation( IdentityBinaryRelation( 5 ) ) );               
[ [  1,  0,  0,  0,  0 ],
  [  0,  1,  0,  0,  0 ],
  [  0,  0,  1,  0,  0 ],
  [  0,  0,  0,  1,  0 ],
  [  0,  0,  0,  0,  1 ] ]

Таким образом, разработанная функция работает корректно.

C.5-2 Варианты заданий для лабораторной работы 5

Вариант 1. Разработать функцию, которая для заданного бинарного отношения возвращает бинарное отношение, являющееся его отрицанием.

Вариант 2. Разработать функцию, которая для двух заданных бинарных отношений возвращает бинарное отношение, являющееся их пересечением.

Вариант 3. Разработать функцию, которая для двух заданных бинарных отношений возвращает бинарное отношение, являющееся их объединением.

Вариант 4. Разработать функцию, которая для двух заданных бинарных отношений возвращает бинарное отношение, являющееся разностью первого и второго отношений.

Вариант 5. Разработать функцию, которая для двух заданных бинарных отношений возвращает бинарное отношение, являющееся композицией первого и второго отношений.

Вариант 6. Разработать функцию, которая для заданного бинарного отношения возвращает обратное к нему бинарное отношение.

Вариант 7. Разработать функцию, которая для двух заданных бинарных отношений проверяет, является ли первое из них подмножеством второго.

Вариант 8. Разработать функцию, которая возвращает бинарное отношение, соответствующее заданному разбиению множества первых n натуральных чисел.

Вариант 9. Разработать функцию, которая возвращает список всех упорядоченных пар, принадлежащих заданному бинарному отношению.

Вариант 10. Разработать функцию, которая для заданного бинарного отношения ρ возвращает список элементов x, для которых выполняется условие x ρ x.

Вариант 11. Разработать функцию, которая для заданного бинарного отношения ρ возвращает список всех упорядоченных пар элементов (x,y), для которых одновременно выполняются условия x ρ y и y ρ x.

Вариант 12. Разработать функцию, которая для заданного бинарного отношения r возвращает список всех упорядоченных пар элементов (x,y), таких что которых выполняется условие x r y, но не выполняется условие y r x.

Вариант 13. Разработать функцию, которая для заданного бинарного отношения r возвращает список всех упорядоченных пар элементов (x,y), таких что которых выполняется условие x r y, и элементы x и y не совпадают.

Вариант 14. Разработать функцию, которая для заданного бинарного отношения определяет минимальный набор упорядоченных пар, которые нужно исключить из бинарного отношения для того, чтобы оно стало антирефлексивным.

Вариант 15. Разработать функцию, которая для заданного бинарного отношения определяет минимальный набор упорядоченных пар, которые нужно исключить из бинарного отношения для того, чтобы оно стало асимметричным.

Вариант 16. Разработать функцию, которая для заданного бинарного отношения определяет минимальный набор упорядоченных пар, которые нужно исключить из бинарного отношения для того, чтобы оно стало антисимметричным.

Вариант 17. Разработать функцию, которая возвращает область определения заданного бинарного отношения.

Вариант 18. Разработать функцию, которая возвращает область значения заданного бинарного отношения.

C.6 Циклические программы (цикл WHILE). Подстановки

C.6-1 Инструкции по выполнению работы 6

Данная лабораторная работа предназначена для изучения оператора цикла WHILE на примере работы с подстановками. Подробные сведения по данным темам содержатся:

Пример: Разработать функцию, которая определяет порядок заданной подстановки, определяя минимальную степень, в которую нужно ее возвести, чтобы получить тождественную подстановку.

Данная задача решается с помощью следующей функции:


OrderOfPermutation:=function(s)
local k, t;
k:=1; 
t:=s; 
while t <> () do
  t:=t*s;
  k:=k+1;
od; 
return k;
end;

Имя функции OrderOfPermutation было выбрано таким образом, чтобы оно не совпадало с именем имеющейся в GAP стандартной функции OrderPerm - иначе при ее вводе было бы получено сообщение об ошибке, т.к. библиотечные функции защищены от переопределения пользователем.

После ввода данной программы протестируем ее на различных подстановках:


gap> OrderOfPermutation( () );
1
gap> OrderOfPermutation( (1,2) );
2
gap> OrderOfPermutation( (1,2,3) );
3
gap> OrderOfPermutation( (1,2,3)(4,5) );
6

Заметим, что порядок подстановки равен наименьшему общему кратному длин независимых циклов в ее разложении (см. последний пример), и использование этого факта позволило бы более эффективно найти порядок подстановки, избежав ее возведения в степень. Поэтому данный пример применим только в учебных целях. Сравним быстродействие нашей функции со стандартной:


gap> for i in [1..1000] do
>      k:=OrderPerm( (1,2,3,4,5)(6,7,8)(9,10)(11,12,13,14,15)(16,17,18) );
>    od;
gap> time;
384
gap> for i in [1..1000] do
>      k:=OrderOfPermutation( (1,2,3,4,5)(6,7,8)(9,10)(11,12,13,14,15)(16,17,18) );
>    od;
gap> time;
743

Таким образом, мы видим, что стандартная функция более эффективна.

Получим с помощью нашей функции список порядков всех элементов симметрической группы подстановок третьей степени:


gap> List( SymmetricGroup(3), OrderOfPermutation );
[ 1, 2, 3, 2, 3, 2 ]

Повторим то же самое для симметрической группы подстановок пятой степени, сгруппировав результаты:


gap> Collected( List( SymmetricGroup(5), OrderOfPermutation ) );
[ [ 1, 1 ], [ 2, 25 ], [ 3, 20 ], [ 4, 30 ], [ 5, 24 ], [ 6, 20 ] ]

Таким образом, в ней 25 элементов второго порядка, 20 - третьего, 30 - четвертого, 24 - пятого, и 20 - шестого порядка.

C.6-2 Варианты заданий для лабораторной работы 6

Примечание: необходимо разработать собственную функцию с обязательным применением цикла WHILE, независимо от того, решается ли задача прямым применением стандартной функции системы GAP или нет. Вариант 1. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, такое что s^k коммутирует с заданной подстановкой t.

Вариант 2. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, такое что s^k переводит заданное натуральное число n в заданное натуральное число m, и возвращает fail, если такого числа k не существует.

Вариант 3. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, которое она оставляет на месте.

Вариант 4. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, такое что s^k оставляет на месте заданное натуральное число n.

Вариант 5. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, такое что количество натуральных чисел, перемещаемых подстановкой s^k, не превосходит заданного натурального числа n.

Вариант 6. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, такое что s^k оставляет на месте единицу.

Вариант 7. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, такое что s^k коммутирует с подстановкой ( 1 2 ).

Вариант 8. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, такое что s^k переводит 1 в 2, и возвращает fail, если такого числа k не существует.

Вариант 9. Разработать функцию, которая для заданной подстановки s вычисляет орбиту числа 1, т.е. множество всех чисел, в которые единицу можно перевести с помощью некоторой степени s^k исходной подстановки.

Вариант 10. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, такое что количество натуральных чисел, перемещаемых подстановкой s^k, не превосходит 5.

Вариант 11. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, такое что s^k оставляет на месте наибольшее число, перемещаемое данной постановкой.

Вариант 12. Разработать функцию, которая для заданной подстановки s определяет максимальное натуральное число k, такое что s^k не коммутирует с подстановкой ( 1 2 ).

Вариант 13. Разработать функцию, которая для заданной подстановки s определяет максимальное натуральное число k, такое что количество натуральных чисел, перемещаемых подстановкой s^k, превосходит заданное натуральное число n, и возвращает fail, если такого числа k не существует.

Вариант 14. Разработать функцию, которая для заданной подстановки s вычисляет орбиту наименьшего числа, перемещаемого данной подстановкой, т.е. множество всех чисел, в которые его можно перевести с помощью некоторой степени s^k исходной подстановки.

Вариант 15. Разработать функцию, которая для заданной подстановки s возвращает множество орбит чисел, перемещаемых данной подстановкой.

Вариант 16. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, такое что s^k оставляет на месте наименьшее число, перемещаемое данной постановкой.

Вариант 17. Разработать функцию, которая для заданной подстановки s вычисляет орбиту наибольшего числа, перемещаемого данной подстановкой, т.е. множество всех чисел, в которые его можно перевести с помощью некоторой степени s^k исходной подстановки.

Вариант 18. Разработать функцию, которая для заданной подстановки s определяет максимальное натуральное число k, такое что количество натуральных чисел, перемещаемых подстановкой s^k, превосходит 5, и возвращает fail, если такого числа k не существует.

C.7 Циклические программы (цикл REPEAT). Группы подстановок

C.7-1 Инструкции по выполнению работы 7

Данная лабораторная работа предназначена для изучения оператора цикла REPEAT на примере работы с подстановками и группами подстановок. Подробные сведения по данным темам содержатся:

Пример: Разработать функцию, которая выбирает случайным образом элемент заданной группы подстановок, действующей на множестве M = {1,...,n}, до тех пор, пока не обнаружит подстановку, которая переставляет все точки множества M, и возвращает найденную подстановку.

Сначала нужно понять, как определить порядок множества M, и как понять, что заданная подстановка не имеет неподвижных точек. Для этого поэкспериментируем в диалоговом режиме с некоторыми функциями из раздела "Подстановки в системе GAP" (http://www.gap-system.org/ukrgap/Examples/permutat.htm):


gap> G:=SymmetricGroup(3);
Sym( [ 1 .. 3 ] )
gap> LargestMovedPoint(G);
3
gap> s:=(1,2);
(1,2)
gap> NrMovedPoints(s);
2
gap> t:=(1,2,3);
(1,2,3)
gap> NrMovedPoints(t);
3

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


FindFixedPointFreePermutation:=function(G)
local n,s;
n:=LargestMovedPoint(G);
repeat
  s := Random(G);
until NrMovedPoints(s) = n;
return s;
end;

Протестируем ее на различных группах:


gap> G:=SymmetricGroup(3);
Sym( [ 1 .. 3 ] )
gap> FindFixedPointFreePermutation(G);
(1,3,2)
gap> FindFixedPointFreePermutation(AlternatingGroup(4));
(1,2)(3,4)
gap> FindFixedPointFreePermutation(AlternatingGroup(5));
(1,3,5,4,2)
gap> G:=SymmetricGroup(30);
Sym( [ 1 .. 30 ] )
gap> Size(G);
265252859812191058636308480000000
gap> FindFixedPointFreePermutation(G);
(1,23)(2,19,10,8,3)(4,12,5,28,6,13,14,29,11,21,20,24,26,18,16,17)(7,27,15,9,25,30,22)

Заметим, что условие M={1,...,n} в постановке задачи существенно, так как программа зацикливается в следующем примере:


gap> G:=Group((2,3));
Group([ (2,3) ])
gap> FindFixedPointFreePermutation(G);

Такое поведение объясняется тем, что в этом случае LargestMovedPoint(G) возвращает 3. Естественно, что никакая подстановка из группы G не перемещает три точки, и поэтому нужное условие никогда не достигается. С другой стороны, функция NrMovedPoints(G) возвращает 2, и нужно использовать именно ее. Поэтому для большей универсальности нашу функцию нужно модифицировать следующим образом:


FindFixedPointFreePermutation:=function(G)
local n,s;
n:=NrMovedPoints(G);
repeat
  s := Random(G);
until NrMovedPoints(s) = n;
return s;
end;

Проверим теперь ее работу:


gap> G:=Group((2,3));
Group([ (2,3) ])
gap> FindFixedPointFreePermutation(G);
(2,3)
gap> FindFixedPointFreePermutation(SymmetricGroup(10));
(1,2)(3,5,9,8)(4,10)(6,7)
gap> FindFixedPointFreePermutation(SymmetricGroup(100));
(1,11,24,8,37,73,62,38,97,54,88,47,2,60,50,56,19,84,67,65,32,69,14,4,10,6,33,
52,83,70,5,29,91,86,77,78,43,61,35,3,22,57,95,85,23)(7,98,16,28,34,13,48,39,
46,90,45,40,21,42,36,18,17,58,76,74)(9,96,92,15,89,41,93,59,75)(12,79,30,94,
99,51,53,31,81,63,44,55)(20,82,71)(25,80,49,68,26,87,64,100,27,72,66)

Мы видим, что она работает корректно как с группами, оставляющими единицу на месте, так и с симметрическими группами подстановок.

Иногда при тестировании гипотез интересно отбражать динамику расчета на экране и проследить, сколько попыток выбора случайного элемента из группы было сделано, прежде чем был найден элемент с необходимыми свойствами. Для этого можно вставить в функцию счетчик и отображать его текущее значение на экране. При этом управляющая строка "\r" используется для стирания результата предыдущего вывода на экран и печати новой информации в той же строке:


FindFixedPointFreePermutation:=function(G)
local n,s,k;
n:=NrMovedPoints(G);
k:=0;
repeat
  s := Random(G);
  k := k+1;
  Print(k, "\r");
until NrMovedPoints(s) = n;
Print("\n");
return s;
end;

Теперь скопируйте в окно GAP последний вариант нашей функции и обратитесь к ней несколько раз для какой-нибудь довольно большой группы. Посмотрите, сколько шагов в среднем требуется для нахождения нужной подстановки.

C.7-2 Варианты заданий для лабораторной работы 7

В данной лабораторной работе Вам необходимо решить ту же задачу, что и в работе C.6, но только с применением цикла REPEAT вместо цикла WHILE. Кроме того, при тестировании разработанной Вами функции Вы должны вместо непосредственного задания подстановки сначала задать некоторую группу подстановок (например, симметрическую, знакопеременную, или порожденную указанным Вами списком подстановок), после чего выбрать случайным образом ее элемент(ы) для использования в качестве аргумента Вашей функции.

Вариант 1. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, такое что s^k коммутирует с заданной подстановкой t.

Вариант 2. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, такое что s^k переводит заданное натуральное число n в заданное натуральное число m, и возвращает fail, если такого числа k не существует.

Вариант 3. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, которое она оставляет на месте.

Вариант 4. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, такое что s^k оставляет на месте заданное натуральное число n.

Вариант 5. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, такое что количество натуральных чисел, перемещаемых подстановкой s^k, не превосходит заданного натурального числа n.

Вариант 6. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, такое что s^k оставляет на месте единицу.

Вариант 7. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, такое что s^k коммутирует с подстановкой ( 1 2 ).

Вариант 8. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, такое что s^k переводит 1 в 2, и возвращает fail, если такого числа k не существует.

Вариант 9. Разработать функцию, которая для заданной подстановки s вычисляет орбиту числа 1, т.е. множество всех чисел, в которые единицу можно перевести с помощью некоторой степени s^k исходной подстановки.

Вариант 10. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, такое что количество натуральных чисел, перемещаемых подстановкой s^k, не превосходит 5.

Вариант 11. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, такое что s^k оставляет на месте наибольшее число, перемещаемое данной постановкой.

Вариант 12. Разработать функцию, которая для заданной подстановки s определяет максимальное натуральное число k, такое что s^k не коммутирует с подстановкой ( 1 2 ).

Вариант 13. Разработать функцию, которая для заданной подстановки s определяет максимальное натуральное число k, такое что количество натуральных чисел, перемещаемых подстановкой s^k, превосходит заданное натуральное число n, и возвращает fail, если такого числа k не существует.

Вариант 14. Разработать функцию, которая для заданной подстановки s вычисляет орбиту наименьшего числа, перемещаемого данной подстановкой, т.е. множество всех чисел, в которые его можно перевести с помощью некоторой степени s^k исходной подстановки.

Вариант 15. Разработать функцию, которая для заданной подстановки s возвращает множество орбит чисел, перемещаемых данной подстановкой.

Вариант 16. Разработать функцию, которая для заданной подстановки s определяет минимальное натуральное число k, такое что s^k оставляет на месте наименьшее число, перемещаемое данной постановкой.

Вариант 17. Разработать функцию, которая для заданной подстановки s вычисляет орбиту наибольшего числа, перемещаемого данной подстановкой, т.е. множество всех чисел, в которые его можно перевести с помощью некоторой степени s^k исходной подстановки.

Вариант 18. Разработать функцию, которая для заданной подстановки s определяет максимальное натуральное число k, такое что количество натуральных чисел, перемещаемых подстановкой s^k, превосходит 5, и возвращает fail, если такого числа k не существует.

C.8 Изучение свойств элементов группы

C.8-1 Инструкции по выполнению работы 8

Данная лабораторная работа предназначена для изучения некоторых приемов работы с элементами групп.

Подробные сведения по данным темам содержатся:

Пример: Найти все 2-элементные множества, порождающие симметрическую группу S_3.

В интерактивном режиме эту задачу можно решить следующим образом:


gap> S:=SymmetricGroup(3); # исходная группа
Sym( [ 1 .. 3 ] )
gap> g:=AsList(S); # список ее элементов
[ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ]
gap> m:=Combinations(g,2); # всевозможные неупорядоченные пары
[ [ (), (2,3) ], [ (), (1,2) ], [ (), (1,2,3) ], [ (), (1,3,2) ],
  [ (), (1,3) ], [ (2,3), (1,2) ], [ (2,3), (1,2,3) ], [ (2,3), (1,3,2) ],
  [ (2,3), (1,3) ], [ (1,2), (1,2,3) ], [ (1,2), (1,3,2) ], [ (1,2), (1,3) ],
  [ (1,2,3), (1,3,2) ], [ (1,2,3), (1,3) ], [ (1,3,2), (1,3) ] ]
gap> Length(m); # всего 15 пар элементов
15
gap> Filtered(m, t -> S=Subgroup(S,t) ); # отбираем пары, порождающие всю группу
[ [ (2,3), (1,2) ], [ (2,3), (1,2,3) ], [ (2,3), (1,3,2) ], [ (2,3), (1,3) ],
  [ (1,2), (1,2,3) ], [ (1,2), (1,3,2) ], [ (1,2), (1,3) ],
  [ (1,2,3), (1,3) ], [ (1,3,2), (1,3) ] ]
gap> Length(last);  # осталось только 9 пар элементов
9

При разработке функции аналогичного назначения можно организовать двойной перебор элементов группы для того, чтобы более оптимально расходовать память и не держать в ней одновременно весь список всех неупорядоченных пар элементов группы (еще одно упрощение может быть получено исключением из рассмотрения нейтрального элемента группы - сделайте это самостоятельно). Такая функция будет выглядеть следующим образом:


FindGeneratingPairs:=function(G)
local g, n, i, j, s;
g := AsList( G );
n := Size( G );
s := [ ];
for i in [ 1 .. n-1 ] do
  for j in [ i+1 .. n ] do
    if G = Subgroup( G, [ g[i], g[j] ] ) then
      Add(s, [ g[i], g[j] ]);
    fi;
  od;
od;
return s;
end;

Протестируем ее и проверим, что результат совпадает с полученным ранее:


gap> S:=SymmetricGroup(3);
Sym( [ 1 .. 3 ] )
gap> FindGeneratingPairs(S);
[ [ (2,3), (1,2) ], [ (2,3), (1,2,3) ], [ (2,3), (1,3,2) ], [ (2,3), (1,3) ], 
  [ (1,2), (1,2,3) ], [ (1,2), (1,3,2) ], [ (1,2), (1,3) ], 
  [ (1,2,3), (1,3) ], [ (1,3,2), (1,3) ] ]

Заметьте, что любое 2-элементное подмножество группы S_3, не равное { (1 2 3), (1 3 2) } и не содержащее тождественной подстановки, порождает всю группу S_3.

C.8-2 Варианты заданий для лабораторной работы 8

Вариант 1. Разработать функцию для непосредственной проверки того, что заданная группа является коммутативной, путем перемножения всевозможных пар ее порождающих элементов. Указание: использовать функцию GeneratorsOfGroups.

Вариант 2. Разработать функцию для проверки того, что знакопеременная группа A_n порождается всевозможными циклами длины 3, и проверить с ее помощью данное утверждение для всех n, не превосходящих 7.

Вариант 3. Разработать функцию, которая возвращает множество элементов заданной группы, имеющих порядок, равный заданному числу k. Указание: использовать функции AsList, Order.

Вариант 4. Разработать функцию, которая возвращает множество порядков элементов заданной группы. Указание: использовать функции AsList, Order, Set.

Вариант 5. Проверить, выполняется ли в группе подстановок S_3 тождество ((x,y),z)=1, где (a,b) = a^-1b^-1ab.

Вариант 6. Известно, что при четном n>4 знакопеременная группа A_n порождается двумя подстановками: (1 2)(n-1 n) и (1 2 dots n-1). Проверить это утверждение для всех n, не превосходящих 10.

Вариант 7. Проверить, выполняется ли в группе подстановок S_3 тождество x^6=1.

Вариант 8. Проверить, что знакопеременная группа A_5 порождается подстановками (2 5 4) и (1 2 3 4 5).

Вариант 9. Проверить, выполняется ли в группе подстановок S_3 тождество (x^2,y^2)=1, где (a,b) = a^-1b^-1ab.

Вариант 10. Известно, что при нечетном n>5 знакопеременная группа A_n порождается двумя подстановками: (1 n)(2 n-1) и (1 2dots n-2). Проверить это утверждение для всех n, не превосходящих 10.

Вариант 11. Проверить что группа подстановок S_n порождается транспозицией (1 2) и циклом (1 2 dots n), для всех n, не превосходящих 10.

Вариант 12. Разработать функцию, которая возвращает множество порядков классов сопряженных элементов заданной группы. Указание: использовать функцию ConjugacyClasses.

Вариант 13. Разработать функцию, которая для заданной конечной группы определяет множество индексов циклических подгрупп, порождаемых ее элементами.

Вариант 14. Разработать функцию, печатающую для заданного натурального n таблицу Кэли для симметрической группы S_n.

Вариант 15. Разработать функцию, которая вычисляет подгруппу заданной p-группы, порожденную p-ми степенями ее элементов.

Вариант 16. Разработать функцию, которая вычисляет подгруппу заданной p-группы, порожденную всеми ее элементами порядка p.

Вариант 17. Разработать функцию для вычисления показателя (экспоненты) конечной группы как наименьшего общего кратного порядков представителей классов сопряженных элементов данной группы. Указание: использовать функцию ConjugacyClasses.

Вариант 18. Разработать функцию для вычисления количества элементов каждого порядка в заданной группе.

C.9 Изучение свойств подгрупп группы

C.9-1 Инструкции по выполнению работы 9

Данная лабораторная работа предназначена для изучения работы с подгруппами. Подробные сведения по данным темам содержатся:

Пример. В каких Силовских 2-подгруппах группы S_4 содержатся подстановки (1 3 2 4), (1 3) и (12)(34) ?

Данную задачу можно решить в интерактивном режиме следующим образом. Сначала зададим исходную группу:


gap> S := SymmetricGroup(4); 
Sym( [ 1 .. 4 ] )

Вычислим ее Силовские 2-подгруппы. Поскольку по второй теореме Силова все Силовские p-подгруппы сопряжены, то функция SylowSubgroup возвращает только одну подгруппу, которая является представителем некоторого класса сопряженных подгрупп.


gap> P2 := SylowSubgroup( S, 2 ); 
Group([ (1,2), (3,4), (1,3)(2,4) ])

Для того, чтобы получить остальные подгруппы из этого класса, сначала нужно создать класс сопряженных подгрупп данной группы с заданным представителем, а затем получить список содержащихся в нем подгрупп:


gap> c2 := ConjugacyClassSubgroups( S, P2 ); 
Group( [ (1,2), (3,4), (1,3)(2,4) ] )^G
gap> l2 := AsList( c2 ); 
[ Group([ (1,2), (3,4), (1,3)(2,4) ]), Group([ (1,3), (2,4), (1,2)(3,4) ]), 
  Group([ (1,4), (2,3), (1,2)(3,4) ]) ]

Теперь мы можем получить из него списки подгрупп, которые содержат указанные подстановки:


gap> Filtered( l2, g -> (1,3,2,4) in g );  
[ Group([ (1,2), (3,4), (1,3)(2,4) ]) ]
gap> Filtered( l2, g -> (1,3) in g );    
[ Group([ (1,3), (2,4), (1,2)(3,4) ]) ]
gap> Filtered( l2, g -> (1,2)(3,4) in g );
[ Group([ (1,2), (3,4), (1,3)(2,4) ]), Group([ (1,3), (2,4), (1,2)(3,4) ]), 
  Group([ (1,4), (2,3), (1,2)(3,4) ]) ]


C.9-2 Варианты заданий для лабораторной работы 9

Вариант 1. Разработать функцию, которая для заданной группы возвращает множество порядков всех ее подгрупп, полученное как множество порядков представителей ее классов сопряженных подгрупп. Указание: использовать функции ConjugacyClassesSubgroups, Representative.

Вариант 2. Разработать функцию, которая для заданной группы возвращает список простых делителей порядка группы с указанием порядка и количества соответствующих Силовских p-подгрупп. Указание: использовать функции SylowSubgroup, ConjugacyClassSubgroups.

Вариант 3. Разработать функцию, которая для заданной группы возвращает множество порядков ее максимальных подгрупп. Указание: использовать функции Size, MaximalSubgroups.

Вариант 4. Разработать функцию, которая для заданной группы возвращает множество порядков ее нормальных подгрупп. Указание: использовать функции Size, NormalSubgroups.

Вариант 5. Разработать функцию, которая для заданной группы определяет список порядков факторов ее нижнего центрального ряда. Указание: использовать функции Size, LowerCentralSeries.

Вариант 6. На примере знакопеременной группы A_4 показать, что нормальная подгруппа K нормальной подгруппы H группы G не обязательно является нормальной во всей группе G. Указание: использовать функции NormalSubgroups, IsNormal.

Вариант 7. Найти все подгруппы в циклической группе порядка 360. Проверить, что они образуют цепь подгрупп. Указание: использовать функции NormalSubgroups, IsSubgroup.

Вариант 8. Проверить, что группы S_3, A_4, S_4 являются разрешимыми. Указание: использовать функцию DerivedSubgroup.

Вариант 9. Составить функцию, которая для заданной группы вычисляет подгруппу Фраттини, т.е. пересечение всех ее максимальных подгрупп. Указание: использовать функции Intersection, MaximalSubgroups.

Вариант 10. Сколько различных силовских p-подгрупп содержится в группе A_5 для p = 2, 3, 5 ? Указание: использовать функцию SylowSubgroup.

Вариант 11. Разработать функцию, которая для для заданной группы возвращает список представителей классов сопряженности ее Силовских p-подгрупп. Указание: использовать функцию SylowSubgroup.

Вариант 12. Разработать функцию, которая для заданной группы определяет порядок ее фактор-группы по коммутанту. Указание: использовать функции Size и DerivedSubgroup.

Вариант 13. Проверить, что знакопеременная группа A_5 является простой, т.е. не содержит нетривиальных нормальных подгрупп. Указание: использовать функцию NormalSubgroups

Вариант 14. Проверить, что подгруппа группы S_7, порожденная подстановками (1 2 3) и (1 4 5 6 7), не является разрешимой. Указание: использовать функцию DerivedSubgroup.

Вариант 15. Разработать функцию, которая для заданной группы определяет список показателей (экспонент) элементов ее нижнего центрального ряда. Указание: использовать функции Exponent, LowerCentralSeries.

Вариант 16. Составить функцию, которая для заданной группы вычисляет список порядков элементов ее нижнего центрального ряда. Указание: использовать функции Size, LowerCentralSeries.

Вариант 17. Составить функцию, которая для заданной группы определяет множество индексов ее максимальных подгрупп. Указание: использовать функции Index, MaximalSubgroups.

Вариант 18. Найти все силовские p-подгруппы в группах S_3, A_4. Указание: использовать функцию SylowSubgroup.

C.10 Работа с библиотекой конечных групп

C.10-1 Инструкции по выполнению работы 10

Данная лабораторная работа предназначена для изучения работы с библиотекой конечных групп системы GAP. Необходимо сначала выбрать группы из библиотеки по указанному критерию (порядок группы в сочетании с некоторым свойством), а затем для каждой из этих групп определить указанное свойство, и вывести результаты на экран в виде таблицы с указанием номера соответствующей группы в библиотеке конечных групп системы GAP.

Подробные сведения по данным темам содержатся:

C.10-2 Варианты заданий для лабораторной работы 10

Вариант 1. Выбрать все нециклические 2-группы порядка 32. Определить их количество. Каждую из них идентифицировать с помощью функции GroupId и вычислить ее класс нильпотентности с помощью функции LowerCentralSeries. Результат вывести в виде таблицы.

Вариант 2. Выбрать все неабелевы 2-группы порядка 32. Определить их количество. Идентифицировать каждую из них с помощью функции GroupId и вычислить порядок ее центра. Результат вывести в виде таблицы.

Вариант 3. Выбрать все неабелевы 2-группы порядка 32. Определить их количество. Идентифицировать каждую из них с помощью функции GroupId, вычислить и идентифицировать ее фактор-группу по коммутанту. Результат вывести в виде таблицы.

Вариант 4. Выбрать все неабелевы 2-группы порядка 32. Определить их количество. Идентифицировать каждую из них с помощью функции GroupId и вычислить порядок ее коммутанта. Результат вывести в виде таблицы.

Вариант 5. Выбрать все 2-группы порядка 32, порядок коммутанта которых равен 8. Определить их количество. Идентифицировать каждую с помощью функции GroupId и вычислить длину ее ряда коммутантов с помощью функции DerivedSeries. Результат вывести в виде таблицы.

Вариант 6. Выбрать все нециклические 3-группы порядка 27. Определить их количество. Каждую из них идентифицировать с помощью функции GroupId и вычислить ее класс нильпотентности с помощью функции LowerCentralSeries. Результат вывести в виде таблицы.

Вариант 7. Выбрать все неабелевы 3-группы порядка 27. Определить их количество. Идентифицировать каждую из них с помощью функции GroupId и вычислить порядок ее центра. Результат вывести в виде таблицы.

Вариант 8. Выбрать все неабелевы 3-группы порядка 27. Определить их количество. Идентифицировать каждую из них с помощью функции GroupId, вычислить и идентифицировать ее фактор-группу по коммутанту. Результат вывести в виде таблицы.

Вариант 9. Выбрать все неабелевы 3-группы порядка 27. Определить их количество. Идентифицировать каждую из них с помощью функции GroupId и вычислить порядок ее коммутанта. Результат вывести в виде таблицы.

Вариант 10. Выбрать все 3-группы порядка 81 с коммутантом порядка 9. Определить их количество. Идентифицировать каждую из них с помощью функции GroupId и вычислить длину ее ряда коммутантов с помощью функции DerivedSeries. Результат вывести в виде таблицы.

Вариант 11. Выбрать все неабелевы 2-группы порядка 32. Определить их количество. Каждую из них идентифицировать с помощью функции GroupId и вычислить ее класс нильпотентности с помощью функции LowerCentralSeries. Результат вывести в виде таблицы.

Вариант 12. Выбрать все неабелевы 2-группы порядка 64. Определить их количество. Идентифицировать каждую из них с помощью функции GroupId и вычислить порядок ее центра. Результат вывести в виде таблицы.

Вариант 13. Выбрать все неабелевы 2-группы порядка 64. Определить их количество. Идентифицировать каждую из них с помощью функции GroupId, вычислить и идентифицировать ее фактор-группу по коммутанту. Результат вывести в виде таблицы.

Вариант 14. Выбрать все неабелевы 2-группы порядка 64. Определить их количество. Идентифицировать каждую из них с помощью функции GroupId и вычислить порядок ее коммутанта. Результат вывести в виде таблицы.

Вариант 15. Выбрать все 2-группы порядка 64, порядок коммутанта которых равен 8. Определить их количество. Идентифицировать каждую с помощью функции GroupId и вычислить длину ее ряда коммутантов с помощью функции DerivedSeries. Результат вывести в виде таблицы.

Вариант 16. Выбрать все нециклические 3-группы порядка 81. Определить их количество. Каждую из них идентифицировать с помощью функции GroupId и вычислить ее класс нильпотентности с помощью функции LowerCentralSeries. Результат вывести в виде таблицы.

Вариант 17. Выбрать все неабелевы 3-группы порядка 81. Определить их количество. Идентифицировать каждую из них с помощью функции GroupId и вычислить порядок ее центра. Результат вывести в виде таблицы.

Вариант 18. Выбрать все неабелевы 3-группы порядка 81. Определить их количество. Идентифицировать каждую из них с помощью функции GroupId, вычислить и идентифицировать ее фактор-группу по коммутанту. Результат вывести в виде таблицы.

C.11 Дополнительные упражнения различной трудности

1. Разработать функцию для вычисления n !! = n ⋅ (n-2) ⋅ (n-4) ⋅ dots ⋅ 1.

2. Разработать функцию для вычисления n-го числа Фибоначчи, где f(1) = f(2) = 1, f(n) = f(n-1) + f(n-2).

3. Разработать функцию для проверки того, четно или нечетно заданное натуральное число.

4. Разработать функцию для проверки того, делится ли заданное натуральное число на три.

5. Разработать функцию для проверки того, сравнимы ли два целых числа по заданному модулю.

6. Разработать функцию для вычисления суммы нечетных натуральных чисел, не превосходящих заданное натуральное число.

7. Разработать функцию для вычисления произведения нечетных натуральных чисел, не превосходящих заданное натуральное число.

8. Разработать функцию для вычисления суммы четных натуральных чисел, не превосходящих заданное натуральное число.

9. Разработать функцию для вычисления произведения четных натуральных чисел, не превосходящих заданное натуральное число.

10. Разработать собственную функцию для проверки того, что заданное натуральное число является простым с помощью одного из известных методов.

11. Разработать функцию для вычисления НОД двух натуральных чисел a и b по алгоритму Евклида: a = b q_1 + r_1, b = r_1 q_2 + r_2, r_1 = r_2 q_3 + r_3, ..., r_n-2 = r_n-1 q_n + r_n, r_n-1 = r_n q_n.

12. Разработать функцию для определения произведения всех простых делителей натурального числа. Указание: использовать функции Factors, Set, Product.

13. Разработать функцию для определения суммы натуральных делителей натурального числа. Указание: использовать функции Factors и Collected.

14. Разработать функцию для определения количества натуральных делителей натурального числа. Указание: использовать функции Factorsи Collected.

15. Разработать функцию для вычисления для натурального n = p_1^k_1 ⋅ dots ⋅ p_s^k_s функции Эйлера ϕ(n) по формуле ϕ(n) = n ( 1 - 1/p_1) dots (1-1/p_s). Указание: использовать функции Factors и Collected.

16. Известна гипотеза о том, что любое четное число n, большее чем 2, можно представить в виде суммы двух простых чисел. Проверьте ее для всех четных чисел n, не превышающих 10000.

17. Гипотеза Гольдбаха спрашивает, верно ли то, что любое нечетное число n, где n > 5, можно представить в виде суммы трех простых чисел. Проверьте ее для всех нечетных чисел n, не превышающих 1000.

18. Пусть t - произвольное натуральное число. Рассмотрим последовательность {n_i}, в которой n_1 = t, а остальные элементы определяются рекурсивно: n_k+1 = n_k / 2, если n_k - четное, и n_k+1 = 3 n_k + 1, если n_k - нечетное. Известна так называемая "гипотеза 3 k + 1", согласно которой такая последовательность достигает единицы для любого начального t. Проверьте ее для всех натуральных чисел t, не превышающих 10000. В вывод результатов включите количество шагов, которые требуются для достижения единицы.

19. Натуральное число n называется совершенным, если оно равняется сумме всех своих собственных делителей. Например, 6 = 1+2+3, 28 = 1+2+4+7+14. Найдите все совершенные числа, не превышающие 10000.

20. Натуральные числа m и n называются дружественными, если каждое из них равняется сумме всех собственных делителей другого. Например, такими являются числа 220 и 284. Выясните, существуют ли другие пары дружественных чисел, не превышающих 1000.

21. Пусть t - произвольное натуральное число. Рассмотрим последовательность {n_i}, в которой n_1 = t, а остальные элементы определяются рекурсивно: n_k+1 равняется сумме всех собственных делителей числа n_k. Исследуйте поведение этой последовательности для всех натуральных чисел t, не превышающих 1000: когда она достигает единицы, стабилизируется, зацикливается; когда можно выдвинуть гипотезу о том, что она неограниченно возрастает?

 [Начало книги]  [Содержание]   [Предыдущая глава]   [Следующая глава] 
Перейти к главе: Начало 1 2 3 4 A B C Bib Ind

generated by GAPDoc2HTML