Декартово произведение множеств.

Предикат dek определяет операцию декартова произведения двух множеств. Декартовым произведением двух множеств X={x_i} и Y={y_i} является множество Z, состоящее из пар элементов [x_i, y_i], где x_i принадлежат множеству X, а y_i принадлежат множеству Y.

Предикат dek(X,Y,Z) ¾истинен, если множество Z является декартовым произведением множеств X и Y. Схема отношения того предиката имеет вид:

dek(<список>,<список>,<список>).

В процедуре dek используются дополнительные предикаты pro и
append[6]. Предикат pro(X,Y,Z)¾истинен, если X есть терм, Y={Y_i}¾множество термов, а Z является множество пар вида [X, Y_i], где X есть заданный терм, а Y_i¾ соответствующий элемент множества Y. Схема отношения предиката pro имеет вид:

pro(<терм>,<список>,<список>).

Декларативное определение предиката pro(X,Y,Z) формулируется следующим образом.

v Список Y состоит из одного элемента. Тогда список Z является списком пар вида [X, Y_i].

v Список, определяющий множество Y можно разделить на голову Н и хвост T. Тогда список Z=[[X,H]|T1], если список список T1 есть результат процедуры pro(X,T,T1].

Декларативное описание предиката dek(X,Y,Z) формулируется следующим образом:   

v Список X состоит из одного элемента. Тогда список Z является результатом процедуры pro(X,Y,Z1.

v Список, определяющий первое множество Х можно разделить на голову X и хвост T1. Если pro(X,Y,T2) и dek(T1,Y,T3) и append(T2,T3,Z) истинны, то Z есть декартово произведение списков X и Y.

 Процедура pro(X,Y,Z) состоит из двух правил:

pro(X,[Y],[[X,Y]|[]]).
    pro(X,[H|T], [[X,H]|T1]):-pro(X,T,T1).

Процедура dek(X,Y,Z) состоит из двух правил:

dek([X|[]],Y,Z):pro(X,Y,Z).
    dek([X|T1],Y,Z):-pro(X,Y,T2), dek(T1,Y,T3),

append(T2,T3,Z).

Пример запроса к процедуре pro.

? ¾ pro(4,[1,2,3],Z).                                            

Z=[4,2],[4,3],[4,3]]

Yes

Пример запроса к процедуре dek.

? ¾ dek([4,2][3,5,8],Z).                                            

Z=[[4,3],[4,5],[4,8], [2,3],[2,5],[2,8]]

Yes

5.6 Пролог¾программы сортировки списков.

5.6.1. Метод прямого выбора.

Наиболее распространены три метода сортировки списков:

1. метод сортировки путем прямого выбора;

2. метод сортировки путем вставки;

3. метод сортировки с использованием перестановок элементов.

Алгоритм сортировки списка путем прямого выбора включает в себя следующие шаги:

1. В исходном списке S1 находится минимальный элемент Min и помещается в результирующий список S2.

2. Этот элемент удаляется из списка S1, и процедура поиска повторяется. С каждым шагом список S1 уменьшается.

3. Когда список S1 станет пустым, список S2 станет результирующим, упорядоченным по возрастанию списком.

Процедура sort_vibor использует следующие процедуры:

1. sort1(<исходный список>, <накапливающийся список>,
<результирующий список>) ¾ процедура накопления списка;

2. delete(<терм>, <список>, <список > ) ¾ процедура удаления элемента из списка;

3. append(<список>, <список>, <список > ) ¾ процедура объединения списков;

4. minlist(<список>, <терм> ) ¾ процедура определения минимального элемента в списке;

5. min(<терм>, <терм>, <терм> ) ¾ процедура определения меньшего из двух термов.

В 5-й процедуре сравниваются числовые термы с помощью операций сравнения чисел >, <, >=, =< или символьные термы с помощью операций сравнения символов (@>, @<, @>=,@=<.

Предикат sort_vibor(L1,LS)истинен, если список LS получен из списка L1 путем упорядочения списка L1 по возрастанию методом прямого выбора. Списки L1 и LS являются списками числовых термов.

Процедура sort_vibor(L1,LS)состоит из следующих правил:

sort_vibor(L1,LS):¾sort1(L1,[],LS).

sort1(L1,L2,LS):¾minlist(L1,Min),append(L2,[Min],L3),
delete(Min,L1,LL),sort1(LL,L3,LS).

sort1([],LS,LS).

delete(A,[A|B],B).

append([],|L,L).

append([X|L1],L2,[X|L3) :¾ append(L1,L2,L3).

minlist([X],X).

minlist([X,Y|T],M) :¾ minlist([Y|T],MinN),min(X,MinN,M).

min(X,Y,X) :¾X=<Y.

min(X,Y,Y) :¾X>Y.

5.6.2. Метод вставки.

Алгоритм сортировки списка путем вставки заключается в следующем: для того, чтобы упорядочить непустой список L = [X|T], необходимо:

1) упорядочить хвост списка, получив список OT;

2) вставить голову X списка L в упорядоченный список OT, поместив X в такое место списка OT, что список OT остался бы упорядоченным.

Процедура sort_insert использует процедуру insert, которая вставляет терм в упорядоченный список, не нарушая упорядочивания. 

Предикат insert(X,L1,L2) ¾истинен, если список L2 получается из упорядоченного списка L1 путем вставки терма X без нарушения порядка. Схема отношения этого предиката имеет вид:

insert(<терм>, <список>, <список>).

В процедуре insert сравниваются числовые термы с помощью операций сравнения чисел >, <, >=, =< или символьные термы с помощью операций сравнения символов (@>, @<, @>=,@=<.

Предикат sort_insert(L1,LS) истинен, если список LS получен из списка L1 путем упорядочения списка L1 по возрастанию методом вставки. Списки L1 и LS являются списками числовых термов.

Процедура sort_insert(L1,LS) состоит из следующих правил:

sort_insert([],[]).

sort_insert([X|T],OL):¾sort_insert(T,OT),insert(X,OT,OL).

insert(X,[],[X]).

insert(X,[Y|T],[X,Y|T]):¾ X=<Y.

insert(X,[Y|T],[Y|T1]):¾ X>Y,insert(X,T,T1).

Метод перестановок.

Алгоритм сортировки списка путем перестановки элементов заключается в следующем: для того, чтобы упорядочить непустой список L = [X|T], необходимо:

1. найти в списке L два смежных элемента X и Y, таких что X>Y,и поменять X и Y местами, получив таким образом новый список L1, затем рекурсивно применить эту процедуру к списку L1;

2. если в списке L нет ни одной пары смежных элементов X и Y, таких что X>Y, то список L упорядочен.

Процедура sort_p использует процедуру perest, которая переставляет два смежных элемента в порядке возрастания (или убывания). 

Предикат perest(L1,L2) ¾истинен, если список L2 получается из упорядоченного списка L1 путем перестановки. Схема отношения этого предиката имеет вид:

perest(<список>, <список>).

В процедуре perest сравниваются числовые термы с помощью операций сравнения чисел >, <, >=, =< или символьные термы с помощью операций сравнения символов (@>, @<, @>=,@=<.

Предикат sort_p(L1,LS) истинен, если список LS получен из списка L1 путем упорядочения списка L1 по возрастанию методом перестановки элементов. Списки L1 и LS являются списками числовых термов.

Процедура sort_p(L1,LS) состоит из следующих правил:

sort_p(L,OL): ¾ perest(L,L1),!,sort_p(L1,OL).

sort_p(OL,OL).

perest([X,Y|T],[Y,X|T]): ¾X>Y.

perest([Z|T],[Z|T1]):¾ perest(T,T1).

Стандартные предикаты языка Пролог.

Арифметические предикаты.

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

X+Y ¾ сложение,

X-Y ¾ вычитание,

X*Y ¾ умножение,

X/Y ¾ деление,

X//Y ¾ целочисленное деление ,

X^Y ¾ возведение в степень,

X/\Y ¾ побитовая конъюнкция (для целых чисел),

X\/Y ¾ побитовая дизъюнкция (для целых чисел),

X<<Y ¾ побитовый сдвиг влево на Y позиций (для целых чисел),

X>>Y ¾ побитовый сдвиг вправо на Y позиций(для целых чисел),

X mod Y ¾ остатот от деления X на Y(для целых чисел),

abs(X) ¾ абсолютная величина X,

acos(X) ¾ арккосинус X,

asin(X) ¾ арксинус X,

atan(X) ¾ арктангенс X,

cos(X) ¾ косинус X,

sin(X) ¾ синус X,

exp(X) ¾ экспонента X,

ln(X) ¾ натуральный логарифм X,

log(X) ¾ логарифм по основанию 10,

sqrt(X) ¾ квадратный корень X,

tan(X) ¾ тангенс X,

round(X,N) ¾ округление X до N десятичных знаков (0≤N≤15).

Арифметические термы (выражения) строятся из атомов и переменных с помощью арифметических операций. Допускается инфиксная и префиксная записи арифметический выражений. Арифметические термы без переменных являются константами.

6.2. Предикаты сравнения арифметических выражений и символьных термов.

Рассмотрим встроенные арифметические предикаты для унификации арифметических выражений. Пусть E1 и E2 ─ арифметические выражения. В Прологе существуют следующие встроенные предикаты для сравнения арифметических выражений:

E1>E2истинно, если Е1 больше Е2,

E1<E2истинно, если Е1 меньше Е2,

E1>=E2истинно, если Е1 больше или равно Е2,

E1=<E2истинно, если Е1 равно или меньше Е2,

E1=:=E2истинно, если Е1 равно Е2,

E1=\=E2истинно, если Е1 равно Е2,

E1=E2истинно, если Е1 и Е2 сопоставимы,

E1\=E2истинно, если Е1 и Е2 несопоставимы,

X is Eистинно всегда, и неконкретизированной переменной присваивается значение Е.

Пусть E1 и E2 ─ символьные термы. Для сравнения символьных термов используются другие встроенные предикаты:

E1@>E2истинно, если терм Е1 больше терма Е2,

E1@<E2истинно, если терм Е1 меньше терма Е2,

E1@>=E2истинно, если терм Е1 больше или равен терму Е2,

E1@=<E2истинно, если терм Е1 равен или меньше терма Е2.

Символьные термы упорядочены в алфавитном порядке; терм rбольше терма a.

Рассмотрим отличительные особенности перечисленных выше предикатов на примерах.

Пример 1.

Оператор унификации “=”        Оператор “is”

? – X=1+2.                                  ? – X is 1+2.

X=1+2 ->                                    X=3 ->

YES                                            YES

В случае унификации сопоставляются переменная Х составной терм 1+2, и устанавливается, что Х сопоставима с 1+2 при подстановке {X=1+2}.

Оператор is заставляет систему вычислить значение выражения справа от обозначения оператора, и это значение сопоставить с переменной X. 

Пример 2.

? – X is 3/2,Y is 3//2.

X=1.5 ->

Y=1 ->

YES

Различие между операторами унификации “=” и арифметического сравнения “=:=” состоит в том, что при выполнении оператора “=” система не производит вычислений, а оператор “=:=” производит вычисление выражений и сравнение и значений.

Пример 3.

Оператор унификации “=”        Оператор сравнения “=:=”

? – 1+2=2+1.                              ? – 1+2 =:= 2+1.

NO                                              YES

6.3. Предикаты определения типов термов.

Программист может предотвратить ошибки Пролога, проверив тип аргумента предиката с помощью следующих встроенных в Пролог-систему предикатов:

1) integer(X)истинно, если X—целое число;

2) float(X)истинно, если X—вещественное число;

3) number(X)истинно, если X— целое или вещественное число;

4) atom(X)истинно, если X—атом;

5)  atomic(X)истинно, если X—атом или число;

6) compound(X)истинно, если X—составной атом (структура);

7) novar(X)истинно, если X—константа;

8) var(X)истинно, если X—переменная.

9) string(X)истинно, если X—строка.