• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Discrete Mathematics

2019/2020
Academic Year
RUS
Instruction in Russian
4
ECTS credits
Course type:
Compulsory course
When:
1 year, 3, 4 module

Instructors

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

Аннотация

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

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

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

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

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

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

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

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

  • неблокирующий Письменные работы
  • блокирующий Итоговое испытание
    Экзамен проводится в письменной форме: 10 задач в течение часа. После этого студенты присылают свои работы по почте. Проверка проводится в системе ЗУМ в диалоге со студентом. Оценка за экзамен блокирующая. Если оценка за экзаменационную работу положительна, то итоговая оценка выводится по формуле: 0.6*экзаменационной оценки+ 0.4*накопленной оценки.
  • неблокирующий Накопленный балл
Промежуточная аттестация

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

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

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

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

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

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

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