Аннотация учебной дисциплины
Учебная дисциплина «ВЫЧИСЛИТЕЛЬНАЯ АЛГЕБРА»
|
Цель изучения дисциплины
|
Целями освоения дисциплины «Вычислительная алгебра» являются:
расширение и углубление фундаментальной алгебраической и алгоритмической подготовки студентов, обеспечивающей возможность овладения современными математическими методами, используемыми в криптографии, теории кодирования и общих моделях безопасности компьютерных систем;
изучение дополнительных разделов алгебры и алгоритмов алгебраических вычислений, находящих непосредственные приложения в задачах защиты информации.
|
Компетенции, формируемые в результате
освоения дисциплины
|
Процесс изучения дисциплины направлен на формирование следующих компетенций:
- способностью корректно применять при решении профессиональных задач научный аппарат математического анализа, геометрии, алгебры, дискретной математики, математической логики, теории алгоритмов, теории вероятностей, математической статистики, теории информации, теоретико-числовых методов (ОПК-2);
- способностью к самостоятельному построению алгоритма, проведению его анализа и реализации в современных программных комплексах (ОПК-10).
|
Знания, умения и навыки, получаемые в процессе изучения дисциплины
|
В результате освоения дисциплины обучающийся должен
знать:
определения и свойства алгебраических структур, используемых непосредственно в приложениях.
принципы построения алгоритмов вычислений в алгебраических структурах;
уметь:
производить вычисления в конкретных кольцах и алгебрах.
выполнять операции над идеалами в коммутативных кольцах.
находить базис Грёбнера полиномиального кольца.
осуществлять вычисления с перестановками конечного множества.
вычислять группу Галуа полиномиального уравнения;
владеть:
владеть алгоритмами вычислений в коммутативных кольцах.
алгоритмом Бухбергера.
алгоритмами вычислений в группах перестановок конечного множества и алгоритмами генерирования групп перестановок.
алгоритмами вычисления групп Галуа полиномиальных уравнений.
|
Краткая
характеристика
учебной дисциплины (основные блоки и темы)
| Содержание основных разделов (тем) курса
Тема 1. Введение
Задачи и программа курса. Место курса «Вычислительная алгебра» в ряду других математических дисциплин. Формы самостоятельной работы студентов по изучению курса. Литература к курсу.
Обзор основных результатов элементарной теории чисел. Обзор основных свойств конечных полей. Общая задача вычисления дискретного логарифма, как задача решения системы полиномиальных уравнений над конечным полем. Проблема упрощения системы уравнений. Задача разрешимости полиномиального уравнения в радикалах.
Тема 2. Вычисления в кольцах и алгебрах
Примеры колец и полей. Подкольца и подполя. Алгебры над кольцом и над полем. Алгебра многочленов от одной переменной, её свойства. Многочлены от многих переменных, его факториальность. Гомоморфизмы колец, полей и алгебр, их свойства примеры. Идеалы коммутативных колец, их свойства. Подкольца и идеалы, порождённые множеством, их свойства, их элементы. Кольца главных идеалов. Факторизация колец и гомоморфизмов по идеалам.
Сумма и произведение идеалов. Свойства операций над идеалами. Максимальные и простые идеалы. Числовые кольца. Алгоритм редукции и умножения идеалов квадратичного кольца.
Тема 3. Вычисления с многочленами
Нётеровы кольца. Эквивалентные условия нётеровости. Теорема Гильберта о базисе. Представления многочленов. Арифметика многочленов. Евклидовы алгоритмы для многочленов. Вычисление результантов и дискриминантов. Факторизация многочленов по модулю p. Алгоритм Берлекэмпа. Факторизация многочленов над и над .
Отношение порядка на множестве одночленов. Алгоритм деления в кольце многочленов от многих переменных. Мономиальные идеалы. Лемма Диксона. Базисы Грёбнера полиномиальных идеалов, их свойства. Зацепление многочленов. Алгоритм Бухбергера. Минимальный и редуцированный базисы Грёбнера, их свойства. Улучшенный алгоритм Бухбергера.
Тема 4. Решение систем алгебраических уравнений
Аффинные алгебраические множеств, операции над ними. Топология Зариского. Идеал множества. Радикал идеала, его свойства. Радикальные идеалы. Свойства идеалов множеств. Понятие неприводимости. Аффинные алгебраические многообразия. Идеал многообразия. Теорема Гильберта о нулях. Соответствие между алгебраическими множествами и идеалами. Алгоритм вычисления радикалов идеалов в полиномиальных кольцах.
Разложение на неприводимые компоненты. Алгоритм решения систем полиномиальных уравнений с помощью базисов Грёбнера. Алгоритм примарного разложения идеалов в полиномиальных кольцах.
Тема 5. Вычисления с группами и перестановками
Группы. Гомоморфизмы групп, их свойства. Подгруппы. Пересечение подгрупп. Образ и прообраз группы при гомоморфизме. Образ гомоморфизма. Отношения эквивалентности в группе по подгруппе. Теорема Лагранжа. Нормальные подгруппы. Образ и прообраз нормальной подгруппы при гомоморфизме. Ядро гомоморфизма. Отношение эквивалентности в группе по нормальной подгруппе. Факторгруппа. Факторизация гомоморфизмов. Теоремы об изоморфизмах.
Подгруппа, порождённая множеством. Образ с помощью гомоморфизма. Циклические группы. Обращение теоремы Лагранжа для циклических групп. Разрешимые группы, их свойства. Примеры разрешимых групп. Произведение и прямое произведение подгрупп. Прямая сумма подгрупп абелевой группы. Разложение циклической группы в прямую сумму примарных циклических подгрупп. Разложение конечной абелевой группы в прямую сумму циклических групп. Тип конечной абелевой группы. Обращение теоремы Лагранжа для конечной абелевой группы.
Перестановки и шифры. Транспозиции. Разложение перестановки в произведение циклов и транспозиций. Системы образующих симметрической группы. Инверсии. Сигнатура перестановки. Четные и нечетные подстановки, теорема о декременте. Орбита и стабилизатор элемента. Сопряжённые перестановки. Критерий сопряженности подстановок. Уравнение Коши. Разрешимость и неразрешимость групп перестановок.
Генерация лексикографической перестановки. Сложные замены. Простые замены. Переходы простых изменений. Общая структура. Пропуск нежелательных блоков. Лексикографические перестановки с ограниченными префиксами. Дуальные методы.
Тема 6. Вычисления в числовых полях
Расширения полей. Степень расширения. Конечные расширения. Теорема транзитивности конечных расширений. Алгебраические и трансцендентные элементы. Стандартные представления алгебраических чисел. Матричные представления алгебраических чисел. Алгебраические расширения полей. Минимальный многочлен алгебраического элемента. Признак алгебраического элемента. Свойства алгебраических расширений. Алгебраическое замыкание поля. Гомоморфизмы алгебраических расширений. Поля разложения многочленов и нормальные расширения. Сепарабельные элементы. Сепарабельные многочлены. Сепарабельные расширения полей.
Тема 7. Вычисления групп Галуа
Группа автоморфизмов поля над подполем. Неподвижное поле группы автоморфизмов. Теорема Артина. Расширения Галуа. Группа Галуа расширения Галуа. Соответствие Галуа. Основная теорема теории Галуа. Группа Галуа как группа перестановок корней многочлена. Примеры. Решение кубических уравнений в радикалах. Решение уравнений четвёртой степени в радикалах. Критерий разрешимости уравнения в радикалах.
Метод резольвент вычисления групп Галуа. Его применения для числовых полей степени 3, 4, 5.
3.2. Тематика практических занятий
Тема 1. По данной теме практических занятий не предусмотрено.
Тема 2. Отыскание подколец, подполей и гомоморфизмов. Отыскание идеалов факторкольца кольца многочленов от одной и многих переменных и операции над ними. Вычисления с идеалами полиномиальных колец.
Тема 3. Построение примеров нётеровых колец. Алгоритмические вычисления с многочленами. Редукция и проверка свойств базисов Грёбнера полиномиальных идеалов. Отыскание базисов Грёбнера полиномиальных идеалов.
Тема 4. Отыскание идеалов аффинных алгебраических множеств. Построение примеров соответствия между алгебраическими множествами и идеалами. Решение систем полиномиальных уравнений с помощью базисов Грёбнера.
Тема 5. Сопряженность элементов в группах. Сопряженность перестановок. Построение примеров факторгрупп матричных групп. Вычисления в циклических группах. Построение примеров разрешимых групп. Разложение конечной абелевой группы в прямую сумму циклических групп. Алгоритмические вычисления в матричных группах. Вычисления в группах перестановок. Примитивные, импримитивные группы подстановок. Алгоритмическое генерирование перестановок.
Тема 6. Вычисления в алгебраических числовых полях. Исследование полей разложений многочленов.
Тема 7. Исследование разрешимости конкретных уравнений в радикалах. Алгоритмическое вычисление групп Галуа многочленов.
|
Трудоёмкость
(з.е. / часы)
|
4 ЗЕ /144часа.
|
Форма итогового контроля знаний
|
Зачет с оценкой.
| |
