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

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

(Различия между версиями)
Перейти к: навигация, поиск
(40 промежуточных версий не показаны.)
Строка 1: Строка 1:
__NOTOC__
__NOTOC__
-
 
Обзорный курс для студентов 3-го потока ВМК МГУ по основам алгебры (группы, кольца, поля, частично-упорядоченные множества) и её приложениям в кодировании и комбинаторике.
Обзорный курс для студентов 3-го потока ВМК МГУ по основам алгебры (группы, кольца, поля, частично-упорядоченные множества) и её приложениям в кодировании и комбинаторике.
Строка 7: Строка 6:
Ассистент: [[Участник:Kropotov|Кропотов Д.А.]]
Ассистент: [[Участник:Kropotov|Кропотов Д.А.]]
-
Свои вопросы по курсу и пожелания можно направлять письмом по адресу ''bayesml@gmail.com'', в название письма просьба добавлять [ПА14]
+
Свои вопросы по курсу и пожелания можно направлять письмом по адресу ''sgur@cs.msu.ru''
-
В осеннем семестре 2014/2015 уч. г. занятия проходят на ВМК по понедельникам в ауд. П8, начало в 14-35.
+
В осеннем семестре 2017/2018 уч. г. занятия проходят на ВМК по понедельникам в ауд. П-8а, начало в 12-50.
== Новости ==
== Новости ==
-
* '''27.01.14''' Первая пересдача по курсу состоится 10 февраля, начало в 14-35. Вторая пересдача по курсу состоится 16 февраля, начало в 10-35. Для студентов, имеющих задолженность по контрольной: семинар с обсуждением решений задач контрольной состоится 9 февраля в ауд. 507, начало в 14-35.
+
'''18.09.17''': занятия по курсу теперь проходят в ауд. П-8а.
-
* '''18.01.14''' Проверены контрольные работы, писавшиеся на экзамене 17 и 18 января. Дальнейшая схема для студентов, имеющих задолженность по контрольной: в начале учебного семестра будет проведён семинар с обсуждением решений задач контрольной, затем на пересдаче студент пишет контрольную работу и, в случае успеха, в тот же день сдаёт экзамен.
+
-
* '''08.01.14''' Консультация к экзамену состоится 16 января в ауд. П-5, начало в 15-00.
+
-
* '''27.12.14''' Добавлены результаты переписывания контрольной 22.12. Показ незачётных работ пройдет в понедельник, 29 декабря, в ауд. 645, начало в 17-00.
+
-
* '''22.12.14''' Выложены список вопросов к экзамену, теоретический минимум и список задач по теории Пойя.
+
-
* '''20.12.14''' В понедельник 22 декабря состоится последнее до экзамена переписывание контрольной работы, ауд. П-8а, начало в 14-35.
+
-
* '''08.12.14''' Показ работ по результатам переписывания контрольной 02.12. пройдет в пятницу, 12 декабря, в ауд. 637, начало в 14-35.
+
-
* '''08.12.14''' Выложены результаты переписывания контрольной работы 02.12.
+
-
* '''26.11.14''' Переписывание контрольной работы состоится во вторник, 2 декабря, в ауд. П-1, начало в 18-05.
+
-
* '''22.11.14''' Выложены результаты контрольной работы 10.11.
+
-
* '''18.11.14''' Консультация по решению задач контрольной, а также показ незачётных работ пройдёт во вторник, 25 ноября, в ауд. П-1, начало в 18-05.
+
== Контрольная работа ==
== Контрольная работа ==
В программе курса предусмотрена письменная контрольная работа. Успешное написание контрольной работы является обязательным условием допуска к экзамену по курсу. При отсутствии допуска студент пишет контрольную работу на экзамене и, в случае успеха, сдает экзамен на первой пересдаче. При написании контрольной работы разрешается пользоваться любыми бумажными материалами, а также калькуляторами. Использование электронных устройств (кроме калькуляторов) запрещено.
В программе курса предусмотрена письменная контрольная работа. Успешное написание контрольной работы является обязательным условием допуска к экзамену по курсу. При отсутствии допуска студент пишет контрольную работу на экзамене и, в случае успеха, сдает экзамен на первой пересдаче. При написании контрольной работы разрешается пользоваться любыми бумажными материалами, а также калькуляторами. Использование электронных устройств (кроме калькуляторов) запрещено.
-
 
-
[[Media:AA3-tasks.pdf| Задачи для подготовки к контрольной]]
 
-
 
-
[https://docs.google.com/spreadsheets/d/1uVhuAJAxJPLGXvDPHe9mwT-2Mob68EECuT_CBRqyzO8/edit?usp=sharing Результаты контрольной]
 
-
 
-
== Экзамен ==
 
-
 
-
К экзамену допускаются только студенты, успешно написавшие контрольную работу. На экзамене при подготовке билета разрешается пользоваться любыми материалами (в том числе с электронных устройств). При ответе экзаменатору ничем пользоваться нельзя. Просьба обратить особое внимание на теоретический минимум. Незнание ответа на '''любой''' из вопросов теоретического минимума влечёт за собой неудовлетворительную оценку по экзамену.
 
-
 
-
[[Media:AA3-exam-questions.pdf| Вопросы к экзамену]]
 
-
 
-
[[Media:AA3-exam-theormin.pdf| Теоретический минимум]]
 
-
 
-
[[Media:AA3_Polya_problems.pdf| Задачи по теории Пойя]]
 
== Материалы ==
== Материалы ==
-
[[Media:AA3-0.pdf| Группы, кольца (напоминание)]] {{важно|(обновлено 09.12.)}}
+
Здесь будут появляться материалы лекций
-
 
+
-
[[Media:AA3-1(GF-I).pdf| Конечные поля (часть 1)]] {{важно|(обновлено 09.12.)}}
+
-
 
+
-
[[Media:AA3-1(GF-II).pdf| Конечные поля (часть 2)]] {{важно|(обновлено 09.12.)}}
+
-
 
+
-
[[Media:AA3-2(ECC).pdf| Коды, исправляющие ошибки]] {{важно|(обновлено 09.12.)}}
+
-
 
+
-
[[Media:AA3-3(PET).pdf| Теория перечисления Пойя]]
+
-
 
+
-
[[Media:AA3-4(Posets).pdf| Частично упорядоченные множества]]
+
-
 
+
-
[[Media:AA3-5(Lattice).pdf| Алгебраические решётки]]
+
== Программа курса ==
== Программа курса ==
Строка 83: Строка 46:
# Применение теоремы Пойя для решения комбинаторных задач
# Применение теоремы Пойя для решения комбинаторных задач
-
=== Некоторые вопросы теории частично упорядоченных множеств ===
 
-
# Основные понятия теории ч.у. множеств
 
-
# Операции над ч.у. множествами
 
-
# Линеаризация
 
-
# Модели Крипке
 
-
# Решение задач
 
-
 
-
=== Алгебраические решётки ===
 
-
# Решётки: определения, основные свойства
 
-
# Модулярные и дистрибутивные решётки
 
-
# Применение теории решёток к задаче классификации
 
== Литература ==
== Литература ==
Строка 104: Строка 56:
# Ромащенко А.Е., Румянцев А.Ю., Шень А. [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.
== См. также ==
== См. также ==

Версия 09:24, 18 сентября 2017

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

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

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

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

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

Новости

18.09.17: занятия по курсу теперь проходят в ауд. П-8а.

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

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

Материалы

Здесь будут появляться материалы лекций

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

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

  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.

См. также

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

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

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