- •Глава 16. Специальные циклы и метрика графов 345
- •Глава 17. Графовые инварианты 404
- •Введение
- •Цели и задачи преподавания дисциплины «дискретная математика»
- •Модуль 1. Основы Теории множеств (2 кредита)
- •Комплексная цель и задачи изучения модуля
- •Глава 1. Исчисление множеств
- •1.1. Понятие множества
- •1.2. Способы задания множеств
- •1.3. Подмножество
- •2. Пустое множество не имеет собственных и истинных подмножеств.
- •3. Одноэлементное множество имеет два подмножества - сaмo себя и , т.Е. Не имеет собственных подмножеств.
- •Множество – это многое, мыслимое как единое.
- •Глава 2. Операции над множествами
- •2.1. Объединение множеств
- •2.2. Пересечение множеств
- •2.3. Разность множеств
- •2.4. Дополнение множества
- •2.5. Тождества алгебры множеств
- •2.6. Доказательства тождеств с множествами
- •Глава 3. Упорядоченные множества
- •3.1. Кортеж (Упорядоченное множество)
- •3.2. Декартово произведение
- •3.3. Операция проектирования множеств
- •3.4. График
- •Декартово произведение множеств позволяет перейти к графическому представлению упорядоченных множеств.
- •Глава 4. Отношения
- •4.1. Основные понятия отношений
- •4.2. Основные свойства отношений
- •4.3. Операции над отношениями
- •4.4. Основные свойства специальных отношений
- •4.5. Разбиение множеств
- •4.6. Отношение порядка
- •Использование отношений позволяет строить модели взаимосвязей между любыми обьектами в природе.
- •5. Соответствия
- •5.1. Определение соответствия
- •5.2. Операции над соответствиями
- •5.3. Понятия образа и прообраза при соответствии
- •5.4. Доказательства тождеств с соответствиями
- •5.5. Основные свойства соответствий
- •5.6. Функция
- •Глава 6. Упорядоченные бесконечные множества
- •6.1. Основные сведения об упорядоченных бесконечных множествах
- •6.2. Проблема континуума
- •Глава 7. Основные понятия теории мультимножеств
- •7.1. Понятие мультимножества
- •7.2. Операции над мультимножествами
- •Возможность многократного вхождения элементов в мультимножество создает новое качество и позволяет расширить класс описываемых, анализируемых и синтезируемых математических объектов.
- •8. Нечеткие множества
- •8.1. Нечеткие высказывания
- •8.2. Операции над нечеткими множествами
- •8.3. Нечеткие отношения и соответствия
- •Тестовые задания к модулю 1
- •24. Множество называется графиком, если каждый его элемент ...
- •25. Соответствие может быть задано … способом.
- •Критерии оценки
- •Нечеткие и приближенные высказывания, множества, соответствия и отношения позволяют формально задавать расплывчатую информацию в виде, удобном для обработки на эвм.
- •Глоссарий к модулю 1
- •Глава 1.
- •Глава 2.
- •Глава 3.
- •Глава 4.
- •Глава 5.
- •Глава 6.
- •Глава 7.
- •Глава 8.
- •Галилей Модуль 2. Основы теории алгоритмов (1,5 кредита) Комплексная цель и задачи изучения модуля
- •Глава 9. Введение в теорию алгоритмов
- •9.1. Понятие алгоритма
- •9.2. Основные свойства алгоритмов
- •9.3. Классификация алгоритмов
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •10.1. Преобразование слов в произвольных абстрактных алфавитах
- •10.2. Числовые функции
- •10.3. Построение алгоритмов по принципу «разделяй и властвуй»
- •10.4. Представление алгоритма в виде детерминированного устройства
- •10.5. Универсальные схемы алгоритмов
- •10.5. “Жадные” алгоритмы
- •10.6. Нечеткие (расплывчатые) алгоритмы
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •11.1. Анализ алгоритмов
- •11.2. Сложность алгоритмов
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •Тестовые задания к модулю 2
- •Критерии оценки
- •Модуль 3. Алгебра логики (1,5 кредита) Комплексная цель и задачи изучения модуля
- •Глава 12. Элементы алгебры логики
- •12.1. Логические функции
- •12.2. Основные логические тождества и законы
- •12.3. Булевы функции одной и двух переменных
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •13.1. Дизъюнктивная и конъюнктивная нормальные формы
- •13.2. Способы перехода от нормальных к совершенным нормальным формам
- •2. Графический способ.
- •13.4. Функциональная полнота бф
- •13.3. Алгебра Жегалкина
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •14.1. Реализация булевых функций
- •14.2. Минимизация булевых функций
- •14.3. Карты Карно
- •14.4. Метод Квайна - Мак-Класски
- •14.5. Переход от бф к простейшим комбинационным схемам
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •Критерии оценки
- •Глоссарий к модулю 3
- •Модуль 4. Основы Теории графОв (2 кредита) Комплексная цель и задачи изучения модуля
- •Глава 15. Введение в теорию графов
- •15.1. Способы задания графов и виды графов
- •15.1.1. Способы задания графов
- •15.1.2. Виды графов
- •15.1.3. Нечеткие неориентированные графы
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •15.2. Маршруты, цепи, циклы
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •При моделировании систем модели и алгоритмы нахождения маршрутов, цепей, циклов, разрезов, связности графов позволяют строить эффективные алгоритмы преобразования графов.
- •15.3. Нахождение кратчайших маршрутов (цепей)
- •15.3.1. Алгоритм Форда
- •15.3.2. Алгоритм Дейкстры
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •Алгоритмы Форда и Дейкстры являются эффективным способом определения кратчайшей по стоимости цепи между двумя вершинами графа.
- •Глава 16. Специальные циклы и метрика графов
- •16.1. Эйлеровы и гамильтоновы цепи и циклы
- •16.1.1. Связь между эйлеровыми и гамильтоновыми графами
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •16.2. Алгоритмы построения гамильтонова цикла
- •16.2.1. Алгоритм Робертса ─ Флореса
- •16.2.2. Алгебраический метод
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •16.3. Задача о коммивояжере и алгоритмы ее решения
- •16.3.1. Алгоритм Хелда и Карпа
- •16.3.2. Геометрический метод решения
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •16.4. Расстояния на графах
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •16.5. Деревья
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •Глава 17. Графовые инварианты
- •17.1. Цикломатическое и хроматическое числа графа
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •17.2. Числа внутренней и внешней устойчивости графа
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •Числа внутренней и внешней устойчивости относятся к инвариантам графа. Они позволяют определить специальные группы вершин в графах.
- •17.3. Планарность графов
- •17.3.1. Плоские и планарные графы
- •17.3.2. Эвристики для определения планарности
- •17.3.3. Минимизация пересечений ребер графов
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •17.4. Ориентированные графы
- •17.4.1. Способы задания
- •17.4.2. Решение стандартных графовых задач с использованием орграфов
- •17.4.3. Выделение сильносвязных компонент
- •17.4.4. Нечеткие ориентированные графы
- •Примеры решения задач
- •Вопросы
- •Задания для самостоятельной работы
- •175 Гиперграфы
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •Тестовые задания к модулю 4
- •Критерии оценки
- •Глоссарий к модулю 4 Глоссарий к главе 1
- •Глоссарий к главе 2
- •Глоссарий к главе 3
- •Библиографический комментарий
- •Литература
- •Заключение
- •Приложение 1
- •Учебное издание Гладков Леонид Анатольевич, Курейчик Владимир Викторович, Курейчик Виктор Михайлович
Глава 8.
Множество называется нечетким или расплывчатым множеством в непустом множестве Х = {x1, x2, ..., xn} и обозначается = {<А(x), x>}, xX.
Функция принадлежности - есть кортеж длины два, первая компонента которого обозначается А(х) и задается на сегменте [0, 1]. Вторая компонента кортежа — элемент множества Х.
Нечеткое высказывание - предложение, относительно которого можно судить о степени его истинности или ложности.
Индифферентное нечеткое высказывание равно 0.5, оно истинно в той же степени, что и ложно.
Отрицанием нечеткого высказывания называется высказывание не , степень истинности которого определяется по формуле = 1 — .
Конъюнкцией нечетких высказываний , называется высказывание, степень истинности которого определяется по формуле: = min ( ).
Дизъюнкцией нечетких высказываний называется нечеткое высказывание, степень истинности которого определяется по формуле: = max ( ).
Импликацией нечетких высказываний называется высказывание степень истинности не меньше, чем степень неистинности ее посылки или степень истинности ее следствия: = max (1 — , ).
Эквивалентностью нечетких высказываний называется новое составное нечеткое высказывание обозначаемое: = min(max(1 - , ), max(1 - , )).
Степень включения нечеткого множества в нечеткое множество обозначается ( , ) и определяется по формуле ( , ) = (А(х) В(х)).
Объединением нечетких множеств называется выражение = { < АB(х), x >, xX }, АB = А B.
Пересечение нечетких множеств называется выражение = { < АB(х), x >, xX }, АB = А B.
Разностью нечетких множеств называется выражение \ = { < А\B(х), x >, xX }, А\B = А B.
Симметрической разностью нечетких множеств и называется выражение = { < АB(х), x >, xX }, АB = А\В B\А.
Нечетким графиком называется множество, состоящее из нечетких упорядоченных пар (кортежей).
Нечетким соответствием называют тройку множеств Г = < X, Y, F >, причем X и Y — это конечные четкие множества, а F — нечеткий график соответствия.
Инверсией нечеткого соответствия Г = < X, Y, F > называется соответствие Г-1 = < Y, X, F-1 >, но Х в инвертируемом соответствии будет областью прибытия, а Y — областью отправления.
Композицией двух нечетких соответствий Г1 = < X, Y, F1 > и Г2 = < Y, Z, F2 > называется выражение Г1•Г2 = < Х, Z, F3 >.
Нечетким отношением на произвольном множестве Х называется выражение = < X, Ф >, причем ФХхХ, ФХ2, где Х — область задания отношения, а Ф — нечеткий график отношения.
Приближенным множеством называется множество пар {Q1, Q2,…, Ql}. Упорядоченную пару Q = <, X> называют пространством приближений. При этом на обучающем множестве X введено отношение эквивалентности = <Ф, X>, Ф X X. Здесь Ф – график отношения, X – область задания отношения.
Исследуя природу, естествоиспытатель должен следовать какой-то математической модели.
