Бакалавриат
2022/2023
Алгебра
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс обязательный (Компьютерные науки и анализ данных)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
2-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Язык:
русский
Кредиты:
5
Контактные часы:
60
Программа дисциплины
Аннотация
Данный курс является плавным введением в теорию алгебраических структур, включая теорию групп, колец, полей с приложениями к криптографии, теории кодирования и символьных вычислений. Изученный материал может быть использован в теории формальных языков, теории игр, информационной безопасности. В рамках данного курса считается, что студенты уже прошли курс линейной алгебры, математического анализа и дискретную математику первого курса.
Цель освоения дисциплины
- Составить представление об основных алгебраических структурах и примерах их применения.
- Поупражняться в вычислениях в группах, кольцах и полях.
- Научиться работать с кодами исправляющими ошибки.
- Освоить символьные вычисления на примере базисов Гребнера.
- Освоить криптографические алгоритмы на основе подхода Диффи-Хеллмана.
Планируемые результаты обучения
- Применить теорему о гомоморфизме для описания фактор группы.
- Проверить является ли данная группа циклической.
- Проверить является ли данная подгруппа нормальной.
- Проверить является ли множество с операцией группой.
- Вычислить порядок элемента в данной группе.
- Построить фактор группу для заданной группы и нормальной подгруппы.
- Привести пример группы.
- Привести пример нормальной группы.
- Дать определение группы.
- Дать определение гомоморфизма и изоморфизма.
- Сформулировать Китайскую теорему об остатках.
- Применить алгоритм шифровки и дешшифровки для передачи сообщения.
- Описать механизм обмена ключами по Диффи-Хеллману.
- Описать алгоритм шифрования и дешифрования на основе проблемы дискретного логарифмирования.
- Привести пример циклической группы подходящей для шифрования.
- Описать операции на кольце полиномиальных остатков.
- Описать алгоритм деления многочленов с одной переменной.
- Сформулировать критерий для кольца полиномиальных остатков, когда оно является полем.
- Привести пример кольца.
- Привести пример идеала.
- Привести пример неприводимого многочлена.
- Дать определение кольца.
- Дать определение идеала.
- Сформулировать теорему о гомоморфизме для колец.
- Явно вычислить структуру конечного расширения поля.
- Описать псевдослучайный генератор Галуа.
- Найти характеристику заданного поля.
- Привести пример поля.
- Привести пример конечного поля.
- Дать определение характеристики поля.
- Дать определение поля.
- Определить расстояние Хэмминга.
- Дать определение линейного кода.
- Дать определение проверочной матрицы кода.
- Установить по проверочной матрице кода количество исправляемых ошибок.
- Построить код БЧХ для заданного количества ошибок.
- Проверить является ли множество полиномов базисом Гребнера.
- Вычислить базис гребнера для данного множества многочленов.
- Для заданного монома найти все мономы меньше заданного.
- Дать определение базиса Гребнера.
- Дать определение неприводимого многочлена.
- Дать определение S-многочлена.
- Дать определение лексикографического порядка.
- Отредуцировать многочлен относительно множества многочленов.
Содержание учебной дисциплины
- Группы
- Криптография
- Кольца и идеалы
- Поля
- Коды с исправлением ошибок
- Базисы Гребнера
Элементы контроля
- Домашние заданияПосле каждого семинара студентам выдается письменное домашнее задание на неделю для самостоятельного выполнения. Выполненное домашнее задание проверяется ассистентом.
- КонтрольнаяПисьменная контрольная проверяющая умение решать задачи по темам курса.
- ЭкзаменУстный экзамен, проверяющий знание теории по курсу.
Промежуточная аттестация
- 2022/2023 учебный год 2 модуль0.4 * Экзамен + 0.3 * Контрольная + 0.3 * Домашние задания
Список литературы
Рекомендуемая основная литература
- Базисы Гребнера и системы алгебраических уравнений, Аржанцев, И. В., 2003
- Введение в алгебру : основы алгебры : учебник для вузов, Кострикин, А. И., 1994
- Введение в алгебру. Ч.1: Основы алгебры, Кострикин, А. И., 2012
- Заметки по теории кодирования, Ромащенко, А. Е., 2017
- Курс алгебры, Винберг, Э. Б., 2019
Рекомендуемая дополнительная литература
- Практическая криптография, Фергюсон, Нильс, 2005
- Сборник задач по алгебре, учебник, под ред. А. И. Кострикина, 3-е изд., испр. и доп., 464 с., , 2001