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

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

Статус: Курс обязательный (Прикладная математика)
Направление: 01.03.04. Прикладная математика
Когда читается: 1-й курс, 3, 4 модуль
Формат изучения: Full time
Язык: русский
Кредиты: 4

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

Аннотация

В данном курсе студенты познакомятся с понятиями дискретной математики как основой важной части математического аппарата теории вероятностей и математической статистики, исследования операций, дискретной оптимизации и других дисциплин, получат опыт анализа дискретных структур, развитие строгого логического мышления.
Цель освоения дисциплины

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

  • Знакомство с методами комбинаторных вычислений, включая числа Каталана и методы групп преобразований
  • Использование проективных методов для решения задач, связанных с пересечениями кривых на плоскости (продолжение темы, начатой в первом семестере)
  • Знакомство с понятиями теории графов
  • Знакомство с теорией выпуклых многогранников в трехмерном пространстве
  • Освоение основных приемов решения практических задач по темам дисциплины
Результаты освоения дисциплины

Результаты освоения дисциплины

  • Способность решения различных задач выбора.
  • Знание реализаций чисел Каталана.
  • Умение использовать формулы Бернсайда для перечисления комбинаторных объектов с точностью до симметрии
  • Получение навыка нахождения кратностей пересечения кривых на конечной плоскости и на бесконечно удаленной прямой.
  • Знание основных понятий теории графов.
  • Умение перечисления многогранников с данным набором вершин, граней и ребер
Содержание учебной дисциплины

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

  • Задачи выбора
    Задачи выбора и выбора с повторениями. Треугольник Паскаля. Общая задача выбора. Бином Ньютона. Решение различных задач выбора. Вычисление степеней многочленов с помощью бинома Ньютона. Метод включения/исключения
  • Реализации чисел Каталана
    Числа Каталана и их реализации: пути Дика, скобочные структуры, деревья и пр. Треугольник чисел Каталана. Формула для чисел Каталана. Задача об одномерном блуждании. Варианты путей Дика.
  • Группы симметрий комбинаторных объектов. Вычисления числа орбит.
    Использование формулы Бернсайда для перечисления комбинаторных объектов с точностью до симметрии.
  • Кривые на проективной плоскости
    Пересечения, их кратности и теорема Безу. Проективное расширение кубической кривой и ее группа точек. Нахождение кратностей пересечения кривых на конечной плоскости и на бесконечно удаленной прямой.
  • Графы
    Изоморфизм. Матрицы смежности. Связные графы. Перечисление графов. Планарность. Карты и формула Эйлера. Кодирование карт.
  • Выпуклые многогранники и их перечисление
    Перечисление многогранников с данным набором вершин, граней и ребер.
Элементы контроля

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

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

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

  • Промежуточная аттестация (4 модуль)
    0.6 * Итоговая аттестация + 0.4 * Письменные работы
Список литературы

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

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

  • Комбинаторика и теория графов : учеб. пособие, Кочетков Ю. Ю., 2009

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

  • Комбинаторика и теория графов. Ч.1: ., Григорьев Б. В., 2005