1-lektsiya. Qatnaslar. Binar qatnaslar
-lektsiya. Algoritmlik sheshiliwshenlik problemasi
Download 353.65 Kb. Pdf ko'rish
|
- Bu sahifa navigatsiya:
- Matematik mantiqda keltirib chiqaruvchanlikni tanish muammosi.
- O`z-o`ziga tatbiq etuvchanlikni tanish muammosi.
- A`debiyatlar
|
12-lektsiya. Algoritmlik sheshiliwshenlik problemasi. Tayanish tu`sinikler: echilish algoritmi. echiluvchi muammolar. echilmovchi muam- molar. Matematik mantikda keltirib chikaruvchanlikni tanish muammosi. Chyorch teoremasi. O`z-o`ziga tatbik etiluvchanlikni tanish muammosi. Assotsiativ hisobidagi so`zlarning ekvivalentlik muammosi. Matematika tarixida biror masalani echish, odatda, uning echilish algoritmini topish deb xisoblanardi. Deyarli XX asr boshlarigacha hamma matematik masalalar algorit-mik echiluvchi masalalar deb qaralgan va ularni echuvchi algoritmlar izlangan. Masalan, haqiqiy koeffitsientli n- darajali ko`phadning ildizlarini uning
41 koeffitsientlari yordamida radikallarda ifoda etish algoritmini izlash bir necha asrlar davom etdi. Masalan, uchinchi va turtinchi darajali tenglamalar uchun bu algoritmni XVI asrda ital`yan matematiklari Kardano va Ferrari yaratdilar. Uzoq yillardan keyin norvegiyalik matematik Abel` n≥5 bo`lganda bunday algoritm mavjud emasligini ko`rsatdi. Ikkinchi misol sifatida Gil`bertning diofant tenglamalar haqidagi 10- muammosini ko`rsatish mumkin. Bu muammoni Gil`bert 1900 yilda Parijda e`lon kilgan edi. Deyarli 70- yilday keyin rus matematiklari Yu. Matiyasevich va G. Chudnovskiy bu muammo algoritmik echilmovchi muammo ekanligini isbotlab berdilar. Faqat algoritmning intuitiv tushunchasidan T`yuring mashinasining aniq tushunchasiga o`tish berilgan ommaviy muammoning algoritmik echiluvchanlik masalasiga aniqlik kiritdi. Bu masalani quyidagicha ifodalash mumkin: berilgan ommaviy muammoni echadigan T`yuring mashinasi mav-judmi yoki bunday mashina mavjud emasmi? Bu savolga algoritmlar nazariyasi ayrim hollarda salbiy javob beradi. Shu turdagi natijalarni birinchilar qatorida 1936 yidda amerikalik matematik A.Chyorch oldi. U predikatlar mantikidagi echilish muammosi umumiy hodtsa algoritmik echimga ega emasligini ko`rsatdi. O`sha yilning o`zida u matematik mantiqtsagi keltirib chiqaruvchanlikni tanish muammosi ham algoritmik echilmasligini isbot kildi. Keyingi masalani batafsilroq ko`rib o`taylik.
Matematikada aksiomatik metodning mazmuni quyidagidan iborat: berilgan nazariyaning hamma mulohazalari (teoremalari) shu nazariyada isbotsiz qabul qilingan mulohazalar (aksiomalar) dan formal mantiqiy keltirib chiqarish vositasi bilan olinadi. Matematik mantiqda formulalarning maxsus tili ifodalanadi. U orqali matematik nazariyaning istalgan mulohazasi butunlay aniqlangan formula ko`rinishida yoziladi. A asos (shart)dan V natijani mantiqiy keltirib chiqarish jarayonini dastlabki formulalarni formal almashtirishlar jarayoni sifatida ifodalash mumkin. Bunga mantiqiy hisobdan foydalanish yo`li bilan erishish mumkin.
42 Tanlangan mantiqiy hisobda V mulohazani A asosdan mantiqiy keltirib chiqarish masalasi A formuladan V formulaga olib keluvchi deduktiv zanjirning mavjudligi masalasidir. Shu tufayli keltirib chiqaruvchanlikni tanish muammosi paydo bo`ladi: mantiqiy hisobdagi istalgan ikkita A va V formula uchun A dan V ga olib keluvchi deduktiv zanjir mavjudmi yoki yo`kmi? Bu muammoning echimi sifatida har qanday A va V lar uchun javob beradigan algoritm mavjudligi ma`nosida tushuniladi. Chyorch olgan natija quyidagicha izohlanadi. Chyorch t e o r e ma s i . Keltiribchiqaruvchanlikni tanish muammosi algoritmik echilmovchidir. O`z-o`ziga tatbiq etuvchanlikni tanish muammosi. T`yuring mashinasining shifri tushunchasini kiritamiz. Hozirgacha T`yuring mashinasining dasturini ikki o`lchovli mxn jadval ko`rinishida yozardik. Ammo uni bir o`lchovli shaklda ham tasvirlash mumkin. Buning uchun 5 ta simvolni shunday ketma- ketlikda yozish kerakki, beshlikning birinchi simvoli jadvalning ustunini, ikkinchisi satrini va keyingi uchtasi jadvalning yuqorida ko`rsatilgan ustun va satrlari kesishmasidagi uchta simvolni (komandani) ifodalasin. Masalan, 3- jadvalda ifodalangan funktsional sxema o`rniga quyidagi bir o`lchovli satrni hosil qilamiz: a 0 q 1 a 0 q 3 │q 1 αn 2 q 1 αlq 1 a 0 q 2 a 0 lq 4 …… (1) Mashina konfiguratsiyasini ifodalashda ham shu usuldan foydalanamiz, ya`ni holatni ifodalovchi harfni «ko`rilayotgan» harfning tagidan emas, balki chap yonidan yozamiz. Masalan, ││││││
q 4
konfiguratsiyani quyidagi shaklda yozamiz: ││││ q 4 ││
(1) satrdagi har bir harfni quyidagi shartlarga rioya qilgan holda qayta nomlaymiz: 1) (1) satrni ayrim kodlashtirilgan guruhlarga bir qiymatli qilib bo`lmoq kerak; 2) kod simvollari uch turda bo`lishlari kerak: a) l, n, n harflari uchun; 43 b) tashqi alfavit harflari uchun; v) mashina holatini ifodalovchi harflar uchun. Shu munosabat bilan kuyidagi kodlashtirish jadvalidan foydalanamiz: Alfavit Harf Kodlashtirilgan guruh Eslatmalar l 101
1 lar orasida 1 ta n 1001 1 lar orasida 2 ta Adreslar harfi
10001 1 lar orasida 3 ta a o
100001 4 ta nol` 2 dan katga juft sonli a 1 10000001 6 ta nol` nollar
…. …. Tashqi alfavit
a n
10...01 2(n + 2) ta q 1 1000001 5 ta nol` 3 dan katta toq sonli q 2
nollar ….
…. Ichki
alfavit
q 10...01 2(n+
1 a 2 , a 3 harflar deb qarasak, u holda uni shu kodlashtirish sistemasi asosida quyidagicha yozish mumkin: 10000110000011000011000110000000001100000011000001... (2) Funktsional sxema yoki alohida olingan biror konfiguratsiya uchun tuzilgan 1 va 0 lardan iborat bo`lgan bunday satr funktsional sxemaning shifri yoki konfiguratsiyaning shifri deb ataladi.
1 Turaev X. Matematik mantik va diskret matematika T. 2003 2 Sukasheva G., Lixtarnikov I. matematicheskaya logika Sank-Peterbu rg, 1999 3 Mendel`son E. Vvedenie v matematicheskuyu logiku
M.:1984 4 Mal`tsev A.I. Algoritmi i rekursivnie funktsii M. 1986 5 Rodjers X. Teoriya rekursivnix funktsiy i effektivnaya vichislimost` M. 1972 6 Lavrov I.A., Maksimova L. Zadachi po teorii mnojestv, matematicheskaya logikai teorii algoritmov M.:1984 7 Ershov YuL. Matematicheskaya logika M.:1983
Download 353.65 Kb. Do'stlaringiz bilan baham: 
|