- •Глава 1. Основные определения, история проблемы,
- •Глава 2 Онтологическая инженерия описания предметной области ……50
- •Глава 3. Представление и вывод знаний в системах искусственного интеллекта на основе логических моделей. 65
- •Глава 4 Представление и вывод знаний в системах искусственного интеллекта на основе семантических сетей 98
- •Контрольные вопросы и задание 110
- •Глава 5. Представление и вывод знаний в системах искусственного интеллекта на основе фреймовых моделей. 111
- •Глава 6. Представление и вывод знаний в системах искусственного интеллекта на основе продукционных моделей. 118
- •Глава 7. Представление и вывод неопределённых знаний в системах искусственного интеллекта. 132
- •Глава 1. Основные определения, история проблемы, современные направления развития.
- •Основные определения искусственного интеллекта.
- •Лекция 1
- •1.2. Тест Тьюринга
- •Науки, лежащие в основе искусственного интеллекта
- •Вычислительная техника (период с 1940 года по настоящее время)
- •История искусственного интеллекта.
- •Рождение искусственного интеллекта (1956 год)
- •Ранний энтузиазм, большие ожидания (период с 1952 года по 1969 год)
- •Столкновение с реальностью (период с 1966 года по 1973 год)
- •Лекция 2
- •Основные современные направления развития искусственного интеллекта
- •1.6. Основные понятия о знаниях.
- •1.7. Выводы по 1-ой главе:
- •Контрольные вопросы и задание
- •Лекция 3
- •Глава 2 Онтологическая инженерия описания предметной области.
- •2.1. Понятие онтологии.
- •2.2. Теория множеств - математический аппарат описания онтологии.
- •2.2.1. Основные понятия и определения.
- •Лекция 4
- •2.2.2.Операции над множествами
- •2.2.3. Декартово произведение множеств
- •2.2.4. Отношения и их свойства.
- •2.3. Предметы, свойства и отношения предметной области.
- •Лекция 5
- •2.4. Понятие цели
- •2.5. Методика решения задач.
- •2.6. Понятие модели.
- •2.7. Методика построения онтологии.
- •2.8. Выводы по 2-ой главе.
- •2.9. Контрольные вопросы и задание.
- •Лекция 6
- •Глава3 Представление и вывод знаний в системах искусственного интеллекта на основе логических моделей.
- •3.1. Основы математической логики
- •3.1.1. Классификация и определение логик, алгебр, исчислений, теорий.
- •3.1.2.Традиционная логика.
- •Лекция 7
- •3.1.3.Логика, алгебра и исчисление высказываний.
- •3.1.4. Логика, алгебра и исчисление предикатов
- •Лекция 8
- •3.1.5. Формальные методы вывода решений в аксиоматических теориях.
- •3.1.6. Приведение формул исчисления предикатов к дизъюнктам Хорна.
- •4. Исключение кванторов существования.
- •3.2. Логическая модель представления знаний.
- •3.3. Вывод в системах искусственного интеллекта с логическим представлением знаний.
- •3.3.1. Правило резолюции.
- •Стратегия полного перебора.
- •Стратегия опорного множества.
- •3. Линейная по входу стратегия.
- •3.4. Выводы по 3-ой главе.
- •Контрольные вопросы и задание.
- •Лекция 9
- •Глава 4 Представление и вывод знаний в системах искусственного
- •Элементы теории графов
- •4.1.1. Способы задания графов.
- •1. Графический
- •2. С помощью матрицы инцидентности.
- •3. С помощью списка ребер.
- •4. С помощью матрицы смежности.
- •4.1.2. Задачи, решаемые с помощью графов.
- •Задача поиска наикратчайшего пути на графе.
- •Транспортная задача.
- •Задача о назначении (задача коммивояжера).
- •Задача о назначении работ.
- •Лекция 10
- •4.2. Представления знаний в виде семантических сетей.
- •4.3. Вывод в системах искусственного интеллекта с представлением знаний в виде семантических сетей.
- •Выводы по 4-ой главе.
- •Контрольные вопросы и задание.
- •Лекция 11
- •Глава 5. Представление и вывод знаний в системах искусственного интеллекта на основе фреймовых моделей.
- •5.1. Представления знаний в виде фреймов
- •5.2. Вывод в системах искусственного интеллекта с фреймовым
- •Выводы по 5-ой главе.
- •5.4. Контрольные вопросы и задание.
- •Лекция 12
- •Глава 6. Представление и вывод знаний в системах искусственного интеллекта на основе продукционных моделей.
- •Представление знаний в виде в виде системы продукций.
- •6.2. Продукционные системы
- •6.3. Прямой и обратный вывод в продукционных системах.
- •Лекция 13
- •6.4. Пример работы продукционной системы.
- •6.5. Выводы по 6-ой главе
- •6.6. Контрольные вопросы и задание
- •Лекция 14
- •Глава 7. Представление и вывод неопределённых знаний в системах искусственного интеллекта
- •Представление и вывод при нечётких знаниях.
- •7.1.1. Определение нечёткого множества.
- •7.1.3. Нечёткие отношения.
- •7.1.2. Операции над нечёткими множествами.
- •Лекция 15
- •Формальные методы вывода решений в нечёткой логике.
- •Лекция 16
- •7.2.Представление и вывод при неполных знаниях.
- •Вероятностный подход к представлению неопределённых знаний.
- •Определения и виды вероятности
- •Аксиомы вероятностей
- •Лекция 17
- •7.2.4. Формальные методы вывода решений при вероятностном подходе.
- •7.2.5. Правило Байеса и его использование.
- •Байесовская сеть представления и вывода вероятностных знаний.
- •Другие способы представления и вывода неопределённых знаний.
- •Выводы по 7-ой главе
- •7.5. Контрольные вопросы и задание.
- •Литература
Элементы теории графов
Граф – совокупность двух множеств V – точек и Е – линий между элементами которых определено отношение инцидентности (связности). Причем каждый элемент е, принадлежащий Е инцидентен ровно двум элементам V` и V``, принадлежащих V.
Элементы множества V называются вершинами графа G; Элементы множества Е называются ребрами графа G.
В некоторых случаях каждому ребру приписывают направление от одной из инцидентных вершин ко второй.
Направленные ребра называют дугами, а содержащий граф - ориентированным.
4.1.1. Способы задания графов.
1. Графический
а) Рис.16. Ориентированный граф
б) Рис.17. Пустой граф
в) Кратные ребра – различные ребра, инцидентны одной и той же паре вершин. Мультиграф – граф, содержащий кратные ребра.
Рис.18. Мультиграф
г) Петля – ребро, соединяющее вершину саму с собой.
Рис.19. Петля
д) Фрагмент бесконечного графа.
Рис.20. Фрагмент бесконечного графа
2. С помощью матрицы инцидентности.
Рис.21. Неориентированный граф Рис.22. Ориентированный граф
Для неориентированного графа.
Пусть V1, V2,…Vn – вершины графа G. Отношение инцидентности задается матрицей / ξij /, имеющая m – строк и n – столбцов.
Столбцы соответствуют вершинам графа, а строки – ребрам.
Если ребро еi инцидентно вершине Vj, то ξij = 1.
В противном случае ξij = 0.
Для ориентированного графа.
Если вершина Vj – начало ребра еi, то ξij = -1. Если вершина Vj – конец ребра еi, то ξij = 1.
Если - еi петля, а Vj - инцидентная вершина, то ξij = α, где α – любое число отличное от 0, 1 и -1.
Во всех остальных случаях ξij = 0.
Для неориентированного графа: Для ориентированного графа:
Таблица 15 Матрица инцидентности Таблица16 Матрица инцидентности
неориентированного графа ориентированного графа
3. С помощью списка ребер.
Каждая строка списка соответствует ребру, в ней записаны номера вершин, инцидентных этому ребру. Для неориентированного графа порядок вершин произволен; Для ориентированного графа – первым стоит номер начала ребра, а вторым – номер его конца.
Для неориентированного графа: Для ориентированного графа:
Таблица 17 Список рёбер Таблица 18 Список рёбер
для неориентированного графа для ориентированного графа
4. С помощью матрицы смежности.
Матрица смежности – квадратная матрица ||δij|| строкам и столбцам которой соответствуют вершины графа.
Для неориентированного графа δij равна количеству ребер, инцидентных i и j вершине.
Для ориентированного графа δij равна количеству ребер с началом в i – вершине и концом в j – вершине.
Для неориентированного графа: Для ориентированного графа:
Таблица 19 Матрица смежности Таблица 20 Матрица смежности
для неориентированного графа для ориентированного графа
Матрица для неориентированного графа симметрична относительно главной диагонали.
Пусть G – неориентированный граф. Маршрутом G называется такая конечная или бесконечная последовательность ребер (е1, е2,…,еn), что каждые два соседних ребра
еi-1, еi имеют общую инцидентную вершину.
Пусть маршрут М, состоящий из (е1, е2,…,еn) ребер, имеет начало V0 и конец Vn.
Если V0 =Vn (начало совпадает с вершиной), то такой маршрут называется циклическим.
Маршрут М называется цепью, если каждое ребро встречается в нем не более 1 раза.
Циклический маршрут называется циклом, если он является цепью.
ПРИМЕР:
Рис.23. Неориентированный граф
Маршрут: М = {VI, IV, III, II, VI, I}
Циклический маршрут: M = {I, VI, IV, III, II, VI, I}
Цепь: M = {IV, III, II, VI, I}
Цикл: M = {IV, III, II}
Вершины V` и V``, принадлежащие графу G, называются связанными, если существует маршрут М с началом V` и концом V``.
Граф G называется связанным, если все его вершины связаны между собой.
Рис.24. Связанный граф
Несвязанный граф:
Рис.25. Несвязанный граф
Неориентированным деревом называется связанный неориентированный граф без циклов.
Рис.26. Дерево
Несвязанный, неориентированный граф без циклов называется лесом.
Рис.27. Лес
