Методические рекомендации по срсп и срс самостоятельная работа студентов под руководством преподавателя (стр. 2 из 7)
Первая подцель достижима, поскольку она унифицируется с фактом в программе: вор(питер).
Вторая подцель: любит(питер, Z) будет унифицирована с фактом любит(питер, деньги), при этом
Z = деньги.
Поскольку и эта цель достижима, интерпретатор выдаст ответ Y = деньги. То есть Питер может_похитить деньги.
Интерпретатор продолжит поиск других целей и расторгнет унификацию цели любит(питер, X) с фактом любит(питер, деньги). Взамен этого цель любит(питер, X) будет унифицирована с правой частью правила, расположенного в пятой строке программы. Эта унификация означает, что X = Z и вместо старой цели любит(питер, X) будет выставлена цель любит(Z, вино), поскольку X = Z. Эта цель будет достигнута, поскольку она унифицируется с фактом, находящимся в третьей строке – любит(мэри, вино). В результате Z = мэри и интерпретатор выдаст ещё один ответ Z = мэри, то есть питер может_похитить мэри.
В заключение отметим, что Пролог позволяет решать задачи, относящиеся к искусственному интеллекту:
- общение с ЭВМ на естественном языке;
- формальные вычисления;
- написание компиляторов;
- работа с базами данных;
- экспертные системы и другие.
Методические указания к занятию № 1
Цель СРСП
1. Изучить основы синтаксиса языка Пролог.
2.Выработать навыки работы с интерактивной системой AMZI! Prolog.
3. Научиться оформлять отношения между данными на языке Пролог на примере родственных отношений между членами семьи.
Задание для подготовки к работе
Изучить лекционный материал и основные понятия настоящей лабораторной работы.
Порядок выполнения работы
1. Изучить основные команды и возможности системы AMZI! Prolog.
2. Отработать команды в системе AMZI! Prolog.
3. Выполнить контрольный пример.
4. Создать в системе AMZI! Prolog программу, которая описывает родственные отношения между членами семьи.
5. Составить отчет о проделанной работе.
Методические рекомендации
Язык программирования Пролог базируется на ограниченном наборе механизмов, включающих в себя сопоставление образцов, древовидное представление структур данных и автоматический возврат. Этот небольшой набор образует удивительно мощный и гибкий программный аппарат.
Программирование на Прологе – программирование в терминах логики. Программы на Прологе записываются в декларативном стиле, это означает что выполнение программ Пролог - машиной происходит по принципу:
Ты скажи: " Что сделать", а я разработаю "Как это сделать". Другими словами, в отличие от императивных языков программирования, на Прологе интерпретатор сам выбирает порядок исполнения операторов в программе.
Особенно хорошо Пролог приспособлен для решения задач, в которых фигурируют объекты и отношения между ними. Примером такой задачи может служить задача, описывающая родственные отношения в семье.
На Прологе легко определить отношения, подобные отношению родитель(X,Y), что означает ИСТИНА если X является родителем Y, и ЛОЖЬ в противном случае.
Программа на языке Пролог состоит из предложений. Каждое предложение заканчивается точкой.
Аргументами отношений могут быть атомы (константные объекты) или переменные. В тексте программы названия переменных начинаются с большой буквы, а названия констант – с маленькой.
На Прологе отношения могут быть записаны в виде фактов и правил. В виде фактов записываются простейшие отношения.
Например:
human(oleg).
fruit(orange).
Правила нужны для получения новых отношений из уже известных.
Например:
ather(X,Y):-parent(X,Y),man(X).
Что означает: X является отцом Y, ЕСЛИ X родитель Y И X является
мужчиной.
Вопрос к системе формируется в виде цели, которая может содержать переменные. В этом случае Пролог-машина проверит все возможно допустимые состояния переменных и найдет те из них, при которых цель достижима.
Повторяющееся применение фактов к правилам, приводящее к новым фактам, называется прямым рассуждением (forward chaining). При обратном рассуждении (backward chaining) осуществляется поиск заключений (заголовков правил), соответствующих цели. Если такое заключение найдено, то в свою очередь должны быть доказаны цели, входящие в данное правило. В Прологе используется обратное рассуждение.
В Прологе поиск осуществляется в глубину. Алгоритм поиска показан на рисунке.
Здесь задействованы три списка. Первый, ПРЕДЛОЖЕНИЯ, содержит предложения. Во втором, ЦЕЛИ, находятся цели, подлежащие удовлетворению. Третий список, РЕШЕНИЯ, включает точки возврата и хранит следы предложений, применявшихся для достижения целей. Это своего рода трасса нахождения решения процедурой поиска.
Процедура ПОИСК просматривает список целей. Если он пуст, то, значит, не осталось ни одной цели, которую нужно доказать, и поиск считается успешным. В противном случае удаляется первая цель из списка ЦЕЛИ, и сканирование продолжается по списку ПРЕДЛОЖЕНИЯ в поисках подходящего предложения. Если таковое найдено, то указатель (в списке ПРЕДЛОЖЕНИЯ) на это предложение вместе с целью добавляется к списку РЕШЕНИЯ. Указатель отмечает, как далеко процедура ПОИСК продвинулась в списке ПРЕДЛОЖЕНИЯ перед нахождением нужного предложения. Затем проверяются цели выбранного предложения. Если хотя бы одна из них недостижима, указатель продвигается до следующего подходящего предложения в списке ПРЕДЛОЖЕНИЯ и его цели помещаются в список ЦЕЛИ. Такая реакция на неудачу называется возвратом. Этот новый указатель замещает прежний в списке РЕШЕНИЯ, и всякий раз, когда совершается возврат, продвигается далее по списку ПРЕДЛОЖЕНИЯ. Если указатель достигает конца списка ПРЕДЛОЖЕНИЯ, то, следовательно, в списке нет предложений, доказывающих искомые цели, и ПОИСК завершается неудачей.
Контрольный пример
| |
Простейшая программа на языке Пролог.
man(nikolay).
man(stepan).
woman(lida).
parent(lida, stepan).
parent(nikolay, stepan).
mother(X,Y):-parent(X,Y),woman(X).
Задание к работе
1. Изобразить граф, иллюстрирующий описываемые родственные отношения.
2. Составить программу, которая описывает родственные отношения.
В качестве фактов описать унарные отношения: мужчина, женщина; и бинарные: состоят_в_браке, родитель_ребенок.
Записать правила, которые определяют следующие отношения: муж, жена, родитель, ребенок, сын, дочь, брат, сестра, дядя, тетя, бабушка, дедушка.
3. Подобрать тестовые данные, проверяющие все полученные отношения. Тестовые данные должны содержать операции «И», «ИЛИ», «НЕ».
4. Оформить отчет о проделанной работе.
Содержание отчета
1. Описание родственных отношений, представленных в лабораторной работе, в виде графа.
2. Исходные тексты программ на языке Пролог.
3. Наборы тестовых данных и результаты работы программ.
4. Перечень и анализ ошибок, допущенных при решении задачи.
5. Выводы по работе.
Методические указания к занятию № 2
Использование рекурсивных правил и структурированных данных
Цель СРСП
Научиться использовать структурированные типы данных и рекурсивные правила при решении задач.
Задание для подготовки к работе
Изучить темы «Рекурсивные правила», «Структурированные данные».
Порядок выполнения работы
1. Выполнить контрольные примеры.
2. Создать в системе программу, которая решает задачи согласно варианту.
3. Модифицировать программу CH06EX03.pro и подобрать цели иллюстрирующие структуру данных.
4. Составить отчет о проделанной работе.
Задание и методические рекомендации
Определения отношений, в которых используется само отношение, называется рекурсивным. Рекурсия – один из фундаментальных механизмов программирования на Прологе. Рекурсию можно применять для достижения такого же эффекта, какой реализуется при употреблении итеративных управляющих конструкций (циклов) в процедурных языках. Примером использования рекурсии может служить определение отношения «предок» [1, 2]. Данное отношение можно выразить с помощью двух правил. Первое правило будет определять непосредственных предков, а второе – отдаленных. Первое правило легко сформулировать через отношение «родитель»:
предок(X, Z) :- родитель(X, Z).
Аналогичным образом можно попытаться сформулировать второе правило:
предок(X, Z) :- родитель(X, Z).
предок(X, Z) :- родитель(X, Y), родитель(Y, Z).
предок(X, Z) :- родитель(X, Y1), родитель(Y1, Y2), родитель(Y2, Z).
Подобное описание отношения будет работать только в определенных пределах, то есть обнаруживать предков лишь до определенной глубины, поскольку длина цепочки людей между предком и потомком ограничена длиной предложений в определении отношения.
Подобные отношения целесообразно описывать с помощью рекурсии. Правило будет выглядеть следующим образом:
Для всех X и Z,
X – предок Z, если
существует Y, такой, что
X – родитель Y и
Y – предок Z.
или на языке Пролог:
предок(X, Z) :- родитель(X, Y), предок(Y, Z).
Таким образом, определение отношения «предок» будет выглядеть следующим образом:
предок(X, Z) :- родитель(X, Z).
предок(X, Z) :- родитель(X, Y), предок(Y, Z).
При описании рекурсивных правил следует соблюдать осторожность во избежание зацикливания рекурсии. Для этого любое рекурсивное определение отношения должно включать по крайней мере два правила:
1) нерекурсивное правило, определяющее исходный вид отношения, т.е. вид отношения в момент прекращения рекурсии;
2) рекурсивное правило – первая подцель, располагающаяся в теле этого правила, вырабатывает новые значения аргументов. Далее размещается рекурсивная подцель, в которой используются новые значения аргументов