Delivered at:: Big Data and Information Retrieval School

Course type:: Compulsory course

When:: 1 year, 4 module

Instructors

Федоров Михаил Антонович

Хрыстик Михаил Андреевич

Shafarevich, Anton

Полная версия программы учебной дисциплины

Аннотация

Цель освоения дисциплины «Алгебра» — познакомить слушателей с основными структурами современной алгебры: группами, кольцами и полями. Мы докажем базовые факты об этих структурах и продемонстрируем их возможные приложения.

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

усвоить основные факты о таких алгебраических структурах, как группы, кольца и поля
освоить алгоритмические аспекты современной алгебры
научиться производить базовые вычисления с алгебраическими структурами, применять изученные факты и методы в прикладных задачах
овладеть навыками работы с конечными группами и конечными полями, овладеть основными техническими приёмами алгебры многочленов и теории абелевых групп

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

демонстрирует знание теоремы о классификации конечных абелевых групп, умеет находить порядки элементов и подгруппы заданной конечной абелевой группы
умеет производить вычисления в факторкольце кольца многочленов от одной переменной над полем, умеет находить базис Грёбнера в идеале кольца многочленов от нескольких переменных над полем
умеет производить вычисления в конечных расширениях полей, умеет строить конечные поля и проводить вычисления в них

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

Группы
Бинарные операции. Полугруппы, моноиды, группы, коммутативные (абелевы) группы. Порядок группы. Примеры групп. Подгруппы. Описание всех подгрупп в группе целых чисел по сложению. Циклические подгруппы. Порядок элемента группы. Связь между порядком элемента и порядком порождаемой им циклической подгруппы. Циклические группы. Левые и правые смежные классы группы по подгруппе. Индекс подгруппы, теорема Лагранжа и пять следствий из неё. Нормальные подгруппы. Факторгруппа группы по нормальной подгруппе. Гомоморфизмы групп, простейшие свойства. Изоморфизм групп, изоморфные группы. Классификация циклических групп с точностью до изоморфизма. Ядро и образ гомоморфизма групп. Теорема о гомоморфизме для групп. Прямое произведение групп и разложение группы в прямое произведение подгрупп. Разложение конечной циклической группы. Примарные абелевы группы. Теорема о разложении конечной абелевой группы в прямое произведение примарных циклических групп, доказательство единственности числа и порядков примарных циклических множителей. Экспонента конечной абелевой группы, критерий цикличности. Криптография с открытым ключом. Задача дискретного логарифмирования. Система Диффи-Хеллмана обмена ключами. Криптосистема Эль-Гамаля.
Кольца
Понятие кольца, примеры. Коммутативные кольца. Обратимые элементы, делители нуля, нильпотенты. Поля. Критерий того, что кольцо вычетов является полем. Подкольца, подполя, гомоморфизмы, изоморфизмы. Идеалы в кольце. Главные идеалы и идеалы, порождённые подмножеством коммутативного кольца. Факторкольцо кольца по идеалу. Ядро и образ гомоморфизма колец. Теорема о гомоморфизме для колец. Делимость в коммутативных кольцах без делителей нуля. Ассоциированные элементы. Кольца главных идеалов. Теорема о том, что всякое евклидово кольцо является кольцом главных идеалов. Наибольший общий делитель двух элементов. Существование наибольшего общего делителя для двух элементов a и b евклидова кольца и его линейная выразимость через a и b. Простые элементы. Факториальные кольца. Факториальность колец главных идеалов. Лексикографический порядок на множестве одночленов от нескольких переменных. Лемма о конечности убывающих цепочек одночленов. Старший член многочлена от нескольких переменных. Элементарная редукция многочлена относительно другого многочлена. Лемма о конечности цепочек элементарных редукций относительно системы многочленов. Остаток многочлена относительно заданной системы многочленов. Системы Грёбнера. Характеризация систем Грёбнера в терминах цепочек элементарных редукций. S-многочлены. Критерий Бухбергера. Базис Грёбнера идеала в кольце многочленов от нескольких переменных, теорема о трёх эквивалентных условиях. Решение задачи вхождения многочлена в идеал. Лемма о конечности цепочек одночленов, в которых каждый следующий одночлен не делится ни на один из предыдущих. Алгоритм Бухбергера построения базиса Грёбнера идеала.
Поля
Поля. Примеры. Характеристика поля. Простое подполе. Расширение полей, его степень. Степень композиции двух расширений. Алгебраические и трансцендентные элементы. Минимальный многочлен алгебраического элемента и его свойства. Поле, порождённое алгебраическим элементом. Существование конечного расширения исходного поля, в котором заданный многочлен имеет корень. Поле разложения многочлена. Конечные поля. Порядок конечного поля. Автоморфизм Фробениуса. Существование и единственность конечного поля, порядок которого — степень простого числа. Поле из четырёх элементов. Цикличность мультипликативной группы конечного поля. Неприводимые многочлены над полем вычетов. Описание подполей конечного поля. Коды над конечным алфавитом. Расстояние Хэмминга. Минимальное расстояние кода. Коды, исправляющие t ошибок: определение и эквивалентные переформулировки. Код с повторением. Линейные коды. Проверочная матрица. Связь минимального расстояния линейного кода с его проверочной матрицей. Бинарный код Хэмминга, его минимальное расстояние и число ошибок, которое он может исправлять.

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

Еженедельные домашние задания
Контрольная работа
Экзамен
Для пилотного потока: устный экзамен проводится в Zoom. С 10.00 готовится и отвечает первая подгруппа, в 11.00 приступает к подготовке вторая подгруппа, в 12.00 -- третья подгруппа. Потом перерыв. В 15.00 приступает к подготовке четвертая подгруппа, в 16.00 --- пятая подгруппа, и в 17.00 -- шестая подгруппа. На подготовку дается до 40 минут. На каждом из мероприятий допускаются до 2 обрывов продолжительностью не более 5 минут каждый. В случае более существенных технических проблем по каждому из мероприятий через несколько дней будет организован повторная контрольная/повторный экзамен. Для основного потока: устный экзамен проводится 2 полных дня, формат, при котором студенты запускаются партиями по 10 человек каждые 30 минут. Один студент сначала письменно готовится (под присмотром проктора), а затем устно отвечает одному из принимающих. Экзамен проводится с прокторингом. К экзамену необходимо подключиться за 10 минут. На платформе Экзамус доступно тестирование системы. Компьютер студента должен удовлетворять следующим требованиям:https://elearning.hse.ru/data/2020/05/07/1544135594/Технические%20требования%20к%20ПК%20студента.pdf). Для участия в экзамене студент обязан: заранее зайти на платформу прокторинга, провести тест системы, включить камеру и микрофон, подтвердить личность. Во время экзамена студентам запрещено: общаться (в социальных сетях, с людьми в комнате), списывать.

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

Промежуточная аттестация (4 модуль)
0.3 * Еженедельные домашние задания + 0.2 * Контрольная работа + 0.5 * Экзамен

Bachelor’s Programme 'Applied Mathematics and Information Science'

Algebra

Instructors

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

Аннотация

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

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

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

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

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

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

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

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