Бакалавриат 2020/2021

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

Статус: Курс обязательный (Прикладная математика)

Направление: 01.03.04. Прикладная математика

Кто читает: Департамент прикладной математики

Где читается: Московский институт электроники и математики им. А.Н. Тихонова

Когда читается: 1-й курс, 3, 4 модуль

Формат изучения: без онлайн-курса

Преподаватели: Боголюбов Дмитрий Петрович, Бусяцкая Ирина Константиновна, Волкова Татьяна Викторовна, Кочетков Юрий Юрьевич

Язык: русский

Кредиты: 4

Контактные часы: 80

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

Аннотация

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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