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

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

Язык: русский
Кредиты: 6

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

Аннотация

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

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

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

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

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

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

  • неблокирующий Накопленная оценка за листки
  • неблокирующий Экзамен
  • неблокирующий контрольная работа
    Работа проводится в середине 4-го модуля
Промежуточная аттестация

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

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

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

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

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