• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2020/2021

Дискретная математика

Статус: Курс обязательный (Совместный бакалавриат НИУ ВШЭ и ЦПМ)
Направление: 01.03.01. Математика
Когда читается: 1-й курс, 1 модуль
Формат изучения: без онлайн-курса
Язык: русский
Кредиты: 4
Контактные часы: 50

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

Аннотация

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

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

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

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

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

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

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

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

  • неблокирующий листки
  • неблокирующий контрольные работы
Промежуточная аттестация

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

  • Промежуточная аттестация (1 модуль)
    Оценка за первый модуль совпадает с накопленной, которая равна среднему арифметическому (со стандартным правилом округления) оценок за шесть листков, но не выше 7 для студентов, не сдавших на положительную оценку последний листок. Формула оценки за каждый листок указана в самом листке; если студент не приступал к сдаче листка, он учитывается с весом -3, за исключением последнего, который в этом случае учитывается с весом 0.
Список литературы

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

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

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

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

  • Введение в дискретную математику, Ландо, С. К., 2012
  • Комбинаторика, Виленкин, Н. Я., 2006