Компьютерная алгебра в задачах
Покупка
Основная коллекция
Тематика:
Математическое программное обеспечение
Издательство:
Московский педагогический государственный университет
Автор:
Шилин Илья Анатольевич
Год издания: 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
ВВЕДЕНИЕ
Компьютерная алгебра — это учебная дисциплина, призванная продемонстрировать и научить, как с помощью компьютеров можно решать математические задачи, относящиеся к общей алгебре. Под словом «решать» здесь следует понимать «решать точно», поскольку, например, задачу о вычислении корня полинома, принадлежащего заданному отрезку, на концах которого полином принимает значения разных знаков, относят к другой дисциплине — «Численным методам», где как раз достаточно найти приближенное решение с заданной точностью.
Эта небольшая книга написана автором в том же духе, в каком написаны подавляющее число толстых книг по компьютерным наукам: отсутствует методически выверенное последовательное изложение от самых азов до сложных изысканностей и вместо этого читателю предлагается изучать дисциплину через разобранные в книге примеры, то есть, по сути, девизом книги является название некогда популярной телепередачи «Делай с нами, делай как мы, делай лучше нас».
Почти все рассмотренные в книге задачи относятся к теории групп. В наше время существует немало вычислительных пакетов, с помощью которых можно найти точные решения теоретико-групповых задач. Наряду с обычными (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 Джон Кэннон.
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) над
полем 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.