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

Материал из 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|Кропотов Дмитрий]], Варламова Арина, Добролюбова Ольга
-Свои вопросы по курсу и пожелания можно направлять письмом по адресу ''sgur@cs.msu.ru''
+Свои вопросы по курсу можно задавать в [https://t.me/joinchat/FIB6dhRLLmm2tsiEIl_ayw телеграм-чате].
-В осеннем семестре 2017/2018 уч. г. занятия проходят на ВМК по понедельникам в ауд. П-8а, начало в 12-50.
+В осеннем семестре 2020/2021 уч. г. занятия проходят в дистанционном режиме по понедельникам, начало в 12-50.
-== Новости ==
+Видеозаписи отдельных занятий: [https://www.youtube.com/playlist?list=PLVF5PzSHILHQ4YmzPn2eYBUrZina5OrS_ ссылка]
-'''08.01.18''': выложены результаты проверки практического задания
+<!--
+== Практическое задание ==
-'''06.01.18''': выложены результаты переписывания контрольной от 20.12.
+Студенты, успешно справившиеся с контрольной работой, могут выполнить практическое задание в качестве альтернативы сдачи экзамена по курсу. Задание выполняется на языке python 3. Срок сдачи: 31 декабря, 23:59. За выполнение этого задания можно получить оценку 5, 4 или 0. В случае получения оценки 4 за задание можно сдавать устный экзамен по курсу по обычной схеме. В случае выявления плагиата в коде задания для всех участвующих студентов оценка за задание будет аннулирована, а оценка за экзамен будет снижена на балл.
-'''28.12.17''': переписывание контрольной работы для студентов, пропустивших переписывание 20 декабря по уважительной причине, состоится завтра (29.12.) в ауд. 523, начало в 11-00.
+Вопросы по заданию можно направлять письмом по адресу ''bayesml@gmail.com''. В название письма обязательно добавлять тег [ВМК ПА18].
-'''26.12.17''': добавлены вопросы к экзамену.
+[[Media:AA3_2018_assignment.pdf|Формулировка задания]]
-'''18.12.17''': выложено практическое задание по курсу.
+[https://docs.google.com/spreadsheets/d/1Y5w8SvOwq4yeCmHCpk657rJy6DkmPqiCq48MPBaSUr4/edit?usp=sharing Результаты проверки задания]
+-->
-'''15.12.17''': консультация по контрольной состоится 18 декабря в ауд. П-8а, начало в 12-50. Переписывание контрольной работы состоится 20 декабря в 18-00 в ауд. 685.
-'''15.12.17''': выложены результаты контрольной работы от 20.11.
-'''13.11.17''': в ближайший понедельник, 20 ноября, состоится написание контрольной работы по курсу. Студенты групп 320, 323, 324, 325 пишут контрольную работу в '''ауд. П-8а''', начало в '''12-50'''. Студенты групп 321, 322, 327, 328 пишут контрольную в '''ауд. П-14''', начало в '''16-20'''.
-'''18.09.17''': занятия по курсу теперь проходят в ауд. П-8а.
 == Экзамен ==
+Консультации к экзамену состоятся 6 января в 14-00 и 10 января в 12-00. [https://zoom.us/j/94903294013?pwd=VXR0RlZ0MGdVdTlZSGVQOFNVakNLUT09 Зум-ссылка].
-Экзамен по курсу для групп 320, 321, 322, 323 состоится 8 января в ауд. П-6, начало в 9-00. Экзамен для групп 324, 325, 327, 328 состоится 20 января в ауд. П-5, начало в 9-00. На экзамене при подготовке билета разрешается пользоваться любыми материалами (в том числе с электронных устройств). При непосредственном ответе ничем пользоваться нельзя. Обратите внимание на теоретический минимум. Незнание ответа на любой вопрос из теоретического минимума влечёт за собой неудовлетворительную оценку за экзамен. К экзамену допускаются только студенты, успешно справившиеся с контрольной работой.
+Все студенты, сдающие экзамен, заранее распределяются по конкретному дню/времени сдачи. Для участия в экзамене необходимо [https://classroom.google.com/c/MjEyMzM3ODI1MDM4?cjc=r6omfqi добавиться] в курс на классруме. За час до запланированного времени сдачи студент через классрум получает номер экзаменационного вопроса, а также зум-ссылку. В течение этого часа студент самостоятельно пишет ответ на экзаменационный вопрос. При этом разрешается пользоваться любыми материалами. Далее в указанное время студент подключается по зум-ссылке и сдаёт устный экзамен экзаменатору. При ответе экзаменатору со стороны студента должна быть обеспечена возможность интерактивного написания формул. Здесь можно использовать графический планшет или установить мобильный телефон в качестве выносной веб-камеры, закрепить его над столом и далее писать ручкой на бумаге. Опрос по курсу начинается с вопросов теоретического минимума. На эти вопросы студент должен готов отвечать без подготовки. Неудовлетворительный ответ на вопросы теор.минимума влечёт неудовлетворительную оценку за экзамен.
-[[Media:AA3_2017_exam_questions.pdf|Вопросы к экзамену]]
+[[Media:AA3-2020-exam-questions.pdf|Вопросы к экзамену]]
-[[Media:AA3_2017_theormin.pdf|Теоретический минимум]]
+[[Media:AA3-2020-theormin.pdf|Теоретический минимум]]
-== Контрольная работа ==
-В программе курса предусмотрена письменная контрольная работа. Успешное написание контрольной работы является обязательным условием допуска к экзамену по курсу. При отсутствии допуска студент пишет контрольную работу на экзамене и, в случае успеха, сдает экзамен на первой пересдаче. При написании контрольной работы разрешается пользоваться любыми бумажными материалами, а также калькуляторами. Использование электронных устройств (кроме калькуляторов) запрещено.
-[https://docs.google.com/spreadsheets/d/1rwz5vo0_LCm01KoN24iEx9dd1IkOy2y4r_5i7xqPD6g/edit?usp=sharing Результаты контрольной]
-== Практическое задание ==
-Все студенты, которые успешно написали контрольную работу с первого раза, могут выполнить практическое задание в качестве альтернативы сдачи экзамена. За практическое задание можно получить оценку 5, 4 и 0. В последнем случае студент сдаёт экзамен. При желании можно также сдавать экзамен при получении оценки 4 за практическое задание.
-Внимание! Задание выполняется полностью самостоятельно. Все похожие коды будут расцениваться как плагиат, а все задействованные в плагиате студенты будут наказаны (в том числе те, у кого списали).
-Вопросы по заданию можно задавать письмом на ''bayesml@gmail.com''. В название письма просьба обязательно добавлять [ПА17].
-Срок сдачи задания: '''30 декабря (суббота), 23:59.'''
-[[Media:AA3_assignment.pdf|Формулировка задания]]
-[https://docs.google.com/spreadsheets/d/1HR_vw0359qjYgy-y3NGcYCueSHPZGXqS5mtvQg8tsiU/edit?usp=sharing Результаты проверки задания]
 == Материалы ==
+[[Media:AA3-2020.pdf|Конспект лекций]]
-[[Media:AA3.pdf|Конспект лекций]] {{важно|(обновлено 15.12.)}}
+== Программа курса ==
-== Программа курса ==
+=== Группы, кольца, поля ===
+# Группы
+# Кольца и поля
+# Векторные пространства, гомоморфизмы, сравнения
-=== Конечные поля (поля Галуа) ===
+=== Конечные кольца и поля ===
-# Группы и кольца (напоминание)
+# Поля Галуа
-# Поле вычетов по модулю простого числа
+# Вычисления в конечных кольцах и полях
-# Вычисление элементов в конечных полях
+# Алгебра векторов над конечным полем
-# Линейная алгебра над конечным полем
 # Корни многочленов над конечным полем
-# Существование и единственность поля Галуа из <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.
-# Берлекэмп Э. Алгебраическая теория кодирования. - М.: Мир, 1971.
-# Блейхут Р. Теория и практика кодов, контролирующих ошибки. - М.: Мир, 1986.
-# Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. - М.: Связь. - 1979.
-# Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. – М.: Техносфера. - 2006.
-# Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. – М.: Мир. – 1976.
 == См. также ==