Discrete Mathematics

2023/2024

Academic Year

RUS

Instruction in Russian

4

ECTS credits

Delivered at:

Department of Higher Mathematics (Independent HSE Departments)

Course type:

Elective course

When:

1 year, 3 module

Instructor

Mikhailovich, Anna

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

Аннотация

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

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

• Студент должен знать основные понятия теории множеств, комбинаторики и теории графов.

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

• Способен работать в команде
• Способен учиться, приобретать новые знания, умения, в том числе в области, отличной от профессиональной
• Способен использовать основные законы естественнонаучных дисциплин в профессиональной деятельности, применять методы математического анализа и моделирования, теоретического и экспериментального исследования при решении профессиональных задач
• Способен критически воспринимать, обобщать, анализировать профессиональную информацию

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

• Множества и операции с ними.
• Комбинаторика. Основные задачи комбинаторики
• Бином Ньютона. Свойства биномиальных коэффициентов.
• Принцип включений и исключений. Диаграммы Эйлера-Венна.
• Основные понятия теории графов.
• Изоморфизм графов.
• Метрические характеристики графа
• Связность графа.
• Алгоритмы на графах

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

• Работа на семинарах
• Текущие домашние задания
• Письменное домашнее задание
• Контрольная работа
• Экзамен

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

• 2023/2024 учебный год 3 модуль
  0.2 * Контрольная работа + 0.08 * Письменное домашнее задание + 0.25 * Работа на семинарах + 0.12 * Текущие домашние задания + 0.35 * Экзамен

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

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

• Гаврилов, Г. П. Задачи и упражнения по дискретной математике : учебное пособие / Г. П. Гаврилов, А. А. Сапоженко. — 3-е изд., перераб. — Москва : ФИЗМАТЛИТ, 2009. — 416 с. — ISBN 978-5-9221-0477-7. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/2157 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
• Графы и их применение, Оре, О., 2008
• Задачи и упражнения по дискретной математике : учеб. пособие, Гаврилов, Г. П., 2005
• Лекции по математической логике и теории алгоритмов. Ч.1: Начала теории множеств, Верещагин, Н. К., 2012
• Лекции по математической логике и теории алгоритмов. Ч.1: Начала теории множеств, Верещагин, Н. К., 2017
• Теория графов, Харари, Ф., 2003

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

• Дискретная математика : курс лекций для студентов-механиков, Редькин, Н. П., 2006
• Дискретная математика для социально-экономических специальностей : учеб. пособие, Андреева, Т. В., 2007
• Задача о коммивояжере, Мудров, В. И., 1969
• Комбинаторика, Виленкин, Н. Я., 1969
• Математическая логика, Шенфилд, Дж., 1975
• Теория графов, Оре, О., 1968