1 misol. Quyidagilar yechuvchi algoritmlarga misol bo‘la oladi


Rekursiv, rekursiv sanaluvchi to‘plam tushunchalari



Download 33,2 Kb.
bet17/18
Sana01.01.2022
Hajmi33,2 Kb.
#301381
1   ...   10   11   12   13   14   15   16   17   18
Bog'liq
ALGORITMLAR NAZARIYASI

Rekursiv, rekursiv sanaluvchi to‘plam tushunchalari.

Biror alfavit berilgan bo'lsin. Bu alfavitdagi hamma so‘zlar to'plamini S bilan va S to‘plamning qism to'plamini M bilan belgilaymiz.

1- ta’rif. Agar x so'zning M to'plamga qarashlilik muammosini hal qila oladigan algoritm mavjud bo'lsa, и holda M rekursiv to‘plain deb ataladi.

  1. ta’rif. Agar M to ‘plamning hamma elementlarini sanab chiqa oladigan algoritm mavjud bo ‘Isa, и holda M effektiv rekursiv sanaluvchi to ‘plam deb ataladi.

Rekursiv va rekursiv sanaluvchi to‘plamlar xossalari.

1- teorema. Agar M va L effektiv rekursiv sanaluvchi to 'plamlar bo ‘Isa, и holda M\JL va M C\L ham effektiv rekursiv sanaluvchi to 'plam bo 'ladi.

Isboti. M va L effektiv rekursiv sanaluvchi to'plamlar bo'lsin. U holda, 2- ta’rifga asosan, ularning har biri uchun alohida algoritm mavjudki, ular orqali mos ravishda M va L dagi hamma elementlami sanab chiqish mumkin. M{JL va Mf)L to'plamlaming effektiv sanaluvchi algoritmi M va L to'plamlaming effektiv sanaluvchi algoritmlarini bir vaqtda qo‘llash natijasida hosil qilinadi.

Post teoremasi . M to ‘plamning о ‘zi va to ‘Idiruvchisi CM effektiv rekursiv sanaluvchi bo'lganda va faqat shundagina M to ‘plam rekursivdir.

Isboti. a) M to‘plam va uning CM to'ldiruvchisi effektiv rekursiv sanaluvchi bo'lsin. U holda, 2- ta’rifga asosan, bu to‘plamlaming elementlarini sanab chiqa oladigan A va В algoritmlar mavjud bo'ladi. U holda M va CM to'plamlaming elementlarini sanab chiqish paytida ularning ro'yxatida x element uchraydi. Demak, shunday С algoritm yuzaga keladiki, u orqali Jt element M to'plamga qarashlimi yoki qarashli emasmi degan muammoni hal qilish mumkin. Shunday qilib, M rekursiv to‘plam bo'ladi. b) M rekursiv to‘plam bo'lsin. U holda, 1- ta’rifga asosan, x bu to'plamning elementimi yoki elementi emasmi degan muammoni hal qiluvchi algoritm mavjud bo‘ladi. Bu algoritmdan foydalanib, M va CM to‘plamlarga kiruvchi elementlarning ro‘yxatini tuzamiz. Shunday qilib, M va C M to‘plamlar elementlarini sanab chiquvchi ikkita A va В algoritmni hosil qilamiz. Demak, M va CM to‘plamlar effektiv rekursiv sanaluvchi to‘plamlar bo'ladi. ■

  1. misol. M = {1, 4,9,...,n2 natural sonlar kvadratlari to‘plami effektiv rekursiv sanaluvchi to'plam bo‘lishi yoki bo'lmasligini aniqlaymiz. M to'plam effektiv rekursiv sanaluvchi to'plam bo‘ladi, chunki uning elementlarini hosil qilish uchun ketma-ket natural sonlarni olib, ularni kvadratga ko‘tarish kerak. Bu to'plam ham rekursiv bo‘ladi. Haqiqatan ham, birorta x natural sonning M to‘plamga kirish yoki kirmasligini aniqlash uchun uni tub ko‘paytuvchilarga ajratish kerak. Bu usul x natural son biror natural sonning kvadratimi yoki yo‘qmi degan savolga javob topish imkonini beradi.

2- misol. Tartiblangan natural sonlar juftliklaridan iborat to‘plam effektiv rekursiv sanaluvchi ekanligini isbotlaymiz. Tartiblangan natural sonlar juftliklaridan iborat to‘plamning effektiv rekursiv sanaluvchi ekanligini isbotlash uchun diagonal metodi deb aytiluvchi usuldan foydalanamiz. Buning uchun hamma tartiblangan natural sonlar juftliklarini 1- shakldagi ko'rinishda yozamiz. Yuqori chap burchakdan boshlab ketma-ket 1- shaklda ko‘rsatilgan yo‘nalishlar bo‘yicha o‘tib to‘plam elementlarini sanab chiqamiz. U holda bu juftliklaming


Download 33,2 Kb.

Do'stlaringiz bilan baham:
1   ...   10   11   12   13   14   15   16   17   18




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish