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

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

Лучший по критерию «Новизна полученных знаний»

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

Направление: 38.03.05. Бизнес-информатика

Кто читает: Кафедра информационных систем и технологий (Нижний Новгород)

Где читается: Факультет информатики, математики и компьютерных наук (Нижний Новгород)

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

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

Охват аудитории: для своего кампуса

Преподаватели: Логвинова Кира Владимировна

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

Кредиты: 6

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

Полная версия программы учебной дисциплины

Аннотация

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

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

Целями освоения дисциплины является ознакомление студентов с фундаментальными основами дискретной математики (математической логики, основой теории множеств, теории моделей, теории доказательств и теории вычислимости). Основной целью освоения дисциплины является: приобретение студентами теоретических знаний и навыков решения задач по теории множеств, логике высказываний, теории моделей, теории алгоритмов и теории вычислимости , комбинаторике, и теории графов; приобретение студентами навыков и компетенций по формализации на строгом математическом языке знаний, относящихся к различным предметным областям, возникающих в этих областях проблем и задач; овладение методами построения дискретных моделей предметных областей.

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

Графическое представление заданного отношения с определением его свойств.
Определение полноты заданной системы булевых функций
Вычисление метрических и структурных характеристик графов.
Подсчет числа перестановок, сочетаний и размещений при различных спецификациях. Подсчет числа объектов через формулу включений-исключений.

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

Теория множеств
- Понятие множества, примеры. Мощность множества. Алгебра множеств (операции над множествами и их свойства). Диаграмма Венна. Декартово произведение множеств. - Натуральный ряд. Аксиома бесконечности и формальное определение множества натуральных чисел. Принцип математической индукции. Его вывод из определения натурального ряда. - Понятие подмножества. Теорема о числе подмножеств и доказательство с помощью математической индукции. Понятие отношений, общие свойства отношений. - Отношение эквивалентности (примеры, разбиение множества, теорема о факторизации). Отношение порядка (примеры, упорядоченные множества). - Функциональные отношения и функции. Инъекция, сюръекция, биекция (примеры). Сравнение бесконечных множеств, счетные и несчетные множества. Теорема о не-счетности множества действительных чисел. Теорема Кантора.
Логические функции. Алгебра логики
- Булевы функции. Существенные и фиктивные переменные. Элементарные функции. Алгебра логики. Булевы формулы. - Нормальные формы (ДНФ и КНФ). Теорема о представимой любой булевой форму-лы в виде ДНФ и КНФ. Теоремы о существовании и единственности СДНФ. - Полином Жегалкина. Определение, связь с булевой алгеброй.- Полные системы. Суперпозиция, замкнутость и полнота. Теорема сведения. Вопрос о полноте. - Важнейшие замкнутые классы: функции, сохраняющие константы, монотонные функции, самодвойственные функции. - Линейные функции. Критерий полноты (теорема Поста). Предполные классы и базисы. - Схемы из функциональных элементов и их построение. Теорема о разложении функции по переменной. Сумматор.
Комбинаторика
-Принципы подсчета: правило равенства, правило суммы, правило произведения. Наборы и слова. Лексикографический порядок. -Перестановки. Число перестановок из n элементов. Последовательный выбор. Теорема о последовательном выборе. Размещение. Число размещений. - Сочетания. Число сочетаний. Бином Ньютона. Связь с сочетаниями. Свойства бинома. -Разбиения множества. Упорядоченные разбиения. Обобщение бинома Ньютона. Полиномиальная теорема. - Сочетания с повторениями. Число сочетаний с повторениями. Формула включений-исключений. Неупорядоченные разбиения. - Функции. Сведение комбинаторных задач к подсчету функций. Примеры задач. Применение комбинаторики к вычислению вероятностей. - Линейные рекуррентные уравнения (первого и второго порядков). Примеры задач на решение различных рекуррентных уравнений.
Графы
-Основные понятия теории графов (граф, вершины, ребра). Ориентированный граф, не-ориентированный граф. Число графов с фиксированным количеством вершин. Теорема о рукопожатиях. -Различные способы представления графов. Подграф, дополнение. Пустой граф, полный граф, путь. -Понятие изоморфизма графов. Классы эквивалентности графов (абстрактные графы). Инварианты графов. Примеры. -Пути и циклы. Теорема о существовании цикла. Связный граф, компоненты связности. Теорема о числе ребер в связном графе. Теорема о перешейках. -Расстояния. Метрические характеристики. Эйлеровы циклы и пути. -Деревья. Определение, свойства. -Код Прюфера. Алгоритмы построения кода Прюфера по дереву и дерева по коду Прюфера. Двудольные графы. Теорема Кёнига. -Планарные графы. Плоская укладка. Формула Эйлера. Критерий Понтрягина-Куратовского. Критерий Вагнера.

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

контрольная работа
контрольная работа

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

Промежуточная аттестация (4 модуль)
0.5 * контрольная работа + 0.5 * контрольная работа

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