Discrete Mathematics

2024/2025

Academic Year

RUS

Instruction in Russian

4

ECTS credits

Delivered at:

Department of Higher Mathematics (Independent HSE Departments)

Course type:

Compulsory course

When:

1 year, 2-4 module

Instructor

Mikhailovich, Anna

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

Аннотация

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

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

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

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

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

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

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

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

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

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

• 2024/2025 3rd module
  0.27 * Контрольная работа + 0.08 * Письменное домашнее задание + 0.27 * Работа на занятиях + 0.11 * Текущее домашнее задание + 0.27 * Экзамен
• 2024/2025 4th module
  0.05 * Письменное домашнее задание + 0.25 * Работа на занятиях + 0.1 * Текущее домашнее задание + 0.6 * Экзамен

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

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

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

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

• Введение в дискретную математику : учеб. пособие для вузов, Яблонский, С. В., 1979
• Дискретная математика и математические вопросы кибернетики. Т. 1: ., Васильев, Ю. Л., 1974
• Лекции по математической логике и теории алгоритмов. Ч.1: Начала теории множеств, Верещагин, Н. К., 2008
• Математическая теория формальных языков, Пентус, А. Е., 2006
• Пентус, А. Е. Математическая теория формальных языков : учебное пособие / А. Е. Пентус, М. Р. Пентус. — 2-е изд. — Москва : ИНТУИТ, 2016. — 218 с. — ISBN 5-9556-0062-0. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100633 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
• Теория графов, Оре, О., 1980
• Теория графов, Харари, Ф., 2009

Авторы

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