2-Maruza: Algoritmning metrik o`lchamlari. Chorch tezisi, hisoblash modellari va algoritmlarning murakkabligi. Murakkablikning asosiy resurslari: vaqt, xotira. Yuqori va pastki chegaralar tushunchasi. Algoritmlarni yomon, o`rta

Download 45 Kb.
bet	2/4
Sana	14.05.2024
Hajmi	45 Kb.
	#232183

1 2 3 4

Bog'liq
2-Maruza A va B

Chorch tezisi

Prostor zaxiralar soni: Algoritmlar tomonidan ajratilgan zaxira (vaqt o‘tkazmalar) soni. Bu metrika algoritmlarning ishlash darajasi va ishlash tezligi uchun muhimdir.

Komplekslik: Algoritmlarning matematik modeli bo‘lib, uning murakkabligi va bajarilish vaqti o‘lchami.
Bu o‘lchovlar algoritmlar uchun ko‘p qo‘llaniladigan metrikalardan faqat ba’zilari. Algoritmning xususiyatlari va maslahatlari bo‘yicha boshqa metrikalar ham mavjud bo‘lishi mumkin. Algoritmni o‘lchash va baholash juda muhimdir, chunki bu algoritmlar ma’lumotlarni ishlash uchun muhim usullardir.
Chorch tezisi
Chorch-Tyuring tezisi - algoritmik hisoblashning intuitiv tushunchasi va qisman rekursiv funktsiya va Tyuring mashinasida hisoblanishi mumkin bo‘lgan funktsiyaning qat’iy rasmiylashtirilgan tushunchalari o‘rtasidagi ekvivalentlik haqidagi gipotezadir.
Algoritmik hisoblashning dastlabki kontseptsiyasining intuitiv tabiati tufayli bu tezis ushbu kontseptsiya bo‘yicha hukm xarakteriga ega va uni qat’iy isbotlab yoki rad etib bo‘lmaydi.
Hisoblash funksiyasining aniq ta’rifidan oldin matematiklar qog‘oz va qalam usullari yordamida hisoblanishi mumkin bo‘lgan funktsiyalarni tavsiflash uchun ko‘pincha "samarali hisoblash" norasmiy atamasini ishlatishgan.
Tezis 1930-yillarning o‘rtalarida Chorch va Alan Turing tomonidan ilgari surilgan. Ushbu tezis matematik mantiq, informatika, kibernetika kabi fan va fan falsafasining ko‘plab sohalari uchun zarur.
Rekursiya nazariyasi nuqtai nazaridan, tezis umumiy rekursiv funktsiyalar sinfi tomonidan hisoblashning intuitiv tushunchasining aniq tavsifi sifatida tuzilgan. Ushbu formula ko‘pincha oddiy chorch tezisi deb ataladi.
Stiven Klin tomonidan algoritmlar tomonidan hisoblab chiqiladigan barcha qisman (ya’ni barcha argument qiymatlari uchun aniq belgilanmagan) funktsiyalar qisman rekursiv ekanligi haqida umumiyroq formula berilgan.
Turingning hisoblash qobiliyati nuqtai nazaridan, tezisda aytilishicha, har qanday algoritmik hisoblab chiqiladigan funksiya uchun uning qiymatlarini hisoblaydigan Tyuring mashinasi mavjud. Ba’zida bu formula Tyuring tezisi sifatida paydo bo‘ladi. Tyuring ma’nosida qisman hisoblanuvchi va qisman rekursiv funktsiyalar sinflari bir-biriga to‘g‘ri kelishini hisobga olgan holda, bayonot yagona Chorch-Tyuring tezisiga birlashtirilgan.

Download 45 Kb.

1 2 3 4

Download 45 Kb.