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

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

(Различия между версиями)
Перейти к: навигация, поиск
(37 промежуточных версий не показаны.)
Строка 6: Строка 6:
Ассистент: [[Участник:Kropotov|Кропотов Д.А.]]
Ассистент: [[Участник:Kropotov|Кропотов Д.А.]]
-
Свои вопросы по курсу и пожелания можно направлять письмом по адресу ''bayesml@gmail.com'', в название письма просьба добавлять [ПА15]
+
Свои вопросы по курсу и пожелания можно направлять письмом по адресу ''sgur@cs.msu.ru''
-
В осеннем семестре 2015/2016 уч. г. занятия проходят на ВМК по понедельникам в ауд. П-8, начало в 14-35.
+
В осеннем семестре 2017/2018 уч. г. занятия проходят на ВМК по понедельникам в ауд. П-, начало в 12-50.
== Новости ==
== Новости ==
-
'''06.01.16''' Консультация к экзамену состоится 15 января, начало в 16-00. Ауд. уточняется.
+
'''08.01.18''': выложены результаты проверки практического задания
-
'''30.12.15''' Выложены результаты переписывания контрольной от 21 декабря.
+
'''06.01.18''': выложены результаты переписывания контрольной от 20.12.
-
'''14.12.15''' Занятия по курсу завершены. В ближайший понедельник, 21 декабря, состоится (последнее) переписывание контрольной работы. Начало в 14-35, ауд. '''П-8а'''.
+
'''28.12.17''': переписывание контрольной работы для студентов, пропустивших переписывание 20 декабря по уважительной причине, состоится завтра (29.12.) в ауд. 523, начало в 11-00.
-
'''14.12.15''' Выложены результаты переписывания контрольной от 8 декабря. Незачётные работы можно посмотреть на ближайшем занятии по курсу.
+
'''26.12.17''': добавлены вопросы к экзамену.
-
'''01.12.15''' Переписывание контрольной работы состоится во вторник, 8 декабря, в ауд. П-8а. Начало в 18-10.
+
'''18.12.17''': выложено практическое задание по курсу.
-
'''30.11.15''' Выложены результаты контрольной работы от 9 ноября.
+
'''15.12.17''': консультация по контрольной состоится 18 декабря в ауд. П-8а, начало в 12-50. Переписывание контрольной работы состоится 20 декабря в 18-00 в ауд. 685.
-
'''24.11.15''' Показ <u>незачётных</u> работ контрольной работы и обсуждение задач контрольной состоится во вторник, 1 декабря, в ауд. П-8а. Начало в 18-10.
+
'''15.12.17''': выложены результаты контрольной работы от 20.11.
-
'''16.11.15''' В связи с болезнью лектора занятия по курсу 16 ноября отменяются.
+
'''13.11.17''': в ближайший понедельник, 20 ноября, состоится написание контрольной работы по курсу. Студенты групп 320, 323, 324, 325 пишут контрольную работу в '''ауд. П-8а''', начало в '''12-50'''. Студенты групп 321, 322, 327, 328 пишут контрольную в '''ауд. П-14''', начало в '''16-20'''.
-
'''29.10.15''' Контрольная работа состоится 9 ноября (понедельник), начало в 14-35. Студенты групп 320, 321 и 323 пишут работу в ауд. П-8, остальные -- в ауд. П-8а.
+
'''18.09.17''': занятия по курсу теперь проходят в ауд. П-8а.
-
== Контрольная работа ==
+
== Экзамен ==
-
В программе курса предусмотрена письменная контрольная работа. Успешное написание контрольной работы является обязательным условием допуска к экзамену по курсу. При отсутствии допуска студент пишет контрольную работу на экзамене и, в случае успеха, сдает экзамен на первой пересдаче. При написании контрольной работы разрешается пользоваться любыми бумажными материалами, а также калькуляторами. Использование электронных устройств (кроме калькуляторов) запрещено.
+
Экзамен по курсу для групп 320, 321, 322, 323 состоится 8 января в ауд. П-6, начало в 9-00. Экзамен для групп 324, 325, 327, 328 состоится 20 января в ауд. П-5, начало в 9-00. На экзамене при подготовке билета разрешается пользоваться любыми материалами (в том числе с электронных устройств). При непосредственном ответе ничем пользоваться нельзя. Обратите внимание на теоретический минимум. Незнание ответа на любой вопрос из теоретического минимума влечёт за собой неудовлетворительную оценку за экзамен. К экзамену допускаются только студенты, успешно справившиеся с контрольной работой.
-
[https://docs.google.com/spreadsheets/d/14llDTJrIYDlRZ2Vo_IIxR-BXEw9TqveFaVH6QkfvmQc/edit?usp=sharing Результаты контрольной]
+
[[Media:AA3_2017_exam_questions.pdf|Вопросы к экзамену]]
-
== Экзамен ==
+
[[Media:AA3_2017_theormin.pdf|Теоретический минимум]]
-
К экзамену по курсу допускаются только те студенты, которые успешно справились с контрольной работой. На экзамене при подготовке ответа на билет разрешается пользоваться любыми материалами, в том числе, с электронных устройств. При непосредственном ответе ничем пользоваться нельзя. Просьба обратить внимание на теоретический минимум по курсу. Незнание ответа на любой вопрос из теоретического минимума влечёт за собой неудовлетворительную оценку за экзамен. Также просьба обратить внимание на задачи по курсу, особенно, на задачи в разделе по теории Пойя.
+
== Контрольная работа ==
-
[[Media:AA3-2015-exam-theormin.pdf| Теоретический минимум]]
+
В программе курса предусмотрена письменная контрольная работа. Успешное написание контрольной работы является обязательным условием допуска к экзамену по курсу. При отсутствии допуска студент пишет контрольную работу на экзамене и, в случае успеха, сдает экзамен на первой пересдаче. При написании контрольной работы разрешается пользоваться любыми бумажными материалами, а также калькуляторами. Использование электронных устройств (кроме калькуляторов) запрещено.
-
[[Media:AA3-2015-exam-questions.pdf| Вопросы к экзамену]]
+
[https://docs.google.com/spreadsheets/d/1rwz5vo0_LCm01KoN24iEx9dd1IkOy2y4r_5i7xqPD6g/edit?usp=sharing Результаты контрольной]
-
== Материалы ==
+
== Практическое задание ==
-
[[Media:AA3-2015-0.pdf|Группы, кольца]]
+
Все студенты, которые успешно написали контрольную работу с первого раза, могут выполнить практическое задание в качестве альтернативы сдачи экзамена. За практическое задание можно получить оценку 5, 4 и 0. В последнем случае студент сдаёт экзамен. При желании можно также сдавать экзамен при получении оценки 4 за практическое задание.
-
[[Media:AA3-2015-1(GF-I).pdf|Конечные поля (часть 1)]]
+
Внимание! Задание выполняется полностью самостоятельно. Все похожие коды будут расцениваться как плагиат, а все задействованные в плагиате студенты будут наказаны (в том числе те, у кого списали).
-
[[Media:AA3-2015-1(GF-II).pdf|Конечные поля (часть 2)]]
+
Вопросы по заданию можно задавать письмом на ''bayesml@gmail.com''. В название письма просьба обязательно добавлять [ПА17].
-
[[Media:AA3-2015-2(ECC).pdf|Коды, исправляющие ошибки]]
+
Срок сдачи задания: '''30 декабря (суббота), 23:59.'''
-
[[Media:AA3-2015-3(PET).pdf|Теория перечисления Пойя]]
+
[[Media:AA3_assignment.pdf|Формулировка задания]]
-
[[Media:AA3-2015-4(Posets).pdf|Частично упорядоченные множества]]
+
[https://docs.google.com/spreadsheets/d/1HR_vw0359qjYgy-y3NGcYCueSHPZGXqS5mtvQg8tsiU/edit?usp=sharing Результаты проверки задания]
 +
 
 +
== Материалы ==
 +
 
 +
[[Media:AA3.pdf|Конспект лекций]] {{важно|(обновлено 15.12.)}}
== Программа курса ==
== Программа курса ==
Строка 82: Строка 86:
# Применение теоремы Пойя для решения комбинаторных задач
# Применение теоремы Пойя для решения комбинаторных задач
-
=== Некоторые вопросы теории частично упорядоченных множеств ===
 
-
# Основные понятия теории ч.у. множеств
 
-
# Операции над ч.у. множествами
 
-
# Линеаризация
 
-
# Модели Крипке
 
-
# Решение задач
 
== Литература ==
== Литература ==
Строка 98: Строка 96:
# Ромащенко А.Е., Румянцев А.Ю., Шень А. [ftp://ftp.mccme.ru/users/shen/coding.pdf Заметки по теории кодирования.] МЦНМО, 2011.
# Ромащенко А.Е., Румянцев А.Ю., Шень А. [ftp://ftp.mccme.ru/users/shen/coding.pdf Заметки по теории кодирования.] МЦНМО, 2011.
# Lin S., Costello D. [http://www.twirpx.com/file/622076/ Error Control Coding Fundamentals and Applications.] Prentice-Hall, 1983.
# Lin S., Costello D. [http://www.twirpx.com/file/622076/ Error Control Coding Fundamentals and Applications.] Prentice-Hall, 1983.
 +
# Берлекэмп Э. Алгебраическая теория кодирования. - М.: Мир, 1971.
 +
# Блейхут Р. Теория и практика кодов, контролирующих ошибки. - М.: Мир, 1986.
 +
# Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. - М.: Связь. - 1979.
 +
# Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. – М.: Техносфера. - 2006.
 +
# Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. – М.: Мир. – 1976.
== См. также ==
== См. также ==

Версия 23:28, 7 января 2018

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

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

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

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

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

Новости

08.01.18: выложены результаты проверки практического задания

06.01.18: выложены результаты переписывания контрольной от 20.12.

28.12.17: переписывание контрольной работы для студентов, пропустивших переписывание 20 декабря по уважительной причине, состоится завтра (29.12.) в ауд. 523, начало в 11-00.

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. На экзамене при подготовке билета разрешается пользоваться любыми материалами (в том числе с электронных устройств). При непосредственном ответе ничем пользоваться нельзя. Обратите внимание на теоретический минимум. Незнание ответа на любой вопрос из теоретического минимума влечёт за собой неудовлетворительную оценку за экзамен. К экзамену допускаются только студенты, успешно справившиеся с контрольной работой.

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

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

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

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

Результаты контрольной

Практическое задание

Все студенты, которые успешно написали контрольную работу с первого раза, могут выполнить практическое задание в качестве альтернативы сдачи экзамена. За практическое задание можно получить оценку 5, 4 и 0. В последнем случае студент сдаёт экзамен. При желании можно также сдавать экзамен при получении оценки 4 за практическое задание.

Внимание! Задание выполняется полностью самостоятельно. Все похожие коды будут расцениваться как плагиат, а все задействованные в плагиате студенты будут наказаны (в том числе те, у кого списали).

Вопросы по заданию можно задавать письмом на bayesml@gmail.com. В название письма просьба обязательно добавлять [ПА17].

Срок сдачи задания: 30 декабря (суббота), 23:59.

Формулировка задания

Результаты проверки задания

Материалы

Конспект лекций (обновлено 15.12.)

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

Конечные поля (поля Галуа)

  1. Группы и кольца (напоминание)
  2. Поле вычетов по модулю простого числа
  3. Вычисление элементов в конечных полях
  4. Линейная алгебра над конечным полем
  5. Корни многочленов над конечным полем
  6. Существование и единственность поля Галуа из p^n элементов
  7. Циклические подпространства
  8. Решение задач

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

  1. Помехоустойчивое кодирование, блоковое кодирование, коды Хэмминга
  2. Групповые (линейные) коды
  3. Циклические коды
  4. Коды БЧХ
  5. Решение задач

Теория перечисления Пойя

  1. Действие группы на множестве
  2. Применение леммы Бернсайда для решения комбинаторных задач
  3. Применение теоремы Пойя для решения комбинаторных задач


Литература

  1. Воронин В.П. Дополнительные главы дискретной математики, ф-т ВМК, 2002.
  2. Гуров С.И. Булевы алгебры, упорядоченные множества, решетки: определения, свойства, примеры. Либроком, 2013.
  3. Журавлев Ю.И., Флеров Ю.А., Вялый М.Н. Дискретный анализ. Основы высшей алгебры. М3-Пресс, 2007.
  4. Лидл Р., Нидеррайтер Г. Конечные поля: в 2-х т. Мир, 1988.
  5. Нефедов В.Н., Осипова В.А. Курс дискретной математики, МАИ, 1992.
  6. Ромащенко А.Е., Румянцев А.Ю., Шень А. Заметки по теории кодирования. МЦНМО, 2011.
  7. Lin S., Costello D. Error Control Coding Fundamentals and Applications. Prentice-Hall, 1983.
  8. Берлекэмп Э. Алгебраическая теория кодирования. - М.: Мир, 1971.
  9. Блейхут Р. Теория и практика кодов, контролирующих ошибки. - М.: Мир, 1986.
  10. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. - М.: Связь. - 1979.
  11. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. – М.: Техносфера. - 2006.
  12. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. – М.: Мир. – 1976.

См. также

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

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

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