Discrete Mathematics

2019/2020

Academic Year

RUS

Instruction in Russian

4

ECTS credits

Delivered at:

School of Applied Mathematics

Course type:

Compulsory course

When:

1 year, 3, 4 module

Instructors

Busjatskaja, Irina

Wolkowa, Tatyana

Kochetkov, Yury

Parusnikova, Anastasia

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

Аннотация

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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