Бакалавриат
2018/2019
Дискретная математика
Статус:
Курс обязательный (Прикладная математика)
Направление:
01.03.04. Прикладная математика
Кто читает:
Департамент прикладной математики
Когда читается:
1-й курс, 3, 4 модуль
Формат изучения:
Full time
Преподаватели:
Акбаров Сергей Саидмузафарович,
Бусяцкая Ирина Константиновна,
Волкова Татьяна Викторовна,
Кочетков Юрий Юрьевич,
Сухоцкий Георгий Валентинович,
Шитов Ярослав Николаевич
Язык:
русский
Кредиты:
4
Программа дисциплины
Аннотация
В данном курсе студенты познакомятся с понятиями дискретной математики как основой важной части математического аппарата теории вероятностей и математической статистики, исследования операций, дискретной оптимизации и других дисциплин, получат опыт анализа дискретных структур, развитие строгого логического мышления.
Цель освоения дисциплины
- Знакомство с методами комбинаторных вычислений, включая числа Каталана и методы групп преобразований
- Использование проективных методов для решения задач, связанных с пересечениями кривых на плоскости (продолжение темы, начатой в первом семестере)
- Знакомство с понятиями теории графов
- Знакомство с теорией выпуклых многогранников в трехмерном пространстве
- Освоение основных приемов решения практических задач по темам дисциплины
Результаты освоения дисциплины
- Способность решения различных задач выбора.
- Знание реализаций чисел Каталана.
- Умение использовать формулы Бернсайда для перечисления комбинаторных объектов с точностью до симметрии
- Получение навыка нахождения кратностей пересечения кривых на конечной плоскости и на бесконечно удаленной прямой.
- Знание основных понятий теории графов.
- Умение перечисления многогранников с данным набором вершин, граней и ребер
Содержание учебной дисциплины
- Задачи выбораЗадачи выбора и выбора с повторениями. Треугольник Паскаля. Общая задача выбора. Бином Ньютона. Решение различных задач выбора. Вычисление степеней многочленов с помощью бинома Ньютона. Метод включения/исключения
- Реализации чисел КаталанаЧисла Каталана и их реализации: пути Дика, скобочные структуры, деревья и пр. Треугольник чисел Каталана. Формула для чисел Каталана. Задача об одномерном блуждании. Варианты путей Дика.
- Группы симметрий комбинаторных объектов. Вычисления числа орбит.Использование формулы Бернсайда для перечисления комбинаторных объектов с точностью до симметрии.
- Кривые на проективной плоскостиПересечения, их кратности и теорема Безу. Проективное расширение кубической кривой и ее группа точек. Нахождение кратностей пересечения кривых на конечной плоскости и на бесконечно удаленной прямой.
- ГрафыИзоморфизм. Матрицы смежности. Связные графы. Перечисление графов. Планарность. Карты и формула Эйлера. Кодирование карт.
- Выпуклые многогранники и их перечислениеПеречисление многогранников с данным набором вершин, граней и ребер.
