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

2026/2027

Учебный год

RUS

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

4

Кредиты

Кто читает:

Кафедра высшей математики (Общеуниверситетские кафедры)

Статус:

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

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

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

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

Сахарова Нина Евгеньевна

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

Аннотация

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

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

• Целями освоения дисциплины «Дискретная математика» являются получение развёрнутого представления об основных разделах дискретной математики, развитие навыка строгих математических доказательств, изучение теоретических оснований и получение первичных практических навыков автоматической обработки текстов, общее развитие мышления, подготовка базы для последующих курсов математики.

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

• Знает основные определения и алгоритмы на графах.
• Умеет решать задачи в рамках которых необходимо использовать графы.
• Знает основные понятия, методы и результаты теории булевых функций.
• Знает определение булевой функции. Может назвать все булевые функции одной переменной и основные булевые функции двух переменных (конъюнкция, дизъюнкция, импликация, эквивалентность, штрих Шеффера, стрелка Пирса)
• Умеет строить таблицы истинности булевых функций.
• Владеть основными понятиями теории булевых функций.
• Использовать булевы функции для формализации и решения логических задач.
• Умеет решать задачи из раздела "Элементы теории множеств".
• Умеет оперировать понятиями "множество" и операциями над множествами. Умеет строить взаимооднозначное соответствие между множествами или доказывать его отсутстсвие.
• Умеет применять метод математической индукции для решения задач
• Умеет применять комбинаторные методы для решения стандартных задач, а также комбинировать стандартные методы.
• Умеет составлять рекуррентные соотношения для соответствующих задач. Умеет решать рекуррентные соотношения.
• Умение выделять в сложных в высказываниях логические связки. Умение строить отрицания высказываний.
• Уметь строить алгоритмы на графах, такие как поиск кратчайшего пути, поиск наиболее надёжного пути, поиск минимального остовного дерева.

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

• Основы теории множеств.
• Метод математической индукции
• Комбинаторика
• Линейные рекуррентные последовательности.
• Функции алгебры логики.
• Предикаты.
• Системы счисления
• Китайская теорема об остатках. Теоремы Эйлера и Ферма. Функция Эйлера.
• Графы.
• Алгоритмы на графах
• Двудольные графы, функции и паросочетания

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

• Контрольная работа
  Письменная работа на 2 часа
• Экзамен
  Письменная работа на 2 часа.
• Домашние работы
  В тестовой системе http://hsemath.ru/ в каждой задаче у вас есть три попытки. За неверные попытки баллы не снимаются, вам зачтется полный балл, если хотя бы в одной попытке есть верный ответ.
• Самостоятельные работы
  Короткие письменные работы на 20 минут
• Аудиторная работа
  В этой оценке учитывается посещаемость занятий и решение задач на семинаре

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

• 2026/2027 2nd module
  0.28 * Контрольная работа + 0.29 * Экзамен + 0.1 * Аудиторная работа + 0.23 * Самостоятельные работы + 0 * Домашние работы

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

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

• Гашков, С. Б.  Дискретная математика : учебник и практикум для среднего профессионального образования / С. Б. Гашков, А. Б. Фролов. — 2-е изд., испр. и доп. — Москва : Издательство Юрайт, 2019. — 483 с. — (Профессиональное образование). — ISBN 978-5-534-11558-1. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/445631 (дата обращения: 28.08.2023).
• Дискретная математика : курс лекций для студентов-механиков, Редькин, Н. П., 2006
• Задачи и упражнения по дискретной математике : учеб. пособие, Гаврилов, Г. П., 2005
• Задачи по теории множеств, математической логике и теории алгоритмов - Лавров И.А., Максимова Л.Л. - Издательство "Физматлит" - 5-9221-0026-2 - 2002 - русский - https://e.lanbook.com/book/2242 - ЛАНЬ - 2242
• Конспект лекций О.Б. Лупанова по курсу "Введение в математическую логику" : учебное пособие для вузов, Лупанов, О. Б., 2023
• Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств - Верещагин Н.К., Шень А. - Московский центр непрерывного математического образования - 978-5-94057-321-0 - 2008 - русский - https://e.lanbook.com/book/9306 - ЛАНЬ - 9306
• Основы теории булевых функций - Марченков С.С. - Издательство "Физматлит" - 978-5-9221-1562-9 - 2014 - русский - https://e.lanbook.com/book/59714 - ЛАНЬ - 59714
• Рассказы о множествах - Виленкин Н.Я. - Московский центр непрерывного математического образования - 978-5-94057-036-3 - 2007 - русский - https://e.lanbook.com/book/9309 - ЛАНЬ - 9309
• Редькин, Н. П. Дискретная математика / Н.П. Редькин. - Москва : ФИЗМАТЛИТ, 2009. - 264 с. ISBN 978-5-9221-1093-8, 700 экз. - Текст : электронный. - URL: https://znanium.com/catalog/product/208908
• Функции алгебры логики. Канонические виды булевых формул - Сорочан С. В. - Национальный исследовательский Нижегородский государственный университет им. Н.И. Лобачевского - - - 2023 - русский - https://e.lanbook.com/book/344945 - ЛАНЬ - 344945

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

• Введение в дискретную математику : учеб. пособие для вузов, Яблонский, С. В., 1979
• Лекции по математической логике и теории алгоритмов. Ч.1: Начала теории множеств, Верещагин, Н. К., 2008
• Теория графов, Оре, О., 1980
• Теория графов, Харари, Ф., 2009

Авторы

• Сахарова Нина Евгеньевна