Часть 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
Список литературы
Предметный указатель

Содержание



Посвящаю третье издание этой книги моей матери, самому доброму человеку из всех, кого я знаю, и моему отцу, который во время Второй Мировой войны сумел убежать из концентрационного лагеря, прорыв подземный туннель, о чем он написал в своемромане "Телескоп".

Наши рекомендации