|
1-ma’ruza. Algoritm tushunchasi. Algoritmni asosiy ta`riflari, xossalari va ularning turlari Oddiy klassik algoritmlar. Algoritm tushunchasi
|
| bet | 5/9 | | Sana | 17.05.2024 | | Hajmi | 48,86 Kb. | | #240309 |
Bog'liq 1-Mavzu 1.2. Hisoblash modellari
Hisoblash nazariyasi va hisoblash murakkabligi nazariyasi hisoblash modelini nafaqat hisoblash uchun foydalaniladigan qabul qilinadigan amallar toʻplamining ta’rifi, balki ularni qoʻllashning nisbiy xarajatlari sifatida ham koʻrib chiqadi. Kerakli hisoblash manbalarini - ijro etish vaqtini, xotira hajmini, shuningdek algoritmlarning cheklanishlarini yoki kompyuterni xarakterlash mumkin - faqat ma’lum bir hisoblash modeli tanlangan taqdirda.
Modelga asoslangan muhandislikda hisoblash modeli va uning tanlovi, agar uning alohida qismlarining xatti-harakatlari ma’lum boʻlsa, umuman tizim qanday ishlaydi degan savolga javob beradi.
Hisoblash murakkabligining asimptotik bahosida hisoblash modeli ma’lum narx bilan qabul qilinadigan primitiv amallar orqali aniqlanadi.
Ma’lum amallar toʻplamiga va ularning hisoblash murakkabligiga qarab bir qator hisoblash modellari ma’lum. Ular quyidagi keng toifalarga boʻlinadi: algoritm hisoblashning murakkabligini yuqori chegarasini olish uchun foydalaniladigan abstrakt mashinalar va algoritmik masalalar uchun hisoblash murakkabligining pastki chegarasini olish uchun ishlatiladigan qaror modellari.
Tyuring tezisi. Chyorch tezisi. Algoritm tushunchasini aniqlashga yondashishlar. Algoritm tushunchasini aniqlash boʻyicha yondashishlarni uch asosiy yoʻnalishga boʻlish mumkin.
Birinchi yoʻnalish effektiv hisoblanuvchi funksiya tushunchasini aniqlash bilan bogʻliq. Bu yoʻnalish boʻyicha A.Chyorch, K.Gyodel, S.Klini1 tadqiqot ishlarini olib borishgan.
1932-1935-yillar davomida A.Chyorch va S.Klini tomonidan oʻrganilgan va “ -aniqlanuvchi funksiyalar” deb atalgan, toʻgʻri aniqlangan hisoblanuvchi nazariy-sonli funksiyalar sinfining “ -aniqlanuvchi funksiyalar” sinfi bizning intuitiv tasavvurimiz boʻyicha hisoblanuvchi deb qaraladigan hamma funksiyalarni qamrab olishi mumkin degan fikr tugʻilganligi 1935-yilda e’lon qilindi. Bu kutilmagan natija edi.
J.Erbranning2 bir gʻoyasi asosida 1934-yilda K.Gyodel tomonidan aniqlangan va “umumrekursiv funksiyalar” deb atalgan boshqa hisoblanuvchi funksiyalar sinfi ham “ -aniqlanuvchi funksiyalar” xossalariga oʻxshash xossalarga ega edi.
1936-yilda A.Chyorch va S.Klini tomonidan bu ikkita sinf bir xil sinf ekanligi isbotlandi, ya’ni har qanday -aniqlanuvchi funksiya umumrekursiv funksiya boʻlishi va har qanday umumrekursiv funksiya -aniqlanuvchi funksiya ekanligi tasdiqlandi.
1936 yilda Chyorch quyidagi tezisni e’lon qildi: har qanday intuitiv effektiv (samarali) hisoblanuvchi funksiyalar umumrekursiv funksiyalardir.
Bu teorema emas, balki tezisdir: tezis tarkibida intuitiv 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 dalillar koʻrsatildi.
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
1-ma’ruza. Algoritm tushunchasi. Algoritmni asosiy ta`riflari, xossalari va ularning turlari Oddiy klassik algoritmlar. Algoritm tushunchasi
|
