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

1. Структура Пролог-программы. Назначение разделов. Примеры.

Структура программы.

Программа, написанная на Visual Prolog, состоит из шести разделов (раздел констант, раздел доменов, раздел базы данных, раздел предикатов, целевой раздел и раздел утверждений) и может включать директивы компилятора. Каждый раздел программы начинается с предопределенного ключевого слова, а именно:

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

paздeл databasе coдepжит утвеpждeния, которые являются предикатами динамической базы данных (если программа такой базы данных не требует, то этот раздел может быть опущен);

раздел domains содержит определения доменов (типов), которые описывают различные классы объектов, используемых в программе;

в разделе predicates объявляются используемые  в программе предикаты;

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

раздел goal содержит формулировку цели создаваемой программы.

Последние четыре раздела являются базовыми. Обычно программа требует по крайней мере разделы predicates и clauses. Для большинства программ раздел domains необходим для объявления списков, составных структур и пользовательских доменов. И наконец для того, чтобы система сгенерировала автономное приложение, ваша программа должна содержать цель (раздел goal), причем только одна цель может быть выполнена в течение трансляции. Таким образом, базовая структура программы на языке Visual Prolog имеет вид:

DOMAINS% объявление доменов

argument_type1, ..., argument_typeN = <standard domain> 

PREDICATES% объявление предикатов

predicateName(argument_type1, argument_type2, ..., argument_typeN)

CLAUSES% объявление фактов и правил

clauses (rules and facts)

GOAL% задание цели программы

subgoal_1,

subgoal_2 , …

subgoal_N . 

   

2. Типы доменов  Пролог-программы. Стандартные домены. Примеры.

Доменом параметра  является стандартный (встроенный) домен  языка, либо домен, объявленный программистом  в разделе domains. Рассмотрим основные стандартные домены

Новые домены целесообразно  объявлять по двум причинам: во-первых, можно объявлять структуры данных, не предусмотренные стандартными доменами, а во-вторых, даже если аргумент принадлежит  стандартному домену, его имя будет  более информативно, например предикат person(name, sex, age) более понятен, чем person(symbol, symbol, integer). Если в объявлениях предикатов программы используются только стандартные домены, раздел domains может быть пропущен. Следующий предикат иллюстрирует использование доменов различных типов:

DOMAINS  

employee_name = symbol

pay_rate = integer

weekly_hours = real 

PREDICATES 

payroll (employee_name, pay_rate, weekly_hours)

CLAUSES

payroll ("John Walker", 16, 45.25).

payroll ("Arthur Berman", 28, 32.50).

payroll ("Sandy Taylor", 23, 40.00).

Функция, возвращающая возведенное в куб число объявлен следующим образом:

PREDICATES

integer cube(integer)

CLAUSES

cube(In,Out):- Out = In*In*In.

Рассмотрим основные форматы объявления нового домена:

name = d /* Стандартный домен */

my_CompDom = f1(d11,d12,...,d1n); /* Составной объект */

                           f2(d21,d22,...,d2n);

mylist = elementDom*    /* Список */

Стандартный домен: такое объявление определяет домен  name, который состоит из элементов стандартного домена d, который может быть char, real, ref (ссылка), string, symbol или одним из целых типов.

 
 
 
 
 
 
 
 
 
 
 

3. Определение предикатов Пролог-программы. Примеры.

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

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.

4. Определение раздела предложений. Использование переменных в правилах. Примеры.

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

Использование переменных значительно расширяет  возможности программы, позволяя записывать более общие правила. Так, если в  определении правила cоntact вместо констант употребить переменные, то можно будет установить, что любые два человека, работающие в одну смену, знают друг друга

 соntact_1 (A, B):-   

            job_relay (A, Relay), 

            job_relay (B, Relay).

Переменная  Relay входит в обе подцели данного правила; в каждой подцели она должна иметь одно и то же значение. Правило соntact_1 является гораздо более общим, чем правило соntact. Правило, в состав которого входят переменные, можно рассматривать как неявное определение множества фактов: правило соntact_1 содержит те же сведения, что и база данных, состоящая из фактов

соntact_1 (sam, bob).

соntact_1 (sam, tony).

соntact_1 (bob, tony).

Отметим, что  база фактов job_relay является явной, т.к. она состоит из фактов, аргументы которых – константы; соntact_1 – это  неявная база данных, поскольку правило соntact_1 определено с использованием переменных, значения которых зависят от подцелей тела данного правила. Область действия переменной, входящей в правило, ограничивается этим правилом (в Прологе отсутствуют глобальные переменные). В качестве имени предиката или переменной предпочтительнее использовать не одиночную букву, а осмысленную строку символов, раскрывающую назначение данного объекта.

Примечание 5: в Прологе переменные начинаются с заглавной буквы или значка подчеркивания ( _ ), а константы – со строчной. Константой также является строка заключенная в двойные кавычки (“ ”), поэтому если Вы хотите, чтобы константа начиналась с заглавной буквы, заключите ее в кавычки (“Mary”)

5. Виды запросов Пролог-программы. Поиск решений. Унификация и откат. Примеры.

Простой запрос состоит из имени предиката, за которым следует список аргументов, т.е. по сути это обычный факт. Аргументами запроса могут быть как константы, так и переменные. Если в запрос не входят переменные, система выдаст один из двух ответов: yes или no Положительный ответ (yes) говорит о том, что система смогла доказать истинность запроса в соответствии с множеством фактов и правил программы, в противном случае – no. Например, на запрос

likes (cindy, tennis).% Нравится ли Cинди играть в теннис?

система ответит  yes поскольку существует факт Тому нравится играть в теннис и правило Синди нравится все то, что нравится Тому. Другой пример  likes (caitlin, frog). % Нравится ли Кэтрин лягушка?

ответ системы  yes Этот вывод был сделан в соответствии с правилом likes (caitlin, Something):- green(Something). и фактом green (frog). Использование в запросах переменных позволяет получить более полную информацию: система отыскивает и возвращает все значения этих переменных, при которых запрос будет истинным. Например, на запрос likes (Who, tennis). %  Кому нравится теннис?система ответит (проследите, как переменная Who получила нижеследующие значения)

    Who = tom

    Who = cindy

    2 Solutions

Составной запрос образуется из нескольких простых запросов, соединенных между собой логической связкой and (,) или or (;). В рассмотренных до сих пор телах правил подцели связывались друг с другом посредством соединителя and (и), однако подцели можно также связывать соединителем or (или). Рассмотрим запрос a(X), b(X,Y); c(Z).

Каждый простой  запрос, входящий в составной, называется подцелью. Для того, чтобы составной запрос оказался истинным, необходимо чтобы каждая подцель была истинна. Для истинности данного запроса нужно либо чтобы одновременно две подцели - a(X) и b(X,Y) – были истинными, либо чтобы подцель c(Z) была истинной. Если подцель a(X) потерпит неудачу, система пропустит подцель b(X,Y) и попытается обработать подцель c(Z), что значительно уменьшит время поиска (в случае просмотра большой базы данных). Например, запрос

wife(X, donald), rich(X); rich(donald).будет истинным, если либо у Дональда есть жена и она богата, либо если Дональд сам богат. Рассмотрим использование составных запросов на примере:

PREDICATES

  car (symbol,long,integer,symbol,long)

  truck (symbol,long,integer,symbol,long)

  nondeterm vehicle (symbol,long,integer,symbol,long)

CLAUSES

  car(chrysler,130000,3,red,12000).

  car(ford,90000,4,gray,25000).

  car(datsun,8000,1,red,30000).

  truck(ford,80000,6,blue,8000).

  truck(datsun,50000,5,orange,20000).

  truck(toyota,25000,2,black,25000).

  vehicle(Make,Odometer,Age,Color,Price):-

  car(Make,Odometer,Age,Color,Price);

    truck(Make,Odometer,Age,Color,Price).

GOAL

  car(Make, Odometer, Years_on_road, Body, 25000).                    % Найти легковой автомобиль, цена которого $25,000.

    Ответ системы

Make=ford, Odometer=90000, Years_on_road=4, Body=gray

1 Solution

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

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

   

6. Принудительный  откат с помощью предиката  fail. Повторения предикатом repeat. Примеры.

Система Visual Prolog производит откат (ищет другое решение) в том случае, когда проверка текущего факта на соответствие подцели потерпела неудачу; если же цель программы полностью удовлетворена отката не происходит. Однако, в некоторых случаях требуется помимо одного решения также найти альтернативные, т.е. необходимо вынудить систему произвести откат. Это делается с помощью специального предиката fail. Следующий пример иллюстрирует использование этого предиката.