Mirzo Ulug‘bek nomidagi O‘zbekiston Milliy universiteti Jizzax filiali “Amaliy matematika” fakulteti

Mirzo Ulug‘bek nomidagi
O‘zbekiston Milliy universiteti Jizzax filiali

“Amaliy matematika” fakulteti

“Amaliy matematika va informatika” kafedrasi

“Algoritmlar Nazariyasi” fanidan

Mustaqil ishi


Mavzu: Norekursiv Funksiyalar

Bajardi: 102-19-guruh talabasi : Ummatov Izzatbek

Fan o‘qituvchisi: Ulug‘murodov Sh

Reja:

1.Norekursiv funksiyalar haqida.

2.Rekursiv va norekursiv funksiyalar o’rtasida farq.

3.Norekursiv funksiyalarga misollar.

Norekursiv funksiyalar haqida

Norekursiv funksiyalar dasturda bir necha funktsiyalardan foydalangan holda Bu funktsiyalar hisoblash elementlari bir biriga bo’g’liq bolmasa ushbu funktsiyalar norekursiv funktsiyalar deyiladi. Bunday funktiyalardan ko’p hollarda sodda algoritmlarda ishlatiladi. Algoritmlarni baholash uchun ko’pgina mezonlar mavjud. Odatda kirituvchi berilganlarni ko’payishida masalani yechish uchun kerak bo’ladigan vaqt va xotira hajmlarini o’sish tartibini aniqlash muammosi qo’yiladi. Har bir aniq masala bilan kiritiladigan berilganlarni miqdorini aniqlovchi qandaydir sonni bog’lash zarur. Bunday son masalaning kattaligi deb qabul qilinadi. Masalan, ikkita matritsani ko’paytirish masalasining o’lchami bo’lib, matritsalar kattaligiga xizmat qilishi mumkin. Graflar haqidagi masalada o’lcham sifatida graf shohlarining soni bo’lishi mumkin. Algoritm sarflanayotgan vaqt masalaning o’lchami funksiyasi sifatida algoritmni vaqt bo’yicha qiyinligi deb nomlanadi. Bunday funksiyaga masalaning kattaligi oshganda limit ostidagi o’zgarish asimptotik qiyinlik deb aytiladi. Shunga o’xshab, hajmiy qiyinlik va asimptotik hajmiy qiyinlikni aniqlash mumkin. Aynan algoritmning asimptotik qiyinligi natijada shu algoritm yordamida yechiladigan masalarni kattaligini aniqlaydi. Agar algoritm n kattalikdagi kirishlarni 2 С  n vaqtda qayta ishlasa (c-const), unda algoritmning vaqt bo’yicha qiyinligi teng deb hisoblanadi, va n tartibda deb aytiladi. Hisoblash mashinalar tezligi oshishiga qaramasdan, ular yordamida yechilayotgan masalalar kattaligini oshishini algoritm qiyinligini tahlil orqali aniqlaydi. Faraz qilaylik, A1,A2,…,A5 nomli 5 ta algoritm quyidagi vaqtli qiyinliklar bilan berilgan. Algoritm va uning qiyinligini batafsilroq muhokama qilish uchun biz algoritmni amalga oshirish uchun qo’llaniladigan hisoblash qurilmalarning modelini va hisoblashning elementar qadamini aniqlashimiz zarur. Afsus-ki, sharoitlarga mos keladigan modelni o’zi yo’q. Eng katta qiyinchilikni mashina so’zlarining kattaliklari tug’diradi. Masalan, agar mashina so’zi ixtiyoriy uzunlikda butun son shaklini qabul qilsa, unda butun masalaning kodi mashina so’zi ko’rinishdagi bir son bo’lishi mumkin. Lekin mashina so’zining uzunligi cheklangan bo’lsa, unda masalaning kattaligi kamroq bo’lganda muammolar yechilsa ham, oddiy katta sonlarni xotiralashda qiyinchiliklar tug’ilishi mumkin. Algoritm va uning qiyinligini batafsilroq muhokama qilish uchun biz algoritmni amalga oshirish uchun qo’llaniladigan hisoblash qurilmalarning modelini va hisoblashning elementar qadamini aniqlashimiz zarur. Afsus-ki, sharoitlarga mos keladigan modelni o’zi yo’q. Eng katta qiyinchilikni mashina so’zlarining kattaliklari tug’diradi. Masalan, agar mashina so’zi ixtiyoriy uzunlikda butun son shaklini qabul qilsa, unda butun masalaning kodi mashina so’zi ko’rinishdagi bir son bo’lishi mumkin. Lekin mashina so’zining uzunligi cheklangan bo’lsa, unda masalaning kattaligi kamroq bo’lganda muammolar yechilsa ham, oddiy katta sonlarni xotiralashda qiyinchiliklar tug’ilishi mumkin.