Алгебра КНАД 2022/2023

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

Преподаватели и учебные ассистенты

Группа БКНАД211/212
Лектор Дима Трушин
Семинарист Галина Калеева
Ассистент Марина Груздева

Контакты

Преподаватель/Ассистент Как связаться Когда
1
Дима Трушин telegram Напишите мне и мы договоримся о времени проведения консультации
2
Галина Калеева см. конспект 1 семинара Напишите мне и мы договоримся о времени проведения консультации
3
Марина Груздева

Формы контроля знаний студентов

  • Еженедельные домашние задания
  • Письменная контрольная работа по задачам
  • Устный экзамен по теории

Порядок формирования итоговой оценки

Итоговая оценка считается по формуле

F = 0,3 * H + 0,3 T + 0,4 E

где H -- оценка за еженедельные домашние задания, T -- оценка за письменную контрольную, E -- оценка за устный экзамен.

Только финальная оценка F округляется. Правила округления арифметические.

Краткое содержание лекций

Лекция 1 (05.09.2022). Бинарные операции. Ассоциативность, нейтральный элемент, обратный элемент, коммутативность. Определение группы. Аддитивная и мультипликативная нотации. Подгруппы и циклические подгруппы. Порядок элемента. Классификация циклических групп.

Лекция 2 (12.09.2022). Описание подгрупп в группе Z. Описание подгрупп в группе Z_n. Левые и правые смежные классы. Нормальные подгруппы. Теорема Лагранжа и ее следствия.

Лекция 3 (19.09.2022). Гомоморфизмы и изоморфизмы групп. Ядро и обрз гомоморфизма их свойства. Произведение групп. Конечные абелевы группы. Китайская теорема об остатках. Структура конечных абелевых групп.

Лекция 4 (26.09.2022). Вторая версия Китайской теоремы об остатках. Структура Z_{p^n}^*. Криптография. Быстрое возведение в квадрат. Проблема дискретного логарифмирования. Система Диффи-Хелмана. RSA.

Лекция 5 (03.10.2022). Кольца, коммутативные кольца, поля, подкольца. Обратимые элементы, делители нуля, нильпотенты, идемпотенты. Идеалы. Описание идеалов в Z и Z_n. Гомоморфизмы и изоморфизмы колец. Китайская теорема об остатках для колец. Ядро и образ гомоморфизма колец и их свойства.

Лекция 6 (10.10.2022). Многочлены от одной переменной. Алгоритм Евклида деления с остатком, наибольший общий делитель, идеалы в F[x]. Неприводимые многочлены и однозначное разложение на множители в F[x]. Кольца полиномиальных остатков, Китайская теорема об остатках для колец полиномиальных остатков.

Лекция 7 (17.10.2022). Характеристика поля. Расширение полей, расширение корнем. Конечные поля: количество элементов в конечном поле, цикличность мультипликативной группы конечного поля, классификация конечных полей (без доказательства). Конструкция построения конечных полей. Случайные генераторы Галуа и Фибоначчи. Потоковое шифрование.

Лекция 8 (31.10.2022). Коды с исправлением ошибок. Расстояние Хэмминга, минимальное расстояние кода, количество исправляемых ошибок. Линейные коды, вес элемента, проверочная матрица, количество исправляемых ошибок в терминах проверочной матрицы. Коды Хэмминга. Неравенство Синглтона. Коды Рида-Соломона.

Лекция 9 (07.11.2022). Многочлены от нескольких переменных. Лексикографический порядок, стабилизация убывающих цепочек мономов. Элементарная редукция, редукция относительно множества многочленов, остатки, базис Грёбнера. Остановка процесса редукции.

Лекция 10 (14.11.2022). S-многочлен и критерий Бухбергера. Идеалы в кольце многочленов от нескольких переменных, алгоритм Бухбергера для построения базиса Грёбнера идеала. Проблема принадлежности идеалу и исключения переменных. Техническая лемма.

Домашнее задание

Каждый листок содержит задачи с семинара и соответствующее ДЗ. Дедлайн сдачи домашнего задания - начало следующего семинара. Дедлайн мягкий. При опоздании на t часов, оценка умножается на 0.7 t / 24.

Семинар и ДЗ 1

Семинар и ДЗ 2

Семинар и ДЗ 3

Семинар и ДЗ 4

Семинар и ДЗ 5

Семинар и ДЗ 6

Семинар и ДЗ 7. Дедлайн - 3.11.2022, 11.10.

Семинар и ДЗ 8

Семинар и ДЗ 9. Дедлайн - 19.11.2022, 14.00.

Ведомости текущего контроля

  • Домашние задания
211/212

Ссылки

Литература

Основная

  • Курс алгебры, Винберг, Э. Б.
  • Заметки по теории кодирования, Ромащенко, А. Е.
  • Введение в алгебру: основы алгебры: учебник для вузов, Кострикин, А. И.
  • Идеалы, многообразия и алгоритмы. Кокс, Литтл, О'Ши.

Дополнительная

  • Практическая криптография, Фергюсон, Нильс
  • Базисы Гребнера и системы алгебраических уравнений, Аржанцев, И. В.
  • Сборник задач по алгебре, учебник, под ред. А. И. Кострикина, 3-е изд., испр. и доп.