1. Algoritmik model

Algoritmik modellar.Algoritmning insitive tushunchasi va uni aniqlash zaruriyati Tyuring mashinalari va ular orqali hisoblanuvchi funksiyalar
Reja
1.Algoritmik model.
2.Algoritmik tushincha.
3.Algoritmik tushunchasini aniqlashga yondashishlar.
4.Tyuring mashinasi.
Bu algoritmning algoritmik modeli- bu algoritmni ketma-ket ravshan ketma-ketlik qilish uchun amalga oshirish uchun ma’lum bir ijroga aniq yo’l.
Algoritm tushinchasi.Matematikaning asosiy tushunchalaridan biri algoritm tushinchasidir.Algoritm so’zi(ba’zan bu so’z “algorifm ko’rinishida yoziladi)IX asrda yashab ijod qilgan vatandoshimiz buyuk matematik Abu Abdullo Muhammad ibn Muso al-Xorazmiy nomining lotincha “Algorithmi” tarzida buzib yozilishidan kelib chiqqan.Har biriga “ha” yoki “yo’q” degan javob berish mumkin bo’lgan ayrim sanoqli cheksiz matematik yoki mantiqiy masalalar sinfi.Formal sistemalar uchun yechilish muammosini kun tartibiga birinchi qo’ygan olimlardan Shryoder (1895),Lyovengeym II (1915) va Gilbertmi III (1918) ko’rsatish mumkin.
1-misol.Quyidagilar yechuvchi algoritmlarga misol bo’la oladi.
1.Sonlar ustida arifmetik amallarni bajarish qoidalari.
2.Kvadrat ildiz chiqarish qoidasi.
3.Eng katta ummiy bo’luvchi toppish qoidasi(Evlid algoritmi).
4.Kvadrat tenglamaning yechimini topish qoidalari.
5.n-tartibli ko’phadning hosilasini topish qoidasi.
6.Ratsional funksiyani integrallash qoidasi.
Yuqorida keltirilgan har bir misolda bir xil tipli (turdagi) masalalar sinfi bilan ish ko’rishga to’g’ri keladi.Bir xil turdagi masalalar bir biridan faqat ifodasidagi paramaetrlar bilan farq qiladi.Masalan, ax+bx+c=0 kvadrat tenglamaning yechimini topish masalasida a,b va c parametralar qatnashadi.Ularning qiymatalari o’zgartirish yo’li bilan bir sinfga mansub turli xil masalalarga kelamiz.
1-ta’rif.Berilgan ommaviy muammodagi barcha masalalarni umumiy bir xil shaklda,aniq ma’lum bo’lgan usul bilan yechish jarayoni algoritm deb ataladi.Bunday ta’rifni qat’iy deb hisoblash mumkin emas.Haqiqatdan ham,unda aniq mazmuni noma’lum so’zlar uchraydi.Bu fikr, xususan “usul” so’ziga ham tegishlidir.Shuning uchun ham algoritmning bu qat’iy bo’lmagan ta’rifi intuitive ta’rifidir.
Algoritm tushunchasini aniqlashga yondashishlarλ.Algoritm tushunchasini aniqlash bo’yicha yondashishlarni uch asosiy yo’nalishga qo’yish mumkin.
Birinchi yo’nalishni effektiv hisoblanuvchi funksiya tushunchasini aniqlash bilan bog’liq.Bu yo’nalish bo’yicha A.Chyorch, K.Gyodel, S.Klini tadqiqot ishlarini olib borishgan.1932-1935-yillar davomida A.Chyorch va S.Klini tomonidan o’rganilgan.1936-yilda A.Chyorch va S.Klini tomonidan bu ikkita sinf bir xil sinf ekanligi isbotlanadi,ya’ni har qanday λ-aniqlovchi funksiya umumrekursiv funksiya bo’lishi va har qanday umumrekursiv funksiya λ aniqlovchi funksiya ekanligini tasdiqlanadi.
1936-yilda Chyorch quyidagi tezisni e’lon qildi:har qanday intuitive efektiv(samarali) hisoblanuvchi funksiyalar umumrekursiv funksiyalardir.Bu teorema emas, tezis tarkibida intuitive aniqlangan effektiv hisoblanuvchi funksiya tushunchasi aniq matematik atamalarda aniqlangan umumrekursiv funksiya tushunchasi bilan aynan tenglashtirilgan.Shuning uchun bu tezisni isbotlash mumkin emas.Ammo Chyorch va boshqa olimlar tomonidan bu tezisni quvvatlovchi ko’p dalilar ko’rsatildi.Ikkinchi yo’nalish algoritm tushunchasini bevosita aniqlash bilan bog’liq .1936-1937-yillarda A.Tyuring Chyorch ishlaridan bexabar holda yangi funksiyalar sinfini kiritdi.Bu funksiyalarni “Tyuring bo’yicha hisoblanuvchi funksiyalar” deb atadilar.Bu sinf ham yuqorida aytilgan xossalarga ega edi va buni Tyuring tezisi deb aytamiz.1937-yilda A.Tyuring uning hisoblanuvchi funksiyalari X-aniqlovchi funksiyalarning o’zi demak umumrekursiv funksiyalarning xuddi o’zi ekanligini isbotladi.Shuning uchun Chyorch tezisi bilan Tyuring tezisi ekvivalentdir.1936-yilda E.Post (Tyuring ishlaridan bexabar holda)aynan Tyuring erishgan natijalariga mos keladigan natijalarni e’lon qildi va 1943-yilda, 1920-1922- yillardagi nashr etilmagan ishlariga asoslanib, to’rtinchi ekvivalent tezisni nashr qildi.Shunday qilib,algoritm tushunchasini bevosita aniqlashga va so’ngra uning yordamida hisoblanuvchi funksiya tushunchasini aniqlashga va so’ngra uning yordamida hisoblanuvchi funksiya tushunchasini aniqlashga birinchi bo’lib bir biridan Post va Tyuring algoritmik jarayonlari ma’lum bir tuzilishga ega bo’lgan <> bajaradigan jarayonlar ekanligini ko’rsatadi.Ushbu mashinalar yordamida barcha hisoblanuvchi funksiyalar sinfi bilan barcha qismiy rekursiv funksiyalar sinfi bir xil ekanligini ko’rsatadilar demak,Chyorch tezisining yana bitta fundamental tasdig’I yuzaga keladi.
Uchinchi yo’nalish Rossiya matematigi A,Markov tomonidan ishlab chiqilgan normal algoritmlar tushunchasi.Agar qandaydir ommaviy muammoni yechish algoritmi ma’lum bo’lsa u holda uni realizatsiya qilish zarur.Algoritmni realizatsiya qilish jarayonini avtomatlashtirish g’oyasi,tabiiyki,inson bajaradigan ishni mashinaga uzatishni taqozo qiladi.Bunday mashinani XX asrning 30-yillarida E.Post va A.Tyuring tavsiya etishgan.
Tyuring mashinasi tushunchasi intuitive ma’lum bo’lgan hisoblash protsedurasini elementar operatsiyalarga ajratish natijasida hosil bo’lgan.Tyuring ta’kidlaydiki ,istalgan mumkin bo’lgan hisoblashni o’tkazish uchun uning elementar operatsiyalarini qaytarish yetarli.Tyuring ayrim turdagi nazariy hisoblash mashinasini izohlab berdi.Bu mashina muayyan mexanik qurilma emas balki “xayoliy” matematik mashinadir.Berilgan ko’rsatmani bajaruvchi hisoblovchi odamdan yoki mavjud raqamli hisoblash mashinasidan Tyuring mashinasi ikki jihati bilan farq qiladi.
Birinchi.”Tyuring mashinasi” xató qila olmaydi,ya’ni u og’ishmay(chetga chiqmasdan) ko’rsatilgan qoidani bekami ko’st bajaradi.
Ikkinchi.”Tyuring mashinasi” potensial cheksiz xotira bilan ta’minlangan.
Tyuring mashinasini quyidagialar to’liq aniqlaydi.
Tashqi alfavit, ya’ni A={ bexabar holda E.Post va A.Tyuring erishdilar.
A to’plam elementlarining chekli ketma-ketligi Ato’plamdagi so’z deyiladi.So’zni tashkil etuvchi simvollar soni shu so’zning uzunligi deyiladi.Masalan A alfavitning har bir elementi uzunligi 1 ga teng bo’lgan so’zdir.Bu alfavit so’z ko’rinishda mashinaga beriladigan axborot kodlashtiriladi.Mashina so’z ko’rinishda berilgan axborotni qayta ishlab yangi so’z hosil qiladi.Ichki alfavit ya’ni ,O’,CH,J simvollar. mashinaning chekli son holatlarini ifodalaydi.Istalgan mashinaning holatlari soni tayinlangan bo’ladi.Ikki holatda maxsus vazifa bajariladi:q x mashinaning boshlang’ich holatini natijaviy (oxirgi) holatini (to’xtash holati)O’,CH,J surilish simvollaridir(mos ravishda, o’nga chapga va joyida).Ikki tomonga cheksiz davom ettirish mumkin bo’lgan lenta (mashinaning tashqi xotirasi).U katakchalarga (yacheykalarga) bo’lingan bo’ladi.Har bir katakchaga faqat bitta harf yozilishi mumkin.Bo’sh katakchani simvollar bilan belgilaymiz.



U lenta bo’ylab harakat qiladi va biror katakcha (yacheyka) qarshisida to’xtatish mumkin.Mashinaning bir vaqt davomidagi ishida kallak faqat bitta katakchaga surilishi (o’ng, chapga) yoki joyida qolishi mumkin.Ikkinchi lentada saqlanayotgan har bir axborotni tashqi alfavitni adan farqli chekli simvollar majmuasi bilan tasvirlanadi.Mashina ish boshlashidan oldin lentaga boshlang’ich axborot (boshlang’ich ma’lumot) beriladi.Bu holda boshqaruvchi kallak,qoidaga asosan, boshlang’ich holat ko’rsatuvchi oxirgi chap belgi qarshisida turadi.Mashinaning ishi taktlar yig’indisidan iborat bo’lib, ish davomida boshlang’ich axborot oraliq axborotga aylanadi.

Uchinchi shaklda.Boshlang’ich axborot sifatida lentaga tashqi alfavitning katakchalariga ixtiyoriy ravishda qo’yilgan chekli simvollar sistemasini alfavitdagi ixtiyoriy so’zni berish mumkin.Berilgan boshlang’ich axborot bog’liq bo’lgan ikki holi bo’lishi mumkin.
1.Mashina chekli son taktdan keyin to’xtaydi(q to’xtash holatiga o’tadi) va lentada B axborot tasvirlangan bo’ladi.Bu holatda mashina A boshlang’ich axborot nisbatan tatbiq etiladigan va uni qayta ishlab B natijaviy axborotga keltiradigan deb aytiladi.
2.Mashina hech qachon to’xtamaydi, ya’ni to’xtash holatiga o’tmaydi.Bu holat mashina A boshlang’ich axborotga nisbatan tatbiq etilmaydi deb aytiladi.
Tyuring mashinasining ishlashi.Barcha komandalar majmuasi Tyuring mashinasining dasturini tashkil qiladi.Dastur ikki o’lchovli jadval shaklida bo’lib u Tyuring funksional sxemasi deb ataladi.Tyuring mashinasining ishi butunlayiga uning dasturi bilan aniqlanishi Ravshan.Agar ikkita Tyuring mashinasining funksional sxemalari bir xil bo’lsa, u holda ular bir-biridan farq qilmaydi.Har xil Tyuring mashinalari har xil dasturga ega bo’ladi.Bundan keyin Tyuring mashinasining har xil konfiguratsiyalarini soddaroq ifodalash uchun lent ava uning katakchalarini ifodalamasdan axborotni faqat so’z shaklida yozamiz.Boshqaruvchi kallak va mashina holatini ifodalash sifatida mashina holatini yozamiz.
1-jadval.

1-misol.Dastlabki konfiguratsiya quyidagicha berilgan bo’lsin:

Boshqaruvchi kallak harfini ko’rib tuganligi va mashina holatda bo’lganligi uchun mashina komandani ishlab chiqadi va natija ikkinchi konfiguratsiyani hosil qilamiz.
Ravshaniki,navbatdagi konfiguratsiyalar quyidagicha ko’rinishlarda bo’ladi.
uchinchi konfiguratsiya
to’rtinchi konfiguratsiya
beshinchi konfiguratsiya
Beshinchi konfiguratsiyada mashina holatda(to’xtash holatida) turganligi uchun , so‘z hisoblashning natijasi bo‘ladi.