Компьютерная алгебра в задачах
Покупка
Основная коллекция
Тематика:
Математическое программное обеспечение
Издательство:
Московский педагогический государственный университет
Автор:
Шилин Илья Анатольевич
Год издания: 2018
Кол-во страниц: 56
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-4263-0664-6
Артикул: 756914.01.99
Учебное пособие содержит подборку практических задач с решениями для изучения дисциплины «Компьютерная алгебра» и адресовано всем студентам Института математики и информатики МПГУ, изучающим эту дисциплину.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 01.03.01: Математика
- 01.03.02: Прикладная математика и информатика
- 01.03.03: Механика и математическое моделирование
- 09.03.01: Информатика и вычислительная техника
- 09.03.02: Информационные системы и технологии
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов.
Для полноценной работы с документом, пожалуйста, перейдите в
ридер.
Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «Московский педагогический государственный университет» И. А. Шилин КОМПЬЮТЕРНАЯ АЛГЕБРА В ЗАДАЧАХ Учебное пособие МПГУ Москва • 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
1. Вычисление образующих элементов мультипликативной группы поля вычетов и индексов по ним Напомним, что факторкольцо кольца Z по идеалу nZ, состоящему из чисел, делящихся на п, состоит из элементов 0,1,... ,п, являющихся в кольце Z классами чисел с равными остатками, получающимися при делении на п. Это кольцо обозначается Zₙ и называется кольцом вычетов по модулю п. Элемент а обратим в том и только том случае, если НОД(а,п) = 1. Обратимые элементы образуют группу относительно умножения — ее называют мультипликативной группой кольца Zₙ . Будем обозначать ее Inv Zₙ . Понятно, что в случае простого п все не равные нулю элементы кольца обратимы и Zₙ является полем. Более того, можно доказать, что в случае простого п группа InvZn = {1,... ,n — 1} циклическая. Как известно, число образующих элементов циклической группы порядка k равно Ф(к), где Ф — функция Эйлера, поэтому число образующих элементов мультипликативной группы поля вычетов вычисляется по формуле Ф(Ф(п)) = Ф(п — 1). Пусть а — один из таких образующих элементов. Тогда группу Inv Zn можно представить в виде Inv Zn = (a) = {a, a²,..., an-2, an-¹ = 1}. Например, в циклической мультипликативной группе Inv Z₁7 = {1,2,..., 16} поля Z17 элемент 3 является образующим, поскольку 31 = 3 35 = 5 39 = 14 013 = 12 3 32 = 9 36 = 15 310 =8 314 = 2 33 = 10 37 = 11 311 =7 315 = 6 34 = 13 38 = 16 312 = 4 316 = 1 Напомним, что если элемент g циклической группы порядка k является образующим элементом, то элемент gs тоже является образующим элементом в том и только том случае, когда НОД($, k) = 1. Так, в приведенном примере числа 3, 5, 7, 9, 11, 13, 15 взаимно просты с 16 и, следовательно, элементы 33 = 10, 35 = 5, 37 = 11, 39 = 14, 3¹¹ = 7, 313 = 12, 315 = 6 7
группы Inv Z17, то есть элементы 5, 6, 7, 10, 11, 12, 14 тоже являются образующими элементами. Пусть a — образующий элемент группы InvZn (n — простое число). Индексом элемента b Е Inv Zn по основанию а называют такое наименьшее неотрицательное целое число s, что as = b. Обозначают индекс так: indab. Так, возвращаясь к рассмотренному примеру, имеем ind31 = 0 ind35 = 5 ind3 9 = 2 ind313 = 4 ind3 2 = 14 ind36 = 15 ind310 = 3 ind314 = 9 ind3 3=1 ind3 7 = 11 ind311 = 7 ind315 = 6 ind3 4 = 12 ind3 8 = 10 ind312 = 13 ind316 = 8 Отображение Ind : Inv Zn —Z Zn-1, b ।—i inda b является изоморфизмом мультипликативной группы Inv Zₙ в аддитивную группу Zₙ₋1, аналогом изоморфизма ln : R₊ -i R, b -i lnb мультипликативной группы положительных действительных чисел в аддитивную группу действительных чисел, и применяется для решения степенных и показательных уравнений над полем Zn. Компьютерная программа, которая спрашивает пользователя простое число n и выводит на экран образующие элементы группы Inv Zₙ и таблицу индексов по одному из образующих элементов, может быть составлена по следующей схеме: а) производится отбор целых чисел i Е {1, . . . , n - 1}, взаимно простых с n — для этого используется включенная в программу функция gcd, вычисляющая наибольший общий делитель двух чисел; б) если i — одно из отобранных чисел, то программа определяет его наименьшую степень s, такую, что остаток от деления is на n равен 1. Если s = n — 1, то i — образующий элемент. При этом остатки от деления чисел i¹, i², . . . , iⁿ⁻¹ на n записываются в массив. Программе достаточно найти всего один образующий элемент: пробегая целые числа s от 2 до n — 1, взаимно простые с n — 1, программа выводит на экран остатки от деления чисел is на n — эти числа суть все остальные образующие элементы; в) используя массив, программа выводит на экран таблицу индексов. Соответствующий программный код может быть таким: program zn; var i,j,n : integer; inv,d : array[1..100] of integer; function gcd (x,y : integer) : integer; begin if x=0 then gcd:=y else gcd:=gcd(y mod x,x) 8
end; BEGIN writeln(); write(’Input n => ’);read(n); i:=2; repeat d[1]:=i; j:=1; repeat j:=j+1; d[j]:=(d[j-1]*i) mod n until d[j]=1; i:=i+1 until j=n-1; writeln(); write(’Generators: ’); for i:=1 to n-2 do if gcd(i,n-1)=1 then if i>2 then write(’; ’,d[i]) else write(d[i]); write(’.’); writeln(); for i:=1 to n-1 do begin j:=1; while d[j]<>i do j:=j+1; writeln(’ind(’,i,’)=’,j mod (n-1)) end END. Упражнение 1. Составьте программу, которая спрашивает у пользователя п, коэффициенты а и b и выводит на экран решения линейного уравнения ax = b над кольцом Zn. Как известно, если a G InvZn, то уравнение ax = b имеет единственное решение x = a- 1b. При a / Inv Zn могут быть два случая: • Если d = НОД(а, п) является делителем числа b, то уравнение имеет d x1 = с, x₂ = c + n, ..., xd = c + (d — 1)n, где n = d и с — единственное решение уравнения ax = b, a = d, b = d, над кольцом Zn; • Если b не делится на d, то уравнение ax = b не имеет решений. Замечание. Поскольку порядок элемента конечной группы является делителем порядка группы, то число |Inv Zn| = Ф(п) делится на порядок s элемента a. Тогда Ф(п) = ks и, следовательно, a?⁽ⁿ) = (as) = 1k = 1. Отсюда aa®⁽n)-1 = 1, то есть a-1 = . (1) При решении уравнения ax = b вручную при больших п гораздо проще использовать формулу (1), однако компьютерная программа совершит гораздо меньше операций, если найдет элемент a-1 методом перебора. 9
Упражнение 2. Составьте программу, которая спрашивает у пользователя п, коэффициенты а и b и выводит на экран решения линейного уравнения ax = b над кольцом Zn, найденное с помощью цепных дробей. Разделим n на a с остатком: n = aq₀ + r1, 0 < r1 < |a|. Если r1 = 0, разделим a на r1 с остатком: a = riqi + Г2, 0 < Г2 < ri. Если r2 = 0, разделим r1 на r2 с остатком: ri = r2q2 + r3, 0 < гз < r2 Последовательность rᵢ , r₂ , r₃ , . . . строго убывает и ограничена снизу числом ноль, поэтому, продолжая процесс деления с остатком далее, получим на некотором шаге равный нулю остаток и запись n1 _ = qo ⁺ -■ a1 q¹⁺-1— q2 +---------j q3 + ... +qₘ которую называют представлением числа n Для цепной дроби используется компактная в виде цепной (или непрерывной) дроби. запись [qₒ; qᵢ , q₂, . . . , qₘ]. Цепные дроби §o :=[qo], Si := [qo; qₓ], §2 := [qo; qi^],---, §m-i := [qo; qi, . . . , qm-i], §m := [qo; qi, q2, . . . , qm] называют подходящими к дроби [qo; qi, q2, . . . , qₙ]. Обозначим числитель и знаменатель подходящей дроби §i соответственно Pi и Qi . Если a и n взаимно просты, то единственным решением уравнения ax = b является класс целых чисел, содержащий число (-1)mPm-ib. Упражнение 3. Составьте программу, которая спрашивает у пользователя простое число п, коэффициенты a, k, c и b и выводит на экран решения показательного уравнения akx+c = b над полем Zn. Пусть z — образующий элемент группы Inv Zn. Тогда indz akx+c = indz b, (kx + c)indz a = indz b, (k indz a)x + (c indz a) = indz b, то есть задача свелась к решению линейного уравнения над кольцом Zₙ₋ᵢ. 10
Упражнение 4. Составьте программу, которая спрашивает у пользователя простое число п, коэффициенты а и b и показатель степени k и выводит на экран решения степенного уравнения axk = b над полем Zn. Если Inv Zn = (z), то indz (axk) = indz b, indz a + k indz x = indz b, k indzx = indz b — indza, то есть задача свелась к решению линейного уравнения над кольцом Zₙ₋1 . 11