Методические рекомендации по дисциплине «Интеллектуальные информационные системы» Лабораторный практикум в средах Visual Prolog и DrRacket оглавление

1
Методические рекомендации по дисциплине
«Интеллектуальные информационные системы»
Лабораторный практикум
в средах Visual Prolog и DrRacket
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ .................................................................................................................. 2 1. ПРОЛОГ – язык логического программирования ............................................... 4 1.1. Создание баз знаний в ПРОЛОГе ................................................................... 4 1.2 Поиск с возвратом. Управление поиском ..................................................... 16 1.3 Решение логических задач в ПРОЛОГе ........................................................ 27 1.4 Арифметические вычисления и рекурсия в ПРОЛОГе ............................... 31 1.5 Списки ............................................................................................................... 35 1.6 Создание экспертных систем средствами ПРОЛОГа ................................. 40 2. ОСНОВЫ ФУНКЦИОНАЛЬНОГО ПРОГРАММИРОВАНИЯ ..................... 50 2.1. Основы работы в среде DrRacket .................................................................. 50 2.2. Управляющие конструкции в Racket ............................................................ 57 2.3.Реализация рекурсии в Racket ........................................................................ 64 2.4. Списки и атомы ............................................................................................... 66
Литература ............................................................................................................... 75

2
ВВЕДЕНИЕ
Языки функционального и логического программирования являются представителями декларативной парадигмы программирования.
В декларативных языках, в отличие от процедурных, описывается не алгоритм решения задачи, а знания об объектах и процессах соответствующей предметной области. Поиск решения задачи вырабатывается и реализуется в ходе логического вывода с помощью специального механизма. Знание общих концепций и методов современного декларативного программирования и, в частности, таких его разновидностей, как функциональное и логическое программирование, позволяет эффективно решать задачи, связанные с обработкой символьной информации, построением систем поддержки принятия рещений, экспертных систем.
Основоположником логического направления программирования является язык ПРОЛОГ, а функционального - ЛИСП. В настоящее время эти и другие языки, поддерживающие и развивающие декларативную парадигму программирования, развиваются и становятся все более универсальными.
Предлагаемое методическое пособие представляет собой описание лабораторных работ по изучению функционального и логического программирования. Пособие состоит из двух частей: в первой рассматривается решение типовых задач на ПРОЛОГе в среде Visual Prolog, во второй части приведены примеры разработки программ на языке DrRacket, который является одним из современных диалектов ЛИСП.
Основная цель пособия – помощь студентам в подготовке к выполнению лабораторных работ.
Целью выполнения данных лабораторных работ является приобретение студентами навыков работы в средах Visual Prolog и DrRacket (формальная постановка задачи, преобразование в форму, пригодную для программирования, трассировка и оценка результатов), а также закрепление теоретических знаний, полученных при прослушивании курса лекций.
Пособие содержит необходимый теоретический материал, примеры решения задач и задания по программированию на языках Пролог и
DrRacket. К каждому разделу приводятся несколько типовых задач с решениями, что

3 позволяет студентам самостоятельно подготовиться к выполнению лабораторной работы.
В качестве результата выполнения лабораторной работы студентом должен быть подготовлен отчет о проделанной работе, который включает:
1. Постановку задачи
2. Входные/Выходные данные (при необходимости)
3. Текст программы (с необходимыми комментариями)
4. Результаты тестирования (наборы входных и выходных данных).
В настоящем пособии приводится список литературы, которая может быть использована при подготовке к лабораторным работам.
Данное пособие может использоваться студентами при изучении дисциплин:
Функциональное и логическое программирование,
Интеллектуальные информационные системы,
Основы логического программирования.

4 1. ПРОЛОГ – язык логического программирования
1.1.
Создание баз знаний в ПРОЛОГе
Краткие теоретические сведения
ПРОЛОГ (ПРОграммирование в ЛОГике) - язык логического программирования, предназначен для решения задач из области искусственного интеллекта. Он используется для обработки естественного языка и разработке систем, основанных на знаниях. Методы поиска, используемые в нем, принципиально отличаются от традиционных. Вместо детальных инструкций, предписывающих как решать ту или иную задачу, программист на языке Prolog уделяет основное внимание описанию задачи.
Основные конструкции ПРОЛОГа заимствованы из логики. ПРОЛОГ относится не к процедурным, а к декларативным языкам программирования. Он ориентирован не на разработку решений, а на систематизированное и формализованное описание задачи с тем, чтобы решение следовало из составленного описания.
Современной средой, в основе которой лежит язык Пролог, является
Visual Prolog. В среде Visual Prolog используется подход, получивший название
«визуальное программирование», при котором внешний вид и поведение программ определяются с помощью специальных графических средств проектирования без традиционного программирования на алгоритмическом языке. рис.1.1 Среда разработки Visual Prolog 6.1 окно проекта кнопки для работы с компонентами проекта компоненты проекта эксперт кода

5
Интерфейс Visual Prolog включает: главное меню, панель инструментов, окно проекта. Если во время последнего использования системы Visual Prolog там был открытый проект, то система автоматически вновь откроет этот проект.
На рис.1.1 изображен внешний вид среды Visual Prolog после запуска. В окне проекта отображаются модули открытого проекта route.prj: karta.pro, route.pro, VPITools.pro.
Левая панель кнопок в окне проекта позволяет выбирать нужный компонент проекта: модуль, окно, меню и т.д. С помощью кнопок правой панели выбранный компонент можно редактировать(кнопка
Edit), удалять(кнопка Delete), а также добавлять новый(кнопка New).
Пункт меню File содержит команды для работы с файлами. Чтобы создавать новое окно редактирования, можно использовать команду File | New.
Эта команда создаст новое окно редактора с заголовком "NONAME".
В меню Edit представлены команды, позволяющие редактировать текст программы. Встроенный редактор системы по интерфейсу похож на обычный текстовый редактор. Можно производить вырезку, копирование и вставку текста, операции Отмена/Восстановление, которые можно активизировать из меню Edit. Также меню Edit показывает "горячие клавиши", связанные для этих действий.
Пункт меню Project содержит команды для работы с проектом: создать новый, открыть, запустить и т.д. Запуск проекта на исполнение выполняется нажатием кнопки на панели инструментов (или F9, или с помощью команд меню Project | Run).
Команды меню Options позволяют выполнять настройку проекта, устанавливать необходимые параметры.
Среда Visual Prolog позволяет протестировать программу без создания проекта. Для этого используется утилита Test Goal. Достаточно создать новый файл, набрать текст программы и активизировать Test Goal нажатием кнопки
на панели инструментов. Автономно исполняемый файл при этом не создается. Утилита Test Goal компилирует только тот код, который определен в активном окне редактора (код в других открытых окнах или модулях проектов, если они есть, игнорируются). Test Goal находит все возможные решения задачи и автоматически выводит значения всех переменных.
Программа на ПРОЛОГе состоит из предложений, которые могут быть фактами, правилами или запросами. Факт – это утверждение о том, что со- блюдается некоторое конкретное соотношение между объектами. Факт используется для того, чтобы показать простую взаимосвязь между данными.
Структура факта:
<имя_отношения>( t1,t2,...,tn) ), t1,t2,...,tn– объекты
Примеры фактов: учится (ира, университет). % Ира учится в университете родитель(иван, алексей). % Иван является родителем Алексея язык_программирования (пролог). % Пролог – это язык программиро- вания

6
Набор фактов составляет базу данных. В виде факта в программе записываются данные, которые принимаются за истину и не требуют доказательства.
Правила используются для того, чтобы установить отношения между объектами на основе имеющихся фактов.
Структура правила:
<имя_правила> :- <тело правила> или
<имя_правила > if <тело правила>
Левая часть правила вывода называется головой правила, а правая часть - телом. Тело может состоять из нескольких условий, перечисленных через запятую или точку с запятой. Запятая означает операцию «логическое И», точка с запятой – операцию «логическое ИЛИ». В предложениях используются переменные для обобщенной формулировки правил вывода. Переменные действуют только в одном предложении. Имя в разных предложениях указывает на разные объекты. Все предложения обязательно заканчиваются точкой.
Примеры правил: мать (Х, У) :- родитель (Х, У), женщина(Х). студент (X) :- учится (X, институт); учится (X, университет).
Правило отличается от факта тем, что факт - всегда истина, а правило является истинным, если выполняются все утверждения, составляющие тело правила. Факты и правила образуют базу знаний.
Переменные служат для обозначения объектов, значения которых меня- ются в ходе выполнения программы. Имена переменных начинаются с заглавных букв или знака «_» Область действия переменной – предложение.
Одноименные переменные в разных предложениях могут иметь разные зна- чения.
Специальным знаком «_» обозначается анонимная переменная, которая используется тогда, когда конкретное значение переменной не существенно для данного предложения. Значение анонимной переменной не выводится на печать.
Если имеется база данных, то можно написать запрос (цель) к ней. За- прос — это формулировка задачи, которую программа должна решить. Его структура такая же, как у правила или факта. Существуют запросы с константами и запросы с переменными.
Запросы с константами позволяют получить один из двух ответов: “да” или “нет”. Если в запрос входит переменная, то интерпретатор пытается найти такие ее значения, при которых запрос будут истинным. Запросы мо-гут быть составными, т.е. состоять из нескольких простых запросов. Они могут объединяться знаком ‘,’, который понимается как логическая связка И или знаком ‘;’(логическое ИЛИ).
Простые запросы называются подцелью, составной запрос принимает истинное значение тогда, когда истинна каждая подцель.
Как правило, программа состоит из четырех разделов.

7
DOMAINS – секция описания доменов(типов). Секция применяется, если в программе используются нестандартные домены.
PREDICATES – секция описания предикатов. Секция применяется, если в программе используются нестандартные предикаты.
CLAUSES – секция предложений. Именно в этой секции записываются предложения: факты и правила вывода.
GOAL – секция цели. В этой секции записывается запрос.
Пример 1.
Имеется база данных, содержащая следующие факты: родитель(илья, марина). родитель(марина, ира). родитель(елена, иван). родитель(николай, ира). родитель(ольга, алексей). родитель(марина, саша). родитель(сергей, иван).
Определить:
1) верно ли, что Марина является родителем Саши;
2) верно ли, что Алексей является родителем Ольги;
3) кто является ребенком Николая;
4) кто родители Ивана;
5) всех родителей и их детей.
Решение.
1. Запустите среду Visual Prolog. Закройте окно проекта (если оно открыто) и откройте новый файл (File|New) (рис.2)
В появившемся окне наберите текст программы, содержащий разделы:
PREDICATES (описание предиката родитель), CLAUSES (перечисляются имеющиеся факты) и GOAL (запрос). рис.2. Рабочее окно редактора

8
DOMAINS имя=symbol
PREDICATES nondeterm родитель(имя, имя)
CLAUSES родитель(илья, марина). родитель(марина, ира). родитель(елена, иван). родитель(николай, ира). родитель(ольга, алексей). родитель(марина, саша). родитель(сергей, иван).
GOAL родитель(марина, саша) .
Запустите и протестируйте программу с помощью команды Project | Test
Goal (можно использовать кнопку на панели инструментов или сочетание клавиш +). Результат выполнения программы будет выведен в отдельном окне рис3. Окно вывода результата
Указание: перед следующим запуском программы следует закрыть это окно.
2. Для ответа на вопрос: верно ли, что Алексей является родителем
Ольги, измените запрос:
GOAL родитель(алексей, ольга).
После запуска программы (Project | Test Goal) будет получен ответ: no
3. Для ответа на вопрос: кто является ребенком Николая, запишите цель:
GOAL родитель(николай, X) .
Результат:
X=ира
1 Solution
4. Для ответа на вопрос: кто родители Ивана, укажите запрос:
GOAL

9 родитель(X, иван), родитель(Y, иван), X<>Y.
Результат:
X=елена, Y=сергей
X=сергей, Y=елена
2 Solutions
5. Для определения всех родителей и их детей, запишите:
GOAL родитель(X, Y).
Результат:
X=илья, Y=марина
X=марина, Y=ира
X=елена, Y=иван
X=николай, Y=ира
X=ольга, Y=алексей
X=марина, Y=саша
X=сергей, Y=иван
7 Solutions
Пример 2
Имеются факты вида: родитель(имя, имя) и женщина(имя). а) составить правило мать и определить, кто мать Маши. б) составить правило бабушка и определить, кто бабушка Ирины. в) составить правило внучка и определить, сколько внучек у Ольги и как их зовут
Решение:
DOMAINS имя= symbol
PREDICATES nondeterm родитель(имя, имя) женщина(имя) nondeterm мать(имя,имя) nondeterm бабушка(имя,имя) nondeterm внучка(имя,имя)
CLAUSES родитель(марина,ирина). родитель(елена, анна). родитель(ольга,марина). родитель(ольга,татьяна). родитель(татьяна,катя). родитель(анна, маша).

10 женщина(ольга). женщина(маша). женщина(ирина). женщина(елена). женщина(анна). женщина(марина). женщина(татьяна). женщина(катя). мать(X,Y):-родитель(X,Y),женщина(X). бабушка(X,Z):-мать(X,Y),родитель(Y,Z). внучка(X,Y):-бабушка(Y,X),женщина(X).
А)GOAL мать(Кто,маша).
Результат:
Кто=анна
1 Solution
Б)GOAL бабушка(Кто,ирина).
Результат:
Кто=ольга
1 Solution
В)GOAL внучка(Кто, ольга).
Результат:
Кто=ирина
Кто=катя
2 Solutions
Замечание: ключевое слово nondeterm определяет недетерминированные предикаты, которые могут совершать откат назад и генерировать множественные решения. Таким образом, если задача предполагает возможность получения несколько решений, следует объявлять предикаты как недетерминированные.
Пример 3
Записать по правилам Пролога следующие факты:
Билл играет в теннис, баскетбол и футбол
Майк играет в футбол и хоккей.
Сформулировать запросы, выясняющие: а) кто играет в футбол

11 б) во что играет Майк в) во что играют и Билл, и Майк
Решение:
DOMAINS имя, спорт=symbol
PREDICATES play(имя,спорт)
CLAUSES play(билл,теннис). play(билл,баскетбол). play(билл,футбол). play(майк,хоккей). play(майк,футбол).
А)GOAL play(X,футбол).
Результат:
X=билл
X=майк
2 Solutions
Б)
GOAL play(майк,X).
Результат:
X=хоккей
X=футбол
2 Solutions
В)
GOAL play(майк,X),play(билл,X).
Результат:
X=футбол
1 Solution
Создание проекта позволяет протестировать пример как автономную исполняемую программу. После запуска проекта на исполнение создается exe- файл, работа которого завершается после первого решения, удовлетворяющего решению задачи. Запуск программы в этом режиме не обеспечивает автоматический вывод значений переменных, поэтому необходимо использовать стандартный предикат вывода write.
Пример 4.

12
Заданы отношения-факты: родитель(“Иван”,”Катя”). родитель(“Анна”,” Олег ”). родитель(“Олег”,”Дима”). родитель(“Игорь”,”Ольга”). родитель(“Олег”,”Виктор”). родитель(“Игорь”,”Иван”). мужчина(“Дима”). мужчина(“Иван”). мужчина(“Игорь”). мужчина(“Олег”). мужчина(“Виктор”). женщина(“Катя”). женщина(“Ольга”). женщина(“Анна”).
Составить новое отношение-правило дед(X,Y) и определить, кто является дедушкой Кати. Создать проект и протестировать пример как автономную исполняемую программу.
Решение
1. Запустите среду Visual Prolog и создайте новый проект (Project | New
Project), активизируется окно Application Expert (эксперт приложения).
2. Определите имя проекта (Primer) и базовый каталог, куда будет сохранен проект (например, D:\VP\Primer)
Введите имя проекта

14 рис.7. Окно проекта
Файл с расширением .pro содержит секции PREDICATES, GOAL,
CLAUSES. Допишите необходимые определения так, чтобы получилась программа:
DOMAINS имя=string
PREDICATES родитель(имя,имя) женщина(имя) мужчина(имя) дед(имя, имя)
CLAUSES родитель("Иван","Катя"). родитель("Анна","Олег"). родитель("Олег","Дима"). родитель("Игорь","Ольга"). родитель("Олег","Виктор"). родитель("Игорь","Иван"). мужчина("Дима"). мужчина("Иван"). мужчина("Игорь"). мужчина("Олег"). мужчина("Виктор"). женщина("Катя"). женщина("Ольга"). женщина("Анна"). дед(X,Z):-родитель(X,Y), родитель(Y,Z), мужчина(X).
GOAL дед(X,"Катя"),write(X).
5. Откомпилируйте исходный код примера и запустите его как автономную исполняемую программу. ( Project | Run, или клавиша , или кнопка ). Результат выполнения программы должен отобразиться в окне: двойной щелчок

15 рис.8. Окно вывода результата
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ
1. Запишите по правилам Пролога следующие факты:
Ник подарил Тому книгу.
Мэри подарила Тому ручку.
Рик подарил Мэри игрушку.
Боб подарил Пэт игрушку.
Сформулируйте запросы, выясняющие: a)
Правда ли, что Рик подарил Мэри игрушку? b)
Правда ли, что Ник подарил Тому игрушку? c)
Что подарила на день рождения Тому Мэри? d)
Что подарили Тому на день рождения? e)
Кто подарил Пэт игрушку?
2. Задано дерево родственных отношений:
Мария
Иван родитель родитель
Федор
Степан родитель
Ольга
Татьяна
Запишите данные факты по правилам ПРОЛОГа и сформулируйте запросы, выясняющие: a) Является ли Федор родителем Ольги? b) Кто является родителем Татьяны? c) Кто дети Ивана? d) Кто является родителем родителя Ольги? e) Кто внуки Ивана? f) Есть ли у Федора и Степана общий родитель? g) Кто чей родитель?
3. Имеется база данных, содержащая факты вида: любит(имя, продукт), фрукты(продукт), конфеты(продукт).
Составьте программу, определяющую: