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

2026/2027

Учебный год

RUS

Обучение ведется на русском языке

5

Кредиты

Кто читает:

Департамент больших данных и информационного поиска

Статус:

Курс обязательный

Когда читается:

1-й курс, 1, 2 модуль

Преподаватели

Александров Кирилл Игоревич

Хитрин Глеб Игоревич

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

Аннотация

Дискретная математика — базовый вводный курс, прививающий студентам азы математической культуры, нужные для последующего изучения других математических дисциплин. Курс знакомит с такими фундаментальными понятиями, как множества, алгебра логики, функции и отображения, отношения и графы, сочетания и перестановки, вероятность. Эти понятия являются фундаментальными в изучении математики и её приложений.

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

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

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

• Владеть определениями и математическим аппаратом, связанным с функциями: образы, прообразы, инъекция, сюръекция, биекция
• Ознакомиться с базовыми математическими понятиями.
• Выработать математическую культуру (культуру доказательств).
• Уметь решать базовые комбинаторные задачи: пользоваться правилами суммы и произведения.
• Уметь решать базовые задачи на графы: находить количество ребер в графе, зная степени вершин.
• Уметь строить ДНФ и КНФ формул.

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

• Логика высказываний. Множества
• Доказательства
• Конечные множества
• Функции
• Булевы функции
• Перечислительная комбинаторика-1
• Перечислительная комбинаторика-2
• Булевы функции-2.
• Вероятность-2
• Графы-1
• Вероятность-1
• Графы-3
• Булевы схемы
• Графы-2

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

• Домашнее задание
  Домашние задания выдаются раз в неделю и должны быть выполнены в течение недели. Для проверки остаточных знаний по темам домашних заданий для каждого домашнего задания проводится выборочная защита (устная беседа) по решённым (хотя бы частично) задачам. В случае, если студент не может ответить на ключевые вопросы по решению задачи или сформулировать используемые при решении задач теоремы и определения, преподаватель уменьшает предварительную оценку за данное домашнее задание на 50%. При неудаче ответа по двум задачам оценка за данное домашнее задание обнуляется.
• Проверочные работы
  Проводятся в письменном виде на лекциях или семинарах по материалам последних лекций. Предполагается несколько проверочных работ в семестре. Длительность одной самостоятельной работы — не более 10 минут.
• Контрольная работа
  Проводится во втором модуле в письменной форме преимущественно по практическому материалу, изученному к моменту проведения коллоквиума. На контрольной работе нужно будет решить несколько задач по темам, изученным на занятиях, и письменно записать их решения.
• Коллоквиум
  Проводится в середине второго модуля в устной форме преимущественно по теоретическому материалу, изученному к моменту проведения коллоквиума. На коллоквиуме могут быть заданы вопросы по известным заранее определениям, формулировкам утверждений, доказательствам утверждений. Также на коллоквиуме могут быть заданы заранее известные задачи. Принимающий по ходу рассказа может задавать уточняющие вопросы.
• Экзамен
  Проводится после второго модуля. Предполагается очная форма сдачи экзамена. При невозможности проведения очного экзамена проводится дистанционный экзамен (при условии согласования с учебным офисом) по правилам, которые дополнительно сообщаются студентам. Экзамен проводится в письменной форме. Письменный экзамен служит для проверки умения творчески использовать полученные знания при решении новых для студента задач. Задания в итоговом письменном экзамене возможны по всем темам, которые изучались в первых двух модулях. Никакими дополнительными материалами или средствами пользоваться нельзя.

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

• 2026/2027 2nd module
  Итог = MIN(10;Округление(0.4 * Э + 0.25 * Колл + 0.2 * КР + 0.15 * ДЗ + 0.05 * ПР)), где ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, Э — оценка за экзамен, Колл – оценка за коллоквиум, ПР – оценка за проверочные работы

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

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

• Графы - Гуровиц В.М., Ховрина В.В. - Московский центр непрерывного математического образования - 978-5-94057-468-2 - 2009 - русский - https://e.lanbook.com/book/9328 - ЛАНЬ - 9328
• Лекции по дискретной математике - Вялый М. Н., Подольский В. В., Рубцов А. А., Шварц Д. А., Шень А. - Издательский дом Высшей школы экономики - 978-5-7598-2212-7 - 2021 - русский - https://e.lanbook.com/book/199883 - ЛАНЬ - 199883
• Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств - Верещагин Н.К., Шень А. - Московский центр непрерывного математического образования - 978-5-94057-321-0 - 2008 - русский - https://e.lanbook.com/book/9306 - ЛАНЬ - 9306
• Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления - Верещагин Н.К., Шень А. - Московский центр непрерывного математического образования - 978-5-94057-322-7 - 2008 - русский - https://e.lanbook.com/book/9307 - ЛАНЬ - 9307
• Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции - Верещагин Н.К., Шень А. - Московский центр непрерывного математического образования - 978-5-94057-323-4 - 2008 - русский - https://e.lanbook.com/book/9308 - ЛАНЬ - 9308
• Математическая индукция - Шень А. - Московский центр непрерывного математического образования - 978-5-94057-772-0 - 2011 - русский - https://e.lanbook.com/book/9444 - ЛАНЬ - 9444

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

• Лекции по дискретной математике / Нац. исслед. ун-т «Высшая школа экономики». — 3-е изд., эл., пересмотр. — (Учебники Высшей школы экономики) - 978-5-7598-2880-8 - Вялый М. Н., Подольский В. В., Рубцов А. А., Шварц Д. А. и др. - 2024 - Москва: ВШЭ - https://ibooks.ru/products/392827 - 392827 - iBOOKS

Авторы

• Максаев Артем Максимович