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

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

(Различия между версиями)
Перейти к: навигация, поиск
(ПРИКЛАДНАЯ АЛГЕБРА (часть 2))
(ПРИКЛАДНАЯ АЛГЕБРА (часть 2))
(3 промежуточные версии не показаны)
Строка 3: Строка 3:
= ПРИКЛАДНАЯ АЛГЕБРА (часть 1) =
= ПРИКЛАДНАЯ АЛГЕБРА (часть 1) =
* Обязательный курс для студентов каф. [[ММП]] 3 курса, читается в 6-м семестре (до 2007/08 уч. года читался в 5-м семестре).
* Обязательный курс для студентов каф. [[ММП]] 3 курса, читается в 6-м семестре (до 2007/08 уч. года читался в 5-м семестре).
-
* Лекции — 32 часа, семинары — 32 часа.
+
* Лекции — 36 часов, семинары — 36 часов.
* Экзамен.
* Экзамен.
* За курс отвечает кафедра [[Математические методы прогнозирования (кафедра ВМиК МГУ)|Математических методов прогнозирования]].
* За курс отвечает кафедра [[Математические методы прогнозирования (кафедра ВМиК МГУ)|Математических методов прогнозирования]].
Строка 9: Строка 9:
* Лектор: [[Участник:Dj|А.Г. Дьяконов]]
* Лектор: [[Участник:Dj|А.Г. Дьяконов]]
-
* '''Новая программа 2015 года:''' [[Media:PAprogram2015.pdf| скачать программу (pdf)]].
+
* '''Новая программа 2018 года:''' [[Media:PAprogram2017.pdf| скачать программу (pdf)]].
{{notice|
{{notice|
-
'''Экзамен 2015 года'''
+
'''Экзамен 2018 года'''
'''Первая часть - письменная.'''
'''Первая часть - письменная.'''
Строка 154: Строка 154:
== Материалы ==
== Материалы ==
-
 
-
[[Media:AA-Bac7s-2016-lecture-notes.pdf| Конспект лекций]]
 
-
 
-
[[Media:AA-Bac7s-2016-theormin.pdf| Теоретический минимум к экзамену]]
 
-
 
-
[[Media:AA-Bac7s-2016-exam-questions.pdf| Вопросы к экзамену]]
 
== Содержание курса ==
== Содержание курса ==

Версия 18:36, 26 июля 2018

Содержание


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


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

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

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-й части курса Прикладной алгебры для студентов кафедры ММП освещаются основы булевых алгебр, отношений и соответствий, частично упорядоченных множеств, алгебраических решёток и алгебраических систем. Упор изложения делается на конечный случай изучаемых математических структур. Доказываются теоремы о фундаментальных свойствах отношений и соответствий. Подробно исследуются свойства эквивалентностей и пространств толерантностей (последнее понятие весьма слабо освящено в литературе, однако является важным для специалистов по распознаванию образов). Рассматриваются различные свойства порядков, в т.ч. конструирование новых множеств из старых и понятие размерности частично упорядоченных множеств. Даются основные понятия, связанные с вполне упорядоченными множествами и трансфинтами. Изучаются основные виды решёток: модулярные, дистрибутивные, решётки с дополнениями. Доказывается фундаментальная теорема для конечных дистрибутивных решёток. Рассматриваются свойства алгебраических решёток, связь булевых алгебр и булевых колец.

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

Материалы

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

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

Определение булевой алгебры (БА). Алгебраические системы. Различные системы аксиом БА. Лемма «о единственности дополнения». Принцип двойственности для БА. Примеры. Алгебры множеств. Изоморфизмы булевых алгебр. Атомы БА и их свойства. Теорема Стоуна и следствия из неё.

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

Декартово произведение множеств и отношения. Виды отношений. Бинарные отношения (соответствия) и их свойства. Представление соответствий конечных множеств в виде (0,1)-матриц. Псевдообращение отношения и его свойства. Произведение отношений и его свойства. Стабильность «положительных» и «отрицательных» свойств отношений.

Однородные отношения и их основные типы (несобственные, единичное, рефлексивные отношения антирефлексивные, симметричные отношения, антисимметричные, транзитивные отношения).

Отношение эквивалентности. Теорема о классах эквивалентности. Перестановочные эквивалентности. Устойчивость отношения эквивалентности относительно теоретико-множественных операций пересечения, объединения и произведения эквивалентностей. Транзитивное, рефлексивное и эквивалентное замыкание отношений. Отношение включения для эквивалентностей.

Отношение и пространства толерантности. Теорема о представлении простых пространств толерантности. Основные типы соответствий. Всюду определённые, частичные, функциональные и дифункциональные соответствия.

Отображения и их основные свойства. Отображения (функциональные соответствия) и их типы (постоянные и тождественное отображения, вложения, наложения, биекции), произведение отображений. Теорема Кантора-Шрёдера-Бернштейна. Моноид эндоморфизмов множества и группа автоморфизмов множества. Каноническое отображение. Ядро отображения как эквивалентность. Основное свойство отображений. Теорема о дробных эквивалентностях.

Порядки

Предпорядки, порядки и частично упорядоченные множества (ч.у. множества). Построение порядка из предпорядка. Диаграммы Хассе. Устойчивость порядков относительно операций над ними. Новые частичные порядки из старых. Принцип двойственности для ч.у. множеств. Размерность ч.у. множества. Экстремальные (максимальные, минимальные, наибольшие, наименьшие) элементы и атомы ч.у. множеств. Верхний и нижний конусы и их свойства. Верхние и нижние грани. Точные верхние и нижние грани. Цепи и антицепи.

Новые множества из старых. Размерность ч.у. множеств. Операции (прямая сумма, прямое произведение, «возведения в степень») над ч.у. множествами и связь между ними. Размерность. Изотонные отображения и порядковые идеалы. Порядковые идеалы и фильтры. Связь между анитцепями и порядковыми идеалами конечных ч.у. множеств. Порядковые гомоморфизмы. Изоморфизм ч.у. множеств. Теорема о вложении ч.у. множеств в алгебру множеств.

Вполне упорядоченные множества и смежные вопросы. Утверждения относительно существования экстремальных элементов в ч.у. м. (лемма Куратовского-Цорна и принцип Хаусдорфа). Полная упорядоченность и аксиома о полном упорядочении. Аксиома выбора и её связь с теоретико-множественной аксиоматикой. Теоремы о сравнении вполне упорядоченных множеств и о сравнении множеств. Принцип трансфинитной индукции.

Полугруппы и полусистемы Туэ. Симметрическая полугруппой Туэ на множестве. Теорема о представлении полугрупп Туэ. Полусистемы Туэ.

Алгебраические решётки

Решётчато упорядоченные множества и решётки. Принцип двойственности для решёток. Теорема о связи решётчато упорядоченных множеств и решёток. Основные свойства решёток (неравенства полудистрибутивности и полумодулярности). Алгебраические гомоморфизмы решёток и их связь с порядковыми гомоморфизмами. Изоморфизмы решёток. Теорема об эквивалентности порядковых и решётчатых изоморфизмов. Подрешётки. Произведения решёток.

Основные свойства решёток. Решёточные гомоморфизмы, идеалы и фильтры. Теорема о вложении решёток в булеан некоторого множества. Представление элементов решётки подмножествами и аналоги диаграмм Эйлера-Венна.

Модулярные решётки. Критерий модулярности решётки. Условия Жордана-Дедекинда для цепей. Характерное свойство модулярных решёток.

Дистрибутивные решётки. Правило сокращения для дистрибутивных решёток. Теорема о модулярных и дистрибутивных решётках. Критерий дистрибутивности решётки (теорема Дедекинда-Биркгофа). Дистрибутивность решётки J(P) порядковых идеалов ч.у. множества P. Построение диаграммы Хассе для решётки порядковых идеалов конечного ч.у. множеств. Неразложимые объединение элементы решётки. Лемма об изоморфизме подрешётки неразложимых в объединение элементов J(P) и P. Теорема Биркгофа о вложимости дистрибутивных решёток в булеан множества. Случай конечных решёток. Фундаментальная теорема для конечных дистрибутивных решёток. Следствия из теоремы Биркгофа. Способ вложения конечной дистрибутивной решётки L в <N, |>.

Фактор-решётки. Решётки с дополнениями и с единственными дополнениями. Примеры. Единственность дополнения в дистрибутивных решётках. Связь дистрибутивности и наличия единственного дополнения, проблема Хантингтона и теорема Дилуорса.

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

Булевы алгебры как решётки. Булевы гомоморфизмы и подалгебры. Булевы алгебры как дистрибутивные решётки с дополнениями. Пример безатомной БА. Критерий для атомных булевых алгебр. Булевы кольца и структуры. Идеалы и фильтры в булевой алгебре.

Булевы многочлены. Множество P и полиномиальная функция, индуцированная P на булевой алгебре. Множество Pn(B) как булева алгебра. Система нормальных форм, СДНФ и СКНФ, ДНФ и КНФ. Алгоритм получения СДНФ булева многочлена. Уравнения в булевых алгебрах. Эквивалентность уравнений P = Q и PQ'+P'Q = 0. Решения булевых уравнений.

Алгебраические системы

Модели и алгебры. Алгебраические системы (АС): определения и базовые понятия (тип АС, алгебры и модели, сигнатура, интерпретация, одноимённые операции и отношения). Сокращённая запись АС, главные операции, отношения и элементы.

Подсистемы. Прямое произведение АС. Редукты и подсистемы АС. Пересечение подсистем и главная подсистема. Порождающие элементы. Теорема об объединении подсистем множеств. Локальная совокупность подмножеств.

Гомоморфизмы АС. Согласованность отображений АС с их операциями и отношениями и виды согласованности. Типы гомоморфизмов АС. Ядро гомоморфизма. Изоморфизмы, эпиморфизмы, мономорфизмы, эндоморфизмы и автоморфизмы АС. Теорема о сюръективном эндоморфизме конечной АС.

Конгруэнции и фактор-системы. Стабильность отношения относительно операции и на АС. Свойство ядра гомоморфизма. Факторсистемы. Определения операций и отношений на факторсистмах. Теоремы о гомоморфизмах и изоморфизмах АС. Многоосновные системы.

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

  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
Личные инструменты