• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Discrete Mathematics

2019/2020
Academic Year
RUS
Instruction in Russian
6
ECTS credits
Delivered at:
Department of Information Technologies in Business (Faculty of Computer Science, Economics, and Social Sciences)
Course type:
Compulsory course
When:
1 year, 1, 2 module

Instructor

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

Аннотация

Настоящая программа учебной дисциплины устанавливает требования к образовательным результатам и результатам обучения студента и определяет содержание и виды учебных занятий и отчетности. Программа предназначена для преподавателей, ведущих дисциплину «Дискретная математика», учебных ассистентов и студентов направления подготовки 38.03.05 Бизнес-информатика, обучающихся по образовательной программе «Бизнес-информатика».
Цель освоения дисциплины

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

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

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

  • решает типовые задачи теории множеств
  • решает типовые задачи теории булевых функций и логики
  • решает типовые задачи теории графов
  • решает типовые задачи комбинаторики
  • решает типовые задачи теории конечных детерминированных автоматов
  • решает типовые задачи теории кодирования
Содержание учебной дисциплины

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

  • Раздел 1.Множества, соответствия, отношения
    Тема 1. Основные понятия теории множеств, способы задания. Основные определения, понятия, обозначения теории множеств. Диаграммы Венна. Операции над множествами: объединение, пересечение, дополнение. Прямое произведение множеств. Основные способы задания множеств. Тема 2. Соответствия и отношения Общее понятие отношения и соответствия. Теоретико-множественные операции над соответствиями, классификация соответствий. Бинарные отношения и их свойства. Транзитивное замыкание отношений. Отношение эквивалентности и классы эквивалентности. Отношение порядка. Диаграммы Хассе. Линейный порядок и частичный порядок. Квазипорядок. Решетки. Тема 3. Мощность множеств. Понятие мощности множества по Кантору. Теорем Кантора. Арифметика бесконечного.
  • Раздел 2. Булевы функции и элементы математической логики
    Тема 4. Элементарные булевы функции, канонические способы задания. Элементарные булевы функции, способы задания булевых функций, существенные и фиктивные переменные, карты Карно. Разложение булевых функций в полиномы Жегалкина, совершенные дизъюнктивные и совершенные конъюнктивные нормальные формы (СДНФ и СКНФ). Минимизация дизъюнктивных и конъюнктивных нормальных форм с помощью карт Карно. Тема 5. Замкнутые классы булевых функций. Полные системы булевых функций, базисы. Замкнутые классы самодвойственных, монотонных, линейных функций и функций, сохраняющих 0 и 1. Леммы о функциях, не принадлежащих замкнутым классам. Примеры полных систем булевых функций и базисов, теорема о двух системах, критерий Поста функциональной полноты, алгоритм проверки системы на полноту. Тема 6. Высказывания, методы проверки логического следования. Интерпретация составного высказывания, тавтология, противоречие, нейтральное, выполнимое, опровержимое высказывание. Логическое следование, логическая эквивалентность составных высказываний, методы проверки логического следования и логической эквивалентности, сведение к противоречию, сведение к тавтологии. Тема 7. Предикаты, предикатные формулы. Предметная область, предметные переменные, область истинности предиката, логические операции над предикатами, кванторы. Предикатная формула, интерпретация, модель, общезначимые, противоречивые, выполнимые, опровержимые формулы. Список основных эквивалентностей, методы проверки логического следования и логической эквивалентности для некоторых классов предикатных формул, геометрический смысл кванторов. Тема 8. Метод резолюций в логике высказываний и логике предикатов. Дизъюнкт, резольвента. Основное правило метода резолюций. Схема метода резолюций для логики высказываний. Предваренный и нормальный вид предикатной формулы, элиминация кванторов, сколемовские константы и функции. Процедура унификации, унификаторы, основное правило метода резолюций, резольвента, схема метода резолюций для логики предикатов. Примеры.
  • Раздел 3. Теория графов
    Тема 9. Основные понятия теории графов, способы задания. Основные определения, понятия, обозначения теории графов: степень вершины, смежность вершин, инцидентность вершин и ребер, удаленность вершины, радиус, диаметр, центр графа. Основные способы задания графов: матрицы смежности и инциденций. Тема 10. Типы графов и обходы графов. Основные типы графов: нулевой, полный, двудольный, связный, дополнительный граф. Основные операции над графами: добавление и удаление вершины, добавление и удаление ребра, отождествление вершин, стягивание графа. Эйлерова цепь, эйлеров цикл, критерии их существования, алгоритм Флери. Гамильтонова цепь, гамильтонов цикл, достаточные условия их существования. Тема 11. Экстремальные задачи на графах. Критерий двудольности графа, правильная раскраска двудольного графа. Свойства деревьев, нахождение центра, радиуса и диаметра дерева, кодирование деревьев, остовное дерево графа. Задача о минимальном остовном дереве, алгоритмы Прима и Краскала. Задача коммивояжера, «жадный алгоритм». Задача о кратчайшем пути, алгоритм Дейкстры. Тема 12. Изоморфизм, планарность, правильная вершинная раскраска. Изоморфизм, гомеоморфизм, планарность графов, методы установления изоморфизма или неизоморфизма, планарности или непланарности, формула Эйлера, критерий Понтрягина-Куратовского, необходимые признаки планарности. Правильная вершинная и реберная раскраска графов, хроматическое число, «жадный» алгоритм правильной раскраски, хроматический многочлен, его свойства. Тема 13. Ориентированные графы. Графы и бинарные отношения. Достижимость и частичное упорядочение. Транзитивное замыкание. Топологическая сортировка, алгоритм Демукрона. Календарное планирование, диаграммы Ганта.
  • Раздел 4. Комбинаторика.
    Тема 14. Основные комбинаторные операции. Основные комбинаторные операции: выборки с возвращением и без возвращения элементов, выборки с упорядочением и без упорядочения элементов, сочетания и размещения, числа сочетаний и размещений. Тема 15. Комбинаторные принципы Основные комбинаторные принципы: принцип сложения, принцип умножения, принцип дополнения, принцип включения-исключения, принцип кодирования. Тема 16. Биномиальная и полиномиальная формулы Треугольник Паскаля, бином Ньютона, биномиальные коэффициенты, их основные свойства. Полиномиальная формула.
  • Раздел 5. Теория автоматов.
    Тема 17. Конечные детерминированные автоматы, способы задания. Схема абстрактного конечного автомата, принципы его функционирования, способы задания: таблицей и диаграммой Мура. Автоматы-распознаватели и автоматы-преобразователи, автоматы Мура, автоматы Мили, автоматы-генераторы. Тема 18. Регулярные выражения, распознавание регулярных языков. Слова и языки, операции над ними: сложение, умножение, итерация, дополнение. Регулярные выражения и регулярные языки, теорема Клини. Тема 19. Задачи анализа, синтеза и минимизации автоматов. Задача анализа автомата-распознавателя, алгоритм для решения задачи анализа, представление распознаваемого языка в виде регулярного выражения. Задача синтеза автомата-распознавателя по заданному регулярному выражению, детерминированные двухполюсные источники, замкнутые множества состояний источника, преобразование источника в автомат. Эквивалентные автоматы, эквивалентные состояния автомата, задача минимизации автоматов-распознавателей и автоматов-преобразователей, алгоритм Мили для решения задачи минимизации. Тема 20. Логические автоматы. Детерминированные и недетерминированные функции, вес детерминированной функции и её задание с помощью бесконечного дерева, автоматная (ограниченно-детерминированная) функция, её задание конечным деревом, диаграммой Мура и таблицей. Способы задания логических автоматов: канонической таблицей, канонической системой, схемой их функциональных элементов с памятью. Операции над логическими автоматами: суперпозиция и введение обратной связи.
  • Раздел 6. Кодирование.
    Тема 21. Однозначно декодируемые схемы алфавитного кодирования. Схемы алфавитного кодирования, достаточные признаки однозначной декодируемости, необходимый признак однозначной декодируемости, неравенство Макмиллана-Крафта. Задача исследования схемы алфавитного кодирования на однозначную декодируемость Теорема Маркова, алгоритм Маркова. Тема 22. Экономное кодирование, коды с минимальной избыточностью. Избыточность схемы кодирования, частотные характеристики алфавита, схемы с минимальной избыточностью, коды Хаффмана. Тема 23. Помехоустойчивое кодирование, самокорректирующиеся коды. Двоичные равномерные коды, расстояние Хэмминга, кодовое расстояние, линейные коды, способы их задания, свойства, двойственные коды. Проблема защиты каналов связи, помехоустойчивые схемы кодирования, коды Хэмминга. Методы сжатия информации, алгоритм Лемпеля-Зива.
Элементы контроля

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

  • неблокирующий контрольная работа 1
  • неблокирующий самостоятельная работа
  • неблокирующий контрольная работа 2
  • неблокирующий Экзамен
Промежуточная аттестация

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

  • Промежуточная аттестация (2 модуль)
    0.2 * контрольная работа 1 + 0.2 * контрольная работа 2 + 0.2 * самостоятельная работа + 0.4 * Экзамен
Список литературы

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

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

  • Лекции по дискретной математике : учеб. пособие / В.Б. Алексеев. — М. : ИНФРА-М, 2018. — 90 с. — (Высшее образование: Бакалавриат). - Режим доступа: http://znanium.com/catalog/product/952158

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

  • Таранников Ю. В. - ДИСКРЕТНАЯ МАТЕМАТИКА. ЗАДАЧНИК. Учебное пособие для академического бакалавриата - М.:Издательство Юрайт - 2019 - 385с. - ISBN: 978-5-534-01180-7 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/diskretnaya-matematika-zadachnik-433218