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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Материалы)
(22 промежуточные версии не показаны)
Строка 6: Строка 6:
Ассистент: [[Участник:Kropotov|Кропотов Д.А.]]
Ассистент: [[Участник:Kropotov|Кропотов Д.А.]]
-
Свои вопросы по курсу и пожелания можно направлять письмом по адресу ''bayesml@gmail.com'', в название письма просьба добавлять [ПА15]
+
Свои вопросы по курсу и пожелания можно направлять письмом по адресу ''sgur@cs.msu.ru''
-
В осеннем семестре 2015/2016 уч. г. занятия проходят на ВМК по понедельникам в ауд. П-8, начало в 14-35.
+
В осеннем семестре 2016/2017 уч. г. занятия проходят на ВМК по понедельникам в ауд. П-8, начало в 14-35.
 +
 
 +
[https://goo.gl/forms/gmp3I7iF2rAk05dm1 Опрос по курсу]
== Новости ==
== Новости ==
-
'''30.12.15''' Выложены результаты переписывания контрольной от 21 декабря.
+
'''08.02.17''': 1-я пересдача по курсу состоится 16 февраля в ауд. 508, начало в 12-15. 2-я пересдача состоится 22 февраля в ауд. 708, начало в 9-00.
-
'''14.12.15''' Занятия по курсу завершены. В ближайший понедельник, 21 декабря, состоится (последнее) переписывание контрольной работы. Начало в 14-35, ауд. '''П-8а'''.
+
'''06.01.17''': добавлен небольшой опрос по курсу (участие анонимное). Нам важно ваше мнение!
-
'''14.12.15''' Выложены результаты переписывания контрольной от 8 декабря. Незачётные работы можно посмотреть на ближайшем занятии по курсу.
+
'''04.01.17''': консультация к экзамену для групп 320, 321, 323 состоится 6-го января в ауд. 523, начало в 15-00. Консультация к экзамену для групп 324, 325, 327, 328 состоится 18-го января в ауд. 579, начало в 16-00.
-
'''01.12.15''' Переписывание контрольной работы состоится во вторник, 8 декабря, в ауд. П-8а. Начало в 18-10.
+
'''04.01.17''': выложены результаты переписывания контрольной от 19 декабря. Показ работ пройдёт 6-го января в ауд. 523, начало в 15-00.
-
'''30.11.15''' Выложены результаты контрольной работы от 9 ноября.
+
'''27.12.16''': добавлены материалы к экзамену.
-
'''24.11.15''' Показ <u>незачётных</u> работ контрольной работы и обсуждение задач контрольной состоится во вторник, 1 декабря, в ауд. П-8а. Начало в 18-10.
+
'''16.12.16''': переписывание контрольной работы состоится 19 декабря в ауд. П-13, начало в 18-00.
-
'''16.11.15''' В связи с болезнью лектора занятия по курсу 16 ноября отменяются.
+
'''16.12.16''': выложены результаты контрольной работы от 5 декабря. Показ работ и обсуждение задач контрольной состоится 16 декабря в 17-00, ауд. П-13.
-
'''29.10.15''' Контрольная работа состоится 9 ноября (понедельник), начало в 14-35. Студенты групп 320, 321 и 323 пишут работу в ауд. П-8, остальные -- в ауд. П-.
+
'''15.11.16''': контрольная работа по курсу состоится 5 декабря, начало в 14-35. Студенты групп 320, 321 и 323 пишут контрольную в ауд. П-8, остальные в ауд. П-14.
== Контрольная работа ==
== Контрольная работа ==
Строка 32: Строка 34:
В программе курса предусмотрена письменная контрольная работа. Успешное написание контрольной работы является обязательным условием допуска к экзамену по курсу. При отсутствии допуска студент пишет контрольную работу на экзамене и, в случае успеха, сдает экзамен на первой пересдаче. При написании контрольной работы разрешается пользоваться любыми бумажными материалами, а также калькуляторами. Использование электронных устройств (кроме калькуляторов) запрещено.
В программе курса предусмотрена письменная контрольная работа. Успешное написание контрольной работы является обязательным условием допуска к экзамену по курсу. При отсутствии допуска студент пишет контрольную работу на экзамене и, в случае успеха, сдает экзамен на первой пересдаче. При написании контрольной работы разрешается пользоваться любыми бумажными материалами, а также калькуляторами. Использование электронных устройств (кроме калькуляторов) запрещено.
-
[https://docs.google.com/spreadsheets/d/14llDTJrIYDlRZ2Vo_IIxR-BXEw9TqveFaVH6QkfvmQc/edit?usp=sharing Результаты контрольной]
+
[https://docs.google.com/spreadsheets/d/1Wonyg6X7u6ZTYiYwG8pGPONhhxozsN717hBLpVYKXjs/edit?usp=sharing Результаты контрольной]
-
== Материалы ==
+
== Экзамен ==
-
[[Media:AA3-2015-0.pdf|Группы, кольца]]
+
Экзамен по курсу состоится: 8 января для групп 320, 321, 323 (ауд. П-13, начало в 9-00), 20 января для групп 324, 325, 327, 328 (ауд. П-13, начало в 9-00). К экзамену допускаются только студенты, успешно справившиеся с контрольной работой. На экзамене при подготовке билета разрешается пользоваться любыми материалами (в том числе, с электронных устройств). При непосредственном ответе ничем пользоваться нельзя. При ответе студенту сначала задаются вопросы из теоретического минимума. Ответы на вопросы из этой части предполагают как знание основных определений, так и умение приводить примеры под каждое определение или теорему. <u>Незнание ответа на любой вопрос из части теоретического минимума влечёт за собой неудовлетворительную оценку за экзамен.</u> Далее обсуждается билет и вычислительные задачи.
-
[[Media:AA3-2015-1(GF-I).pdf|Конечные поля (часть 1)]]
+
[[Media:AA3-2016-theormin.pdf|Теоретический минимум]]
-
[[Media:AA3-2015-1(GF-II).pdf|Конечные поля (часть 2)]]
+
[[Media:AA3-2016-exam-questions.pdf|Вопросы к экзамену]]
-
[[Media:AA3-2015-2(ECC).pdf|Коды, исправляющие ошибки]]
+
== Материалы ==
-
 
+
-
[[Media:AA3-2015-3(PET).pdf|Теория перечисления Пойя]]
+
-
[[Media:AA3-2015-4(Posets).pdf|Частично упорядоченные множества]]
+
[[Media:AA3-lecture-notes.pdf|Конспект лекций]] {{важно|(обновлено 05.05.17)}}
== Программа курса ==
== Программа курса ==
Строка 72: Строка 72:
# Применение теоремы Пойя для решения комбинаторных задач
# Применение теоремы Пойя для решения комбинаторных задач
-
=== Некоторые вопросы теории частично упорядоченных множеств ===
 
-
# Основные понятия теории ч.у. множеств
 
-
# Операции над ч.у. множествами
 
-
# Линеаризация
 
-
# Модели Крипке
 
-
# Решение задач
 
== Литература ==
== Литература ==
Строка 88: Строка 82:
# Ромащенко А.Е., Румянцев А.Ю., Шень А. [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.
== См. также ==
== См. также ==

Версия 10:48, 5 мая 2017

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

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

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

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

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

Опрос по курсу

Новости

08.02.17: 1-я пересдача по курсу состоится 16 февраля в ауд. 508, начало в 12-15. 2-я пересдача состоится 22 февраля в ауд. 708, начало в 9-00.

06.01.17: добавлен небольшой опрос по курсу (участие анонимное). Нам важно ваше мнение!

04.01.17: консультация к экзамену для групп 320, 321, 323 состоится 6-го января в ауд. 523, начало в 15-00. Консультация к экзамену для групп 324, 325, 327, 328 состоится 18-го января в ауд. 579, начало в 16-00.

04.01.17: выложены результаты переписывания контрольной от 19 декабря. Показ работ пройдёт 6-го января в ауд. 523, начало в 15-00.

27.12.16: добавлены материалы к экзамену.

16.12.16: переписывание контрольной работы состоится 19 декабря в ауд. П-13, начало в 18-00.

16.12.16: выложены результаты контрольной работы от 5 декабря. Показ работ и обсуждение задач контрольной состоится 16 декабря в 17-00, ауд. П-13.

15.11.16: контрольная работа по курсу состоится 5 декабря, начало в 14-35. Студенты групп 320, 321 и 323 пишут контрольную в ауд. П-8, остальные — в ауд. П-14.

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

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

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

Экзамен

Экзамен по курсу состоится: 8 января для групп 320, 321, 323 (ауд. П-13, начало в 9-00), 20 января для групп 324, 325, 327, 328 (ауд. П-13, начало в 9-00). К экзамену допускаются только студенты, успешно справившиеся с контрольной работой. На экзамене при подготовке билета разрешается пользоваться любыми материалами (в том числе, с электронных устройств). При непосредственном ответе ничем пользоваться нельзя. При ответе студенту сначала задаются вопросы из теоретического минимума. Ответы на вопросы из этой части предполагают как знание основных определений, так и умение приводить примеры под каждое определение или теорему. Незнание ответа на любой вопрос из части теоретического минимума влечёт за собой неудовлетворительную оценку за экзамен. Далее обсуждается билет и вычислительные задачи.

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

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

Материалы

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

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

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

  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.

См. также

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

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

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