ГОУ ВПО МГТУ «Станкин»

Факультет «Информационные технологии»

Кафедра «Информационные технологии и вычислительные системы»

Методические указания и рекомендации по выполнению лабораторных работ

по дисциплине «Искусственный интеллект и экспертные системы»

Лабораторная работа №1. Основы работы в системе Prolog.

Лабораторная работа №2. Синтаксис и семантика программ на языке Prolog.

Лабораторная работа №3. Работы со списочными структурами при программировании на языке Prolog.

Лабораторная работа №1 Основы работы в системе Prolog.

Данная лабораторная работа предполагает изучение основ программирования на языке Prolog и освоение программной среды Prolog.

Задачи:

1. Изучить основы синтаксиса языка Пролог.

2. Научиться оформлять отношения между данными на языке Пролог на примере родственных отношений между членами семьи.

3. Научиться реализовывать рекурсивные вызовы.

Основные понятия программирования на Прологе

Программирование на Прологе – программирование в терминах логики. Программа на языке Пролог состоит из предложений. Каждое предложение заканчивается точкой.

Аргументами отношений могут быть атомы (константные объекты) или переменные. В тексте программы названия переменных начинаются с большой буквы или знака подчеркивания, а названия констант – с маленькой.

Программирование на языке Пролог состоит из следующих этапов:

• объявления некоторых фактов об объектах и отношениях между ними;

• определения некоторых правил об объектах и отношениях между ними;

• формулировки вопросов об объектах и отношениях между ними.

На Прологе отношения могут быть записаны в виде фактов и правил. В виде фактов записываются простейшие отношения. Имя отношения записывается с маленькой буквы, далее в круглых скобках – список аргументов через запятую. Если аргументов 2 и больше, то порядок их следования выбирается любой, но далее в аналогичных отношениях этот порядок должен соблюдаться. Например:

human(oleg).

fruit(orange).

man(nikolay).

man(stepan).

woman(lida).

parent(lida, stepan).

parent(nikolay, stepan).

Правила нужны для получения новых отношений из уже известных. Например:

father(X,Y):-parent(X,Y),man(X).

Что означает: X является отцом Y, ЕСЛИ X родитель Y И X является мужчиной.

mother(X,Y):-parent(X,Y),woman(X).

Вопрос к системе формируется в виде цели, которая может содержать переменные. В этом случае Пролог-машина проверит все возможно допустимые состояния переменных и найдет те из них, при которых цель достижима.

Приведенной выше программе можно задать вопрос:

?- parent(X,stepan).

Обратите внимание, что в конце вопроса обязательно нужно поставить точку.

Пролог-машина выдаст ответ:

X=lida

Если после этого ввести ; (точку с запятой), то Пролог-машина выдаст еще одно решение:

X=nikolay

Если снова ввести точку с запятой, Пролог-машина будет искать еще одно решение, и поскольку больше решений нет, она выдаст ответ:

No

Если после вывода очередного решения нажать клавишу Enter, то Пролог-машина не будет искать других решений и выдаст

Yes

Рекурсия

Определения отношений, в которых используется само отношение, называется рекурсивным. Рекурсия – один из основных механизмов программирования на Прологе.

Рекурсию можно применять для достижения такого же эффекта, какой реализуется при употреблении итеративных управляющих конструкций (циклов) в процедурных языках.

Примером использования рекурсии может служить определение отношения «предок». Данное отношение можно выразить с помощью двух правил. Первое правило будет определять непосредственных предков, а второе – отдаленных. Первое правило легко сформулировать через отношение «родитель»:

предок(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. рекурсивное правило – первая подцель, располагающаяся в теле этого правила, вырабатывает новые значения аргументов. Далее размещается рекурсивная подцель, в которой используются новые значения аргументов

В приведенном выше определении отношения «предок» первая фраза определяет исходный вид этого отношения. Как только она станет истинной, рекурсия прекратится. Вторая фраза – это рекурсивное правило. При каждом вызове данное правило поднимается на одно поколение вверх. Подцель «родитель(X, Y)» вырабатывает значение переменной Y, а в рекурсивной подцели «предок(Y, Z)» используется этот новый аргумент.

С помощью рекурсии в Прологе также можно решать математические задачи. Например, вычисление факториала:

factorial(0, 1) :- !.

factorial(N, X) :- M is N-1, factorial(M, Y), X is N*Y.

В данной программе «!» - символ отсечения (cut). Отсечение ставится для блокировки дальнейших вычислений.