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

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

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

Направление: 09.03.01. Информатика и вычислительная техника

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

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

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

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

Охват аудитории: для всех кампусов НИУ ВШЭ

Преподаватели: Боголюбов Дмитрий Петрович, Рабинович Александр Соломонович, Сироткин Дмитрий Валерьевич, Тутуров Алексей Александрович

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

Кредиты: 4

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

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

Аннотация

Настоящая дисциплина относится к базовой части математического и естественнонаучного цикла дисциплин образовательной программы "Информатика и вычислительная техника". Цели изучения дисциплины: знакомство с понятиями дискретной математики и теории графов; освоение основных приемов решения практических задач по темам дисциплины; развитие способности интерпретации формальных алгебраических структур, развитие четкого логического мышления. В результате освоения дисциплины студент должен: • Знать базовые понятия дисциплины • Понимать доказательства ключевых теорем курса • Иметь навыки использования математического аппарата дисциплины в дальнейшей учебной и профессиональной деятельности

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

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

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

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

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

• Элементы теории множеств
• Элементы математической логики
• Комбинаторные схемы
• Методы подсчета и оценивания
• Основы теории графов
• Транспортные сети

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

• Активность на семинарских занятиях 1
• Активность на семинарских занятиях 2
• Контрольная работа 1
• Контрольная работа 2
• Экзамен 1
• контрольно-измерительные материалы
  контрольно-измерительные материалы

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

• 2021/2022 учебный год 2 модуль
  0.2 * Контрольная работа 2 + 0.5 * Экзамен 1 + 0.2 * Контрольная работа 1 + 0.1 * Активность на семинарских занятиях 1

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

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

• Дискретная математика - Гладков Л.А., Курейчик В.В., Курейчик В.М. - Издательство "Физматлит" - 978-5-9221-1575-9 - 2014 - русский - https://e.lanbook.com/book/71976 - ЛАНЬ - 71976
• Дискретная математика : Алгоритмы и программы: Учеб. пособие, Иванов, Б. Н., 2002
• Дискретная математика : Логика, группы, графы, Акимов, О. Е., 2001
• Задачи и упражнения по дискретной математике - Гаврилов Г.П., Сапоженко А.А. - Издательство "Физматлит" - 978-5-9221-0477-7 - 2009 - русский - https://e.lanbook.com/book/2157 - ЛАНЬ - 2157

Авторы

• Рабинович Александр Соломонович