Білім беру бағдарламасы білім алушыларына арналған. Лекциялар жинағы «Техника және ақпараттандыру»
жүктеу/скачать 316.11 Kb.
|
- Бұл бет үшін навигация:
- Ұсынылған әдебиеттер
- ЛЕКЦИЯ № 3 3. Тақырыбы
- ЛЕКЦИЯ МАЗМҰНЫ
| Бақылау сұрақтары:
1. Хорновтық дизъюнктері дегеніміз не? 2. Резолюция принципінің мағынасы неде? 3. Жүйе алфавитіне анықтама беріңіз жəне оларды атаңыз. 4. Жүйе аксиомасы түсінігіне анықтама беріңіз. 5. Жүйе формуласына анықтама беріңіз жəне оларды атаңыз. 6. Жүйе ережесіне анықтама беріңіз. Мысал келтіріңіз. 7. Дизъюнк деген не? 8. Литерал түсінігі. Олардың түрлері. 9. Резолюция ережесі. 10. Логикалық бағдарлама дегеніміз не? 11. Бектринг бағдарламамен не істейді? 12. Сколемовскидің нормалды формасы деген не? 13. Клозамалар түсінігіне анықтама беріңіз. Ұсынылған әдебиеттер 1. Непейвода Н.Н. Стили и методы программирования Интернет-университет информационных технологий - ИНТУИТ.ру, 2015 2. Терехов А.Н. Технология программирования БИНОМ. Лаборатория знаний, Интернет-университет информационных технологий - ИНТУИТ.ру, 2016 ЛЕКЦИЯ № 3 3. Тақырыбы: Прологтың негізгі түсінігі. ЛЕКЦИЯ ЖОСПАРЫ 1. Айғақтар мен ережелер. 2. Ішкі жəне сыртқы мақсаттардың қарым-қатынасы. 3. Еркін жəне байланысқан айнымалылар. 4. Анонимді айнымалы. 5. “Жасыл” жəне “қызыл” қималар. 6. Прологтың семантикалық моделдері: декларативті жəне процедуралы. ЛЕКЦИЯ МАЗМҰНЫ Бұл дəріс Пролог тілінің негізгі түсініктеріне арналған. Осы жəне келесі дəрістерде біз Прологта бағдарламалардың жазылуының негізін оқимыз. Б экус-Наурдың (БНФ) қалыпты формасымен танысамыз, оны 1960 жылы Джон Бэкус жəне Питер Наур ойлап тапты жəне бағдарламалау тілінің синтаксисін формальді жазуы үшін қолданылады. БНФ алғашында Алгол-60 тілінің синтаксисін жазғанда Питер Наурмен қолданылды. Құрылым синтаксисін жазуда келесі белгілер қолданылады: ::=белгісі “анықтау бойынша” (“бұл”, ”бар”) деп оқылады. Бөлгіштің сол жағында түсіндіретін түсінік орналасады, оң жағында –оны айқындаушы конструкция. Мысалы, < Ат > ::= < Идентификатор > Бұрыштық жақшаларда тілдің синтаксистік құрылысын белгілеуге арналған бөлігі жоғарыда келтірілген мысалда ол < Ат > жəне < Идентификатор > белгісі БНФ нотациясында “немесе” білдіреді. Ол анықталатын түсініктің түрлі баламалы талқылаулардың бөлінуі үшін қолданылады. Мысал, Ондық санды келесі жолмен анықтау керек: < сан > :: = 0|1|2|3|4|5|6|7|8|9 Синтаксистік құрылыс бөлігі тік жақшамен қоршалған,міндетті емес (болуы да, болмауы да мүмкін); Мысал. Жазба < бүтін сан > :: = [-]< оң бүтін сан > Бүтін санды оң алдында минус таңбасы тұруы мүмкін бүтін сан арқылы табуға болатынын көрсетеді. белгісі синтаксистік құрылыс бөлігі. Таңдалынған санмен ( нөл жəне үлкен ) қайталануы мүмкін екенін білдіреді. Кейде * белгісінің орнына жүйелі жақша ({,}) қолданылады. Мысал, БНФ нотациясыда оң бүтін санды былай анықтауға болады. < оң бүтін сан > ::= <сан>[<сан>]*. Яғни оң бүтін сан бір немесе бірнеше саннан тұрады. Пролог тіліндегі программа оны кейде білім негізі деп атайды.Ол сөйлемдерден тұрады (немесе бекітулерден ) , əрбір сөйлем екі түрлі болады : дерек , ереже. Сөйлем түрі A:- B1,... , Bn. А сөйлемнің басы деп аталады, ал B1,... , Bn -денесі. Бұл жайлы өткен дəрісте айтылды. Бірақ онда теориялық тұрғыдан бұлт түсініктерді қарастырған жоқпыз, ал қазір бағдарламалау жағынан тəжірибелі болады. Дерек объектер арасындағы кейбір қатынастардың орындалуын айқындайды.Ол тек қана тақырыптан тұрады. Факті-денесі жоқ сөйлем деп есептеуге болады. Мысалы, бізге белгілі факт , Наташа Дашаның анасы, ол мына түрде жазылуы мүмкін: Мама ( Наташа, Даша ). Факт шындық дəлелді көрсетеді. Өткен лекцияда танысқан математикалық логикада қатынастарды предикаттар деп айту қабылданған. Егер Бэкус-Науэрдің қалыпты формасын қолдансақ , онда предикатты келесідей анықтауға болады: <Предикат>::=<Аты> <Аты>(<аргумент>[,<аргумент>]*), яғни предикат не тек аттан ,не атау мен одан кейін жақшаға алынған аргументтен тұрады. Предикаттың аргументі немесе параметрі константа айнымалы немесе құрамды объект болуы мүмкін .Предикат аргументінің саны оның арностью немесе местностью деп аталады. Айнымалылар туралы сəл-пəл кейін айтамыз,ал тұрақтыларды толық қарастыруды бесінші дəріске қалдырамыз. Т урбо Прологта предикат аты латын əріптерінің реттілігімен тұруы керек жəне асты сызылатын əріптер мен белгілерден басталады. Прологтың басқа версияларында предикат аты тек ағылшын алфавитінің əріптерін ғана емес басқа да жəне ұлттықтанда , мысалы орыс тілінен тұруы мүмкін. Сəйкесінше ,жоғарыда келтірілген факт мысалын Турбо Прологта былай жазуға болады: mother("Наташа", "Даша"). Кейбір предикаттар жүйеде белгілі олар стандартты немесе құрылған деп аталады. Турбо Прологта атау бірдей предикаттан тұратын сөйлемдер бірінен соң бірі жүруі керек. Сөйлемдердің мұндай жиынтығы процедура деп аталады. Жоғарыда келтірілген мысалда ,Наташа Дашаның мамасы екендігі , мама – бұл екі аргументті предикаттың аты, оның жолдық тұрақтысы “Наташа” бірінші аргумент ,ал “Даша” – екінші . Е реже –бұл ұсыныс , оның шынайылығы бір немесе бірнеше ұсыныс шынайылығынан тұрады.Əдетте ереже бірнеше мақсаттарды қамтиды , олар шынайы болуы керек , сонда ереже де шынайы болады. БНФ нотациясында ереже түрі мынадай болады: <Ереже>::=<предикат>:-<предикат>[,<предикат>]*. Мысал. Адамның əжесі – оның анасының немесе əкесінің анасы екені белгілі. Сəйкес ереже түрі мынадай: əже(X,Y):- мама(X,Z), мама(Z,Y). əже(X,Y):- мама(X,Z),папа(Z,Y). ":-"белгісі “егер” дегенді білдіреді , жəне оның орнына if жазуға болады. "," белгісі –бұл логикалық байланыс “жəне” немесе конъюнкция , оның орнына and жазуға болады. Бірінші ереже бойынша Х Y –тің əжесі ,егер Z –Y –тің мамасы. Екінші ереже бойынша ХY-тің əжесі болып табылады.,егер мынадай Z болса ,Х Z-тің мамасы ,ал Z-Y-тің əкесі. Берілген мысалда X,Yжəне Z – айнымалылар. Т урбо прологтағы айнымалы аты латын алфавитінің əріптерінен , сандардан , белгілеу белгілерінен тұруы мүмкін жəне жазба əріптен басталуы керек. Бұл уақытта ережедегі айнымалылар жалпы квантормен байланысқан. Прологтағы айнымалы алгоритімдік програмалау тілімен салыстырғанда объекті білдіреді. Прологта құрылымсыз иемдену механизмдерін қолдамайды. Айнымалылар еркін жəне байлаулы болуы мүмкін. Еркін айнымалы –ол əлі мəн алмаған айнымалы. Ол нөлге де, бос орынға да тең емес; оның ешқандай мəні жоқ. Мұндай айнымалылар нақтыланбаған деп те аталады. Қ андай да мəн алған айнымалы жəне белгілі бір объектпен байланысқан айнымалы байлаулы деп аталады. Егер айнымалы нақты болса жəне оған белгілі объект берілсе ,онда ол айнымалы өзгертуге келмейді. П рологтағы айнымалының əрекет облысы бір сөйлем болып табылады. Түрлі сөйлемде түрлі объекті белгілеу үшін бір айнымалының аты қолданылуы мүмкін. Əрекет облысын анықтау ережесінен ерекшесі жасырын айнымалы ол ″-″ белгісімен белгіленеді . Жасырын айнымалы , айнымалы мəні елеусіз болғанда қолданылады. Əрбір жасырын айнымалы-жеке объект. Прологтың үшінші арнаулы құжаттық сөйлем түрі сұрақтар болып табылады. Сұрақ тек денеден тұруы мүмкін жəне БНФ-ң көмегімен былайша көрсетілуі мүмкін: <сұрақ>::=<предикат>[<предикат>]* Сұрақтар бағдарламада көрсетілген кейбір объектер арасындағы қатынастың орындалуын айқындау үшін қолданылады. Жүйе сұрақты мақсат ретінде қарастырады. Сұраққа жауап оң жəне теріс болуы мүмкін. Прологтағы бағдарлама бағдарламаның ішінде сұрақты ұстауы мүмкін (ішкі мақсат деп аталады) . Егер бағдарламаның ішкі мақсаты болса, онда бағдарламаны орындауға қосылған соң жүйе берілген мақсаттың жетістігін тексереді. Е гер бағдарламада ішкі мақсат болмаса , онда бағдарлама іске қосылғаннан кейін жүйе диалогты режим де сұрақ енгізуді сұрайды (сыртқы мақсат) . Орындалатын файлда компиляцияланатын бағдарлама міндетті түрде ішкі мақсатқа ие болуы керек. Егер мақсат орындалса, онда жүйе (″Yes″) сұрағының шынайылығы туралы нəтиже жасауға мүмкіндік береді. Егер сұрақта айнымалылар болса, онда жүйе оның мəнін береді егер шешім болса, (″No solunion″) деген шешім болмаса хабарлайды.Егер мақсатқа жетпесе , онда жүйе (″No″) деген жауап береді. “No” деген жауап əрқашан сұрақ орындалмайды дегенді білдірмейді. Жүйе мұдай жауапты ақпарат жоқ болған жағдайда да беруі мүмкін. Бекіту – бұл ереже ал дерек немесе сұрақ – бұл оның жеке жағдайы. Бірнеше мысалды қарастырайық. Бағдарламада келесі байланыстар берілген болсын. Мама («Наташа», «Даша») Мама («Даша», «Мама»). Жүйеден Дашаның анасы Наташа ма деп жүйеден сұрауға болады. Бұл сұрақты мына түрде беруге болады. Мама («Наташа», «Даша») Жүйеден __________сəйкес дерек тауып, жүйе «Yes» деп жауап береді. Егер біз сұрасақ: Мама («Наташа», «Мама») десек, онда «No» деген жауап аламыз. Сонымен қатар Дашаның анасының атын сұрауға болады. Мама (х, Даша). Жүйе бірінші дерекпен сұрақты салыстырады да, Наташа мəндə Х айнымалысын нақтылау жəне жауап береді: Х= Наташа 1solution Наташаның қызының аты туралы сұрақ былайша жазылады: Мама (Наташа, Х) Сəйкес жауап Х=Даша 1Solution Сұрақ беру арқылы жүйеден барлық белгілі аналар мен қыздарының аттарын табуды сұрауға болады: Мама(Х,У) Жүйе біртіндеп бар сұрақтарды бағдарламадағы сөйлемдердің біріншісінен соңғысына дейін сəйкестендіруге тырысады. Қолайлы унификациядан соң Х айнымалысы анасының атын, ал У айнымалысы оның қызының атымен берілетін болады. Нəтижесінде мынадай жауап аламыз: X=Наташа У=Даша Х=Даша У=Мама 2 solution Егер барлық аналардың атын алу керек болса, жасырын айнымалыны қолдануға жəне сұрақ жазуға болады: Мама (Х, - ) Жауап : Х=Наташа Х=Даша 2 solution Егер сұраққа жауап алу керек болса: «Мама – қызы» қатынасындағы адамдар туралы ақпарат бар ма, онда оны мына түрге келтіруге болады: Мама (-,-) Берілген жағдайда бізге нақты аттар қажетсіз, ал біздің базамызда сəйкес бір деректің бар болуы. Бұл жағдайда жауап тек “yes” болады. Біздің ережелер бағдарламамызға «əже-немере» байланысын анықтайтын ереже енгіземіз, «ана болу» терминдерінде: Əже (Х,У):- Мама (Х,Z), Мама (Z, У). Істің барысында бұл жерде бір адам екіншісінің əжесі, егер ол оның анасының анасы болса, əрине дəлдік үшін екінші ережені жазуға болады. Əже – ол əкенің анасы, егер бағдарламаға əкелер туралы дерек енгізсек. Біздің бағдарламамызда əже қатынасымен байланысты бір де бір дерек жоқ. Соған қарамастан жүйе əжелер туралы сұрақтарға жауап табуға бейім. Мысалы, Егер Наташа кімнің əжесі екені қызықтырса онда біз бұл сұрақты былай жазуымызға болады: Əже («Наташа», Х). Сұраққа жауап табу үшін жүйе біздің базамызды басынан аяғына дейін қарайды, сөйлем табу керек. Max (X, У,У):-Х=У/* егер бірінші сан екіншісіне тең болса, максимум ретінде екінші сана аламыз */ Соңғы сөйлемді екінші немесе үшінші сөйлеммен біріктіруге болады. Сонда процедура екі сөйлемнен тұрады: Max (X,Y,X):- X>Y./* егер бірінші сан екіншісінен үлкен болса, онда бірінші сан максимум */ Max (X, У,У):- X<=Y./* егер бірінші сан кіші немесе екіншісіне тең болса, максимум ретінре екінші санда аламыз */ Дегенмен алынған процедура шындықтан əлі алыста. Бір жағынан, (Х>У) бірінші тексеру шарты орындалмаған жағдайда, екінші шарт (Х<=У) тексеріледі. Екінші жағынан, егер бірінші шарт орынды болып жəне бірінші сан екіншісінен үлкен болса, онда Пролог – жүйе предикаттың үшінші аргументін мах бірінші аргументпен байланыстырылады, содан кейін екінші сөйлемді солғастырғысы келеді. Бізге белгілі болғандай максимум анықталғаннан кейін ешнəрсе жасаудың қажеті жоқ. Басқа нұсқаның болуы мүмкін емес. Бұл жағдайда бізге құрылымды предикат керек, ол ағылшынша cut деп аталады, орысша қима, ал Пролог бағдарламасында ол леп белгісімен «!» белгіленеді. Бұл предикат бағдарлама жұмысының тиімділігін арттыру мақсатымен іздеу кеңістігін шектеуге арналған, ол əрқашан сəтті аяқталады. Қиманы қолданып біздің шешіміміз қысқа болады: Мах 2 (Х, У, Х) : -X>У, !./* егер бірінші сан екіншісінен үлкен болса, онда бірінші сан мак симум */ Мах 2 (-,У,У) /*басқа жағдайда екінші сан максимум болады */ Егер қима жұмыс жасаса, ол тек Х>У шарты шын болғанда ғана мүмкн, Пролог – жүйе альтернативті екінші сөйлемді қарастырмайды. Екінші сөйлем шарт дұрыс болмаған жағдайда ғана жасалады. Бұл жағдайда үшінші аргументке екінші аргументтің мəні беріледі. Бұл жағдайда бірінші аргумент неге теңелгені бізге қажет еместігіне назар аударыңыз жəне оны жасырын айнымалымен алмастыруға болады. Қиманы қолданудың барлық жағдайында «жасыл» жəне «қызылға» бөлу қабылданған. Лақтыру кезінде бағдарлама қима кезіндегі мəндерді беруді тоқтатпау жасыл деп аталады. Егер қиманы алып тастау кезінде бағдарлама дұрыс шешім бермесе, онда мұндай қималар қызыл деп аталады. «Қызыл» қиманың мысалы мах2 предикатын жүзеге асыруда бар ( егер қиманы алып тстасақ, предкат максимум ретінде екінші санды береді, ол бірінші саннан кіші болса деп аталады). «Жасыл» қиманың мысалын мах предикаттың жазбасына қиманы қосу арқылы алуға болады ( предикат олармен де, оларсыз да бір шешімді береді). Прологта қима көмегімен тарамдалу сияқты императивті тілдерді моделдеуге болады. Процедура S:- <шарт>, !, P, S:- P2. If <шарт> then P else P2 операторына сəйкес болады, яғни шарт орынды болса, онда P орындайды, əйтпесе P2. Мысалы, максимум жағдаында біздің процедурамызды « егер Х > Y, онда M = X, əйтпесе M = Y» деп ашып жазуға болады. жүктеу/скачать 316.11 Kb. Достарыңызбен бөлісу:
|