Программирование на языке Пролог для искусственного интеллекта
6ec30db9

В средние века знание латинского


Preface

Программирование на языке Пролог для искусственного интеллекта

Пример программы родственные отношения
Дерево родственных отношений
Отношение родительродителя выраженное через композицию двух отношений родитель
Упражнения

Расширение программыпримера с помощью правил
Графы отношений родительродителя мать и отпрыск определенных через другие отношения
Определение отношения сестра


Рекурсивное определение правил
Пример отношения предок (а) X ближайший предок Z; (b) X отдаленный предок Z
Пары предокпотомок разделенных разным числом поколений

Программа о родственных отношениях
Упражнение
Первый шаг вычислений Верхняя цель истинна если истинна нижняя
Продолжение процесса вычислений показанного на a>
Все шаги достижения цели предок( том пат) Правая ветвь демонстрирует что цель достижима
Упражнение

Декларативный и процедурный смысл программ
Резюме
Литература

Программирование на языке Пролог для искусственного интеллекта

Объекты данных
Обьекты данных Пролога

Атомы и числа
Переменные
Имеетребенка( X) родитель( X _ )
Некто_имеет_ребенка родитель( _ _ )
Некто_имеет_ребенка родитель( X Y)
? Родитель( X _ )
Структуры
Дата пример структурного
Простые геометрические объекты
Представление объектов с Рисунок 2 3 в виде деревьев

Древовидная структура соответствующая арифметическому выражению (а + w)*(s 5)
Некоторые простые
Упражнения
Сопоставление
Помогает сформулировать это отношение Отрезок
Сопоставление треугольник((
Пример вертикальных и горизонтальных отрезков прямых
Входы и выходы процедуры вычисления списка целей

Пример иллюстрирующий
Вычисление целевых утверждений Пролога
Исходное состояние
Рекурсивная формулировка отношения можетзавладетъ
Программа для задачи об обезьяне и банане
Поиск банана обезьяной
Порядок предложений и целей
Опасность бесконечного цикла
Варианты программы полученые путем переупорядочивания предложений и целей

Четыре версии программы предок
Поведение трех вариантов
Сочетание декларативного и процедурного подходов
Замечания о взаимосвязи между Прологом и логикой
Литература

Программирование на языке Пролог для искусственного интеллекта

Представление списков
Представление списка [энн теннис том лыжи] в виде дерева

Некоторые операции над списками
Принадлежность к списку
Сцепление ( конкатенация)
Конкатенация списков
Процедура принадлежит1
Упражнения
Добавление элемента
Удаление элемента
Подсписок
Отношения принадлежит и подсписок

Один из способов построения перестановки списка [X | L]
Операторная запись (нотация)
Представление выражения 2*а+b*с в виде дерева
Две интерпретации
Множество предопределенных операторов
Интерпретация терма ~(А В) === ~A v ~В
Арифметические действия

Резюме

Программирование на языке Пролог для искусственного интеллекта

Получение структурированной информации из базы данных
Структурированная информация о семье
Описания объектов
Упражнения
Абстракция данных
Упражнение
Моделирование недетерминированного автомата
Пример недетерминированного конечного автомата

Допущение цепочки
Планирование поездки
Планировщик воздушных маршрутов и база данных о рейсах самолетов
Задача о восьми ферзях
Решение задачи о восьми
Программа1 для задачи о восьми ферзях
Программа 2
а) Расстояние по

Программа 2 для задачи о восьми ферзях
Программа 3
Связь между вертикалями
Программа 3 для задачи о восьми ферзях
Заключительные замечания
Резюме

Программирование на языке Пролог для искусственного интеллекта

Ограничение перебора
Двухступенчатая функция

В точке помеченной
Примеры использующие отсечение
Вычисление максимума
Процедура проверки принадлежности списку дающая единственное решение
Задача классификации объектов
Упражнения
Отрицание как неуспех
Еще одна программа для решения задачи о восьми ферзях
Трудности с отсечением и отрицанием

Резюме
Литература

Программирование на языке Пролог для искусственного интеллекта

Связь с файлами
Связь между прологпрограммой и различными файлами
Обработка файлов термов
Reаd и write
Вывод списков
Формирование термов
Улучшенный формат вывода термов представляющих семью

Программа обеспечивающая вывод в формате представленном на Рисунок 6 2
Обработка произвольного файла термов
Обработка символов
Упражнение
Создание и декомпозиция атомов
Процедура для преобразования предложения в список атомов
Упражнения
Ввод программ consult reconsult
Резюме

Программирование на языке Пролог для искусственного интеллекта


Проверка типов термов
Предикаты var nоnvar atom integer atomic
Решение числового ребуса с использованием nonvar
Поразрядное сложение
Упражнения
Создание и декомпозиция термов = functor arg name
Процедура подстановки в терм вместо одного из его подтермов некоторого другого подтерма
Упражнения
Различные виды равенства
Работа с базой данных

Упражнения
Bagof setof и findall
Реализация отношения findall
Упражнения
Резюме

Программирование на языке Пролог для искусственного интеллекта

Общие принципы хорошего программирования
Как представлять себе программы на Прологе
Использование рекурсии
Обобщение

Использование рисунков
Стиль программирования
Некоторые правила хорошего стиля
Табличная организация длинных процедур
Отладка
Эффективность
Повышение эффективности решения задачи о восьми ферзях
Повышение эффективности программы раскраски карты
Повышение эффективности конкатенации списков за счет совершенствования структуры данных
Повышение эффективности зa счет добавления вычисленных фактов к базе данных

Вычисление 6го числа Фибоначчи процедурой фиб
Вычисление 6го числа
Помогает понять отношение фибВперед
Отношения в последовательности
Упражнения
Резюме

Программирование на языке Пролог для искусственного интеллекта

Представление списков Сортировка
Замечания в некоторых альтернативных способах представления списков
Упражнения

Сортировка списков
Сортировка списка процедурой быстрсорт
Более эффективная
Представление множеств двоичными деревьями
Двоичное дерево
Представление двоичных деревьев
Поиск элемента Х в двоичном справочнике
а) Дерево Д построенное

Двоичные справочники добавление и удаление элемента
Введение в двоичный
Вставление в двоичный справочник нового элемента в качестве листа
Удаление X из двоичного
Заполнение пустого места после удаления X
Удаление элемента из двоичного справочника
Внесение Х в двоичный справочник в качестве корня
Внесение элемента на произвольный уровень двоичного справочника
Отображение деревьев
а) Обычное изображение

Отображение двоичного дерева
Упражнение
Графы
Представление графов
а) Граф (b) Направленный граф Каждой дуге приписана ее стоимость
Поиск пути в графе
Поиск в графе Граф ациклического пути Путь из А в Z
Поиск пути в графе Путь путь между А и Z в графе Граф стоимостью Ст
Построение остовного дерева
Построение остовного

Резюме
Литература

Программирование на языке Пролог для искусственного интеллекта

Двоично троичные справочники
Полностью разбалансированный
справочник Отмеченный путь показывает процесс поиска элемента 10
Иллюстрирует описанный принцип
Вставление нового
Объекты показанные на рисунке удовлетворяют отношению встав( Дер 6 НДа Мб НДб)

Некоторые из случаев
Упражнения
а) Программа для
AVL дерево приближенно сбалансированное дерево
Задача вставления
Три правила построения нового AVLдepевa
Упражнение
Вставление элемента
Резюме
Литература

Программирование на языке Пролог для искусственного интеллекта

Предварительные понятия и примеры
Задача перестановки кубиков
Игра в восемь" и ее представление в форме графа
Стратегия поиска в глубину
Пример простого пространства
Начинаясь в а поиск вглубину заканчивается бесконечным циклом между d и h a b d h d h d
Отношение вглубину( Путь В Решение)
Программа поиска в глубину без зацикливания
Программа поиска в глубину с ограничением по глубине

Упражнения
Поиск в ширину
Простое пространство
Списковое представление множества кандидатов
Программа поиска
Древовидное представление множества кандидатов
Отношение paсширить(
Реализация поиска
Упражнения
Замечания относительно поиска в графах оптимальности к сложности

а) Пространство
Резюме
Литература

Программирование на языке Пролог для искусственного интеллекта

Поиск с предпочтением
Построение эвристической
Поиск кратчайшего
Программа поиска с предпочтением
Отношение расширить
Связь между gоценкой

Упражнение
Поиск c предпочтением применительно к головоломке "игра в восемь"
Процедуры для головоломки
Три стартовых позиции
Упражнение
Применение поиска с предпочтением к планированию выполнения задач
Планирование прохождения
Проект
Отношения для задачи
Резюме

Литература

Программирование на языке Пролог для искусственного интеллекта

Представление задач в виде И / ИЛИграфов
Поиск маршрута из
И / ИЛИпредставление
а) Решить Р это
а) Пример И / ИЛИграфа
Примеры И/ИЛИпредставления задач
И / ИЛИпредставление задачи поиска маршрута
Решающее дерево минимальной

Задача о ханойской башне
Задача о ханойской башне
Формулировка игровых задач в терминах И / ИЛИграфов
Формулировка игровой
Базовые процедуры поиска в И / ИЛИграфах
Поиск в глубину для
Упражнения
Поиск с предпочтением в И / ИЛИграфах
Эвристические оценки и алгоритм поиска
Получение оценки Н трудности задач И / ИЛИграфа

Трассировка процесса
Представление дерева поиска
Программа поиска с предпочтением в И / ИЛИграфе
Пример отношений определяющих конкретную задачу поиск маршрута
Упражнение
Резюме
Литература

Программирование на языке Пролог для искусственного интеллекта

Функции выполняемые экспертной системой
Грубая структура экспертной системы

Правила типа "еслито" для представления знаний
Еслито"правило
и 14 4 дают
Два правила из демонстрационной
Правило уточнения плана из системы AL3 для решения шахматных задач (Bratko 1982)
Простая база знаний
Соединения между предохранителями и приборами в простой электрической схеме
Разработка оболочки
Процесс рассуждений
Формирование ответа на вопрос "почему"

Объяснение типа "почему"
Формирование ответа на вопрос "как"
Реализация
Отношение рассмотреть(
Основная процедура оболочки экспертной системы
Процедура ответпольз
Оболочка экспертной
Процедура выдать
Драйвер верхнего уровня
Оболочка экспертной

Цели с отрицанием
Оболочка экспертной
Упражнение
Степень достоверности
Модель Prospector'а
Сеть вывода системы
Правила распространения
Принципы реализации
Определение степени
Заключительные замечания

Проекты
Резюме
Литература

Программирование на языке Пролог для искусственного интеллекта

Игры двух лиц с полной информацией
Сложность игровых
Проект
Минимаксный принцип
Статические (нижний
Упрощенная реализация минимаксного принципа

Альфабета алгоритм эффективная реализация минимаксного принципа
Дерево Рисунок 15
Реализация альфабета алгоритма
Минимаксные игровые программы усовершенствования и ограничения
Знания о типовых ситуациях и механизм "советов"
Цели и ограничения на ходы
Выполнимость совета
Правила и таблицы советов
Программа на языке AL0 для игры в шахматном эндшпиле

Миниатюрный интерпретатор языка AL0
Миниатюрный интерпретатор языка AL0
Программа на языке советов для эндшпиля "король и ладья против короля"
Иллюстрирует смысл некоторых из
Таблица советов на
Фрагмент шахматной
а) "Критическая
Библиотека предикатов для окончания "король и ладья против короля"
Резюме

Литература

Программирование на языке Пролог для искусственного интеллекта

Архитектура ориентированная на типовые конфигурации
Основные понятия
Система управляемая типовыми конфигурациями ( образцами)
Прологовские программы как системы управляемые образцами
Основной цикл работы
Пример составления программы
Процесс вычисления
Простой интерпретатор программ управляемых образцами

Простой интерпретатор для программ управляемых образцами
Простая программа для автоматического докаэательства теорем
Доказательство теоремы
Программа управляемая образцами для автоматического доказательства теорем
Преобразование пропозициональных
Проект
Резюме
Литература
Glossary
End

Содержание раздела