Учебник содержит лекционный материал по дисциплине "Дискретная математика", а также примеры задач с решениями и задачи для самостоятельной работы. Основные разделы учебника: множества, математическая индукция, комбинаторика, булевы функции, логика высказываний и предикатов, графы, автоматы и формальные языки, алгоритмы.
Учебник адресован, прежде всего, студентам младших курсов, обучающихся по направлениям укрупненных групп 01.03.00 "Математика и механика", 02.03.00 "Компьютерные и информационные науки", 09.03.00 "Информатика и вычислительная техника".
Author(s): Дехтярь М.И., Дудаков С.М., Карлов Б.Н.
Edition: 3
Publisher: Тверской государственный университет
Year: 2021
Language: Russian
Pages: 528
City: Тверь
Предисловие
К третьему изданию
Ко второму изданию
К первому изданию
Множества и отношения
Множества
Операции над множествами
Как доказывать равенство множеств
Отношения и функции
Мощность множеств
Слова и языки
Индукция и комбинаторика
Метод математической индукции
Размещения, перестановки, сочетания
Принцип включения и исключения
Булевы функции и их представления
Булевы функции и их представления
Булевы функции от одной и двух переменных
Формулы
Булевы функции и логика высказываний
Эквивалентность формул и нормальные формы
Основные эквивалентности
Эквивалентные преобразования формул
Дизъюнктивные и конъюнктивные нормальные формы
Сокращённые ДНФ
Многочлены Жегалкина
Полные множества функций и теорема Поста
Замкнутые множества функций
Критерий полноты (теорема Поста)
Хорновские формулы и задача получения продукции
Хорновские формулы
Задача получения продукции
Решение задачи о продукции
Язык логики предикатов
Утверждения об отношениях между объектами
Синтаксис логики предикатов
Интерпретации и значение формул
Замена предметных переменных
Эквивалентные преобразования и предварённые формулы
Логика предикатов и базы данных
Реляционные базы данных
Реляционная алгебра
SQL-запросы
Ограничения целостности
Ориентированные графы
Основные определения
Представления графов
Граф достижимости
Сильная связность и базы
Неориентированные графы
Основные определения
Плоские графы
Эйлеровы графы
Раскраска графов
Деревья
Неориентированные и ориентированные деревья
Деревья и формулы (выражения)
Обходы деревьев
Три алгоритма на графах
Минимальное остовное дерево
Поиск в глубину и задача о лабиринте
Задача о кратчайших путях из одного источника
Схемы из функциональных элементов
Схемы и булевы функции
Схемы и линейные программы
Построение сумматора
Упорядоченные бинарные диаграммы решений
Основные определения
Сокращённые УБДР
Построение сокращённых УБДР по формулам
Конечные автоматы
Конечные преобразователи
Детерминированные конечные автоматы
Недетерминированные конечные автоматы
Детерминизация конечных автоматов
Регулярные выражения
Регулярные выражения и языки
Автоматность регулярных языков
Регулярность автоматных языков
Кодирования. Неавтоматные языки
Кодирование языков
Проблема однозначности декодирования
Оптимальное кодирование Хаффмана
Лемма о разрастании для автоматных языков
Неавтоматные языки
Алгоритмы и программы
Что такое алгоритм?
Программы с метками
Ограниченные программы
Частично рекурсивные функции
Построение частично рекурсивных функций
Вычислимость частично рекурсивных функций
Частичная рекурсивность вычислимых функций
Машины Тьюринга
Основные определения
Примеры машин Тьюринга
Стандартная заключительная конфигурация
Односторонние машины Тьюринга
Вычислимость: программная и по Тьюрингу
Универсальная машина Тьюринга
Вычислимость и неразрешимые проблемы
Тезис Тьюринга-Чёрча
Алгоритмически неразрешимые проблемы
Невычислимые функции
Ответы и решения
Указатель обозначений
Указатель терминов
Список литературы
