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

2019/2020

Учебный год

RUS

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

6

Кредиты

Кто читает:

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

Статус:

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

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

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

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

Коротков Александр Геннадьевич

Самылина Евгения Александровна

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

Аннотация

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

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

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

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

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

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

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

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

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

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

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

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

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

• Вечтомов Е. М., Широков Д. В. - МАТЕМАТИКА: ЛОГИКА, ТЕОРИЯ МНОЖЕСТВ И КОМБИНАТОРИКА 2-е изд. Учебное пособие для СПО - М.:Издательство Юрайт - 2019 - 243с. - ISBN: 978-5-534-06616-6 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/matematika-logika-teoriya-mnozhestv-i-kombinatorika-441708
• Глибичук А.А., Дайняк А.Б., Ильинский Д.Г. - Элементы дискретной математики в задачах - Московский центр непрерывного математического образования - 2016 - 174с. - ISBN: 978-5-4439-3024-4 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/80156
• Клековкин Г. А. - ТЕОРИЯ ГРАФОВ. СРЕДА MAXIMA 2-е изд. Учебное пособие для прикладного бакалавриата - М.:Издательство Юрайт - 2019 - 133с. - ISBN: 978-5-534-10084-6 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/teoriya-grafov-sreda-maxima-438694
• Ландо С.К. - Введение в дискретную математику - Московский центр непрерывного математического образования - 2012 - 264с. - ISBN: 978-5-4439-2019-1 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/56405
• Математика. Элементы дискретной математики: Учебное пособие / Сапронов И.В., Зюкин П.Н., Веневитина С.С. - Воронеж:ВГЛТУ им. Г.Ф. Морозова, 2013. - 118 с.: ISBN 978-5-7994-0526-7

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

• Лавров И.А., Максимова Л.Л. - Задачи по теории множеств, математической логике и теории алгоритмов - Издательство "Физматлит" - 2002 - 256с. - ISBN: 5-9221-0026-2 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/2242