Гаврилов Г.П. Сапоженко А.А. Задачи и упражнения по дискретной математике

Учебное пособие — М.: Физматлит, 2005. — 416 с. — ISBN 5-9221-0477-2.В пособии включены задачи и упражнения по конечнозначным логикам (в т.ч. и по алгебре логики), по теории алгоритмов, теории графов и сетей, теории кодирования, комбинаторике, минимизации булевых функций и синтезу схем и формул, реализующих булевы функции. Имеются задачи, предназначенные для первоначальной проработки и освоения методов дискретной математики, а также задачи для углубленного изучения предмета. Для студентов и преподавателей университетов и технических вузов, в которых изучается дискретная математика.Способы задания и простейшие свойства функций алгебры логики.
Функции алгебры логики и способы их задания. Операция суперпозиции.
Специальные представления булевых функций (в т.ч. Разложения булевых функций по переменным. СДНФ и СКНФ. Полиномы Жегалкина).Замкнутые классы и полнота систем функций алгебры логики.
Понятие функциональной замкнутости и полноты.
Класс самодвойственных функций.
Класс линейных функций.
Классы функций, сохраняющих константы.
Класс монотонных функций.
Полнота и замкнутые классы.k-значные логики.
Представление функций k-значных логик формулами.
Замкнутые классы и полнота в k-значных логиках.Ограниченно-детерминированные функции.
Отображения последовательностей.
Диаграммы, таблицы, канонические уравнения, схемы.
Диаграммы Мура, канонические таблицы и уравнения.
Операции над детерминированными функциями.
Реализация ограниченно- детерминированных функций схемами.
Замкнутые классы и полнота во множествах детерминированных и ограниченно-детерминированных функций.Элементы теории алгоритмов.
Машины Тьюринга и операции над ними. Функции, вычислимые на машинах Тьюринга.
Классы вычислимых и рекурсивных функций.Графы и сети.
Основные понятия теории графов.
Планарность и раскраска графов.
Деревья и сети.Элементы теории кодирования.
Алфавитное кодирование.
Коды с минимальной избыточностью.
Самокорректирующиеся коды.
Линейные коды.Элементы комбинаторики.
Перестановки и сочетания. Св-ва биномиальных коэффициентов.
Формулы включений и исключений.
Возвратные последовательности.
Теория Пойа.
Асимптотические оценки и неравенства.
Оценки в теории графов и сетей.Минимизация булевых функций.
Структура граней n-мерного куба.
Методы построения сокращенной ДНФ.
Методы построения тупиковых, минимальных и кратчайших ДНФ.Реализация булевых функций схемами и формулами.
Схемы из функциональных элементов.
Контактные схемы и формулы.Ответы, указания, решения.
Список литературы.
Предметный указатель.—414 с.