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

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

(Перенаправлено с Прикладная алгебра (часть I))
Перейти к: навигация, поиск

Содержание


ПРИКЛАДНАЯ АЛГЕБРА (часть 1)


Экзамен 2019 года

Первая часть - письменная.

15 вопросов/задач. На решение - 1 час.

Критерии (число решённых - оценка):

  • 14-15 - отлично (ставится сразу)
  • 11-13 - хорошо-отлично
  • 8-10 - удовл.-хорошо
  • 5- 7 - неуд.-удовл.
  • меньше 5 - неуд. (ставится сразу)

Практически по всем задачам система оценки - "чистый плюс или чистый минус". "Плюс-минус" ставится в крайнем случае.

За хорошие показатели в течение семестра некоторые студенты имеют дополнительные баллы, которые приравниваются к решённым задачам (будут объявлены позже).

Вторая часть - устная.

Для тех, кто набрал от 5 до 13 баллов, проводится опрос по всем темам (опрос теоретический, без вытягивания билетов). По результатам опроса студент получает одну из двух оценок (которые определены в таблице критериев).


Аннотация

Первая (вводная) часть курса Прикладная алгебра для студентов каф. ММП посвящена введению в высшую алгебру и алгебраическую теорию кодирования. В ней рассматриваются основные алгебраические структуры: группы, кольца, поля. Центральная роль отведена конечным полям, приводится классический пример их приложений — построение кодов, исправляющих ошибки. Курс поддерживается семинарскими занятиями, на которых решаются задачи, и попутно рассматриваются дополнительные вопросы, не отражённые в лекциях. По теме кодирование несколько лекций играют роль семинаров, поскольку на них подробно излагаются методы решений прикладных задач кодирования. Разработано несколько оригинальных домашних контрольных: студенты в течение недели должны решить несколько непростых задач, каждый решает свой вариант, все задачи после сдачи работ подробно разбираются на семинарах. Предусмотрены коллоквиумы по курсу, а также письменные контрольные на знание терминологии и схем доказательств. Основная цель всех этих разработок — постоянный контроль знаний и стимулирование студентов к плотному графику обучения в течение всего семестра.

Содержание курса

Лекции, 6 семестр

1. Группы

1.1. Введение. Алгебра. Алгебраические операции. Группа (определение, простейшие свойства, примеры, терминология). Все конечные группы малых порядков. Симметрические группы. Циклические группы. Подгруппы.

1.2. Группа автоморфизмов. Перестановки. Теорема Кэли. Смежные классы. Отношение эквивалентности в группе (через принадлежность смежным классам). Теорема Лагранжа, ее следствия и невозможность обращения. Задание группы порождающими соотношениями.

1.3. Нормальные делители (нормальные подгруппы). Факторгруппы. Критерий нормальности делителя через сопряженные элементы.

1.4. Гомоморфизм. Ядро и образ гомоморфизма. Естественный (канонический) гомоморфизм. Свойства гомоморфизмов групп. Теорема о гомоморфизмах групп.

2. Кольца

2.1. Кольцо (определение, простейшие свойства, терминология). Кольцо классов вычетов. Свойства сравнений. Корректность операций в кольце классов вычетов. Гомоморфизмы и изоморфизмы колец. Теорема о гомоморфизмах колец.

2.2. Евклидовы кольца. Идеалы. Кольца главных идеалов.

2.3. Максимальные идеалы. Необходимое и достаточное условие для кольца классов вычетов быть полем. Кольцо многочленов над полем. Нули многочленов, теорема об остатке и теорема Безу. Неприводимые (простые) многочлены.

3. Векторные пространства.

3.1. Векторное пространство (напоминание определений и свойств, изученных в курсе линейной алгебры). Линейная зависимость. Базис. Лемма Штайнера.

3.2. Изоморфизм векторных пространств. Линейные функционалы. Сопряжённое пространство.

4. Поля

4.1. Тело, поле (определение, терминология, примеры).

4.2. Конечные поля. Число элементов в конечном поле характеристики p. Существование полей порядка pm для всех простых p и натуральных m.

4.3. Существование в конечном поле примитивного элемента (с доказательством вспомогательной леммы из теории групп). Уравнение, которому удовлетворяют все элементы конечного поля. Мультипликативная группа поля.

4.4. Минимальный многочлен (минимальная функция элемента поля). Минимальный многочлен элемента {x} в F[x]/(g(x)).

4.5. Теорема о разложении многочлена Xq^m-X на множители (с доказательством всех вспомогательных лемм).

4.6. Корни многочленов над конечном полем.

5. Кодирование

5.1. Кодирование. Основная задача теории кодирования. Коды Боуза-Чоудхури-Хоквингема (БЧХ). Оценка расстояния между кодовыми вершинами БЧХ. Теорема о линейной независимости в проверочной матрице.

5.2. Структура идеалов в F[x]/(g(x)). Циклические линейные подпространства классов вычетов.

5.3. Другие подходы к кодированию. Матрица Адамара. Примеры кодов.

Практические занятия, 6 семестр

  • 1. Группы
    • 1. Группы. Группы малых порядков [1-7].
    • 2. Моноиды, группы матриц, группы движения плоскости [8-15].
    • 3. Абелевы группы, обратные элементы, порядки элементов [16-22].
    • 4. Порождения групп, коммутаторы, перестановки [23-32].
    • 5. Группы симметрий/поворотов, нормальные делители [33-40].
    • 6. Домашняя контрольная работа [41-80].
    • 7. Классы сопряжённости, автоморфизмы, гомоморфизмы [85-91].
    • 8. Центры, факторгруппы [92-97].
    • 9. Домашняя контрольная работа [98-102].
    • 10. Группа автоморфизмов, характеристическая группа. [103-107]
    • 11. Коммутант(а), группа симметрий квадрата [108-113].
    • 12. Прямое произведение групп [114-122].
    • 13. Некоторые свойства групп [123-125].
    • 14. Домашняя контрольная работа [126-137].
  • 2. Кольца
    • 15. Кольца, идемпотенты, нильпотенты, кольца матриц [138-150].
    • 16. Кольца функций, идеалы [151-156].
    • 17. Системы уравнений, кольца многочленов [157-162].
    • 18. Гомоморфизмы колец [163-166].
    • 19. Идеалы [168-169].
    • 20. Домашняя контрольная работа [177-208].
  • 3. Векторные пространства
    • Нет семинарских занятий по этой подтеме.
  • 4. Поля
    • 21. Изоморфизмы полей [170-176].
    • 22. Автоморфизмы полей, решение уравнений [209-214].
    • 23. Алгебраические и трансцендентные элементы, поля частных [215-220].
  • 5. Кодирование
    • 24. Структура идеалов в {p(x)}F/(g(x).
    • 25. Разложение многочленов на множители, нахождение корней многочленов.
    • 26. Построение кодов БЧХ.

Практические занятия проводятся по разработанному авторами программы сборнику задач. Нумерация в квадратных скобках соответствует версии сборника от 26.12.2006 (сборник постоянно пополняется и обновляется). Авторы не считают целесообразным выкладывать его в общественный доступ.

Литература

  1. Журавлёв Ю. И., Флёров Ю. А., Вялый М. Н. Дискретный анализ. Основы высшей алгебры. — М. МЗ Пресс, 2006. — 208 с (большинство лекций читается по этому учебнику). Электронная версия на сайте автора
  2. Биркгоф Г., Барти Т. Современная прикладная алгебра. — М.: Мир, 1976 (хорошо описана тема «Кольца»).
  3. Кострикин А. И. Введение в алгебру. Часть I. Основы алгебры. Часть II. Линейная алгебра. Часть III. Основные структуры алгебры: Учебник для вузов (в 3-х томах). М.: Физико-математическая литература, 2000. (хорошие учебное пособие, отлично изложены некоторые факты теории групп).
  4. Ван дер Варден Б. Л. Алгебра. М.: Наука, 1976. (классическая монография по алгебре).
  5. Касами Т., Токура Н., Ивадари Ё., Инагаки Я. Теория кодирования. М.: Мир, 1978. — 576 с (тема «Кодирование» читается по этой книге).
  6. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.: Мир, 1976. (часть доказательств по теме «Кодирование» взято из этой книги).
  7. Халмош П. Конечномерные векторные пространства. — М.: Физматгиз, 1978. (тема «Векторные пространства» читается по этой книге).
  8. Сборник задач по алгебре: Учебное пособие / Под. ред. А. И. Кострикина. М.: Факториал, 1995. (многие задачи взяты из этого учебного пособия).

ПРИКЛАДНАЯ АЛГЕБРА (часть 2)

  • Обязательный курс для студентов 4 курса каф. ММП, читается в 7 семестре
  • Лекции — 32 часов, семинары — 16 часа
  • Форма контроля — экзамен
  • Авторы программы: академик РАН Журавлёв Ю.И., доцент Гуров С.И.
  • Лектор: доцент Гуров С.И.

Аннотация

В 2-й части курса Прикладной алгебры для студентов кафедры ММП освещаются основы булевых алгебр, отношений и соответствий, частично упорядоченных множеств, алгебраических решёток. Исследуются свойства эквивалентностей и пространств толерантностей. Рассматриваются различные свойства порядков, в т.ч. конструирование новых множеств из старых и понятие размерности частично упорядоченных множеств. Изучаются основные виды решёток: модулярные, дистрибутивные, решётки с дополнениями. Доказывается фундаментальная теорема для конечных дистрибутивных решёток. Рассматриваются свойства алгебраических решёток, связь булевых алгебр и булевых колец. Водятся основные понятия идемпотентной алгебры: полуполе обобщенных сумм, операция вычитания и отношение порядка. Действия над векторами и матрицами. Даются примеры приложений идемпотентной алгебры для решения практических задач. В курсе даются алгебраические основы криптографии: система шифрования RSA, задачи факторизация натуральных чисел и дискретного логарифмирование. Изучаются криптосистемы МакЭлиса и Нидеррайтера.

Материалы

Содержание курса

Булевы алгебры

Аксиоматика булевой алгебры. Алгебры множеств. Изоморфизмы булевых алгебр. Теорема Стоуна.

Отношения и соответствия

Декартово произведение множеств и отношения. Однородные отношения. Отношение эквивалентности. Пространства толерантности. Соответствия. Основные свойства отображений.

Частично упорядоченные множества

Предпорядки и порядки. Особые элементы и основные свойства частично упорядоченных (ч. у.) множеств. Грани, изотонные отображения и порядковые идеалы. Операции над ч. у. множествами. Линеаризация. Размерность ч. у. множеств. Вполне упорядоченные множества и смежные вопросы. Некоторые применения теории ч. у. множеств.

Решётки

Определение и основные свойства. Гомоморфизмы, идеалы, фильтры. Модулярные и дистрибутивные решётки. Решётки с дополнениями. Применение теории решёток к задаче классификации.

Булевы алгебры (продолжение)

Булевы алгебры как решётки. Идеалы, фильтры и конгруэнции. Булевы многочлены. Булевы уравнения.

Идемпотентная алгебра

Тропическая математика. Полуполе обобщенных сумм. Уравнения, операция вычитания и отношение порядка. Действия над векторами. Действия над матрицами.

Линейные рекуррентные последовательности (опция)

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

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

Практические занятия

  1. Булевы алгебры – 2 часа.
  2. Отношения соответствия – 4 часа.
  3. Порядки – 4 часа.
  4. Решётки – 4 часа.
  5. Алгебраические системы – 2 часа.

Практические занятия проводятся по разработанному авторами программы сборнику задач.

Литература

Основная литература

  1. Биркгоф Г., Барти Т. Современная прикладная алгебра. М.: Мир. 1976.
  2. Гуров С.И. Упорядоченные множества и универсальная алгебра (вводный курс). М.: ВМК МГУ. 2004.
  3. Гуров С.И. Лекции по упорядоченным множествам и универсальной алгебре. М.: ВМК МГУ (в печати).
  4. Курош А.Г. Общая алгебра (лекции 1969 1970 учебного года). М.: Наука. 1974.
  5. Мальцев А.И. Алгебраические системы. М.: Наука. 1970.
  6. Скорняков Л.А. Элементы общей алгебры. М.: Наука. 1983.

Дополнительная литература

  1. Владимиров Д.А. Булевы алгебры. М.: Наука. 1969.
  2. Кон П. Универсальная алгебра. М.: Мир. 1968.
  3. Лидл Р., Пильц Г. Прикладная абстрактная алгебра. Екатеринбург: Изд-во Урал. ун-та. 1996.
  4. Плоткин Б.И. Универсальная алгебра, алгебраическая логика и базы данных. М.: Наука. 1991.
  5. Салий В.Н. Решётки с единственными дополнениями. М.: Наука. 1984.
  6. Скорняков Л.А. Элементы теории структур. М.: Наука. 1970.
  7. Стенли Р. Перечислительная комбинаторика (Volume I). М.: Мир. 1990.
  8. Шрейдер Ю.А. Равенство, сходство, порядок. М.: Наука. 1971.
  9. Яглом И. М. Булева структура и её модели. М.: Сов. Радио. 1980.

ПРИКЛАДНАЯ АЛГЕБРА (часть 3)

  • Обязательный курс для в рамках магистерской программы, читается в 1 семестре
  • Лекции — 36 часов
  • Форма контроля — экзамен
  • Авторы программы: академик РАН Журавлев Ю.И., профессор Леонтьев В.К.
  • Лектор: профессор Леонтьев В.К.

Аннотация

Третья часть курса Прикладная алгебра для студентов кафедры ММП содержит ряд ключевых разделов, относящихся к применению классических алгебраических конструкций для решения комбинаторных перечислительных и оптимизационных задач. Такого рода задачи являются фундаментом для многих областей дискретной математики.

Содержание курса

Комбинаторика конечных множеств

Рассматриваются классические перечислительные и экстремальные проблемы на семействе подмножеств конечного множества. Типичные из них состоят в оценке мощности семейства подмножеств с определёнными ограничениями на пересечения. В этом же ключе рассматриваются стандартные теоретико-числовые задачи, связанные с классическими функциями теории чисел: τ(n), σ(n), φ(n), π(n). Заключают раздел комбинаторные задачи, связанные с представлениями булевых функций.

Метод производящих функций

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

Частичные порядки

Рассматриваются классические понятия из теории частично упорядоченных множеств и показывается как многие классические задачи комбинаторного анализа могут быть сформулированы в геометрических терминах теории частичного упорядочения. Даются все стандартные определения, связанные с алгеброй рядов Дирихле и устанавливаются основные классические соотношения, связывающие дзета-функцию Римана с рядами Дирихле для ранее введённых теоретико-числовых функций : τ(n), σ(n), φ(n), μ(n). Доказывается формула обращения Мёбиуса и на её основе выводится классическая формула для числа неприводимых полиномов заданной степени над конечным полем.

Верхние и нижние оценки

Рассматриваются методы получения нижних и верхних границ разного типа в задачах, связанных с теорией информации. Изучаются методы криптографической защиты сообщений с помощью теоретико-числовых соображений, связанных с группой Эйлера.

Семинары

  1. Производящие функции.
  2. Производящие функции (продолжение). Числа Каталана.
  3. Лемма Бернсайда.
  4. Цикловые индексы.
  5. Платоновы тела.
  6. Теорема Пойа.
  7. Теорема Пойа (продолжение).

Литература

  1. Журавлёв Ю.И., Флёров Ю.А., Вялый М.Н. Дискретный анализ. Основы высшей алгебры. М.: МЗ Пресс. 2006.
  2. Биркгоф Г., Барти Т. Современная прикладная алгебра. М.: Мир. 1976.
  3. Пойя Г., Сеге Г. Задачи и теоремы из анализа. Т.1. М.: ГИТЛ. 1956
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BA%D0%BB%D0%B0%D0%B4%D0%BD%D0%B0%D1%8F_%D0%B0%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D0%B0_%28%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%2C_%D0%AE.%D0%98._%D0%96%D1%83%D1%80%D0%B0%D0%B2%D0%BB%D0%B5%D0%B2%2C_%D0%90.%D0%93._%D0%94%D1%8C%D1%8F%D0%BA%D0%BE%D0%BD%D0%BE%D0%B2%29»
Личные инструменты