• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 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

Авторы

  • Трушин Дмитрий Витальевич