В книге представлены основные разделы дискретной математики: теория множеств, алгоритмов, графов, алгебра логики. Для лучшего усвоения материала использована современная методика обучения на основе решебников. Авторы рассмотрели вопросы исчисления множеств, задания отношений и соответствий, описания упорядоченных бесконечных множеств, мультимножеств и нечетких множеств, основные алгоритмические модели, логические функции и законы алгебры логики, виды и способы задания графов, алгоритмы решения задач на ориентированных и неориентированных графах, а также основные определения из теории гиперграфов и нечетких графов. Даются контрольные задачи, упражнения и глоссарий с пояснением терминов. Учебник предназначен студентам вузов, обучающимся по направлениям «Информатика и вычислительная техника» и «Информационные системы», может быть полезен также специалистам, занятым разработкой интеллектуальных САПР, систем поддержки и принятия решений, новых информационных технологий в науке, технике, образовании, бизнесе и экономике.
Введение Цели и задачи преподавания дисциплины «Дискретная математика»
Основы теории множеств
Исчисление множеств Понятие множества Способы задания множеств Подмножество Примеры решения задач Контрольные вопросы Задания для самостоятельной работы
Операции над множествами Объединение множеств Пересечение множеств Разность множеств Дополнение множества Тождества алгебры множеств Доказательства тождеств с множествами Примеры решения задач Контрольные вопросы Задания для самостоятельной работы
Упорядоченные множества Кортеж (упорядоченное множество) Декартово произведение Операция проектирования множеств График Примеры решения задач Контрольные вопросы Задания для самостоятельной работы
Отношения Основные понятия отношений Основные свойства отношений Операции над отношениями Основные свойства специальных отношений Разбиение множеств Отношение порядка Контрольные вопросы Задания для самостоятельной работы
Соответствия Определение соответствия Операции над соответствиями Понятия образа и прообраза при соответствии Доказательства тождеств с соответствиями Основные свойства соответствий Функция Контрольные вопросы Задания для самостоятельной работы
Упорядоченные бесконечные множества Основные сведения об упорядоченных бесконечных множествах Проблема континуума Примеры решения задач Контрольные вопросы Задания для самостоятельной работы
Основные понятия теории мультимножеств Понятие мультимножества Операции над мультимножествами Примеры решения задач Контрольные вопросы Задания для самостоятельной работы
Нечёткие множества Нечеткие высказывания Операции над нечеткими множествами Нечеткие отношения и соответствия Примеры решения задач Контрольные вопросы Задания для самостоятельной работы Тестовые задания к модулю Глоссарий к модулю
Основы теории алгоритмов
Введение в теорию алгоритмов Понятие алгоритма Основные свойства алгоритмов Классификация алгоритмов Примеры решения задач Контрольные вопросы Задания для самостоятельной работы
Универсальные алгоритмические модели Преобразование слов в произвольных абстрактных алфавитах Числовые функции Построение алгоритмов по принципу «разделяй и властвуй Представление алгоритма в виде детерминированного устройства Универсальные схемы алгоритмов Примеры решения задач «Жадные» алгоритмы Нечеткие (расплывчатые) алгоритмы Контрольные вопросы Задания для самостоятельной работы
Сложность алгоритмов Анализ алгоритмов Сложность алгоритмов Контрольные вопросы Задания для самостоятельной работы Тестовые задания к модулю Глоссарий к модулю
Алгебра логики
Элементы алгебры логики Логические функции Примеры решения задач Основные логические тождества и законы Примеры решения задач Булевы функции одной и двух переменных Контрольные вопросы Задания для самостоятельной работы
Нормальные формы булевых функций Дизъюнктивная и конъюнктивная нормальные формы Примеры решения задач Способы перехода от нормальных к совершенным нормальным формам Примеры решения задач Алгебра Жегалкина Функциональная полнота булевых функций Контрольные вопросы Задания для самостоятельной работы
Логические схемы Реализация булевых функций Минимизация булевых функций Примеры решения задач Карты Карно Примеры решения задач Метод Куайна–Мак-Класки Примеры решения задач
Переход от булевых функций к простейшим комбинационным схемам Примеры решения задач Контрольные вопросы Задания для самостоятельной работы Тестовые задания к модулю Глоссарий к модулю
Основы теории графов
Введение в теорию графов Способы задания графов и виды графов Способы задания графов Виды графов Нечёткие неориентированные графы Примеры решения задач Вопросы для самоконтроля Задания для самостоятельной работы Маршруты, цепи, циклы Примеры решения задач Вопросы для самоконтроля Задания для самостоятельной работы Нахождение кратчайших маршрутов (цепей) Алгоритм Форда Алгоритм Дейкстры Примеры решения задач Вопросы для самоконтроля Задания для самостоятельной работы
Специальные циклы и метрика графов Эйлеровы и гамильтоновы цепи и циклы Связь между эйлеровыми и гамильтоновыми графами Примеры решения задач Вопросы для самоконтроля Задания для самостоятельной работы Алгоритмы построения гамильтонова цикла Алгоритм Робертса–Флореса Алгебраический метод Примеры решения задач Вопросы для самоконтроля Задания для самостоятельной работы Задача о коммивояжере и алгоритмы ее решения Алгоритм Хелда и Карпа Геометрический метод решения Примеры решения задач Вопросы для самоконтроля Задания для самостоятельной работы Расстояния на графах Примеры решения задач Вопросы для самоконтроля Задания для самостоятельной работы Деревья Примеры решения задач Вопросы для самоконтроля Задания для самостоятельной работы
Графовые инварианты Цикломатическое и хроматическое числа графа Примеры решения задач Вопросы для самоконтроля Задания для самостоятельной работы Числа внутренней и внешней устойчивости графа Примеры решения задач Вопросы для самоконтроля Задания для самостоятельной работы Планарность графов Плоские и планарные графы Эвристики для определения планарности Минимизация пересечений ребер графов Вопросы для самоконтроля Задания для самостоятельной работы Ориентированные графы Способы задания Решение стандартных графовых задач с использованием орграфов Выделение сильносвязных компонент Нечёткие ориентированные графы Примеры решения задач Вопросы для самоконтроля Задания для самостоятельной работы Гиперграфы Примеры решения задач Вопросы для самоконтроля Задания для самостоятельной работы Задача определения паросочетаний в графе Вопросы для самоконтроля Задания для самостоятельной работы Изоморфизм графов Вопросы для самоконтроля Задания для самостоятельной работы Тестовые задания к модулю 4 Глоссарий к модулю 4 Заключение Библиографический комментарий Список литературы
Приложение. Основные положения ГОСТ 70-90 (ИСО 5807-85) «Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения
Внимание
Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.
