«Пролог логикалық программалау тілі»

GOAL

Егер бұл бағдарламаны іске қосатын болсақ, ол өзінің жұмысын диалог терезесінде ештенені шығармай аяқтайды. Себебі, бағдарламада ішкі мақсат болатын болса, Турбо Пролог диалогтық терезеде айнымалылардың мəнін көрсетпейді, ал __________сыртқы мақсатты іске асырған кезде Турбо Пролог трезеге сұрақта бар барлық айнымалыларды шығарады. Бұл сыртқы мен ішкі мақсаттың ең бірінші маңызды айырмашылығы.

Бірақ та іште құрастырылға write предикаттын қолданып, мақсатасты ретінде B жəне V айнымалыларды қоса отырып ішкі мақсаттың есептеу нəтижесіндегі шешімін экранға шығаруды біз өзіміз ұйымдастыруымызға болады.

Ішкі мақсатты сипаттау бөлімі, мысалы, мынадай болуы мүмкін:

GOAL grandmother(B,V),write("Имя бабушки — ",B), write(",

имя внучки — ",V),nl Бұл кезде біз экранда əже мен немеренің атын көреміз, бірақ диалог терезесінде екі шешім емес тек бір ғана шешім шығады:

Əженің аты — Наташа, енмеренің аты — Маша.

Бағдарламада ішкі мақсат болатын болса, Турбо Пролог сыртқы мақсат жағдайында сияқты барлық мүмкін айнымалыларды мəндендіруді емес, тек мүмкін болатын біреуін ғана табады. Бұл сыртқы мен ішкі мақсаттардың екінші ерекшелігі. Егер бізге барлық шешімдер керек болатын болса, оныəдейі ұйымдастыру керек, мысалы, сəтсіздіктен кейінгі шегіну əдісі арқылы. Жаңа предикаттарды кейінге қалдыру сатысында сыртқы мақсаттар қолданылады.

Егер бізге өңдеу ортасынан тыс іске қосыла алатын бағдарлама керек болатын болса, онда оның ішінде міндетті түрде ішкі мақсат болуы керек. Сəтсіздіктен кейінгі шегіну əдісінде негізінде əрдайым алдындағы лекцияда айтылған жалған предикат fail қолданылады. Бірақ та, бұл предикаттың орнына қандай да бір біле тұра жалған айтылуды қолданылуға болады.

Мысалы, 1=2 немесе осы сияқты.

Егер біздің ішкі мақсатымызға fail предикатын қосатын болсақ, онда диалог терезесінде сыртқы мақсатты қолдана отырып осы сұрақты қойғанда көре алатын екі шешімді алатын боламыз:

Əженің аты — Наташа, немеренің аты — Маша

Əженің аты — Наташа, немеренің аты — Саша.

Мысал. Енді write стандартты предикаты арқылы барлық қыздардың аттарын экранға шығаратын предикат жазайық.

show_names:–

mother(_,Name), /* Name айнымалысы

қыз атымен */

write(" ", Name), nl,

/* айнымалының мəнін шығарады

Name на экран */

fail. /* қайта оралу нүктелер стекінде сақталған орынға шегінуді */

Осы предикатты, оның сипаттамасын PREDICATES бөліміне қосуды ұмытпай, мамалар мен əжелер туралы біздің бағдаламаға жазайық. Ішкі мақсат ретінде "Имена дочек:" хабарламасын шығаруды көрсетейік (write предикаты арқылы), nl стандартты предикат арқылы курсорды келесі жолға ауыстырайық. Үшінші мақсатасты ретінде барлық қыздардың атын шығаратын show_names предикатын жазып алайық.

GOAL

show_names.

Бұл бағдарлама қалай жұмыс істейді? Ең алдымен "Имена дочек:" жол шығарылады, содан соң келесі жолға өтеміз. Бұдан кейін show_names мақсатасты орындалады.

Осы мақсатастыны есептеу кезінде унификация механизмі mother предикатын сипаттайтын процедураның бірінші сөйлемінде екінші аргумент кейпінде көрсетілген айнымалыны қыздың атымен белгілейді. Name айнымалысы "Маша" мəніне ие болады. Сонымен қатар қайта оралу стекінде mother(_,Name) мақсатастының басқа шешімдерін алу үшін шегінуге болатын жерге сілтеуші барын көрсететін жұлдызшаны трассировка терезесінде көруге болады. Write предикаты арқылы "Маша" аты экранға шығарылады. Осыдан кейін fail предикаты ережені сəтсіз аяқтауды шақырады, содан соң стекке ең соңғы енгізілген нүктесіне шегіну іске асырылады. Бұл үрдіс mother(_,Name) мақсатастыға қол жеткізудің барлық əдістері біткенше дейін жалғаса береді. Диалог терезесінде барлық қыздардың аттар тізімі біздің бағдарламада көрсетілген ретпен шығарылады:

Имена дочек:

Маша

Глаша

show_names2(Mother):–

mother(M,Name), /* Name айнымалысын маманың қызының атымен белгілейді

Mother */

M=Mother, /* M

жəне Mother */ мамалардың аттарының сəйкестігін тексереді

write(" ", Name), nl, /* Name айнымалысының мəнін экранға шығарады */

fail. /* қайта оралу нүктелер стекінде сақталған жерге шегінуді шақырады */

Бастапқы екі мақсатастының орнына mother(M,Name), M=Mother альтернативтік нұсқаны жазуға болады: mother(Mother,Name). Оның нəтижесі содай, бірақ есептеу үрдісі ерекшелеу болады. Модифицияланған предикат арқылы Дашаның қыздарының аттарын шығарайық.

Бұл үшін ішкі мақсатты мынадай қылып өзгертеміз:

GOAL

write("Имена дочек Даши:"),nl,

Барлық қыздардың аттарын шығаратын предикаттан осы предикаттың жұмыс істеу ерекшелігі келесіде. М айнымалысы кезекті маманың атымен белгіленгеннен кейін оның мəнінің "Даша" атымен сəйкестігін тексереді. Сəйкес болған кезде Дашаның қызының аты шығады да, шегіну орындалады. Ал егер аты "Даша" атынан өзгеше болатын болса, шегіну дəл сол мезетте орындалады. Бұл жағдайда бағдарламаны орындау қыздың атын экранға шығаруға дейін жете алмайды. fail предикаты M=Mother мақсатасты өзінен өзі сəтсіз болғандықтан керек емес болып қалады. Əйтсе де, fail стандартты предикаттың ереженің соңғы мақсатасты түрінде болуы M=Mother мақсатасты сəтті болған жағдайда шегінуді шақыру үшін керек.

Бұл бағдарламаның жұмысы аяқталған кезде диалогтық терезеде нəтижені көруге болады:

Имена дочек Даши:

Маша

Саша

1. Тереңдікте іздестіру əдісі.

2. Сəтсіздіктен кейінгі шегіну.

3. Кесу жəне шегіну.

4. Қолданушымен анықталатын іздестіру əдісі.

5. Бэктрекинг не істейді?

6. Мақсатастынан мақсатастыға қалай өтуге болады?

7. Предикатты модификациялау қалай жүргізіледі?

Тізімдер. Тізімді рекрусивті анықтау. Тізімдермен операция жасау.

болып табылады. Прологта да Лиспада сияқты мəліметтер түрінің негізгі құрамы тізім болып табылады. Бұл дəрісте тізімдерді меңгерумен айналысамыз. Бастапқыда тізімге формалды емес анықтама берейік.

Тізімді элементтер ұзындығының реттелген дəйектілігі деп атайық.

Төменде көрсетілген мысалдар сияқты тізімдер – тізімдердің элементтері үтір арқылы жазылып,тік жақшаның ішінде беріледі.

[monday, tuesday, wednesday, thursday, friday, saturday, sunday] — ағылшын тіліндегі аптадағы күндердің аты элементтерінің тізімі;

["понедельник", "вторник", "среда", "четверг", "пятница", "суббота", "воскресенье"] — орыс тіліндегі аптадағы күндердің аты элементтерінің тізімі;

[1, 2, 3, 4, 5, 6, 7] — аптадағы күндердің номері элементтерінің тізімі;

['п', 'в', 'с', 'ч', 'п', 'с', 'в'] — орыс тіліндегі аптадағы күндер номерінің бірінші əріптерінің элементтерінің тізімі;

[] — бос тізім , яғни элементтерден тұрмайтын тізім.

Тізімдер элементі түрлі болуы мүмкін ,соның ішінде құрамды объекттер. Тізімдер элементтерінің өзі тізімдер болуы мүмкін.

Домендерді жазу бөлімінде тізімдер келесідей түрде жазылады:

DOMAINS

<домен тізімінің аты>=<домен тізімі элементінің аты>*

Домен атынан кейінгі қойылған жұлдызша, объекттердің сəйкес типінен құралған тізімді бейнелеуін көрсетеді.

Мысалы:

listI = integer* /*бүтін сандардан тұратын элементтер тізімі */

listC = char* /* символдар тізімі*/

lists = string* /* жолдардан тұратын тізім*/

listL = listI* /* бүтін сандар тізімі элементтерінен тұратын тізім */

Соңғы мысалға сəйкес болатын тізім түрі:

[[1,3,7],[],[5,2,94],[–5,13]]

Классикалық Прологта тізімдер элементі түрлі домендерге жатуы мүмкін, мысалы: [monday, 1, "понедельник"]

Турбо Прологта ,қатал типизацияға байланысты барлық тізімдер элементі бір доменге жатуы керек. Доменге сəйкес альтернативаларды қолданып, түрлі табиғат объектлерін бір тізімге орналастыруға болады.

Мысалы, келесідей жазулар:

DOMAINS

listE = element*

тізімдер түрімен жұмыс істеуге мүмкіндік береді

[i(–15), s("Мама"),c('A'),s("мыла"),c('+'),s("раму"),

i(48),c('!')]

Тізімдерге рекурсивті анықтама берейік.

1. Бос тізім ([ ]) тізім болады;

2. [H|T] құрылым түрі тізім болады егер, H — тізімнің бірінші элементі , ал T — нəтижелі тізімде қалған элементтерден тұратын тізім Н-ді тізім басы деп ,ал Т-ны тізімнің аяғы деп айту қабылданған. Басы мен аяғын білдіру үшін айнымалыны таңдау кездейсоқ еместігін ескерейік. Head – ағылшын тілінде басы, ал Tail - аяғы.

(І) операциясы тізімді басы мен аяғы деп бөлуіне мүмкіндік береді , немесе керісінше объектті тізім басына жазуын.

Берілген анықтама бос емес тізімді басы мен аяғына бөліп ,тізімді рекурсивті өңдеуін ұйымдастыруға мүмкіндік береді. Аяғы да өз бетінше, нəтижелі тізімге қарағанда аз элементтерден тұратын тізім болып табылады .Егер аяғы бос болмаса , онда оны да басы мен аяғына бөлуге болады.Басы жоқ бос тізімге жеткенше осылай болады.

Мысалы, [1, 2, 3] тізімінде 1 элементі басы болады, ал [2, 3] тізімі — аяғы, яғни [1, 2, 3] =[1|[2, 3]].

Бұл тізімнің аяғы [2, 3] екенін ескерейік , жəне ол басы 2 ал аяғы [3] болып берілуі мүмкін, [3] тізімінде басы 3 жəне аяғы [2] деп қарастыруға болады. Келешекте бос тізім бөлінбейді.

Нəтижесінде [1, 2, 3] тізімі [1|[2, 3]] тізіміне эквивалентті, ал оның өзі [1|[2|[3]]] тізіміне эквивалентті. Соңғысын [1|[2|[3|[ ]]]] тізімімен салыстырайық.

Бұл тізімде екі бірінші элементті жəне [1,2|[3]] үшінші элементтің аяғын атап көрсетуге болады.

[1, 2, 3|[]] бос аяқ пен үш бірінші элементтің басын бөлу мүмкіндігі бар.

Жоғарыда көрсетілген рекурсивті анықтамаға сəйкес тізімді өңдеуді ұйымдастыру үшін рекурсияның базисі болатын сөйлемнің қойылымы жеткілікті жəне барлық бос емес тізімнен оның аяғын өңдеуге өту тəртібін орналастыратын рекурсивті ереже. Кейбір кезде базис рекурсиясы бос тізімге емес,тізімнің бір немесе екі элементін жазуға арналады.

Біздің пайымдауымызға байланысты резюме ретінде Бэкуса–Науэра нотациясында тізімге тағы бір анықтама берейік:

Тізім::= [ ]|[Элемент <,Элемент>*]|[Басы|Аяғы ]

Басы ::= Элемент <,Элемент>*

Аяғы ::= Тізім

Тізімдерді өңдеуін қарастырайық.

length([], 0). /* бос тізімде элементтер жоқ */

length([_|T], L) :–

length(T, L_T), /* L_T — аяғындағы элементтер саны */

L = L_T + 1. /* L — нəтижелі тізімнің элементтер саны */

Барлық тізімнен оның аяғына өткенде тізімнің бірінші элементі неге тең екендігі қажет емес, сол үшін белгісіз айнымалыны қолданамыз.

Қалай жұмыс істейтіндігін мысалда қарастырайық. [1,2,3] тізіміндегі элементтер саны бізге керек болсын . Пролог-жүйеге сəйкес сұрақты жазайық:

length([1,2,3],X).

Жүйе басында біздің мақсатымызды бірінші length([], 0) ұсынысымен салыстыруға тырысады , бірақ оны жасау мүмкін емес, өйткені аргументтің бірінші мақсаты бос емес тізім болып табылады.Жүйе процедураның екінші ұсынысына көшеді. Тақырыпшамен салыстыру ереже бойынша табысты, X айнымалысы L айнымалысымен байланысады, [1,2,3] тізімі [_|T] тізімімен салыстырылады, T айнымалысы [2,3] мəнімен нақтыланады. Енді жүйе length(T,L_T) мақсатына жетуге тырысады. Алдыңғы жағдайлар сияқты Т тізімі бос емес болғандықтан бірінші ұсыныс мақсатымен салыстырылмайды. Тақырыпты ереже мақсатымен салыстыру кезінде Т аяғы бірэлементті [3] тізімімен нақтыланады . Рекурсияның келесі қадамында Т айнымалысы бос тізіммен белгіленген. Яғни біздің мақсатымыздың түрі мынандай: length([], L_T). Бұл мақсат фактпен салыстырылады, L_T айнымалысы 0-ге тең болады. Рекурсияның қайта жолын кері айналдыру: L_T айнымалысы бір бірлікке көбейеді , нəтижесі L айнымалысына кіреді. Осыдан [3] тізімінің ұзындығы бірге тең болатындығын аламыз.Келесі кері қадамда тағы бір бірлік қосылады , осыдан кейін [2,3] тізімінің ұзындығы екімен нақтыланады. Соңғы қайтарылған қадамда L айнымалысының 3 санымен білдірілуі көрсетіледі .

Мысал. Элементтің тізімге жатуын тексеруге мүмкіндік беретін предикат құрайық.

Предикат екі аргументтен тұрады: біріншісі — ізделінді мəн , екіншісі — тізім, онда іздеу жүргізіледі.

Берілген предикатты мынандай фактке қарап құрайық : объект тізімге жатсын , ол не тізімнің бірінші элементі болады не аяғының элементі болады. Бұл екі сөйлем түрінде жазылуы мүмкін:

member(X,[X|_]). /* X —тізімнің бірінші элементі*/

member(X,[_|T]) :–

member(X,T). /* X аяққа жатады T*/

Бірінші жағдайда тізімнің аяғы қандай екендігі ескерілген жоқ ,сондықтан аяғы ретінде белгісіз айнымалыны көрсетуге болады .Егер екінші жағдайда Х аяққа жатса , бізге бірінші элемент қандай екендігі қажет емес.

Жазылған предикатты екі жағдайда қолдануға болатындығы белгілі: біріншіден, оны не үшін құрдық соған байланысты , яғни тізімде нақты мəн бар ма екендігін тексеру үшін. Біз, мысалы , [1, 2, 3]тізіміне екі жататындығын тексереміз :

member(2, [1, 2, 3]).

Əрине "Yes" жауабын аламыз.

Осылайша , 4 саны [1, 2, 3] тізімінің элементіне кіре ма екендігін сұрауға болады:

member(4, [1, 2, 3]).

Əрине жауабы "No" болады.

Берілген предикатты қолданудың екінші əдісі — олардың элементтерін тізім бойынша алу.

Ол үшін предикаттың бірінші аргументі ретінде бос айнымалыны көрсету керек. Мысалы:

member(X, [1, 2, 3]).

Нəтиже ретінде тізімнің барлық элементтер тізімін аламыз:

X=1

X=3

member(1, X).

Басында Пролог-жүйе X айнымалысының бірінші ұсыныспен байланысты еместігін ескереді

("708 WARNING: The variable is not bound in this clause. (F10=ok, Esc=abort)").

Осы ескертудің назар аударылуына 2 тəсіл бар: бірлікті құрайтын элемент ретінде генерация тізімінен бас тарту үшін Esc батырмасын басу; мақсатты орындауды жалғастыру үшін F10 батырмасын басу. Екінші жағдайда бірлікті құрайтын тізімдер нұсқасын Пролог-жүйе бере бастайды:

X=[1|_] /* бірлік — тізімнің бірінші элементі */

X=[_,1|_] /* бірлік — тізімнің екінші элементі */

X=[_,_,1|_] /* бірлік — тізімнің үшінші элементі */

жəне т.б

Бұл процесс Ctrl+Break батырмасын басқанша жалғаса береді.

Егер берілген предикатты тек бірінші тəсілмен қолдану жоспарланса , тізімнің аяғында элементті іздеуді жойып оның жұмысын тездетуге болады , егер ол тізімнің бірінші элементі ретінде табылған болса.Оны екі тəсілмен жасауға болады.

Бірінші тəсіл. Тізімнің бірінші элементі ізделінді элементпен сəйкес келмейтіндей тексеру ережесіне қосайық жəне тізімнің бірінші элементі ізделінді болмаған жағдайда тізімнің аяғында элементті іздеу. Модифицирияланған предикаттың түрі келесідей:

member2(X,[X|_]).

member2(X,[Y|T]):–

X<>Y, member2(X,T).

Member предикатының модификациясын тізімнің барлық элементтерін алуға қолдануға болмайтындығын ескерейік. Бірінші аргумент ретінде байланыспаған айнымалыны қойсақ , онда мақсатты келістіру кезінде белгіленбеген Х айнымалысы белгіленбеген У айнымалысымен салыстырылады. Қате туралы хабарлама аламыз"Free variable in expression".

Екінші тəсіл. Тізімнің бірінші элементі ізделінді элемент болғанда бастапқы тізімнің аяғында керек емес іздеу болмайтын фактті қосайық.Алатынымыз:

member3(X,[X|_]):–!.

member3(X,[_|T]):–

member3(X,T).

Member предикатының модификациясы бастапқыға қарағанда тиімдірек болғанымен , ізделінді элемент табылғаннан кейін аяғында іздеу жұмысы орындалмайды, оны тізімде нақты мəн бар екендігін тексеруге қолдануға болады. Егер біз байланыспаған айнымалының бірінші аргументі ретінде қойып тізімнің барлық элементтерін алуға қолдансақ, онда нəтижесі тек тізімнің бірінші элементі болады. Қалған элементтерді алуға кесу мүмкіндік бермейді.

Мысал. Екі тізімді қосып бір тізім жасайтын предикат құрайық . Предикаттың бастапқы екі аргументі біріктірілген тізімді көрсетеді , ал үшіншісі – біріктіру нəтижесін.

Бұл есепті шығарудың негізі ретінде бірінші тізім бойынша рекурсияны аламыз.

Рекурсияның базисі ретінде мынандай факт орнатамыз, егер тізімге бос тізімді қоссақ , онда нəтижесінде бастапқы тізімді аламыз. Рекурсияның қадамы басы мен аяғынан тұратын тізімнің элементтерін қайта жазуын анықтайтын ереже құруға , ал екінші тізімге екінші тізім мен аяғын қосып нəтижесіне бірінші тізімнің бірінші элементін алдына жазуға мүмкіндік береді.Шешімді жазайық:

conc([ ], L, L). /* бос тізіммен L тізімін біріктіргенде L тізімін аламыз */

conc([H|T], L, [H|T1]) :– conc(T,L,T1). /* L тізімі мен аяғын біріктіреміз де аяғының нəтижесін аламыз */

Бұл предикатты басқа көптеген есептерді шешуге қолдануға болатындығын ескерейік.

Біріншіден , тізімдерді біріктіру үшін. Мысалы, егер мынандай сұрақ қойсақ

conc([1, 2, 3], [4, 5], X) нəтижесінде алатынымыз X= [1, 2, 3, 4, 5]

Екіншіден ,екі тізімді біріктіргенде үшіншісін алуға болатындығын тексеру үшін. Мысалы ,

сұрақ :

жауабы əрине No болады.

Үшіншіден , бұл предикатты тізімді жазылымға бөлу үшін қолдануға болады. Мысалы, егер келесідей сұрақ қойсақ :

conc([1, 2], Y, [1, 2, 3]).

жауабы Y=[3].

мынандай сұраққа

conc(X, [3], [1, 2, 3]).

алатын жауабымыз X=[1, 2].

Енді сұрауға болады

conc(X, Y, [1, 2, 3]).

Төрт шешім аламыз:

X=[], Y=[1, 2, 3]

X=[1], Y=[2, 3]

X=[1, 2], Y=[3]

X=[1, 2, 3], Y=[]

Төртіншіден , бұл предикатты берілген элементтен оңға жəне солға қарай орналасқан элементтерді іздеуге қолдануға болады. Мысалы , егер бізді қандай элементтер 2 санының оң жағында жəне оған сəйкес сол жағында орналасқанын білгіміз келсе, онда мынандай сұрақ қоямыз:

conc(L, [2|R], [1, 2, 3, 2, 4]).

Екі шешім аламыз:

L=[1], R=[3, 2, 4].

L=[1, 2, 3], R=[4]

Бесіншіден , тізімнің соңғы элементін табатын conc предикатының негізінде предикат құру:

last(L,X):–

conc(_,[X],L).

Бұл предикатты conc предикатын қолданбай-ақ тікелей қолдануға болады :

last2([X],X). /* бұл элемент – бірэлементтік тізімнің соңғысы */

last2([_|L],X):–

last2(L,X). /* тізімнің соңғы элементі аяғының соңғы элементімен сəйкес келеді */

Алтыншыдан , conc, предикатты қолданып , элементтің тізімге жатуын тексеруді анықтауға болады. Егер элемент тізімге жатса , онда тізім екі тізімшеге бөлініп, ол ізделінді элементтің екінші тізімшесінің басы болуы мүмкіндігін қолданамыз:

member4(X,L):–

conc(_,[X|_],L).

Жетіншіден, тізімдерді біріктіруге болатын предикатты қолдана , тізімнің элементтері көршілес мəндерін тексеретін екі мəнді тізімді предикат құру . Предикаттың үш параметрі болады:екі біріншісі— мəні , үшіншісі — тізім.

Шешімнің қорытындысы келесідей болады. Егер тізімде екі элемент көршілес болса, онда бұл тізімді екі тізімшеге жіктеуге болады жəне екінші тізімшенің басы дұрыс тəртіпте біздің екі элементтен тұрады. Оның түрі келесідей болады:

neighbors(X,Y,L):–

c onc(_,[X,Y|_],L). /* тізімнің кейбіреуін біріктіруден L тізімін аламыз ,басы X и Y элементтерінен тұрады */

Бұл предикат көрсетілген тəртіпте керекті мəндерді тексеретініне назар аударыңыз. Егер бізге кейбір тізімде екі берілген мəн кездессе, оның тəртібінің қажеті жоқ , ізделінді элементтің орнын тексеретін нұсқаны алып одан көрсетілген предикаттың модификациясын жазып алу қажет. Ол үшін тізімді екі тізімшеге орналастырып жəне екінші тізімшенің басы біздің екі элементтерден тұратын болса жеткілікті. Сəйкес программалық кодтың түрі мынандай:

neighbors2(X,Y,L):–

conc(_,[X,Y|_],L);

conc(_,[Y,X|_],L). /*кейбір тізімді біріктру жолынан L болады, басы X

жəне Y элементтерінен құралады */

Негізгі əдебиет 1 [35-49]

Қосымша əдебиет 3 [78-88]

Бақылау сұрақтары:

1. Тізімдер.

2. Тізімді рекурсивті анықтау.

3. Тізімдер бойынша операция жасау.

4. Тізім қалай беріледі.

5. Бос тізім құруға бола ма?

6. Аптаның күндерінін тізімін сан етіп қалай жасауға болады?

7. Аптаның күндерінін тізімін əріп етіп қалай жасауға болады?

Орташа жəне минималды мəнді, тізімдегі элементтердің суммасын табу қарастырылады; тізімдерді іріктеу алгоритмі: көпіршіктік, таңдау , қыстыру , қосылуы , жылдам сұрыптау.

Осылайша, біз жұмыс істеуге жоспарланған тізімдерді, домендерді сипаттайтын бөлімде келесідей берілуі мүмкін:

DOMAIN listI= integer* Енді бұдан қызық мəселеге көшейік, анығырақ айтқанда,тізімдерді іріктейік. Іріктеу дегенде элементтердің кейбір тізімде қойылуын түсінеді. Анық болу үшін, тізім элементтерін кему емес бойынша орналастырамыз. Яғни, егер тізімдегі кез-келген жақын екі элементті салыстырсақ, онда келесісі алдынғысынан кіші болмауы керек.

Сортаудың көптеген алгоритмдері бар. Сорттау алгоритмдерінің екі класы бар

екендігін ескерейік: берілгендерді сорттау, ол негізгі есте сақтау жүйесінде орналасқан (внутреняя сортировка), жəне файлдарды сорттау, ол сыртқы сақтау жүйесінде сақталған (внешняя среда). Біз тек ішкі сорттау əдісімен айналысамыз. Ішкі сорттаудың белгілі əдістерін, оларды прологта тізімді сорттау үшін қалай қолдану керектігін қарастырайық жəне анықтайық.

Айтарлықтай белгілі көпіршіктік іріктеу тəсілінен бастайық. Оны тағы тікелей ауыстыру немесе қарапайым ауыстыру əдісі деп атайды.

Бұл əдістің ойы келесіге негізделген. Əр бір қадамда тізімдегі көршілес элементтер салыстырылады. Егер олар дұрыс емес тұрса, яғни алдынғы элемент келесіден кіші болса, онда олар орындарымен ауысады. Бұл процесті көршілес, дұрыс емес тізімде орналасқан элементтердің пары балғанға дейін созылады. Ол тізімнің іріктелгенін көрсетеді.

Көпіршікпен аналогия болған себебі, өйткені əр бір минималды элемент тізім басына шығады.

Көпіршіктік іріктеуді екі предикат арқылы жүзеге асырамыз. Олардың біріеуін permutation деп атайық, тізімнің бірінші екі элементтерін салыстырады, егер біріншісі екінші элементтен үлкен болса, онда олардың орындарын ауыстырамыз. Ал егер бірінші жұп дұрыс тізімде орналасса, ол предикат соңын қарастыруға көшеді.

Көмекші предикатты permutation пайдалана отырып, негізгі предикат bubble сізімдегі көпіршіктік іріктеуді жүзеге асырады.

permutation([X,Y��T],[Y,X��T]:Х>У,!.

/* Егер бірінші екіншіден үлкен болса, бірінші екі элементтердің орнын ауыстырамыз

*/

permutation ([X ,T],[X��Tl ]):-

/*соңындағы орын ауыстыруларға көшейік*/

bubble(L,Ll):-

permutation (L,LL), /* орын ауыстыруды жүзеге асыратын предикатты шақырайық * /

bubble(LL,L!). /* алынған тізімді қайта іріктеуге тырысайық */

bubble(L,L). /* егер орын ауыстырулар болмаса, тізім сортталмағанын көрсетеді. * /

Бірақ біздің көпіршіктік əдіс тек дұрыс емес тізбекте орналасқан, ең болмағанда тізімнің бір жұбы болғанша жұмыс істейді. Ондай элементтер біткеннен кейін permutation предикаты сəтсіздікке ұшырайды, ал bubble ережеден фактке өтеді жəне сұрыптаумен тізімді екінші аргументтің сапалы түріне қайтарады.