Бакалавриат 2024/2025

Алгебра

Статус: Курс обязательный (Компьютерные науки и анализ данных)

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет компьютерных наук

Когда читается: 2-й курс, 1, 2 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для своего кампуса

Преподаватели: Калеева Галина Анатольевна, Трушин Дмитрий Витальевич

Язык: русский

Кредиты: 6

Программа дисциплины

Аннотация

Данный курс является плавным введением в теорию алгебраических структур, включая теорию групп, колец, полей с приложениями к криптографии, теории кодирования и символьных вычислений. Изученный материал может быть использован в теории формальных языков, теории игр, информационной безопасности. В рамках данного курса считается, что студенты уже прошли курс линейной алгебры, математического анализа и дискретную математику первого курса.

Цель освоения дисциплины

• Составить представление об основных алгебраических структурах и примерах их применения.
• Поупражняться в вычислениях в группах, кольцах и полях.
• Научиться работать с кодами исправляющими ошибки.
• Освоить символьные вычисления на примере базисов Гребнера.
• Освоить криптографические алгоритмы на основе подхода Диффи-Хеллмана.

Планируемые результаты обучения

• Применить теорему о гомоморфизме для описания фактор группы.
• Проверить является ли данная группа циклической.
• Проверить является ли данная подгруппа нормальной.
• Проверить является ли множество с операцией группой.
• Вычислить порядок элемента в данной группе.
• Построить фактор группу для заданной группы и нормальной подгруппы.
• Привести пример группы.
• Привести пример нормальной группы.
• Дать определение группы.
• Дать определение гомоморфизма и изоморфизма.
• Сформулировать Китайскую теорему об остатках.
• Применить алгоритм шифровки и дешшифровки для передачи сообщения.
• Описать механизм обмена ключами по Диффи-Хеллману.
• Описать алгоритм шифрования и дешифрования на основе проблемы дискретного логарифмирования.
• Привести пример циклической группы подходящей для шифрования.
• Описать операции на кольце полиномиальных остатков.
• Описать алгоритм деления многочленов с одной переменной.
• Сформулировать критерий для кольца полиномиальных остатков, когда оно является полем.
• Привести пример кольца.
• Привести пример идеала.
• Привести пример неприводимого многочлена.
• Дать определение кольца.
• Дать определение идеала.
• Сформулировать теорему о гомоморфизме для колец.
• Явно вычислить структуру конечного расширения поля.
• Описать псевдослучайный генератор Галуа.
• Найти характеристику заданного поля.
• Привести пример поля.
• Привести пример конечного поля.
• Дать определение характеристики поля.
• Дать определение поля.
• Определить расстояние Хэмминга.
• Дать определение линейного кода.
• Дать определение проверочной матрицы кода.
• Установить по проверочной матрице кода количество исправляемых ошибок.
• Построить код БЧХ для заданного количества ошибок.
• Проверить является ли множество полиномов базисом Гребнера.
• Вычислить базис гребнера для данного множества многочленов.
• Для заданного монома найти все мономы меньше заданного.
• Дать определение базиса Гребнера.
• Дать определение неприводимого многочлена.
• Дать определение S-многочлена.
• Дать определение лексикографического порядка.
• Отредуцировать многочлен относительно множества многочленов.

Содержание учебной дисциплины

• Группы
• Криптография
• Кольца и идеалы
• Поля
• Коды с исправлением ошибок
• Базисы Гребнера

Элементы контроля

• Домашние задания
  После каждого семинара студентам выдается письменное домашнее задание на неделю для самостоятельного выполнения. Выполненное домашнее задание проверяется ассистентом.
• Контрольная
  Письменная контрольная проверяющая умение решать задачи по темам курса.
• Экзамен
  Устный экзамен, проверяющий знание теории по курсу.

Промежуточная аттестация

• 2024/2025 2nd module
  0.3 * Домашние задания + 0.3 * Контрольная + 0.4 * Экзамен

Список литературы

Рекомендуемая основная литература

• Базисы Гребнера и системы алгебраических уравнений, Аржанцев, И. В., 2003
• Введение в алгебру : основы алгебры : учебник для вузов, Кострикин, А. И., 1994
• Введение в алгебру. Ч.1: Основы алгебры, Кострикин, А. И., 2012
• Заметки по теории кодирования, Ромащенко, А. Е., 2017
• Курс алгебры, Винберг, Э. Б., 2019

Рекомендуемая дополнительная литература

• Практическая криптография, Фергюсон, Нильс, 2005
• Сборник задач по алгебре, учебник, под ред. А. И. Кострикина, 3-е изд., испр. и доп., 464 с., , 2001

Авторы

• Боднарук Иван Иванович
• Трушин Дмитрий Витальевич