Mustaqil ish. Mavzu: Chiziqli va tarmoqlanuvchi algoritmlar. Nazariy malumotlar
Algoritmlarni vaqt va hajmiy murakkablik bo’yicha baholashda tekis va logarifmik solishtirma mezonlar
Algoritmlarni Loyihalash” fanidan 1- laboratoriya ishi
- Bu sahifa navigatsiya:
- 4. Taqribiy integrallash usuli va aniqligi bo’yicha hisoblash Aniq integralni taqribiy hisoblash usullari
|
Ko'pgina algoritmlar xotira hajmi va tezligi o'rtasida tanlovni taklif qiladi. Muammoni tezroq, katta hajmdagi xotiradan foydalangan holda yoki ozroq hajmni olib, sekinroq hal qilish mumkin. Bu holatda odatiy misol eng qisqa yo'llarni qidirish algoritmi hisoblanadi. Tarmoq shaklida shahar xaritasini taqdim etib, siz ushbu tarmoqning har qanday ikkita nuqtasi orasidagi eng qisqa masofani aniqlash uchun algoritm yozishingiz mumkin. Bu masofalarni kerak bo'lganda hisoblamaslik uchun barcha nuqtalar orasidagi eng qisqa | |
|
masofani ko'rsatib, natijalarni jadvalga saqlashimiz mumkin. Berilgan ikkita nuqta orasidagi eng qisqa masofani aniqlashimiz kerak bo'lsa, biz shunchaki jadvalning tugagan masofasini olishimiz mumkin. Natija bir zumda olinadi, ammo bu juda katta hajmdagi xotirani talab qiladi. Katta shahar xaritasida o'n minglab fikrlar bo'lishi mumkin. Keyin, yuqorida tavsiflangan jadvalda 10 milliarddan ortiq hujayralar bo'lishi kerak. Bular Algoritmning ishlashini yaxshilash uchun qo'shimcha 10 Gb xotirani ishlatish kerak. Ushbu qaramlikdan kosmik-vaqt murakkabligi g'oyasi kelib chiqadi. Ushbu yondashuv bilan, algoritm bajarilish tezligi va iste'mol qilinadigan xotira nuqtai nazaridan baholanadi. Vaqtinchalik murakkablikka e'tiborni qaratamiz, ammo shunga qaramay, biz iste'mol qilingan xotiraning hajmini aniq belgilaymiz. |
4. Taqribiy integrallash usuli va aniqligi bo’yicha hisoblash
Aniq integralni taqribiy hisoblash usullari
Odatda aniq integralarni taqribiy hisoblash uchun integralash sohasidagi [a,b] kesma n ta teng bo’lakka bulinadi. Har bir bo’lakning uzunligi h=(b-a)/n formula bilan hisoblanadi.
n bo’laqlar soni qancha ko’p bo’lsa integralning kiymati shuncha aniq
bo’ladi. Integralarni taqribiy hisoblashda ko’pincha to’g’ri burchaqlar, trapetsiyalar va Simpson formulalaridan foydalaniladi. Integrallarning kiymatlarini taqribiy hisoblash uchun biror bir usul tallanadi, sung algoritm tuziladi va bu algoritmlarga mos ravishda biror bir dasturlashtirish tilida dasturlar tuzilib, dasturlar kompyuterga kiritilib natijalar olinadi.
Integrallarning taqribiy hisoblash formulalarini keltirib chiqarish ishlarini ko’rib o’tirmaymiz, bu bizga oliy matematika kursidan ma‘lum. Formulalarning keltirib chiqarish ma‘lumotlarini o’quvchilarga berilgan adabiyotlardan [11] adabiyotdan ukib olishlarini tavsiya etamiz.
Integralning kiymatini taqribiy xisolash formulalarini keltiramiz:
yoki
Bu formula integeralarni taqribiy hisoblashning to’g’ri turtburchaqlar formulasi.
b u formula itegrallarni taqribiy hisoblashning trapetsiya formulasi. ya‘ni
bu yerda
Bu formula esa aniq integralni taqribiy hisoblashning Simpson formulasi
Download 0.5 Mb.
Do'stlaringiz bilan baham:
