Рекомендуем

Ключевые слова:
Дискретная математика
Дискретная математика для инженеровПономарев В.Ф. Дискретная математика для инженеров
Дискретная математикаДанилов В.Г., Дубнов В.Л., Лакерник А.Р., Райцин А.М. Дискретная математика

Книга

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

Учебное пособие для вузов
2017 г.
114 стр.
Тираж 500 экз.
Формат 60х90/16 (145x215 мм)
Исполнение: в мягкой обложке
ISBN 978-5-9912-0659-4
ББК 22.176я73
УДК 519.854(073)
Гриф УМО
Рекомендовано федеральным государственным автономным учреждением «Федеральный институт развития образования» (ФГАУ «ФИРО») в качестве учебного пособия для использования в учебном процессе образовательных организаций, реализующих программы высшего образования по направлениям подготовки 10.03.01 – «Информационная безопасность», 09.03.03 – «Прикладная информатика», 38.03.05 – «Бизнес-информатика» (уровень бакалавриата)
Аннотация

В краткой форме доступно изложены основы дискретной математики. Рассмотрены основы теории множеств, уделено внимание комбинаторному и теоретико-множественному подходам. Рассмотрены элементы математической логики. Изложены основные методы и подходы теории графов. Рассмотрены специальные маршруты в графах и поиск путей. Раскрыты основные вопросы теории кодирования. Наряду с основополагающими понятиями – кодами Грея и Хемминга уделено внимание применению алгоритма RSA в режимах шифрования и электронной цифровой подписи. Пособие подготовлено в соответствии с разработанными автором рабочими программами Финансового университета (ФГОБУ ВО «Финансовый университет при Правительстве РФ»).

Для студентов, обучающихся по направлениям подготовки бакалавров 10.03.01 – «Информационная безопасность», 09.03.03 – «Прикладная информатика», 38.03.05 – «Бизнес-информатика».

Шептунов Максим Валерьевич – канд. техн. наук, доцент; научно-педагогический стаж свыше 18 лет, в том числе свыше 3 лет в Финансовом университете; в настоящее время доцент РГГУ и МГЛУ (бывш. им. Мориса Тореза)

Оглавление

Введение

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
Пример выполнения приближенного к типовому варианта контрольной работы с решением

Заключение