Капитонова Ю.В. и др. Лекции по дискретной математике

Учебное пособие. — СПб.: БХВ-Петербург, 2004. — 624 с.: ил.Изложены методы и средства дискретной математики как инструментария при обработке информации в компьютерах. Книга состоит из трех частей: математические основы, математические модели и приложения, в которых представлены наиболее часто употребляемые в теоретической и прикладной информатике математические конструкции. Освещаются основные математические свойства той или иной теории вместе с данными, необходимыми для решения упражнений. Материал пособия построен на использовании аксиоматического метода и может служить основой для таких курсов как базы данных и базы знаний, теории сетей Петри и транзиционных систем, методы оптимизации и обоснования алгоритмов и программ, системы искусственного интеллекта, компьютерная алгебра и геометрия.
Для студентов и аспирантов высших учебных заведений.ПредисловиеМатематические основыМножества, отношения, комбинаторика
Множества, отношения, функции, операции
Интуитивное понятие множества. Основные принципы
Операции над множествами. Законы для операций
Декартово произведение множеств. Отношения
Примеры отношений
Примеры отображений
Аксиоматика Цермелло-Френкеля
Контрольные вопросы
Задачи и упражнения
Элементы комбинаторного анализа
Основное правило комбинаторики
Число различных ^элементных подмножеств я-элементного множества
Число подмножеств данного множества
Перестановки и размещения упорядоченных множеств
Перестановки с повторениями
Размещение элементов множества
Комбинации элементов с повторениями
Бином Ньютона
Свойства биномиальных коэффициентов
Метод рекуррентных соотношений
Метод включений и исключений
Метод производящих функций
Контрольные вопросы
Задачи и упражненияОсновные понятия общей алгебры
Универсальные алгебры
Общие сведения
Отношение конгруэнтности
Гомоморфизмы универсальных алгебр
Язык (алгебра) термов
Производные операции и конечные алгебры
Свободные аглебры и их основные свойства
Абсолютно свободные алгебры
Свободный группоид
Свободная полугруппа
Свободная коммутативная полугруппа
Свободные группы
Свободные абелевы группы
Свободное кольцо
Векторные пространства 00
Булевы алгебры
Структуры
Многоосновные алгебры. Алгебра алгоритмов Глушкова
Полные структуры и полукольца
Полные структуры
Замкнутые полукольца
Контрольные вопросы
Задачи и упражненияЭлементы теории алгоритмов и математической логики
Понятие алгоритма и алгоритмической системы
Интуитивное понятие алгоритма:
Вычислимые и частично рекурсивные функции. Тезис Черча
Алгоритмические проблемы
Машины Поста и машины Тьюринга
Алгоритмическая система Маркова
Контрольные вопросы
Задачи и упражнения
Исчисление высказываний
Алфавит и формулы
Интерпретация формул логики и высказываний
Полные системы связок
Система аксиом для исчисления высказываний
Теорема дедукции
Непротиворечивость и полнота исчисления высказываний
Исчисление высказываний и булевы алгебры
Методы проверки тождественной истинности формул исчисления высказываний
Алгебраический метод
Метод Куайна
Метод редукции
Метод Девиса-Патнема
Метод резолюций
Контрольные вопросы
Задачи и упражнения
Исчисление предикатов первого порядка
Алфавит и формулы
Истинность интерпретации, модели
Аксиоматика и правила вывода
Основные свойства теории первого порядка
Нормальные формы формул логики предикатов первого порядка
Скулемовские стандартные формы
Классификация логик
Понятие о неклассических логиках
Понятие алгебраической системы
Контрольные вопросы
Задачи и упражненияЭлементы теории графов
Определение графов, разновидности графов
Определение неориентированного графа
Разновидности графов
Изоморфизм графов. Подграфы
Контрольные вопросы
Задачи и упражнения
Операции над графами
Операция удаления ребра
Операция удаления вершины
Операция введения ребра
Операция введения вершины в ребро
Операция объединения графов
Произведение графов
Отождествление (слияние) вершин
Операция стягивания ребра
Операция раздвоения (расщепления) вершины
Операция соединения графов
Операция дополнения графа
Свойства графов
Маршруты, циклы, связность
Свойства регулярных графов
Свойства двудольных графов
Свойства связных графов
Метрические характеристики связных графов
Свойства эйлеровых графов
Свойства гамильтоновых графов
Матрицы и фафы
Матрицы смежностей и достижимости:
Матрица Кирхгофа
Матрица инцидентности графа
Планарность и укладка графов
Плоские и планарные графы
Грани плоского графа. Формула Эйлера
Раскраска графов. Хроматическое число
Правильная раскраска
Практические задачи, сводящиеся к задаче раскраски
Хроматические числа некоторых графов
Гипотеза четырех красок
Гипотеза четырех красок для карт
Бесконечные фафы
Конфольные вопросы
Задачи и упражнения
Деревья
Определение дерева. Свойства деревьев
Фундаментальная система циклов фафа
Остов наименьшего веса
Ориентированные фафы и деревья
Основные понятия
Бинарные отношения и орфафы
Размеченные фафы и представление термов 00
Конфольные вопросы
Задачи и упражненияМатематические моделиАбстрактная теория автоматов
Основные определения
Определение автомата и его разновидности
Таблицы переходов и выходов
Граф переходов и выходов
Подавтоматы. Гомоморфизмы автоматов
Теорема о приведенном автомате
Представление событий в автоматах. Автоматы Мура
и недетерминированные автоматы
Автоматные отображения
Автоматные системы событий
Автоматы Мура
Недетерминированные автоматы
Задачи и упражненияТеория конечных автоматов
События, алгебра регулярных событий. Основная теорема теории конечных автоматов
Регулярные события
Теорема анализа конечных автоматов
Теорема синтеза конечных автоматов
Задачи и упражнения
Практические методы анализа и синтеза конечных автоматов
Уравнения в алгебре событий
Системы линейных уравнений
Применение уравнений в алгебре событий к задачам анализа и синтеза конечных автоматов
Основной алгоритм синтеза конечных автоматов
Контрольные вопросы
Задачи и упражнения
Минимизация конечных автоматов без выходов
Общий алгоритм минимизации
Алгоритм минимизации конечных автоматов без выходов
Алгоритм минимизации ациклических автоматов
Алгоритмы построения конгруэнтных замыканий для конечных автоматов
Определение отношения конгруэнтного замыкания
Общий алгоритм вычисления конгруэнтного
и симметричного конгруэнтного замыканий
Алгоритм вычисления конгруэнтных замыканий для ациклических автоматов
Контрольные вопросы
Задачи и упражненияМодели алгоритмов и программ
Машины Тьюринга
Определение и функционирование
Словарное представление машины Тьюринга
Алгоритмически разрешимые и неразрешимые проблемы
Контрольные вопросы
Задачи и упражнения
Конечные автоматы с одной лентой
Определение автомата с одной лентой
Проблема пустоты 00
Проблема бесконечности 00
Магазинные автоматы
Определение магазинного автомата
Представление языков в магазинных автоматах
Анализ магазинных автоматов
Синтез магазинных автоматов
Контрольные вопросы
Задачи и упражнения
Дискретные динамические системы
Контрольные вопросы
Задачи и упражнения
U—Y-схемы программ над памятью
Контрольные вопросы
Задачи и упражненияФормальные грамматики и формальные языки
Регулярные грамматики и их свойства
Определение формальной грамматики
Классификация грамматик
Правоволинейные и леволинейные грамматики (регулярные грамматики) и конечные автоматы
Задачи и упражнения
Контекстно-свободные грамматики и их свойства
Контекстно-свободные грамматики и уравнения
Уравнения, КС-языки и магазинные автоматы
Задачи и упражненияПриложенияАлгебры в компьютерных информационных технологиях
Преобразования в векторных пространствах
Перемещения плоскости
Группы преобразований плоскости
Перемещения пространства
Группы преобразований пространства
Масштаб
Проекции
Реляционная алгебра и понятие реляционной базы данных
Определение реляционной алгебры
Контрольные вопросы
Задачи и упражнения
Алгебраическая система списковых структур
Списки. Операции над списками
Реализация списков в памяти ЭВМ
Сложность выполнения операций над списками
Разновидности списков
Задание графов с помощью списков
Задание множеств и термов с помощью списков
Контрольные вопросы
Задачи и упражненияТеория автоматов и графов в компьютерных информационных технологиях
Универсальный программный автомат
Применение в системах подготовки и редакции текстов
Идентификация слов при построении текстовых редакторов
Понятие гипертекста
Контрольные вопросы
Задачи и упражнения
Компьютерная алгебра
Задача упрощения алгебраических выражений
Важные упрощения
Полные системы редукций, критические пары, алгоритм пополнения
Алгоритм Кнута-Бендикса критической пары
Алгоритм пополнения Кнута-Бендикса
Проблема общих подвыражений и канонизации для свободных групп
Задачи и упражнения
Теорема Холла и ее применение
Трансверсали
Латинские квадраты
Теорема Менгера и потоки в сетях
Задачи и упражненияМетоды поиска доказательств теорем в логике предикатов
Метод Эрбрана
Основные определения
Семантические деревья
Теорема Эрбрана
Метод резолюций
Контрарные пары и подстановки
Алгоритм унификации
Метод резолюций для логики предикатов первого порядка
Примеры применения метода резолюций
Правило поглощения
Контрольные вопросы
Задачи и упражненияОсновные понятия теории программных инвариантов
Инварианты в состояниях U-Y-программ и языки инвариантов
Определение программного инварианта
Методы поиска программных инвариантов
Язык равенств. Основные задачи
Основные задачи теории программных инвариантов
Алгоритмы поиска программных инвариантов
Поиск инвариантов в программах над свободными алгебрами данных
Векторные пространства
Решение основных задач
Свободные абелевы группы и коммутативные полугруппы
Примеры
Задачи и упражненияСписок литературы