Гданский Н.И. Прикладная дискретная математика. Логика. Графы. Автоматы. Алгоритмы. Кодирование

М.: Вузовская книга, 2019. — 508 с.: ил. — ISBN 978-5-89522-400-7.Изложены основы дискретной математики в объеме, достаточном для понимания и использования ее методов при решении задач. При минимально возможном числе вводимых теоретических понятий акцент сделан на более глубоком их объяснении, выявлении связи с практикой, выработке у студентов навыков самостоятельного решения заданий методами дискретной математики. С этой целью в пособии приведены многочисленные примеры и задачи.Для студентов, аспирантов и преподавателей технических вузов.Введение
Основы теории множеств и комбинаторика
Множества, операции с ними
Алгебра множеств
Элементы и множества
Отображения, функции, предикаты
Метод математической индукции
Способы задания множеств
Предметные операции на множествах. Формула множества
Операции сравнения – логические операции на множествах
Алгебра множеств. Ее формулы, теоремы и законы
Мощность множеств
Мощность. Счетные множества
Множества мощности континуум
Бинарные отношения на множествах
Определение и способы задания отношений
Аксиомы на отношениях
Основные типы отношений
Проверка типов отношений. Решение задач
Системы счисления
Позиционные системы счисления с постоянными основаниями. Двоичная система. Двоичные векторы
Шестнадцатеричная система счисления. Арифметические действия в системах с постоянными основаниями
Позиционные смешанные системы счисления. Факториальная система
Комбинаторика
Размещения
Перестановки и размещения без повторений. Упорядоченность перестановок
Сочетания
Подсчет числа вариантов расположений объектов для специальных случаевМатематическая логика
Алгебра логики
Объекты изучения алгебры логики. Булевы константы, переменные и векторы
Булевы функции, способы их задания. Элементарные функции. Алгебра логики, ее формулы
Моделирование составных высказываний при помощи формул алгебры логики
Эквивалентность формул. Тавтологии. Законы логики. Двойственность
Специальные формульные представления булевых функций
Конъюнкции и дизъюнкции над множеством переменных. Нормальные формы
Конституенты единицы. Совершенные дизъюнктивные и веббовы нормальные формы
Конституенты нуля. Совершенные конъюнктивные и шефферовы нормальные формы
Полиномы Жегалкина
Минимизация нормальных форм булевых функций
Метод покрытий
Метод минимизирующих карт
Частично определенные функции. Их минимальное доопределение
Анализ и синтез релейных управляющих схем
Релейные схемы. Связь их физической структуры и функций проводимости с алгеброй логики
Проектирование релейных схем
Применение алгебры логики к анализу логических рассуждений
Замкнутость и полнота систем функций
Операции суперпозиции и замыкания. Полнота, базис системы функций
Функции, сохраняющие константы. Классы Т₀ и Т₁
Самодвойственность. Класс S
Монотонность. Класс M
Линейность. Класс L
Критерий Поста полноты системы функций в алгебре логики
Анализ и синтез функциональных схем
Аксиоматический подход к построению теорий
Алгебраические системы. Исчисление высказываний
Универсальные и предметные формальные теории. Общие принципы их построения.
Универсальные алгебраические системы.
Группы
Подгруппы. Порядок элементов конечных групп. Циклические группы
Кольца, поля
Решетки
Булевы алгебры
Аксиоматическое построение исчисления высказываний
Конечнозначные логики
Многозначные логики
Элементарные функции многозначных логик. Представление функций формулами специального вида
Законы k-значных логик
Функциональная полнота в Р_к
Счетнозначная логика
Континуум-значные логики. Теория вероятности. Логический подход
Алгебра событий. Вероятность
Основные свойства вероятности
Повышение надежности дискретных устройств путем применения дублирования
Теория нечетких множеств. Нечеткая логика
Нечеткие множества. Основные понятия
Предметные операции на нечетких множествах. Формулы нечетких множеств
Операции сравнения на нечетких множествах – включение и равенство
Алгебра нечетких множеств
Нечеткие высказывания, переменные и логические связки. Нечеткие логические формулы
Логико-лингвистическое описание функционирования нечетких систем. Нечеткие базы знаний
Нечеткий логический вывод
Максиминный метод композиции
Метод масштабирования выполнения композиции
Логика предикатов
Кванторы, предикаты, предметные функции
Терм, формула, свободные и связанные переменные. Логика предикатов
Интерпретация формул ЛП
Равносильность формул ЛП
Аксиоматическое построение ЛП. Исчисление предикатов
Теории первого порядка
Модальность. Модальная логика, Интерпретированная посредством кванторов
Проблема разрешимости. Теория автоматического вывода
Пренексная нормальная форма
Скулемовская форма
Эрбрановский универсум и базис. H-интерпретации
Семантические деревья. Теорема Эрбрана
Метод резолюций
Метод резолюций в исчислении высказываний
Операции подстановки, унификации и склейки
Правило и метод резолюций в теориях первого порядкаТеория графов
Основные понятия теории графов. Примеры ее применения
Псевдографы, графы, способы их задания
Деревья
Полное бинарное дерево
Проблема разрешимости. Теория автоматического вывода
Комбинаторика. Теория вероятности
Иерархические структуры и процессы
Остовные деревья
Полные графы
Двудольные графы
Задачи о расписаниях
Распределение ресурсов
Единичные n-мерные кубы
Комбинаторика и алгебра логики
Теория кодирования
Сети
Моделирование транспортных систем. Потоки в сетях
Сетевое планирование
Моделирование релейных и функциональных схем
Однополюсные сети – корневые деревья
Операции и отображения на графах
Изоморфизм и гомеоморфизм графов
Маршруты и обходы на графах
Оптимальные маршруты во взвешенных графах
Гамильтоновы цепи и циклы
Эйлеровы цепи и циклы
Раскраски графов
Планарность графовОсновы теории конечных автоматов
Основные понятия теории
Автоматы первого и второго рода. Автоматы Мили и Мура. Граф переходов. Однотактные и многотактные автоматы
Таблица состояний автомата
Реакция, эквивалентность и сокращение автоматов
Свойства классов k-эквивалентности. Построение сокращенных автоматов
Автоматы Мура
Анализ и синтез двоичных автоматов
Числовая форма задания автоматов. Двоичные автоматы
Канонические уравнения и схема автомата
Канонические уравнения
Схема автомата
Оптимальные автоматыТеория комбинаторных алгоритмов
Общая характеристика задач. Интуитивное определение алгоритма
Корректные и некорректные,разрешимые задачи
Интуитивное определение алгоритма. Основные требования к алгоритмам. Примеры
Блок-схема алгоритма
Формализация понятия алгоритма
Машина Тьюринга
Устройство, принцип работы, основные понятия
Примеры машин Тьюринга
Тезис Тьюринга. Существование неразрешимых корректных задач
Рекурсивные функции
Примитивно-рекурсивные функции
Частично-рекурсивные и общерекурсивные функции. Тезис Черча
Размер задачи. Сложность алгоритма
Размер задачи. Скорость роста
Сложность алгоритма. Классификация алгоритмов по сложности
Точные и приближенные комбинаторные алгоритмы. Оценки их сложности
Класс P. Полиномиальная сводимость
Класс АР. АР-полнота
Основные виды сложности комбинаторных алгоритмов
Приближенные алгоритмы решения комбинаторных задачКодирование и сжатие информации
Основные понятия теории кодирования и сжатия информации
Кодирование и сжатие информации
Информация и энтропия
Основные структурные свойства кодов и их численные характеристики
Основные характеристики методов сжатия информации
Неизбыточные коды. Методы сжатия без потерь
Равномерные коды для чисел
Простой двоичный код
Двоично-десятичные коды
Отраженные коды. Коды Грея
Равномерные коды для символьной информации
Телеграфный код Бодо
Представление символьной информации в памяти компьютера
Сжатие байтовой информации групповыми методами (RLE)
Сжатие байтовой информации по методу LZW
Энтропийные (статистические) методы
Код Морзе. Префиксные коды. Стоимость кода
Классический код Хаффмена
Блочное и словесное двоичное кодирование
Метод Хаффменас фиксированной кодовой таблицей
Урезанный код Хаффмена
Сдвиговые коды
Арифметическое кодирование
Избыточные коды
Обнаружение и исправление ошибок. Разделимые и неразделимые коды
Линейные коды. Систематический код
КодыХемминга
Циклические коды
Отображение двоичных кодовых слов на множество многочленов над полем GF(T). Расширенные поля GF(2^m)
Построение циклического кода
Коды Боуза – Чоудхури – Хоквингема (БХЧ)
Коды Рида – Соломона
Основные методы исправления ошибок
Метод с использованием кодов-спутников (декодирующих таблиц)
Метод синдромов
Обнаруживающие коды
Код с однократной проверкой четности
Коде простым повторением
Корреляционный код
Список литературы