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

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

(Различия между версиями)
Перейти к: навигация, поиск
(25 промежуточных версий не показаны.)
Строка 1: Строка 1:
__NOTOC__
__NOTOC__
-
Обзорный курс для студентов 3-го потока ВМК МГУ по основам алгебры (группы, кольца, поля, частично-упорядоченные множества) и её приложениям в кодировании и комбинаторике.
+
Обзорный курс для студентов 3-го потока ВМК МГУ по основам алгебры (группы, кольца, поля) и её приложениям в кодировании и шифровании.
Лектор: [[Участник:Sgur|Гуров Сергей Исаевич]]
Лектор: [[Участник:Sgur|Гуров Сергей Исаевич]]
Строка 8: Строка 8:
Свои вопросы по курсу и пожелания можно направлять письмом по адресу ''sgur@cs.msu.ru''
Свои вопросы по курсу и пожелания можно направлять письмом по адресу ''sgur@cs.msu.ru''
-
В осеннем семестре 2017/2018 уч. г. занятия проходят на ВМК по понедельникам в ауд. П-, начало в 12-50.
+
В осеннем семестре 2019/2020 уч. г. занятия проходят на ВМК по понедельникам в ауд. П-8, начало в 12-50.
== Новости ==
== Новости ==
 +
'''05.11.19''': в ближайший понедельник 11 ноября состоится написание письменной контрольной работы по курсу. Студенты групп 323, 324 и 325 пишут контрольную работу в ауд. П-8, начало в 12-50. Студенты групп 320, 321, 327 и 328 пишут контрольную работу в ауд. П-5, начало в 14-35.
-
'''28.12.17''': переписывание контрольной работы для студентов, пропустивших переписывание 20 декабря по уважительной причине, состоится завтра (29.12.) в ауд. 523, начало в 11-00.
+
'''23.09.19''': лекция по курсу 23 сентября отменяется.
-
 
+
-
'''26.12.17''': добавлены вопросы к экзамену.
+
-
 
+
-
'''18.12.17''': выложено практическое задание по курсу.
+
-
 
+
-
'''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а.
+
-
 
+
-
== Экзамен ==
+
-
 
+
-
Экзамен по курсу для групп 320, 321, 322, 323 состоится 8 января в ауд. П-6, начало в 9-00. Экзамен для групп 324, 325, 327, 328 состоится 20 января в ауд. П-5, начало в 9-00. На экзамене при подготовке билета разрешается пользоваться любыми материалами (в том числе с электронных устройств). При непосредственном ответе ничем пользоваться нельзя. Обратите внимание на теоретический минимум. Незнание ответа на любой вопрос из теоретического минимума влечёт за собой неудовлетворительную оценку за экзамен. К экзамену допускаются только студенты, успешно справившиеся с контрольной работой.
+
-
 
+
-
[[Media:AA3_2017_exam_questions.pdf|Вопросы к экзамену]]
+
-
 
+
-
[[Media:AA3_2017_theormin.pdf|Теоретический мимимум]]
+
== Контрольная работа ==
== Контрольная работа ==
Строка 38: Строка 19:
В программе курса предусмотрена письменная контрольная работа. Успешное написание контрольной работы является обязательным условием допуска к экзамену по курсу. При отсутствии допуска студент пишет контрольную работу на экзамене и, в случае успеха, сдает экзамен на первой пересдаче. При написании контрольной работы разрешается пользоваться любыми бумажными материалами, а также калькуляторами. Использование электронных устройств (кроме калькуляторов) запрещено.
В программе курса предусмотрена письменная контрольная работа. Успешное написание контрольной работы является обязательным условием допуска к экзамену по курсу. При отсутствии допуска студент пишет контрольную работу на экзамене и, в случае успеха, сдает экзамен на первой пересдаче. При написании контрольной работы разрешается пользоваться любыми бумажными материалами, а также калькуляторами. Использование электронных устройств (кроме калькуляторов) запрещено.
-
[https://docs.google.com/spreadsheets/d/1rwz5vo0_LCm01KoN24iEx9dd1IkOy2y4r_5i7xqPD6g/edit?usp=sharing Результаты контрольной]
+
<!--
-
 
+
== Практическое задание ==
== Практическое задание ==
-
Все студенты, которые успешно написали контрольную работу с первого раза, могут выполнить практическое задание в качестве альтернативы сдачи экзамена. За практическое задание можно получить оценку 5, 4 и 0. В последнем случае студент сдаёт экзамен. При желании можно также сдавать экзамен при получении оценки 4 за практическое задание.
+
Студенты, успешно справившиеся с контрольной работой, могут выполнить практическое задание в качестве альтернативы сдачи экзамена по курсу. Задание выполняется на языке python 3. Срок сдачи: 31 декабря, 23:59. За выполнение этого задания можно получить оценку 5, 4 или 0. В случае получения оценки 4 за задание можно сдавать устный экзамен по курсу по обычной схеме. В случае выявления плагиата в коде задания для всех участвующих студентов оценка за задание будет аннулирована, а оценка за экзамен будет снижена на балл.
-
Внимание! Задание выполняется полностью самостоятельно. Все похожие коды будут расцениваться как плагиат, а все задействованные в плагиате студенты будут наказаны (в том числе те, у кого списали).
+
Вопросы по заданию можно направлять письмом по адресу ''bayesml@gmail.com''. В название письма обязательно добавлять тег [ВМК ПА18].
-
Вопросы по заданию можно задавать письмом на ''bayesml@gmail.com''. В название письма просьба обязательно добавлять [ПА17].
+
[[Media:AA3_2018_assignment.pdf|Формулировка задания]]
-
Срок сдачи задания: '''30 декабря (суббота), 23:59.'''
+
[https://docs.google.com/spreadsheets/d/1Y5w8SvOwq4yeCmHCpk657rJy6DkmPqiCq48MPBaSUr4/edit?usp=sharing Результаты проверки задания]
 +
-->
 +
== Материалы ==
-
[[Media:AA3_assignment.pdf|Формулировка задания]]
+
[[Media:AA3-2019.pdf|Конспект лекций]]
-
== Материалы ==
+
[[Media:AA3-test-problems.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.
+
== См. также ==
== См. также ==

Версия 16:58, 10 ноября 2019

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

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

Ассистент: Кропотов Д.А.

Свои вопросы по курсу и пожелания можно направлять письмом по адресу sgur@cs.msu.ru

В осеннем семестре 2019/2020 уч. г. занятия проходят на ВМК по понедельникам в ауд. П-8, начало в 12-50.

Новости

05.11.19: в ближайший понедельник 11 ноября состоится написание письменной контрольной работы по курсу. Студенты групп 323, 324 и 325 пишут контрольную работу в ауд. П-8, начало в 12-50. Студенты групп 320, 321, 327 и 328 пишут контрольную работу в ауд. П-5, начало в 14-35.

23.09.19: лекция по курсу 23 сентября отменяется.

Контрольная работа

В программе курса предусмотрена письменная контрольная работа. Успешное написание контрольной работы является обязательным условием допуска к экзамену по курсу. При отсутствии допуска студент пишет контрольную работу на экзамене и, в случае успеха, сдает экзамен на первой пересдаче. При написании контрольной работы разрешается пользоваться любыми бумажными материалами, а также калькуляторами. Использование электронных устройств (кроме калькуляторов) запрещено.

Материалы

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

Задачи для подготовки к контрольной

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

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

  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.

См. также

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

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

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