По существующей традиции предисловие редактора перевода - это своего рода рецензия, в которой обычно излагается история вопроса, а затем даётся обзор содержания книги и оценка. ее качества (как правило, рекламного характера). В данном случае моя задача несколько упрощается, так как все это читатель, перевернув страницу, найдет в предисловии известного американского ученого, специалиста по искусственному интеллекту П. Уинстона,' а .затем - в предисловии автора. Мне остается только присоединиться к авторитетному мнению П. Уинстона, что перед нами прекрасно написанный учебник по Прологу, ориентированный на практическое использование в области искусственного интеллекта. Добавлю также, что для советского читателя потребность в такой книге особенно велика, поскольку в нашей стране Пролог пока еще не получил того распространения, которого он заслуживает.
Несколько замечаний относительно особенностей перевода. Кроме обычных терминологических трудностей, как правило возникающих при переводе книг по программированию, переводчикам пришлось преодолевать одну дополнительную сложность. Дело в том, что в Прологе идентификаторы (имена переменных, процедур и атомов) несут на себе значительно большую смысловую нагрузку, чем в традиционных языках программирования. Поэтому программные примеры пришлось излагать на некоей условной русской версии Пролога - в противном случае, для читателей, не владеющих английским языком, эти примеры стали бы значительно менее понятными. Мы оставили без перевода все имена встроенных операторов и процедур, все же остальные имена переводились на русский язык. Следует признать, что в ряде случаев русская
версия этих имея оказалась менее эстетически привлекательной, чем исходный английский вариант. Пытаясь наиболее точно передать смысл того или иного имени, переводчик нередко оказывался перед нелегким выбором между громоздким идентификатором (иногда из нескольких слов) и неблагозвучной аббревиатурой. Впрочем, все эти проблемы хорошо известны любому «русскоязычному» программисту.
Главы 1-8 перевел А. И- Лупенко, а предисловия и главы 9-16 - А.М. Степанов. Подготовку оригинала-макета книги на ЭВМ выполнили А.Н. Черных и Н.Г. Черных.
Эту книгу можно рекомендовать как тем читателям, которые впервые приступают к изучению Пролога и искусственного интеллекта, так и программистам, уже имеющим опыт составления пролог-программ.
A.M. Степанов
ПРЕДИСЛОВИЕ
В средние века знание латинского к греческого языков являлось существенной частью образования любого ученого. Ученый, владеющий только одним языком, неизбежно чувствовал себя неполноценным, поскольку он был лишен той полноты восприятия, которая возникает благодаря возможности посмотреть на мир сразу с двух точек зрения-. Таким же неполноценным ощущает себя сегодняшний исследователь в области искусственного интеллекта, если он не обладает основательным знакомством как с Лиспом, так и с Прологом - с этими двумя основополагающими языками искусственного интеллекта, без знания которых невозможен более широкий взгляд на предмет исследования.
Сам я приверженец Лиспа, так как воспитывался в Массачусетском технологическом институте, где этот язык был изобретен. Тем не менее, я никогда не забуду того волнения, которое я испытал, увидев в действии свою первую программу, - написанную в прологовском стиле. Эта программа была частью знаменитой системы Shrdlu Терри Винограда. Решатель задач, встроенный в систему, работал в «мире кубиков» и заставлял руку робота (точнее, ее модель)-перемещать кубики на экране дисплея, решая при этом хитроумные задачи, поставленные оператором.
Решатель задач Винограда был написан на Микропленнере, языке, который, как мы теперь понимаем, был своего рода Прологом в миниатюре. Любой прологоподобный язык заставляет программиста мыслить в терминах целей, поэтому, несмотря на - все недостатки Микропленнера, достоинством этой программы было то, что в ее структуре содержались многочисленные явные указания на те или иные цели. Процедуры-цели «схватить», «освободить», «избавиться», «переместить», «отпустить» и т.п. делали программу простой и компактной, а поведение ее
Казалось попяяителкно ПЯЗУМНЫМ.
ОГЛАВЛЕНИЕ
От редактора перевода ............................. 5
Предисловие ......................................... 7
Предисловие автора ..................•............. 12
ЧАСТЬ 1. ЯЗЫК ПРОЛОГ............................. 17
Глава 1. Общий обзор языка Пролог ................. 18
1.1. Пример программы: родственные отношения •• 18
1.2. Расширение программы-примера с помощью
правил ................................... 24
1.3. .Рекурсивное определение правил ........... 31
1.4. Как пролог-система отвечает на вопросы ..... 37
1.5. Декларативный и процедурный смысл программ 43
Глава '2. Синтаксис и семантика пролог-программ • — • 47
2.1. Объекты данных............................. 47
2.2. Сопоставление т...............•........... 57
.2.3. Декларативный смысл пролог-программ......*• 64
2.4. Процедурная семантика .................... 67
2.5. Пример: обезьяна и банан ................. 74
2.6. Порядок предложений и целей ......•....... 81
2.7. Замечания о взаимосвязи между Прологом и логикой • •................................. 90
Глава 3. Списки. Операторы. Арифметика.............. 94
3.1. Представление списков • •.................. 94
3.2. ~ Некоторые операции над списками • • • •....... 98
3.3. Операторная запись (нотация) .............. 112
3.4. Арифметические действия ..............•..... 120
Глава 4. Использование структур: примеры ........... 130 ,
4.1. Получение структурированной информации из
базы данных................................ • 130
4.2. Абстракция данных ......................• • • • 135
4.3. Моделирование недетерминированного автомата 138
4.4. Планирование поездки .........•............. 143
4.5. Задача о восьми ферзях .........•.......... 149
Глава 5. Управление перебором ....................... 164
5.1. Ограничение перебора ....................... 164
5.2. Примеры, использующие отсечение ........... 171
--------'—•— —
5.3. Отрицание как неуспех ................
5.4. Трудности с отсечением и отрицанием ......!." «Г?
API
Глава в. Ввод и вывод.............................
6.1. Связь с файлами ....................
6.2. Обработка файлов термов ................'.','.' Jfjj
6.3. Обработка символов ...................'.'.[' |~JJ
6.4. Создание и декомпозиция атомов ..........'. in?
6.5. Ввод программ: consult, recommit........ 205
Глава 7. Другие встроенные процедуры .............. 208
7.1. Проверка типов термов .................... «08
7.1: 3Z^uSrS^^:::::*«»M 2»
7.4. Работа с базой данных .................... «2fi
7.5. Средства управления ....................... 941
7.6. bagof, setof и findall .................... 232
Глава 8. Стиль и методы программирования ........... 238
8.1. Общие принципы хорошего программирования •• 238
о Г ?ак представлять себе программы на Прологе 242
8.3. Стиль программирования .................... 245
8.4. Отладка ................................... 250
8.5. Эффективность ............................. 252
ЧАСТЬ 2. ПРОЛОГ В ИСКУССТВЕННОМ ИНТЕЛЛЕКТЕ.....267
Глава 9. Операции над структурами данных ........... 268
9.1. Представление списков. Сортировка ........ 268
9.2. Представление множеств двоичными деревьями 278
9.3. Двоичные справочники: добавление и удаление элемента* ................................ 286
9.4. Отображение деревьев ....................• • • 292
9.5. Графы...................................... 295
Глава 10. Усовершенствованные методы представления
множеств деревьями....................... 306
10.1. Двоично-троичные справочники .............. 306
10.2. AVL-дерево: приближенно сбалансированное
дерево .....................•............. 316
Глава 11. Основные стратегии решения задач ........323
11.1. Предварительные понятия и примеры ........323
11.2. Стратегия поиска в глубину .................330
11.3. Поиск в ширину............................. 336
11.4. Замечания относительно поиска в графах, оптимальности я сложности ..........•......345
Глава 12. Поиск с предпочтением: эвристический поиск 349
12.1. Поиск с предпочтением .................... 349
12.2. Поиск с предпочтением применительно к головоломке "игра в восемь" . .............. 361
12.3. Применение поиска с предпочтением к планированию выполнения задач.............. 367
Глава 13. Сведение задач к подзадачам. И/ИЛИ-графы 377
13.1. Представление задач в виде И/ИЛИ-графов • • 377
13.2. Примеры И/ИЛИ-представления задач ........ 383
13.3. Базовые процедуры поиска в И/ИЛИ-графах • • 388
13.4. Поиск с предпочтением в И/ИЛИ-графах ..... 395
Глава 14. Экспертные системы ....................... 414
14.1. Функции, выполняемые экспертной системой • • 414
14.2. Грубая структура экспертной системы ........ 416
14.3. Правила типа «если-то» для представления знаний ................•.................. 417
14.4. Разработка оболочки ....................... 426
14.5. Реализация................................ 434
14.6. Работа с неопределенностью ................. 456
14.7. Заключительные замечания ................. 466
Глава 15. Игры...................................... 472
15.1. Игры двух лиц с полной информацией ........ 472 '
15.2. Минимаксный принцип....................... 475
15.3. Альфа-бета алгоритм: эффективная реализация минимаксного принципа .................... 479
15.4. Минимаксные игровые программы: усовершенствования и ограничения ........... 485
15.5. Знания о типовых ситуациях и механизм «советов> .....•.......................... 488
15.6. Программа на языке ALO для игры в шахматном эндшпиле................................... 494
Глава 16. Программирование в терминах типовых
конфигураций ............................. 514
16.1. Архитектура, ориентированная на типовые конфигурации ............................. 514
16.2. Простой интерпретатор программ, управляемых образцами ................................ 521
16.3. Простая программа для автоматического доказательства теорем.................... 524
16.4. Заключительные замечания ................. 532
Ответы к некоторым упражнениям- ..........•......... 536
Предметный указатель..............................• • 552
Цена: 300руб.
