Дискретная математика

Description

Минск: БГУИР, 2015 - 195 с. Вводятся основные понятия теории множеств и отношений, излагаются основы теорииграфов, абстрактной булевой алгебры с различными интерпретациями. Рассматриваютсязадачи комбинаторной оптимизации, возникающие при логическом проектировании.Рассматриваются различные методы минимизации булевых функций и систем в классе ДНФ.Описываются формальные методы проектирования комбинационных логических схем наоснове теории булевых функций. Излагаются методы логического проектирования,использующие модель конечного автомата в его синхронной и асинхронной реализации.Предназначается для студентов и аспирантов, специализирующихся в областипроектирования дискретных устройств. Автор – доцент кафедры ЭВМ Белорусского госуниверситета информатики ирадиоэлектроники Поттосин Ю.В.Содержание:Основные понятия теории множеств Отношения бинарные и п-арныеОсновные понятия теории графов Изоморфизм графов Циклы и разрезы Доминирующие и независимые множества Раскраска графа Обходы графаПланарные графыКомбинаторные задачи и методы комбинаторного поиска Задача о кратчайшем покрытииБулевы функцииНормальные формыГрафическое представление булева пространства и булевых функций Полные системы булевых функций. Реализация функций комбинационными схемами Троичные векторы и матрицы Локальные упрощения ДНФ Минимизация ДНФ Минимизация не полностью определенных булевых функцийМинимизация системы булевых функций Декомпозиция булевых функций Конечный автомат. ТипыМинимизация полных автоматов Минимизация частичных автоматов Кодирование состояний синхронного автомата Кодирование состояний асинхронного автомата