Discrete Mathematics

2019/2020

Academic Year

RUS

Instruction in Russian

6

ECTS credits

Delivered at:

Faculty of Mathematics

Course type:

Compulsory course

When:

1 year, 1, 4 module

Instructors

Artamkin, Igor

Merzon, Grigory

Osipov, Pavel

Smirnov, Evgeny

Shtern, Alexander

Программа дисциплины

Аннотация

В дисциплине «Введение в дискретную математику» излагаются базовые понятия и приёмы рассуждений, необходимые в большинстве дальнейших математических курсов, и описываются методы работы с различными комбинаторными объектами (т.е. объектами, нумерующимися элементами конечных множетств). К числу таких методов относятся методы перечислительной комбинаторики, теории производящих функций, теории графов и др.

Цель освоения дисциплины

• Целью изучения дисциплины «Введение в дискретную математику» в первом модуле первого курса является знакомство студентов с базовыми понятиями и приёмами рассуждений, необходимыми в большинстве дальнейших математических курсов.
• Цель изучения второй части дисциплины, читаемой в четвертом модуле первого курса, состоит в том, чтобы научить студентов работать с различными комбинаторными объектами, узнавать эти комбинаторные объекты в задачах из других областей математики и применять к ним методы дискретной математики. К числу таких методов относятся методы перечислительной комбинаторики, теории производящих функций, теории графов и др.

Планируемые результаты обучения

• Студенты должны овладеть методом математической индукции и научиться применять его в различных алгебраических и комбинаторных задачах
• Студенты должны научиться распознавать известные им комбинаторные конструкции (перестановки, размещения, сочетания) в предлагаемым им комбинаторных и простейших вероятностных задачах и применять комбинаторные методы к решению таких задач.
• Студенты должны овладеть понятием отношения на множестве, в частности, освоить понятия отношения эквивалентности, разбиения на классы эквивалентности, фактормножества, а также частично упорядоченного множества, и научиться применять эти конструкции к решению задач из различных областей математики.
• Студенты должны овладеть понятиями мощности множеств, равномощных множеств, научиться доказывать счётность или несчётность различных множеств (в частности, Z, Q, R, C...).
• Студенты должны изучить основные логические операции, принципы работы с кванторами, а также основные понятия теории множеств.
• Студенты должны познакомиться с аксиомой выбора (в различных формулировках) и эквивалентными ей утверждениями: теоремой Цермело и леммой Цорна, и научиться применять её в различных задачах теории множеств.
• Студенты должны повторить изложенный в 1-м модуле материал, относящийся к элементарной перечислительной комбинаторике и научиться применять его к решению комбинаторных задач. В частности, они должны освоить комбинаторные методы доказательства различных тождеств с биномиальными коэффициентами.
• Студенты должны освоить принципы работы с формальными степенными рядами и научиться выписывать общее и частное решение линейного рекуррентного уравнения с постоянными коэффициентами (в частности, в случае кратных корней характеристического уравнения).
• Студенты должны познакомиться с понятием q-биномиального коэффициента и научиться доказываь q-аналоги различных комбинаторных тождеств, а также выписывать производящую функцию Эйлера для числа разбиений и обратный к ней ряд, задаваемый пентагональной теоремой Эйлера.
• Студенты должны научиться работать с числами Каталана, Шрёдера и Моцкина, в частности, выписывать их производящие функции и строить биекции между множествами, дающими их различные комбинаторные интерпретации (в случае чисел Каталана — пути Дика, бинарные деревья, разбиения треугольника и т.д.)
• Студенты должны освоить основные понятия теории графов: изоморфизм и гомотопическая эквивалентность графов, критерий планарности и др., и овладеть навыками применения методов теории графов в комбинаторных задачах.

Содержание учебной дисциплины

• Метод математической индукции
  Применение метода математической индукции к доказательству тождеств и другим задачам
• Элементы комбинаторики
  Перестановки, размещения, сочетания
• Простейшие понятия логики
  Язык теории множеств
• Отношения
  Отношения эквивалентности и порядка
• Мощности множеств
  Счетные и несчетные множества. Теорема Кантора-Бернштейна, континуум-гипотеза.
• Вполне упорядоченные множества
  Аксиома выбора, теорема Цермело, лемма Цорна.
• Перечисление комбинаторных объектов
  Биномиальные и мультиномиальные коэффициенты. Формула включений-исключений.
• Простейшие производящие функции
  Вычисления с формальными степенными рядами. Линейные рекурренты и рациональные производящие функции.
• Нелинейные рекурренты
  Числа Каталана, Шрёдера и Моцкина, их производящие функции
• Разбиения
  q-биномиальные коэффициенты. Производящая функция Эйлера, пентагональная теорема
• Графы
  Изоморфизм графов. Планарные графы, теорема Эйлера. Критерии планарности, теорема Куратовского. Перечислительные задачи теории графов. Теорема Кэли.

Элементы контроля

• экзамен
• Контрольная работа
• домашние задания
• МООС курс "Introduction to Enumerative Combinatorics"

Промежуточная аттестация

• Промежуточная аттестация (1 модуль)
  Оценка совпадает с накопленной, которая равна среднему арифметическому (со стандартным правилом округления) оценок за шесть листков, но не выше 7 для студентов, не сдавших на положительную оценку последний листок. Формула оценки за каждый листок указана в самом листке; если студент не приступал к сдаче листка, он учитывается с весом -3, за исключением последнего, который в этом случае учитывается с весом 0.
• Промежуточная аттестация (4 модуль)
  0.2 * домашние задания + 0.25 * Контрольная работа + 0.1 * МООС курс "Introduction to Enumerative Combinatorics" + 0.45 * экзамен

Список литературы

Рекомендуемая основная литература

• Лекции о производящих функциях, Ландо, С. К., 2007

Рекомендуемая дополнительная литература

• Комбинаторика, Виленкин, Н. Я., 2006