Прикладная алгебра (курс лекций, С.И. Гуров)

Материал из MachineLearning.

(Различия между версиями)

Текущая версия

Обзорный курс для студентов 3-го потока ВМК МГУ по основам алгебры (группы, кольца, поля) и её приложениям в кодировании и шифровании.

Лектор: Гуров Сергей Исаевич

Ассистенты: Кропотов Дмитрий, Варламова Арина, Добролюбова Ольга

Свои вопросы по курсу можно задавать в телеграм-чате.

В осеннем семестре 2020/2021 уч. г. занятия проходят в дистанционном режиме по понедельникам, начало в 12-50.

Видеозаписи отдельных занятий: ссылка

Экзамен

Консультации к экзамену состоятся 6 января в 14-00 и 10 января в 12-00. Зум-ссылка.

Все студенты, сдающие экзамен, заранее распределяются по конкретному дню/времени сдачи. Для участия в экзамене необходимо добавиться в курс на классруме. За час до запланированного времени сдачи студент через классрум получает номер экзаменационного вопроса, а также зум-ссылку. В течение этого часа студент самостоятельно пишет ответ на экзаменационный вопрос. При этом разрешается пользоваться любыми материалами. Далее в указанное время студент подключается по зум-ссылке и сдаёт устный экзамен экзаменатору. При ответе экзаменатору со стороны студента должна быть обеспечена возможность интерактивного написания формул. Здесь можно использовать графический планшет или установить мобильный телефон в качестве выносной веб-камеры, закрепить его над столом и далее писать ручкой на бумаге. Опрос по курсу начинается с вопросов теоретического минимума. На эти вопросы студент должен готов отвечать без подготовки. Неудовлетворительный ответ на вопросы теор.минимума влечёт неудовлетворительную оценку за экзамен.

Вопросы к экзамену

Теоретический минимум

Материалы

Конспект лекций

Программа курса

Группы, кольца, поля

Группы
Кольца и поля
Векторные пространства, гомоморфизмы, сравнения

Конечные кольца и поля

Поля Галуа
Вычисления в конечных кольцах и полях
Алгебра векторов над конечным полем
Корни многочленов над конечным полем
Циклические подпространства колец вычетов

Коды, исправляющие ошибки

Блоковое кодирование: основные понятия
Линейные коды
Синдромное декодирование линейных кодов
Циклические коды
Коды БЧХ
Декодирование кодов БЧХ

Алгебраические основы криптографии

Основные понятия
Система шифрования RSA
Факторизация натуральных чисел
Дискретное логарифмирование
Криптосистемы МакЭлиса и Нидеррайтера

Начала эллиптической криптографии

Эллиптические кривые: введение
Основные понятия
Эллиптические кривые в конечных полях
Криптосистемы на эллиптических кривых

Литература

Журавлёв Ю. И., Флёров Ю. А., Вялый М. Н. Дискретный анализ. Основы высшей алгебры. М.: МЗ Пресс, 2007.
Лидл Р., Нидеррайтер Г. Конечные поля: В 2-х т. М.: Мир, 1988.
Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.: Техносфера, 2006.
Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.: Мир, 1976.
Токарева Н. Н. Симметричная криптография. Краткий курс: учебное пособие / Новосиб. гос. ун-т. Новосибирск, 2012.
Применко Э. А. Алгебраические основы криптографии: Учебное пособие. - М.: Книжный дом «Либроком», 2014.

См. также

Страница кафедры математических методов прогнозирования ВМК МГУ

Курс «Прикладная алгебра» для студентов ММП

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BA%D0%BB%D0%B0%D0%B4%D0%BD%D0%B0%D1%8F_%D0%B0%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D0%B0_%28%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%2C_%D0%A1.%D0%98._%D0%93%D1%83%D1%80%D0%BE%D0%B2%29»

Категория: Учебные курсы

@@ Строка 1: / Строка 1: @@
 __NOTOC__
-Обзорный курс для студентов 3-го потока ВМК МГУ по основам алгебры (группы, кольца, поля, частично-упорядоченные множества) и её приложениям в кодировании и комбинаторике.
+Обзорный курс для студентов 3-го потока ВМК МГУ по основам алгебры (группы, кольца, поля) и её приложениям в кодировании и шифровании.
 Лектор: [[Участник:Sgur|Гуров Сергей Исаевич]]
-Ассистент: [[Участник:Kropotov|Кропотов Д.А.]]
+Ассистенты: [[Участник:Kropotov|Кропотов Дмитрий]], Варламова Арина, Добролюбова Ольга
-Свои вопросы по курсу и пожелания можно направлять письмом по адресу ''bayesml@gmail.com'', в название письма просьба добавлять [ПА15]
+Свои вопросы по курсу можно задавать в [https://t.me/joinchat/FIB6dhRLLmm2tsiEIl_ayw телеграм-чате].
-В осеннем семестре 2015/2016 уч. г. занятия проходят на ВМК по понедельникам в ауд. П-8, начало в 14-35.
+В осеннем семестре 2020/2021 уч. г. занятия проходят в дистанционном режиме по понедельникам, начало в 12-50.
-'''[http://goo.gl/forms/Hgfe4ddCOh Опрос по курсу]'''
+Видеозаписи отдельных занятий: [https://www.youtube.com/playlist?list=PLVF5PzSHILHQ4YmzPn2eYBUrZina5OrS_ ссылка]
-== Новости ==
+<!--
-'''13.02.16''' Результаты контрольной работы, писавшейся 11 февраля, добавлены в таблицу. На последней пересдаче 18 февраля студенты, не имеющие допуск по контрольной работе, пишут контрольную работу и, в случае успеха, в тот же день сдают экзамен.
+== Практическое задание ==
-'''03.02.16''' Пересдачи экзамена по курсу состоятся 11 и 18 февраля в ауд. 510, начало в 16-20.
+Студенты, успешно справившиеся с контрольной работой, могут выполнить практическое задание в качестве альтернативы сдачи экзамена по курсу. Задание выполняется на языке python 3. Срок сдачи: 31 декабря, 23:59. За выполнение этого задания можно получить оценку 5, 4 или 0. В случае получения оценки 4 за задание можно сдавать устный экзамен по курсу по обычной схеме. В случае выявления плагиата в коде задания для всех участвующих студентов оценка за задание будет аннулирована, а оценка за экзамен будет снижена на балл.
-'''20.01.16''' Результаты контрольной работы, писавшейся на экзамене, добавлены в таблицу.
+Вопросы по заданию можно направлять письмом по адресу ''bayesml@gmail.com''. В название письма обязательно добавлять тег [ВМК ПА18].
-'''13.01.16''' По ссылке выше находится небольшой опрос по курсу. Большая просьба его заполнить. Данные из этого опроса помогут в совершенствовании курса для следующих поколений студентов.
+[[Media:AA3_2018_assignment.pdf|Формулировка задания]]
-'''12.01.16''' Посмотреть незачётные контрольные работы по последнему переписыванию можно будет на консультации к экзамену 15 января.
+[https://docs.google.com/spreadsheets/d/1Y5w8SvOwq4yeCmHCpk657rJy6DkmPqiCq48MPBaSUr4/edit?usp=sharing Результаты проверки задания]
+-->
-'''06.01.16''' Консультация к экзамену состоится 15 января в ауд. П-8а, начало в 16-00.
-'''30.12.15''' Выложены результаты переписывания контрольной от 21 декабря.
-'''14.12.15''' Занятия по курсу завершены. В ближайший понедельник, 21 декабря, состоится (последнее) переписывание контрольной работы. Начало в 14-35, ауд. '''П-8а'''.
-'''14.12.15''' Выложены результаты переписывания контрольной от 8 декабря. Незачётные работы можно посмотреть на ближайшем занятии по курсу.
-'''01.12.15''' Переписывание контрольной работы состоится во вторник, 8 декабря, в ауд. П-8а. Начало в 18-10.
-'''30.11.15''' Выложены результаты контрольной работы от 9 ноября.
-'''24.11.15''' Показ <u>незачётных</u> работ контрольной работы и обсуждение задач контрольной состоится во вторник, 1 декабря, в ауд. П-8а. Начало в 18-10.
-'''16.11.15''' В связи с болезнью лектора занятия по курсу 16 ноября отменяются.
-'''29.10.15''' Контрольная работа состоится 9 ноября (понедельник), начало в 14-35. Студенты групп 320, 321 и 323 пишут работу в ауд. П-8, остальные -- в ауд. П-8а.
-== Контрольная работа ==
-В программе курса предусмотрена письменная контрольная работа. Успешное написание контрольной работы является обязательным условием допуска к экзамену по курсу. При отсутствии допуска студент пишет контрольную работу на экзамене и, в случае успеха, сдает экзамен на первой пересдаче. При написании контрольной работы разрешается пользоваться любыми бумажными материалами, а также калькуляторами. Использование электронных устройств (кроме калькуляторов) запрещено.
-[https://docs.google.com/spreadsheets/d/14llDTJrIYDlRZ2Vo_IIxR-BXEw9TqveFaVH6QkfvmQc/edit?usp=sharing Результаты контрольной]
 == Экзамен ==
+Консультации к экзамену состоятся 6 января в 14-00 и 10 января в 12-00. [https://zoom.us/j/94903294013?pwd=VXR0RlZ0MGdVdTlZSGVQOFNVakNLUT09 Зум-ссылка].
-К экзамену по курсу допускаются только те студенты, которые успешно справились с контрольной работой. На экзамене при подготовке ответа на билет разрешается пользоваться любыми материалами, в том числе, с электронных устройств. При непосредственном ответе ничем пользоваться нельзя. Просьба обратить внимание на теоретический минимум по курсу. Незнание ответа на любой вопрос из теоретического минимума влечёт за собой неудовлетворительную оценку за экзамен. Также просьба обратить внимание на задачи по курсу, особенно, на задачи в разделе по теории Пойя.
+Все студенты, сдающие экзамен, заранее распределяются по конкретному дню/времени сдачи. Для участия в экзамене необходимо [https://classroom.google.com/c/MjEyMzM3ODI1MDM4?cjc=r6omfqi добавиться] в курс на классруме. За час до запланированного времени сдачи студент через классрум получает номер экзаменационного вопроса, а также зум-ссылку. В течение этого часа студент самостоятельно пишет ответ на экзаменационный вопрос. При этом разрешается пользоваться любыми материалами. Далее в указанное время студент подключается по зум-ссылке и сдаёт устный экзамен экзаменатору. При ответе экзаменатору со стороны студента должна быть обеспечена возможность интерактивного написания формул. Здесь можно использовать графический планшет или установить мобильный телефон в качестве выносной веб-камеры, закрепить его над столом и далее писать ручкой на бумаге. Опрос по курсу начинается с вопросов теоретического минимума. На эти вопросы студент должен готов отвечать без подготовки. Неудовлетворительный ответ на вопросы теор.минимума влечёт неудовлетворительную оценку за экзамен.
-[[Media:AA3-2015-exam-theormin.pdf| Теоретический минимум]]
+[[Media:AA3-2020-exam-questions.pdf|Вопросы к экзамену]]
-[[Media:AA3-2015-exam-questions.pdf| Вопросы к экзамену]]
+[[Media:AA3-2020-theormin.pdf|Теоретический минимум]]
 == Материалы ==
+[[Media:AA3-2020.pdf|Конспект лекций]]
-[[Media:AA3-2015-0.pdf|Группы, кольца]]
+== Программа курса ==
-[[Media:AA3-2015-1(GF-I).pdf|Конечные поля (часть 1)]]
+=== Группы, кольца, поля ===
+# Группы
-[[Media:AA3-2015-1(GF-II).pdf|Конечные поля (часть 2)]]
+# Кольца и поля
+# Векторные пространства, гомоморфизмы, сравнения
-[[Media:AA3-2015-2(ECC).pdf|Коды, исправляющие ошибки]]
-[[Media:AA3-2015-3(PET).pdf|Теория перечисления Пойя]]
-[[Media:AA3-2015-4(Posets).pdf|Частично упорядоченные множества]]
-== Программа курса ==
-=== Конечные поля (поля Галуа) ===
+=== Конечные кольца и поля ===
-# Группы и кольца (напоминание)
+# Поля Галуа
-# Поле вычетов по модулю простого числа
+# Вычисления в конечных кольцах и полях
-# Вычисление элементов в конечных полях
+# Алгебра векторов над конечным полем
-# Линейная алгебра над конечным полем
 # Корни многочленов над конечным полем
-# Существование и единственность поля Галуа из <tex>p^n</tex> элементов
+# Циклические подпространства колец вычетов
-# Циклические подпространства
-# Решение задач
 === Коды, исправляющие ошибки ===
-# Помехоустойчивое кодирование, блоковое кодирование, коды Хэмминга
+# Блоковое кодирование: основные понятия
-# Групповые (линейные) коды
+# Линейные коды
+# Синдромное декодирование линейных кодов
 # Циклические коды
 # Коды БЧХ
-# Решение задач
+# Декодирование кодов БЧХ
-=== Теория перечисления Пойя ===
+=== Алгебраические основы криптографии ===
-# Действие группы на множестве
+# Основные понятия
-# Применение леммы Бернсайда для решения комбинаторных задач
+# Система шифрования RSA
-# Применение теоремы Пойя для решения комбинаторных задач
+# Факторизация натуральных чисел
+# Дискретное логарифмирование
+# Криптосистемы МакЭлиса и Нидеррайтера
-=== Некоторые вопросы теории частично упорядоченных множеств ===
+=== Начала эллиптической криптографии ===
-# Основные понятия теории ч.у. множеств
+# Эллиптические кривые: введение
-# Операции над ч.у. множествами
+# Основные понятия
-# Линеаризация
+# Эллиптические кривые в конечных полях
-# Модели Крипке
+# Криптосистемы на эллиптических кривых
-# Решение задач
 == Литература ==
-# Воронин В.П. [http://padabum.com/d.php?id=10281 Дополнительные главы дискретной математики], ф-т ВМК, 2002.
+# Журавлёв Ю. И., Флёров Ю. А., Вялый М. Н. [http://vyalyy.narod.ru/da2-090419.pdf Дискретный анализ. Основы высшей алгебры.] М.: МЗ Пресс, 2007.
-# Гуров С.И. [http://istina.msu.ru/publications/book/641802/ Булевы алгебры, упорядоченные множества, решетки: определения, свойства, примеры.] Либроком, 2013.
+# Лидл Р., Нидеррайтер Г. [http://www.twirpx.com/file/34003/ Конечные поля: В 2-х т.] М.: Мир, 1988.
-# Журавлев Ю.И., Флеров Ю.А., Вялый М.Н. [http://vyalyy.narod.ru/da2-090419.pdf Дискретный анализ. Основы высшей алгебры.] М3-Пресс, 2007.
+# Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.: Техносфера, 2006.
-# Лидл Р., Нидеррайтер Г. [http://www.twirpx.com/file/34003/ Конечные поля: в 2-х т.] Мир, 1988.
+# Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.: Мир, 1976.
-# Нефедов В.Н., Осипова В.А. [http://www.twirpx.com/file/391140/ Курс дискретной математики], МАИ, 1992.
+# Токарева Н. Н. Симметричная криптография. Краткий курс: учебное пособие / Новосиб. гос. ун-т. Новосибирск, 2012.
-# Ромащенко А.Е., Румянцев А.Ю., Шень А. [ftp://ftp.mccme.ru/users/shen/coding.pdf Заметки по теории кодирования.] МЦНМО, 2011.
+# Применко Э. А. Алгебраические основы криптографии: Учебное пособие. - М.: Книжный дом «Либроком», 2014.
-# Lin S., Costello D. [http://www.twirpx.com/file/622076/ Error Control Coding Fundamentals and Applications.] Prentice-Hall, 1983.
 == См. также ==