Компьютерная алгебра в задачах

Министерство образования и науки Российской Федерации


Федеральное государственное бюджетное образовательное учреждение высшего образования
«Московский педагогический государственный университет»


И. А. Шилин






                КОМПЬЮТЕРНАЯ АЛГЕБРА
                В ЗАДАЧАХ




Учебное пособие

















МПГУ
Москва • 2018

УДК 512.6(076.1)
ББК 22.14-4
      Ш 578




Рецензенты:
А. В. Царев, доктор физико-математических наук (кафедра алгебры МПГУ);
А. А. Туганбаев, доктор физико-математических наук, профессор (кафедра высшей математики НИУ «МЭИ»)








      Шилин, Илья Анатольевич.
Ш578 Компьютерная алгебра в задачах : учебное пособие / И. А. Шилин.
      - Москва : МПГУ, 2018. - 56 с.


            ISBN 978-5-4263-0664-6


Учебное пособие содержит подборку практических задач с решениями для изучения дисциплины «Компьютерная алгебра» и адресовано всем студентам Института математики и информатики МПГУ, изучающим эту дисциплину.

УДК 512.6(076.1)
ББК 22.14-4







ISBN 978-5-4263-0664-6

(О МПГУ, 2018
(О Шилин И. А., текст, 2018

Содержание


   ВВЕДЕНИЕ .................................... 4
   1. Вычисление образующих элементов мультипликативной группы поля вычетов и индексов по ним ... 7
   2. Вычисление коэффициентов унитарного комплексного многочлена по его корням, являющимися целыми гауссовыми числами ......................... 12
   3. Вычисление числа транзитивных отношений . 15
   4. Вложение конечной группы в группу преобразований этой группы .............................. 22
   5. Вычисление подгрупп и выделение нормальных делителей конечной группы .................. 30
   6. Вычисление централизаторов и нормализаторов подгрупп конечных неабелевых групп ....... 34
   7. Представление подстановки в виде композиции транспозиций ............................... 39
   8. Вычисление групп гомоморфизмов конечных групп . 43
   9. Вычисление групп автоморфизмов и внутренних автоморфизмов конечных групп ............... 47
   10. Решение линейного дифференциального уравнения второго порядка с постоянными коэффициентами . . 52


3

                ВВЕДЕНИЕ





   Компьютерная алгебра — это учебная дисциплина, призванная продемонстрировать и научить, как с помощью компьютеров можно решать математические задачи, относящиеся к общей алгебре. Под словом «решать» здесь следует понимать «решать точно», поскольку, например, задачу о вычислении корня полинома, принадлежащего заданному отрезку, на концах которого полином принимает значения разных знаков, относят к другой дисциплине — «Численным методам», где как раз достаточно найти приближенное решение с заданной точностью.
   Эта небольшая книга написана автором в том же духе, в каком написаны подавляющее число толстых книг по компьютерным наукам: отсутствует методически выверенное последовательное изложение от самых азов до сложных изысканностей и вместо этого читателю предлагается изучать дисциплину через разобранные в книге примеры, то есть, по сути, девизом книги является название некогда популярной телепередачи «Делай с нами, делай как мы, делай лучше нас».
   Почти все рассмотренные в книге задачи относятся к теории групп. В наше время существует немало вычислительных пакетов, с помощью которых можно найти точные решения теоретико-групповых задач. Наряду с обычными (Maple, Mathematica, MathCad, REDUCE, Derive, MATLAB) существуют специализированные вычислительные пакеты, целиком предназначенные именно для этой цели: свободно распространяемые GAP, Sage, FGB и коммерческие CAYLEY и Magma, созданные в Университете Сиднея¹. Однако в этой книге, возможно, наперекор духу времени, под решением задач с помощью компьютера подразумевается их решение с помощью программирования, а не использования уже готовых пакетов. Изучению возможностей пакетов компьютерной алгебры должен, по всей видимости, быть посвещен отдельный курс, итогом которого должно быть, например, знание команды NormalSubgroups в GAP, которая выводит на экран список всех нормальных делителей заданной группы. Пользуясь пакетом GAP, с помощью всего лишь одной командной строки

   gap> NormalSubgroups(SymmetriGroup(4));
удается вывести на экран все нормальные делители симметрической группы S4:

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

  ¹ Автору довелось побывать в Лаборатории компьютерной алгебры Университета Сиднея, которую возглавляет создатель CAYLEY и Magma Джон Кэннон.

4

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


то есть подгруппы {id}, K, A4 и S4, где K — так называемая подгруппа Клейна, состоящая из подстановок id, (1 2)(3 4), (1 3)(2 4) и (1 4)(2 3) и изоморфная группе Z₂² . Но такой способ использования компьютера непригоден для нашего курса, цель которого научить мыслить алгоритмически при решении алгебраических задач, переводить задачу с языка математики на язык программных кодов и результаты программы обратно на математический язык.

   При решении алгебраических задач с помощью программирования на первый план выступает задача реализации исследуемого математического объекта в программном коде. Подобный прием мы встречаем и в самой математике, например:
   а)    множество C реализуется как плоскость П = R2 посредством взаимно однозначного отображения z -—( (re z, im z);
   б)    расширенная комплексная плоскость C реализуется как сфера Римана S : Z2 + v² + Z2 = Z: совместив плоскость Z = 0 с П так, что ось Z = 0 совпадает с осью у = 0 и ось v = 0 — с осью x = 0, используем взаимно однозначное отображение


a + bi

।—м

           a            b        a² + b²
a² + Ь2 + 1, а² + Ь2 + 1, а² + Ь2 + 1

ж ।—м (0,0,1);


   в)    скалярное v • w и векторное v х w произведение векторов v = (x1 , x2 , x3 ) и w = (y1 , y2 , y3 ) реализуется как произведение чисто мнимых кватернионов h1 = x1i + x2j + x3k и h2 = y1i + y2j + y3k, а именно

h1h2 = —v • w + (v х w) • h,

где под h подразумевается символический вектор (i, j, k);
   г)    группа G реализутся в некотором линейном пространстве L в виде подгруппы мультипликативной группы невырожденных линейных операторов этого пространства посредством гомоморфизма G —g GL(L), а для конечной группы G, стало быть, в виде подгруппы мультипликативной группы невырожденных матриц (над соответствующем полем Ф) посредством гомоморфизма G —м Mat(dim L, Ф). Такую реализацию называют представлением группы G. Например, группа Sₙ реализутся в виде подгруппы в Mat(n, Z2) посредством гомоморфизма T : о -—м т(о), где т(о) = б[1,о(1)] + ... + e[n,ₒ(n)] и под e[s,ₜ] понимается матрица (aij) над


5

полем Z2 , матричные элементы которой определены правилом


= 0₁,,

если s = i или t = j , если s = i и t = j ;


   д)   подмножество A непустого множества B реализуется как характеристическая функция (индикатор) xa : B —{ {0,1}, где

I

XA⁽x⁾ =

если x / A, если x G A

(обобщая эту реализацию, Заде определил в 1965 году нечеткое подмножество в B как отображение ф : B —[ [0; 1]).
   Если множество B конечно, а именно, B ={b1 , . . . , bₙ}, то, выписывая друг за другом значения характеристической функции xA , получаем двоичное число c1c₂ ... cn, где ci = XA(bi). Мы будем использовать этот прием, то есть реализовывать подмножества множества B в виде целых двоичных чисел от 0 (пустое подмножество) до 2ⁿ - 1 (само B), на протяжении всей книги. Аналогичную реализацию будем применять для отображений B —D D, где D состоит из m элементов: в кодах программ эти отображения будут заменяться целыми числами в m-ичной системе счисления, записанными с помощью n цифр (разрядов).
   К каждой из разобранных задач в качестве примера приведен программный код на языке PASCAL.

6