Элементы дискретной математики

Бакалавриат 2022/2023

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

Направление: 06.03.01. Биология

Кто читает: Базовая кафедра Института биоорганической химии им. академиков М.М. Шемякина и Ю.А. Овчинникова РАН

Где читается: Факультет биологии и биотехнологии

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

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

Охват аудитории: для своего кампуса

Преподаватели: Кочергин Вадим Васильевич, Михайлович Анна Витальевна

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

Кредиты: 3

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

Полная версия программы учебной дисциплины

Аннотация

Комбинато́рика (комбинаторный анализ) — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана с другими областями математики — алгеброй, геометрией, теорией вероятностей и применяется в различных областях знаний (например, в генетике, информатике, статистической физике). Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве». Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов. Данная учебная дисциплина включена в раздел «Профессиональный цикл» Учебного плана 06.03.01 Биология и относится к базовой профильной части. Осваивается на 3 курсе. Изучение данной дисциплины базируется на освоении дисциплины «Математический анализ», «Линейная алгебра». Основные положения дисциплины «Комбинаторика» будут использоваться в рамках изучения дисциплин «Дифференциальные уравнения», «Теория вероятностей и математическая статистика», «Биоинформатика» и др., а также при прохождении практик на 3-4 курсах образовательной программы «Клеточная и молекулярная биотехнология».

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

Освоение ключевых тем и разделов комбинаторики и теории графов

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

Умение решать соответствующие задачи базовыми методами комбинаторики.

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

Основные правила комбинаторики. Выборки. Биномиальные коэффициенты.
Формула включений-исключений
Производящие функции. Линейные рекуррентные соотношения с постоянными коэффициентами.
Числа Фибоначчи.
Деревья
Основные понятия теории графов
Планарные графы.
Ориентированные графы.
Алгоритмы на графах

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

Работа на семинарах
Домашние задания
Письменная экзаменационная работа

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

2022/2023 учебный год 2 модуль
0.3 * Работа на семинарах + 0.35 * Домашние задания + 0.35 * Письменная экзаменационная работа

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