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

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

(Различия между версиями)
Перейти к: навигация, поиск
 
(21 промежуточная версия не показана)
Строка 1: Строка 1:
__NOTOC__
__NOTOC__
-
Обзорный курс для студентов 3-го потока ВМК МГУ по основам алгебры (группы, кольца, поля) и её приложениям в кодировании и комбинаторике.
+
Обзорный курс для студентов 3-го потока ВМК МГУ по основам алгебры (группы, кольца, поля) и её приложениям в кодировании и шифровании.
Лектор: [[Участник:Sgur|Гуров Сергей Исаевич]]
Лектор: [[Участник:Sgur|Гуров Сергей Исаевич]]
-
Ассистент: [[Участник:Kropotov|Кропотов Д.А.]]
+
Ассистенты: [[Участник:Kropotov|Кропотов Дмитрий]], Варламова Арина, Добролюбова Ольга
-
Свои вопросы по курсу и пожелания можно направлять письмом по адресу ''sgur@cs.msu.ru''
+
Свои вопросы по курсу можно задавать в [https://t.me/joinchat/FIB6dhRLLmm2tsiEIl_ayw телеграм-чате].
-
В осеннем семестре 2018/2019 уч. г. занятия проходят на ВМК по понедельникам в ауд. П-8а, начало в 12-50.
+
В осеннем семестре 2020/2021 уч. г. занятия проходят в дистанционном режиме по понедельникам, начало в 12-50.
-
== Новости ==
+
Видеозаписи отдельных занятий: [https://www.youtube.com/playlist?list=PLVF5PzSHILHQ4YmzPn2eYBUrZina5OrS_ ссылка]
-
'''10.12.18''': выложена формулировка практического задания, которое можно выполнять в качестве альтернативы сдачи устного экзамена.
+
<!--
 +
== Практическое задание ==
-
'''03.12.18''': переписывание контрольной работы состоится в следующий вторник, 11 декабря, в ауд. П-8, начало в 18-00.
+
Студенты, успешно справившиеся с контрольной работой, могут выполнить практическое задание в качестве альтернативы сдачи экзамена по курсу. Задание выполняется на языке python 3. Срок сдачи: 31 декабря, 23:59. За выполнение этого задания можно получить оценку 5, 4 или 0. В случае получения оценки 4 за задание можно сдавать устный экзамен по курсу по обычной схеме. В случае выявления плагиата в коде задания для всех участвующих студентов оценка за задание будет аннулирована, а оценка за экзамен будет снижена на балл.
-
'''03.12.18''': в этот четверг, 6 декабря, состоится консультация по решению задач контрольной работы. Ауд. П-14, начало в 18-00.
+
Вопросы по заданию можно направлять письмом по адресу ''bayesml@gmail.com''. В название письма обязательно добавлять тег [ВМК ПА18].
-
'''03.12.18''': выложены результаты контрольной работы от 12 ноября.
+
[[Media:AA3_2018_assignment.pdf|Формулировка задания]]
-
'''08.11.18''': в понедельник, 12 ноября, состоится написание контрольной работы. Студенты групп 323, 324, 327 пишут контрольную в ауд. 579, а студенты групп 320, 321, 325, 328 - в ауд. П-8а.
+
[https://docs.google.com/spreadsheets/d/1Y5w8SvOwq4yeCmHCpk657rJy6DkmPqiCq48MPBaSUr4/edit?usp=sharing Результаты проверки задания]
 +
-->
-
== Контрольная работа ==
+
== Экзамен ==
 +
Консультации к экзамену состоятся 6 января в 14-00 и 10 января в 12-00. [https://zoom.us/j/94903294013?pwd=VXR0RlZ0MGdVdTlZSGVQOFNVakNLUT09 Зум-ссылка].
-
В программе курса предусмотрена письменная контрольная работа. Успешное написание контрольной работы является обязательным условием допуска к экзамену по курсу. При отсутствии допуска студент пишет контрольную работу на экзамене и, в случае успеха, сдает экзамен на первой пересдаче. При написании контрольной работы разрешается пользоваться любыми бумажными материалами, а также калькуляторами. Использование электронных устройств (кроме калькуляторов) запрещено.
+
Все студенты, сдающие экзамен, заранее распределяются по конкретному дню/времени сдачи. Для участия в экзамене необходимо [https://classroom.google.com/c/MjEyMzM3ODI1MDM4?cjc=r6omfqi добавиться] в курс на классруме. За час до запланированного времени сдачи студент через классрум получает номер экзаменационного вопроса, а также зум-ссылку. В течение этого часа студент самостоятельно пишет ответ на экзаменационный вопрос. При этом разрешается пользоваться любыми материалами. Далее в указанное время студент подключается по зум-ссылке и сдаёт устный экзамен экзаменатору. При ответе экзаменатору со стороны студента должна быть обеспечена возможность интерактивного написания формул. Здесь можно использовать графический планшет или установить мобильный телефон в качестве выносной веб-камеры, закрепить его над столом и далее писать ручкой на бумаге. Опрос по курсу начинается с вопросов теоретического минимума. На эти вопросы студент должен готов отвечать без подготовки. Неудовлетворительный ответ на вопросы теор.минимума влечёт неудовлетворительную оценку за экзамен.
-
[https://docs.google.com/spreadsheets/d/1O7soLwBx-AIC3ayucTcysfR_7zvEeh8wiD1aj_ucj1A/edit?usp=sharing Результаты контрольной]
+
[[Media:AA3-2020-exam-questions.pdf|Вопросы к экзамену]]
-
== Практическое задание ==
+
[[Media:AA3-2020-theormin.pdf|Теоретический минимум]]
-
 
+
-
Студенты, успешно справившиеся с контрольной работой, могут выполнить практическое задание в качестве альтернативы сдачи экзамена по курсу. Задание выполняется на языке python 3. Срок сдачи: 31 декабря, 23:59. За выполнение этого задания можно получить оценку 5, 4 или 0. В случае получения оценки 4 за задание можно сдавать устный экзамен по курсу по обычной схеме. В случае выявления плагиата в коде задания для всех участвующих студентов оценка за задание будет аннулирована, а оценка за экзамен будет снижена на балл.
+
-
 
+
-
[[Media:AA3_2018_assignment.pdf|Формулировка задания]]
+
-
 
+
-
{{важно|Здесь появятся юнит-тесты по заданию}}
+
== Материалы ==
== Материалы ==
-
[[Media:AA3_2018.pdf|Конспект лекций]]
+
[[Media:AA3-2020.pdf|Конспект лекций]]
== Программа курса ==
== Программа курса ==
Строка 44: Строка 41:
# Группы
# Группы
# Кольца и поля
# Кольца и поля
 +
# Векторные пространства, гомоморфизмы, сравнения
=== Конечные кольца и поля ===
=== Конечные кольца и поля ===
Строка 63: Строка 61:
# Основные понятия
# Основные понятия
# Система шифрования RSA
# Система шифрования RSA
-
# Простота и факторизация натуральных чисел
+
# Факторизация натуральных чисел
-
# Задача дискретного логарифмирования
+
# Дискретное логарифмирование
 +
# Криптосистемы МакЭлиса и Нидеррайтера
 +
 
 +
=== Начала эллиптической криптографии ===
 +
# Эллиптические кривые: введение
 +
# Основные понятия
 +
# Эллиптические кривые в конечных полях
 +
# Криптосистемы на эллиптических кривых
== Литература ==
== Литература ==

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

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

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

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

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

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

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


Экзамен

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

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

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

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

Материалы

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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

См. также

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

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

Личные инструменты