Учебное пособие по курсу «Математические и алгоритмические основы построения интеллектуальных систем». В 3 ч. Ч. 1 (213,00 руб.)

Стр.3

Стр.4

Стр.5

УДК 004 (075.8) ББК 73я73 М20 Печатается по решению кафедры вычислительной техники Института компьютерных технологий и информационной безопасности Южного федерального университета (протокол № 7 от 8 апреля 2022 г.) Рецензенты: доктор технических наук, профессор кафедры прикладной математики и искусственного интеллекта ФГБОУ ВО «Национальный исследовательский университет «МЭИ», г. Москва А. П. Еремеев доктор технических наук, заведующий лабораторией информационных технологий и процессов управления ФГБУН «ФИЦ Южный научный центр РАН», г. Ростов-на-Дону Э. В. Мельник Мунтян, Е. Р. М20 Учебное пособие по курсу «Математические и алгоритмические основы построения интеллектуальных систем» : учебное пособие : в 3 ч. / Е. Р. Мунтян, Н. Е. Сергеев ; Южный федеральный университет. – Ростовна-Дону ; Таганрог : Издательство Южного федерального университета, 2022. ISBN 978-5-9275-4182-9 Часть 1. – 142 с. ISBN 978-5-9275-4183-6 (Ч. 1) Учебное пособие по курсу «Математические и алгоритмические основы построения интеллектуальных систем» (часть 1) совмещает в себе конспект лекций и практикум в части модуля «Использование графовых и гиперграфовых моделей в интеллектуальных системах» и отражает состояние современных аспектов теории графов и гиперграфов с элементами научной новизны, а также возможности их применения для решения реальных практических задач. Пособие содержит теоретический, практический и методический материал по темам: «Основные понятия теории графов», «Виды графов», «Алгоритмы на графах», «Использование графов в интеллектуальных системах», «Гиперграфы» и «Специальные графы в интеллектуальных системах». Каждая тема завершается заданиями для самостоятельной работы студентов и списком вопросов для самоконтроля. Пособие предназначено для магистрантов всех форм обучения по направлению 09.04.01 – Информатика и вычислительная техника для образовательной программы «Технологии интеллектуальных автоматизированных систем». УДК 004 (075.8) ББК 73я73 ISBN 978-5-9275-4183-6 (Ч. 1) ISBN 978-5-9275-4182-9 © Южный федеральный университет, 2022 © Мунтян Е. Р., Сергеев Н. Е., 2022 © Оформление. Макет. Издательство Южного федерального университета, 2022

Стр.3

СОДЕРЖАНИЕ ВВЕДЕНИЕ ........................................................................................................ 5 1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ .............................................. 8 1.1. Понятие графа. Типы графов ................................................................. 8 1. Неориентированные графы ............................................................ 8 1. Ориентированные графы .............................................................. 13 1. Смешанные графы ........................................................................ 15 1.1.4. Графы с разнотипными связями .................................................. 16 1.1. 1.2. 1.3. 1.2. Способы представления графов .......................................................... 19 1.3. Типы графов. Части и подграфы ......................................................... 29 1.4. Операции над графами ......................................................................... 34 1.5. Нечеткие графы .................................................................................... 36 Рекомендации для проведения практического занятия № 1 ................. 42 Задания для самостоятельной работы .................................................... 45 Задания для контрольной работы №7 .................................................... 46 Вопросы для самоконтроля .................................................................... 47 2. ВИДЫ ГРАФОВ ........................................................................................... 48 2.1. Двудольные графы ............................................................................... 48 2.2. Регулярные графы ................................................................................ 50 2.3. Планарные и плоские графы ................................................................ 52 2.4. Деревья, эйлеров граф, гамильтонов граф .......................................... 55 Рекомендации для проведения практического занятия № 2 ................. 58 Задания для самостоятельной работы .................................................... 61 Задания для контрольной работы №8 .................................................... 61 Вопросы для самоконтроля .................................................................... 61 3. АЛГОРИТМЫ НА ГРАФАХ ....................................................................... 63 3.1. Нахождение кратчайшего пути в графе .............................................. 63 3.2. Вычисление метрик графа ................................................................... 65 3.3. Раскраска графов .................................................................................. 68 3.4. Обход графов ........................................................................................ 71 3.5. Генерация графов ................................................................................. 72 Рекомендации для проведения практического занятия № 3 ................. 74 Задания для самостоятельной работы .................................................... 76 Задания для контрольной работы № 9 ................................................... 76 Вопросы для самоконтроля .................................................................... 76 3

Стр.4

Содержание 4. ИСПОЛЬЗОВАНИЕ ГРАФОВЫХ МОДЕЛЕЙ В ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМАХ .................................................. 78 4.1. Семантические сети .............................................................................. 78 4.2. Представление фреймовых моделей .................................................... 82 4.3. Представление баз продукционных знаний ........................................ 85 4.4. Трехуровневая модель представления знаний на основе нечеткого графа ..................................................................................... 87 Рекомендации для проведения практического занятия № 4 ................. 95 Задания для самостоятельной работы .................................................... 95 Задания для контрольной работы № 10 .................................................. 96 Вопросы для самоконтроля ..................................................................... 96 5. ГИПЕРГРАФЫ ............................................................................................. 98 5.1. Определения и типы гиперграфов ....................................................... 98 5. Неориентированные гиперграфы ................................................. 98 5. Ориентированные гиперграфы ..................................................... 99 5. Смешанные гиперграфы ............................................................. 100 5. Нечеткие гиперграфы ................................................................. 102 1.1. 1.2. 1.3. 1.4. 5.2. Представление гиперграфов ............................................................... 103 Рекомендации для проведения практического занятия № 5 ............... 107 Задания для самостоятельной работы .................................................. 108 Задания для контрольной работы №11 ................................................. 108 Вопросы для самоконтроля ................................................................... 109 6. СПЕЦИАЛЬНЫЕ ГРАФЫ В ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМАХ ... 110 6.1. Разработка модели взаимодействия элементов СТС на основе нечетких графов с множественными разнотипными связями .......... 110 6.2. Анализ структурных задержек в распределенных ВС на основе нечетких графов с множественными разнотипными связями .......... 113 6.3. Формирование онтологии сложной предметной области на основе нечеткого графа с множественными разнотипными связями .......... 119 Вопросы для самоконтроля ................................................................... 126 ЗАКЛЮЧЕНИЕ ............................................................................................... 127 ПРИНЯТЫЕ СОКРАЩЕНИЯ И ОБОЗНАЧЕНИЯ ...................................... 130 СЛОВАРЬ МАТЕМАТИЧЕСКИХ ТЕРМИНОВ .......................................... 131 ГЛОССАРИЙ ТЕРМИНОВ И ОПРЕДЕЛЕНИЙ .......................................... 133 СПИСОК ЛИТЕРАТУРЫ .............................................................................. 137 4

Стр.5