Дискретная математика для бакалавриата

Оглавление

Введение

1. Множества, отношения и функции
1.1. Множества и способы их задания
1.1.1. Базовые понятия теории множеств
1.1.2. Кортежи и прямое произведение множеств
1.1.3. Способы задания множеств и особенности их применения
1.1.4. Теоретико-множественный парадокс Рассела и возможности его преодоления
1.2. Операции над множествами и диаграммы Эйлера–Венна
1.3. Комбинаторный принцип включений и исключений
1.3.1. Формулировка принципа включений и исключений в общем случае и для некоторых частных его случаев
1.3.2. Доказательство комбинаторного принципа включений и исключений
1.4. Отношения
1.4.1. Бинарные отношения
1.4.2. Отношение эквивалентности
1.4.3. Отношение порядка
1.4.4. Отношение доминирования
1.4.5. Унарные и n-местные отношения
1.5. Соответствия
1.6. Отображения
1.7. Функции
1.7.1. Полная и частичная функции
1.7.2. Обратная функция
1.7.3. Инъективная, сюръективная и биективная функции
1.8. Элементы комбинаторного анализа
1.8.1. Перестановки, размещения и сочетания
1.8.2. Разбиения
1.8.3. Взаимосвязь между перестановками с повторениями и отображением
1.9. Средневзвешенное по элементам множества
1.10. Принцип (метод) математической индукции
1.10.1. Формулировка принципа (метода) математической индукции и его доказательство
1.10.2. Формулировка принципа (метода) строгой математической индукции
1.10.3. Особенности и примеры применения принципа (метода) математической индукции
Вопросы для самоконтроля
1.11. Решение задач
Литература к главе 1

2. Элементы математической логики
2.1. Основные законы математической логики, булевы функции и таблицы истинности
2.1.1. Основные законы математической логики
2.1.2. Булевы функции и приоритет логических операций
2.1.3. Таблицы истинности
2.1.4. Сводная таблица логических функций двух переменных
2.2. Логика высказываний и язык математической логики
2.2.1. Простые высказывания
2.2.2. Сложные (составные) высказывания
2.2.3. Эквивалентные высказывания и замена операций импликации и эквивалентности
2.2.4. Упрощение сложных высказываний
2.3. Взаимосвязь между языком математической логики и алгеброй множеств
2.3.1. Тождества алгебры множеств
2.3.2. Язык математической логики и алгебра множеств
2.3.3. Доказательства логико-математических выражений на основе диаграмм Эйлера-Венна
2.3.4. Доказательства логико-математических выражений путём построения таблицы истинности для левой и правой частей
2.3.5. Доказательство логико-математических выражений путём правильных логических рассуждений
2.4. Логические сети и контактные схемы
2.4.1. Логические сети
2.4.2. Релейно-контактные схемы и возможности их использования
2.4.3. Анализ и синтез логических сетей с применением функции проводимости
2.5. Предикаты
2.5.1. Отличие предикатов от высказываний и основные понятия логики предикатов
2.5.2. Предикаты и кванторы
2.6. Исчисление предикатов (первого порядка)
2.6.1. Основные понятия исчисления предикатов
2.6.2. Правила вывода в исчислении предикатов (первого порядка)
Вопросы для самоконтроля
2.7. Решение задач
Литература к главе 2

3. Элементы теории графов
3.1. Основные понятия теории графов
3.1.1. Диаграммы графов
3.1.2. Типы графов, ориентированные и неориентированные графы
3.1.3. Элементы графов; подграф и частичный граф
3.1.4. Понятия инцидентности и валентности в теории графов
3.1.5. Понятие маршрута, цепи и цикла в графе
3.2. Задача о кёнигсберских мостах; эйлеровы и гамильтоновы циклы
3.2.1. Задача о кёнигсбергских мостах
3.2.2. Понятие уникурсального графа
3.2.3. Теорема Эйлера о сумме степеней вершин графа и её доказательство
3.2.4. Эйлеровы и гамильтоновы циклы
3.3. Деревья
3.3.1. Дерево как частный случай графа
3.3.2. Применение деревьев в экономике и информатике
3.3.3. Применение деревьев в сфере информационной безопасности
3.4. Диаметр, радиус и центр графа
3.4.1. Понятия диаметра графа и эксцентриситетов
3.4.2. Диаметр графа и центр графа
3.4.3. Метрические характеристики графов и задачи размещения
3.5. Специальные маршруты в графах
3.5.1. Латинские свойства путей в графах
3.5.2. Метод латинской композиции и его применение
3.6. Планарные графы
3.6.1. Понятие планарного графа и плоского изображения графа
3.6.2. Критерий планарности графа
3.6.3. Применение планарных графов
3.7. Обходы деревьев и стратегии поиска в глубину и ширину
3.7.1. Обходы деревьев
3.7.2. Стратегии поиска в глубину и ширину
3.7.3. Особенности и основные возможности применения стратегий поиска в глубину и ширину
3.8. Матрицы смежности и инциденций графа
3.8.1. Матрица смежности
3.8.2. Матрица инциденций (инцидентности)
Вопросы для самоконтроля
3.9. Решение задач
Литература к главе 3

4. Элементы теории кодирования
4.1. Двоичное кодирование и коды Грея и Хемминга
4.1.1. Позиционные системы счисления и переход от десятичной к двоичной системе и обратно
4.1.2. Понятия кодов постоянной и переменной длины и кодов с проверкой чётности
4.1.3. Коды Грея и Хемминга
4.1.4. Управление доступом в компьютерную систему по матричному принципу как задача о назначениях
4.2. Однонаправленные функции и однонаправленные функции с секретом
4.2.1. Понятия трудно решаемых задач и стойких шифров
4.2.2. Однонаправленные функции
4.2.3. Однонаправленные функции с секретом
4.3. Алгоритм RSA в режиме шифрования
4.3.1. Понятие о криптосистеме с открытым ключом
4.3.2. Применение алгоритма RSA в режиме шифрования
4.4. Алгоритм RSA в режиме электронной цифровой подписи
4.4.1. Понятие об электронной цифровой подписи
4.4.2. Применение алгоритма RSA в режиме электронной цифровой подписи
Вопросы для самоконтроля
4.5. Решение задач
Литература к главе 4
Пример выполнения приближенного к типовому варианта контрольной работы с решением

Заключение