Ответы по информатике

DOMAINS

name = symbol

PREDICATES

nondeterm father(name, name)

everybody

CLAUSES

father(leonard,katherine).

father(carl,jason).

father(carl,marilyn).

everybody:-

father(X,Y),

write(X," is ",Y,"'s father\n").

GOAL

 everybody.

  В данном случае  целью является  правило everybody, состоящее из двух подцелей. При обращении к подцели father(X,Y) система найдет первый подходящий факт father(leonard,katherine) и присвоит переменным X и Y соответствующие значения, после чего эти значения будут выведены на экран предикатом write(X," is ",Y,"'s father\n") и система возвратит. Откат не был произведен, поскольку вторая подцель правила была успешно выполнена. Теперь модифицируйте правило everybody чтобы оно выглядело так:

everybody:-

father(X,Y),

write(X," is ",Y,"'s father\n"),

fail.

  Предикат fail, стоящий после предиката write, вынуждает систему произвести откат даже тогда, когда решение найдено (предикат write возвращает истину), и таким образом найти все возможные решения.

leonard is katherine's father

carl is jason's father

carl is marilyn's father

yes

Значение  предиката fail всегда ложно, поэтому система вынуждена сделать откат к первой подцели в правиле. Обратите внимание на то, что в теле правила помещать подцель после предиката fail бесполезно, т.к. часть правила, начинающаяся с предиката fail, всегда терпит неудачу.

Из  примера видно, что  с помощью предиката  fail можно организовать многократно повторение одних и тех же действий. Общий вид правила, выполняющего повторение:

repetitive_rule:-   /* правило повторения */

<предикаты  и правила>,

fail.            /* неудача */

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

Встроенный  предикат отсечения  cut (обозначается символом ! ) имеет назначение, противоположное назначению предиката fail: этот предикат, вычисление которого всегда завершается успешно, запрещает откат, заставляя внутренние унификационные подпрограммы "забыть" все указатели отката, установленные во время попыток вычислить текущую подцель. Другими словами, предикат cut "устанавливает барьер", запрещающий выполнить откат ко всем альтернативным решениям текущей подцели. Следует однако помнить, что последующие поддели могут создать новые указатели отката, и тем самым создать условия для поиска новых решений, т.к. действие предиката cut на них уже не распространяется. Предикат cut (!) не имеет четкого декларативного смысла (т.е. он всегда будет истинным), поэтому при его употреблении будет наноситься некоторый ущерб понятности программы. Наличие данного предиката может непредвиденным образом нарушить работу программы.

Предикат  cut помещается в программу так же, как подцель помещается в тело правила. Когда во время обработки программы отладчику системы встречается предикат отсечения, подцель, предшествующая предикату cut, немедленно преуспевает, после чего  вызывается следующая подцель. После обработки предиката отсечения невозможно произвести откат к подцелям, расположенным в обрабатываемой фразе перед ним, и к предикатам, определяющим подцель, которая содержит отсечение.Отсечение используется в двух случаях: когда Вы заранее знаете, что некоторые пути никогда не приведут к значимым решениям, и поиск альтернативные решения означает бесполезную трату времени и памяти; когда логика программы требует исключить рассмотрение альтернативных подцелей; Очень часто система попусту тратит время на поиски несуществующих ответов. Рассмотрим правило registration, оперделяющее какие лица должны зарегистрироваться для прохождения обязательной воинской службы

    PREDICATES

       age(symbol, integer)

       male(symbol)

       registration(symbol)

    CLAUSES

       age(brayn,18).

       age(mike,17).

       age(stiv,18).

       male(brayn).

       male(mike).

       male(stiv).

       registration(X):-

         male(X),

         age(X,Y), Y=18.

    GOAL

       age(Who, 18), !.   % Найти всех, кому 18 лет

    ответ: Who=brayn

Задатим системе вопрос ”подлежит ли регистрации Брайен?" - regiatration(brayn). Интуитивно понятно, что лицо может иметь только один возраст, однако система будет автоматически просматривать базу данных age даже после того, как возраст Брайена уже определен. Если база будет иметь большой объем, этот бесполезный поиск займет много времени. Предикат cut (!) позволяет избавиться от просмотра ненужной информации, т.е. ”отсечь” ту часть пространства поиска, которую просматривает программа при поиске второго возраста Брайена, что не повлияет на способность программы находить правильные ответы. Следует помнить, что предикат cut (!) по-разному действует на составной запрос и на множество фраз программы (эти два вида действия следует четко различать между собой).Рассмотрим случай, когда предикат отсечения cut (!) является подцелью составного запроса. После того, как система пройдет этот предикат, невозможно будет возвратиться назад к подцелям, стоящим перед ним, т.е. система обязана использовать те значения переменных, расположенных в запросе слева от предиката cut (!), которые они получили при конкретизации. Пример составного запроса с предикатом cut (!):

GOAL

  subgoal_a(X),

subgoal_b(Y),

!,

subgoal_c(X, Y, Z).

Построим  базу данных хage, в которой каждая фраза является правилом с единственной подцелью - предикатом cut (!).

       xage(brayn,18):- !.

       xage(mike,17):- !.

       xage(stiv,18):- !.

       registration3(X):-

         male(X),

         xage(X,Y),

         Y=18.

8.Рекурсивное задание предикатов. Примеры.

При работе с данными  часто требуется  произвести такие  действия, как поиск  элементов в базе данных или вывод  данных на экран, выполнить  несколько раз. Система  Visual Prolog не содержит встроенных предикатов для выполнения повторяемых (циклических) действий, подобных функциям for, while и repeat декларативных языков. В Прологе существует два способа реализации правил, выполняющих одну и ту же задачу многократно: повторение и рекурсия. Правила, выполняющие повторение, используют откат, инициируемый предикатом fail, а правила, выполняющие рекурсию, используют самовызов. Правило, содержащее в своем теле в качестве компоненты само себя, называется правилом рекурсии. Вид правила, выполняющего рекурсию, следующий:  

    recursive_rule:-   /* правило рекурсии */

    <предикаты  и правила>,

    recursive_rule.

Последней подцелью тела правила recursive rule является само правило.

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

Классическим  примером рекурсивного определения  в Прологе является такая конструкция:

    ancestor(A, B):-   % предок_1

                parent(A, B).  

    ancestor(A, B):-   % предок_2

                parent(C, B),

                ancestor(A, C).

Если рекурсивное  правило не генерирует указателей отката и последняя подцель правила  является рекурсивным вызовом самого правила, система устранит вызываемые рекурсией дополнительные расходы. Этот процесс вызывается устранением  хвостовой рекурсии. Возникновения  бесконечной рекурсии можно избежать. Для этого следует ввести предикат завершения, содержащий условие выхода. Формулировка условия выхода для  правила write_string может иметь вид: "Продолжать печать строки до тех пор, пока счетчик печати не превысит число 7, после чего остановить процесс". Определение условий выхода и включение их в правило рекурсии является очень важным элементом программирования на Прологе. Следующая программа демонстрирует простое правило рекурсии, в которое включено условие выхода.

    DOMAINS

       data = char

    PREDICATES

       write_prompt

       read_a_character

    CLAUSES

       write_prompt :-

         write("Пожалуйста, введите символы "), nl,

         write("Для завершения введите #  "), nl.

       read_a_character :-

         readchar(Char_data),

         Char_data <> '#',

         write(Char_data),

         read_a_character.

    GOAL

       write_prompt,

       read_a_character. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

9.Составные объекты данных. Определение списка. Ввод и вывод списков. Примеры.

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

functor(object1, object2, ..., objectN)

Например, нам  нужно записать утверждение, включающее в себя дату, например 15 октября 1991 года. Структура, описывающая дату, представляет совокупность трех простых (представляющих самих себя)  объектов - день, месяц  и год. Объявление структуры date имеет вид:

DOMAINS

date_cmp = date(mounth, day, year)

mounth =string

day, year=unsigned

При обращении  к составному объекту указывается  его функтор, например

..., D = date("October",15,1991), ...

Параметрами составных объектов данных могут быть как простые, так  и составные объекты; например утверждение  “Уолтер Эдисон родился 14 апреля 1960 года” записывается в виде факта:

birthday(person("Walter","Edison"),date("Apr",14,1960))

где предикат birthday состоит из двух составных объектов с функторами person и date.

Составной объект может быть унифицирован с переменной или другим составным  объектом идентичной структуры, который  может включать переменные. Это означает, что  с помощью составной  структуры можно  передать множество  объектов как один, а затем используя унификацию по отдельности выбрать каждый объект. Например, факт

date("April",14,1960)

можно унифицировать с  переменной X, которая получит значение X=date("April",14,1960), или с фразой

date(Mo,Da,Yr)

причем  переменные получат  такие значения: Mo="April", Da=14, Yr=1960.

Составные объекты могут  интерпретироваться и обрабатываться системой как одиночные  объекты, что значительно  упрощает программирование. Рассмотрим такой  факт “Джон имеет  книгу “Отсюда  к вечности”, написанную Джеймсом Джонсом”

owns(john, book("From Here to Eternity", "James Jones")).

Предположим, существует другой факт “Джон имеет лошадь по кличке Блэки”

owns(john, horse(blacky)).

В этих фактах присутствуют простой объект john и два составных объекта book("From Here to Eternity", "James Jones") и horse(blacky). Если вместо рассмотренных фактов написать такие

owns(john, "From Here to Eternity").

owns(john, blacky ).

невозможно  будет понять, что  такое blacky - заголовок книги или кличка лошади. Таким образом, функторы составных объектов используются для того, чтобы можно было отличать различные объекты одинаковых предикатов.