Часть I. Язык Prolog 25
Оглавление
Предисловие 18
Часть I. Язык Prolog 25
Глава 1. Введение в Prolog 26
Глава 2. Синтаксис и значение программ Prolog 45
Глава 3. Списки, операции, арифметические выражения 76
Глава 4. Использование структур: примеры программ 98
Глава 5. Управление перебором с возвратами 121
Глава 6. Ввод и вывод 136
Глава 7. Дополнительные встроенные предикаты 149
Глава 8, Стиль и методы программирования 169
Глава 9. Операции со структурами данных 192
Глава 10. Усовершенствованные методы представления деревьев 215
Часть II. Применение языка Prolog Б области искусственного интеллекта 227
Глава 11. Основные стратегии решения проблем 228
Глава 12. Эвристический поиск по заданному критерию 247
Глава 13. Декомпозиция задач и графы AND/OR 277
Глава 14. Логическое программирование в ограничениях 301
Глава 15. Представление знаний и экспертные системы 326
Глава 16. Командный интерпретатор экспертной системы 357
Глава 17. Планирование 383
Глава 18. Машинное обучение 408
Глава 19. Индуктивное логическое программирование 446
Глава 20. Качественные рассуждения 478
Глава 21. Обработка лингвистической информации с помощью
грамматических правил 510
Глава 22. Ведение игры 532
Глава 23. Метапрограммирование 559
Приложение А. Некоторые различия между реализациями Prolog 590
Приложение Б. Некоторые часто используемые предикаты 592
Решения к отдельным упражнениям 595
Список литературы 611
Предметный указатель 619
Содержание
Предисловие 18
Часть I. Язык Prolog 25
Глава 1. Введение в Prolog 26
1.1. Определение отношений на основе фактов 26
1.2. Определение отношений на основе правил 30
1.3. Рекурсивные правила 35
1.4. Общие принципы поиска ответов на вопросы системой Prolog 39
1.5. Декларативное и процедурное значение программ 42 Резюме 43 Дополнительные источники информации 44
Глава 2. Синтаксис и значение программ Prolog 45
2.1. Объекты данных 45
2.1.1. Атомы и числа 46
2.1.2. Переменные 47
2.1.3. Структуры 48
2.2. Согласование 52
2.3. Декларативное значение программ Prolog 56
2.4. Процедурное значение 58
2.5. Пример: обезьяна и банан 62
2.6. Порядок предложений и целей 66
2.6.1. Опасность возникновения бесконечных циклов 66
2.6.2. Модификация программы путем переупорядочения предложений
и целей 68
2.6.3. Объединение декларативного и процедурного представлений 72
2.7. Взаимосвязь между языком Prolog и логикой 73
Резюме 74
Глава 3. Списки, операции, арифметические выражения 76
3.1. Представление списков 76
3.2. Некоторые операции со списками 78
3.2.1. Проверка принадлежности к списку 79
3.2.2. Конкатенация 79
3.2.3. Добавление элемента 82
3.2.4. Удаление элемента 82
3.2.5. Подсписок 83
3.2.6. Перестановки 84
3.3. Запись в операторной форме 87
3.4. Арифметические выражения 92 Резюме 96
Глава 4. Использование структур: примеры программ 98
4.1. Выборка структурированной информации из базы данных 98
4.2. Методы абстрагирования данных 102
4.3. Моделирование недетерминированного конечного автомата 103
4.4. Консультант бюро путешествий 107
4.5. Задача с восемью ферзями 111 4.5.1. Программа 1 111
4.5.2. Программа 2 114
4.5.3. Программа 3 116
4.5.4. Заключительные замечания 119 Резюме 120
Глава 5. Управление перебором с возвратами 121
5.1. Предотвращение перебора с возвратами 121
5.1.1. Эксперимент 1 122
5.1.2. Эксперимент 2 123
5.2. Примеры использования оператора отсечения 125
5.2.1. Вычисление максимума 125
5.2.2. Проверка принадлежности к списку, при которой возможно
только одно решение 126
5.2.3. Добавление элемента к списку без дублирования 126
5.2.4. Классификация с разбивкой по категориям 127
5.3. Отрицание как недостижение цели 129
5.4. Проблемы, связанные с использованием отрицания и оператора
отсечения 132
Резюме 135
Дополнительные источники информации 135
Глава 6. Ввод и вывод 136
6.1. Обмен данными с файлами 136
6.2. Обработка файлов, состоящих из термов 139
6.2.1. Предикаты read и write 139
6.2.2. Вывод списков на внешнее устройство 141
6.2.3. Обработка файла, состоящего из термов 142
6.3. Манипулирование символами 143
6.4. Формирование и анализ атомов 144
6.5. Чтение программ 146 Резюме 147 Дополнительные сведения, касающиеся стандарта Prolog 148
Глава 7. Дополнительные встроенные предикаты 149
7.1. Проверка типа термов 149
7.1.1. Предикаты var, noiwarp atom, integer, float, number, atomic, compound 149
7.1.2. Решение числового ребуса с использованием предиката nonvar 151
7.2. Создание и декомпозиция термов; предикаты =.., functor, arg и name 156
7.3. Операторы сравнения и проверки на равенство различных типов 159
7.4. Операции с базой данных 161
7.5. Средства управления 164
7.6. Предикаты bagof, setof и findall 165 Резюме 167
Глава 8. Стиль и методы программирования 169
8.1. Общие принципы качественного программирования 169
8.2. Общий подход к разработке программ Prolog 171
8.2.1. Использование рекурсии 171
8.2.2. Обобщение 172
8.2.3. Использование графических схем 173
8.3. Стиль программирования 173
8.3.1. Некоторые правила хорошего стиля 174
8.3.2. Табличная организация длинных процедур 175
8.3.3. Комментирование 175
8.4. Отладка 176
8.5. Повышение эффективности 177 8.5.1. Повышение эффективности программы решения задачи с восемью
ферзями 178
Содержание
8.5.2. Повышение эффективности программы раскраски карты 179
8.5.3. Повышение эффективности конкатенации списков
с использованием разностных списков 181
8.5.4. Оптимизация последнего вызова и накапливающие параметры 182
8.5.5. Моделирование массивов с помощью предиката arg 184
8.5.6. Повышение эффективности путем внесения в базу данных производных фактов 186
Резюме 190
Дополнительные источники информации 191
Глава 9. Операции со структурами данных 192
9.1. Сортировка списков 192
9.2. Представление множеств с помощью бинарных деревьев 197
9.3. Вставка и удаление в бинарном словаре 201
9.4. Отображение деревьев 206
9.5. Графы 208
9.5.1. Представление графов 208
9.5.2. Поиск пути 209
9.5.3. Поиск остовного дерева графа 211 Резюме 214 Дополнительные источники информации 214
Глава 10. Усовершенствованные методы представления деревьев 215
10.1. Двоично-троичный словарь 215
Вариант А 218
Вариант Б 218
Вариант В 218
10.2. AVL-дерево - приближенно сбалансированное дерево 221
Резюме 225
Дополнительные источники информации 225
Часть II. Применение языка Prolog в области искусственного интеллекта 227
Глава 11. Основные стратегии решения проблем 228
11.1. Вводные понятия и примеры 228
11.2. Поиск в глубину и итеративное углубление 232
11.3. Поиск в ширину 238
11.4. Анализ основных методов поиска 242 Резюме 245 Дополнительные источники информации 246
Глава 12. Эвристический поиск по заданному критерию 247
12.1. Поиск по заданному критерию 247
12.2. Применение поиска по заданному критерию для решения
головоломки "игра в восемь" 256
12.3. Применение поиска по заданному критерию при планировании 261
12.4. Методы экономии пространства для поиска по заданному критерию 265
12.4.1. Потребность алгоритма А* в ресурсах времени и пространства 265
12.4.2. Метод IDA* 266
12.4.3. Метод RBFS 269
Резюме 275
Дополнительные источники информации 275
Глава 13. Декомпозиция задач и графы AND/OR 277
13.1. Представление задач в виде графов AND/OR 277
13.2. Примеры представлений в виде графа AND/OR 281
13.2.1. Представление в виде графа AND/OR задачи поиска маршрута 281
13.2.2. Задача с ханойской башней 282
13.2.3. Формулировка процесса игры в виде графа AND/OR 283
13.3. Основные процедуры поиска в графе AND/OR 284
Содержание
13.4. Поиск в графе AND/OR по заданному критерию 289
13.4.1. Эвристические оценки и алгоритм поиска 289
13.4.2. Программа поиска 292
13.4.3. Пример отношений с определением задачи - поиск маршрута 298 Резюме 300 Дополнительные источники информации 300
Глава 14. Логическое программирование в ограничениях 301
14.1. Удовлетворение ограничений и логическое программирование 301
14.1.1. Удовлетворение ограничений 301
14.1.2. Решение задачи удовлетворения ограничений 303
14.1.3. Расширение Prolog для использования в качестве языка логического программирования в ограничениях 305
14.2. Применение метода CLP для обработки действительных чисел —
CLP{R) 306
14.3. Планирование с помощью метода CLP 310
14.4. Программа моделирования в ограничениях 317
14.5. Применение метода CLP для поддержки конечных областей определения - CLP(FD) 321
Резюме 324
Источники дополнительной информации 325
Глава 15. Представление знаний и экспертные системы 326
15.1. Назначение и структура экспертной системы 326
15.2. Представление знаний с помощью правил вывода 328
15.3. Прямой и обратный логический вывод в системах, основанных на правилах 331
15.3.1. Обратный логический вывод 331
15.3.2. Прямой логический вывод 333
15.3.3. Сравнение прямого и обратного логического вывода 334
15.4. Формирование объяснений 336
15.5. Учет неопределенности 337
15.5.1. Простая схема учета неопределенности 337
15.5.2. Сложности, связанные с учетом неопределенности 339
15.6. Байесовские сети доверия 340
15.6.1. Вероятности, достоверности и байесовские сети доверия 340
15.6.2. Некоторые формулы из области исчисления вероятностей 344
15.6.3. Формирование рассуждений в байесовских сетях 345
15.7. Семантические сети и фреймы 348
15.7.1. Семантические сети 349
15.7.2. Фреймы 350 Резюме 355 Дополнительные источники информации 356
Глава 16. Командный интерпретатор экспертной системы 357
16.1. Формат представления знаний 357
16.2. Проектирование механизма логического вывода 361
16.2.1. Требования к организации работы программы 361
16.2.2. Организация процесса формирования рассуждений 363
16.2.3. Формирование ответов на вопросы, требующие обоснования необходимости получения запрашиваемой информации 364
16.2.4. Формирование ответов на вопросы, касающиеся описания последовательности рассуждений 365
16.3. Реализация 366
16.3.1. Процедура explore 366
16.3.2. Процедура useranswer 369
16.3.3. Усовершенствование процедуры useranswer 371
16.3.4. Процедура present 376
Содержание
16.3.5. Управляющая процедура верхнего уровня 377
16.3.6. Пояснения к программе командного интерпретатора 378
16.3.7. Отрицаемые цели 378 16.4. Заключительные замечания 380
Резюме 382
Дополнительные источники информации 382
Глава 17. Планирование 383
17.1. Представление действий 383
17.2. Разработка планов с помощью анализа целей и средств 387
17.3. Защита целей 390
17.4. Процедурные аспекты и режим поиска в ширину 393
17.5. Регрессия целей 395
17.6. Сочетание планирования по принципу анализа целей и средств с эвристическим поиском по заданному критерию 398
17.7. Неконкретизированные действия и планирование с частичным упорядочением 401
17.7.1. Неконкретизированные действия и цели 402
17.7.2. Планирование с частичным упорядочением 404
Резюме 406
Дополнительные источники информации 407
Глава 18. Машинное обучение 408
18.1. Введение 408
18.2. Проблема изучения понятий на примерах 409
18.2.1. Понятия, представленные в виде множеств 409
18.2.2. Примеры и гипотезы 410
18.2.3. Языки описания объектов и понятий 412
18.2.4. Точность гипотез 413
18.3. Подробный пример формирования реляционных описаний в
результате обучения 414
18.4. Обучение с помощью простых правил вывода 419
18.4.1, Описание объектов и понятий с использованием атрибутов 419
18.4.2. Логический вывод правил на основании примеров 422
18.5. Логический вывод деревьев решения 426
18.5.1. Основной алгоритм логического выаода дерева 426
18.5.2. Выбор "наилучшего" атрибута 428
18.5.3. Реализация процедуры обучения с помощью дерева решения 430
18.6. Обучение по зашумленным данным и отсечение частей деревьев 433
18.7. Успех обучения 439
18.7.1. Критерии успеха обучения 440
18.7.2. Оценка точности гипотез, полученных путем обучения 440
18.7.3. Влияние отсечения частей на точность и наглядность деревьев решения 441
Резюме 442
Дополнительные источники информации 443
Глава 19. Индуктивное логическое программирование 446
19.1. Введение 446
19.2. Формирование программ Prolog на примерах 449
19.2.1. Постановка задачи обучения 449
19.2.2. Граф усовершенствования 450
19.2.3. Программа MIMIHYPER 452
19.2.4. Обобщение, уточнение и тэта-классификация 458
19.3. Программа HYPER 459
19.3.1. Оператор усовершенствования 460
19.3.2. Поиск 463
19.3.3. Программа HYPER 463
Содержание
19.3.4. Эксперименты с программой HYPER 470
Одновременное изучение предикатов odd(L) и even(L) 470
Изучение предиката path( StartNode, GoalNode, Path) 471
Изучение предиката, предназначенного для сортировки по методу
вставки 472
Изучение предиката, позволяющего распознать конструкцию арки 474
Резюме 476
Дополнительные источники информации 477
Глава 20. Качественные рассуждения 478
20.1. Здравый смысл, качественные рассуждения и обыденные физические
представления 478
20.1.1. Различие между количественными и качественными
рассуждениями 478
20.1.2. Качественное абстрагирование количественной информации 479
Абстрагирование числовых данных путем их замены
символическими значениями и интервалами 480
Абстрагирование производных по времени путем их замены
обозначениями направлений изменения 480
Абстрагирование функций путем замены монотонными отношениями 480
Абстрагирование возрастающих временных последовательностей 480
20.1.3. Назначение и область применения качественного моделирования
и качественных рассуждений 481
20.2. Качественные рассуждения о статических системах 482
Вопросы прогностического типа 486
Вопросы диагностического типа 486
Вопросы управленческого типа 486
20.3. Качественные рассуждения о динамических системах 486
20.4. Программа качественного машинного моделирования 493
20.4.1. Способы представления качественных состояний 496
20.4.2. Ограничения 497
20.4.3. Переходы между качественными состояниями 498
20.5. Описание программы качественного машинного моделирования 502
Резюме 507
Дополнительные источники информации 508
Глава 21. Обработка лингвистической информации с помощью
грамматических правил 510
21.1. Применение грамматических правил в программе на языке Prolog 510
21.2. Обработка смысла 516
21.2.1. Формирование деревьев синтаксического анализа 516
21.2.2. Применение деревьев синтаксического анализа для извлечения смысла 518
21.2.3. Совместное применение синтаксических и семантических конструкций в системе обозначений DCG 520
21.3. Определение смысла фраз на естественном языке 521
21.3.1. Представление смысла простых фраз с помощью логических высказываний 521
21.3.2. Смысл определяющих слов "а" и "every" 525
21.3.3. Обработка относительных предложений 527
Резюме 531
Дополнительные источники информации 531
Глава 22. Ведение игры 532
22.1. Игры с полной информацией, с двумя участниками 532
22.2. Принцип минимакса 534
22.3. Альфа-бета-алгоритм: эффективная реализация принципа минимакса 537
Содержание
22.4. Программы, основанные на принципе минимакса: усовершенствования и ограничения 541
22.5. Типовые знания и механизм советов 543
22.5.1. Цели и ограничения ходов 543
22.5.2. Выполнимость совета 544
22.5.3. Объединение элементарных советов в правила и таблицы советов 544
22.6. Программа ведения шахматного эндшпиля на языке Advice
Language 0 546
22.6.1. Миниатюрный интерпретатор ALO 546
22.6.2. Программа ведения эндшпиля "король и ладья против короля"
на основе таблицы советов 549
Резюме 556
Дополнительные источники информации 557
Глава 23. Метапрограммирование 559
23.1. Метапр о граммы и метаинтерпретаторы 559
23.2. Метаинтерпретаторы Prolog 560
23.2.1. Простейший метаинтерпретатор Prolog 560
23.2.2. Трассировка с помощью метаинтерпретатора 562
23.2.3. Формирование деревьев доказательства 563
23.3. Обобщение на основе объяснения 564
Дано 565
Найти 565
23.4. Объектно-ориентированное программирование 570
23.5. Программирование, управляемое шаблонами 576
23.5.1. Архитектура, управляемая шаблонами 576
23.5.2. Программы Prolog, реализованные в виде систем, управляемых шаблонами 578
23.5.3. Пример разработки программ, управляемых шаблонами 579 Модуль 1 579 Модуль 2 579
23.5.4. Простой интерпретатор для программ, управляемых шаблонами 580
23.5.5. Возможные усовершенствования 582
Проект 583
23.6. Простая программа автоматического доказательства теорем,
реализованная в виде программы, управляемой шаблонами 583
Резюме 588
Дополнительные источники информации 589
Приложение А. Некоторые различия между реализациями Prolog 590
Динамические и статические предикаты 590
Предикаты assert и retract 590
Неопределенные предикаты 590
Отрицание как недостижение успеха — операторы not и "\+ " 591
Предикат name( Atom, CodeList) 591
Загрузка программ с помощью предикатов consult и reconsult 591
Модули 591
Приложение Б. Некоторые часто используемые предикаты 592
Решения к отдельным упражнениям 595
Глава 1 595
Глава 2 595
Глава 3 596
Глава 4 599
Глава 5 600
Глава 6 601
Глава 7 601
Глава 8 602
Содержание
| Глава 9 | |
| Глава 10 | |
| Глава 11 | |
| Глава 12 | |
| Глава 13 | |
| Глава 14 | |
| Глава 15 | |
| Глава 17 | |
| Глава 18 | |
| Глава 19 | |
| Глава 20 | |
| Глава 21 | |
| Глава 23 | |
| Список литературы | |
| Предметный указатель |
Содержание
Посвящаю третье издание этой книги моей матери, самому доброму человеку из всех, кого я знаю, и моему отцу, который во время Второй Мировой войны сумел убежать из концентрационного лагеря, прорыв подземный туннель, о чем он написал в своемромане "Телескоп".