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

Учебное пособие - М.: ФИЗМАТЛИТ, 2005 г. - 416 с. В пособии включены задачи и упражнения по конечнозначным логикам (втч и по алгебре логики), по теории алгоритмов, теории графов и сетей, теории кодирования, комбинаторике, минимизации булевых функций и синтезу схем и формул, реализующих булевы функции. Имеются задачи, предназначенные для первоначальной проработки и освоения методов дискретной математики, а также задачи для углубленного изучения предмета. - Для студентов и преподавателей университетов и технических вузов, в которых изучается дискретная математика.

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

Ответы, указания, решения. - 324 с., Список литературы - 412 с., Предметный указатель- 414 с.