Дискретные структуры
Содержание курса
Раздел 1. Математический инструментарий
Тема 1.1. Язык математической логики
Высказывания и операции над ними. Равносильные формулы. Логическое следствие. Законы логики. Предикаты и кванторы.
Тема 1.2. Множества
Множества и операции над ними. Диаграммы Эйлера – Вэнна.
Тема 1.3. Бинарные отношения
Бинарные отношения. Виды отношений: рефлексивные, антирефлексивные, симметричные, антисимметричные, транзитивные, связные. Исследование отношений. Отношения эквивалентности и порядка.
Тема 1.4. Метод математической индукции
Доказательство тождеств, неравенств и делимости методом математической индукции
Тема 1.5. Комбинаторика
Принцип суммы и произведения. Перестановки, размещения, сочетания без повторений и с повторениями. Бином Ньютона.
Раздел 2. Последовательности
Тема 2.1. Рекуррентные соотношения
Рекурсия. Числа Фибоначчи. Производящие функции. Преобразование производящей функции при преобразовании последовательности. Решение возвратных рекуррентных соотношений.
Раздел 3. Графы
Тема 3.1. Виды графов
Основные понятия теории графов. Степень вершины графа. Дерево.
Плоские графы. Формула Эйлера. Теорема Фари.
Эйлеровы графы. Обход ребер графа по одному разу в обоих направлениях. Гамильтоновы графы.
Тема 3.2. Взвешенные графы
Взвешенные графы. Минимальное остовное дерево. Поиск кратчайшего маршрута. Сетевой график. Потоки в сетях.
Раздел 4. Булевы функции
Тема 4.1. Представление булевых функций
Булевы функции. Элементарные операции. Таблица значений. Двойственные булевы функции. Сднф и скнф.
Полнота. Полином Жегалкина.
Тема 4.2. Классы булевых функций
Замкнутые классы. Теорема о функциональной полноте. Минимизация булевых функций.
Раздел 5. Теория кодирования
Тема 5.1. Теория кодирования
Однозначность декодирования. Самокорректирующиеся коды
Результаты освоения курса
Выпускник знает:
Язык математической логики, основы теории множеств, комбинаторики, теории графов, теории булевых функций
Умеет:
Использовать теоретические знания для решения широкого круга задач
Владеет и (или) имеет опыт деятельности:
Методами решения комбинаторных задач, использования графов для моделирования и решения задач в различных областях математики
Раздел 1. Математический инструментарий
Тема 1.1. Язык математической логики
Высказывания и операции над ними. Равносильные формулы. Логическое следствие. Законы логики. Предикаты и кванторы.
Тема 1.2. Множества
Множества и операции над ними. Диаграммы Эйлера – Вэнна.
Тема 1.3. Бинарные отношения
Бинарные отношения. Виды отношений: рефлексивные, антирефлексивные, симметричные, антисимметричные, транзитивные, связные. Исследование отношений. Отношения эквивалентности и порядка.
Тема 1.4. Метод математической индукции
Доказательство тождеств, неравенств и делимости методом математической индукции
Тема 1.5. Комбинаторика
Принцип суммы и произведения. Перестановки, размещения, сочетания без повторений и с повторениями. Бином Ньютона.
Раздел 2. Последовательности
Тема 2.1. Рекуррентные соотношения
Рекурсия. Числа Фибоначчи. Производящие функции. Преобразование производящей функции при преобразовании последовательности. Решение возвратных рекуррентных соотношений.
Раздел 3. Графы
Тема 3.1. Виды графов
Основные понятия теории графов. Степень вершины графа. Дерево.
Плоские графы. Формула Эйлера. Теорема Фари.
Эйлеровы графы. Обход ребер графа по одному разу в обоих направлениях. Гамильтоновы графы.
Тема 3.2. Взвешенные графы
Взвешенные графы. Минимальное остовное дерево. Поиск кратчайшего маршрута. Сетевой график. Потоки в сетях.
Раздел 4. Булевы функции
Тема 4.1. Представление булевых функций
Булевы функции. Элементарные операции. Таблица значений. Двойственные булевы функции. Сднф и скнф.
Полнота. Полином Жегалкина.
Тема 4.2. Классы булевых функций
Замкнутые классы. Теорема о функциональной полноте. Минимизация булевых функций.
Раздел 5. Теория кодирования
Тема 5.1. Теория кодирования
Однозначность декодирования. Самокорректирующиеся коды
Результаты освоения курса
Выпускник знает:
Язык математической логики, основы теории множеств, комбинаторики, теории графов, теории булевых функций
Умеет:
Использовать теоретические знания для решения широкого круга задач
Владеет и (или) имеет опыт деятельности:
Методами решения комбинаторных задач, использования графов для моделирования и решения задач в различных областях математики