Ma’ruza. Algoritmlarni baxolashdagi mezonlar. Algoritmlarni vaqt va hajm bo’yicha baholash

Algoritmik hal etilmaslik. Shunday masalalar borki uning yechimini olish uchun
umumiy algoritm (Tyuring mashinasi) mavjud emas, bu masalalarni tavsiflovchi
kirish ma’lumotlari qo’llaniladigan algoritmlar ishlamaydi yoki cheksiz davom
etadi.

---

1-masala.
sonida sonining taqsimlanishini hisoblash;
= 3,141592 … ,
9
(1) = 5.
= 48
(1/18) + 24
(1/57) − 20
(1/239).
Ixtiyoriy uchun
( ) funksiyani hisoblash masalasi.
2-masala. Mukammal sonlarni hisoblash;
Mukammal son – bu o’zining bo’luvchilari yig’indisidan tashkil topgan son,
masalan:
(1) = 1 = 1
(2) = 6 = 1 + 2 +3
(3) = 28 = 1 + 2 + 4 + 7 + 14.
Ixtiyoriy berilgan soni uchun ( ) ni hisoblash masalasi.
Algoritmni to’liq qurish bosqichlari bilan quyida tanishib chiqamiz:
1) Masalaning qo’yilishi
2) Modelni qurish
3) Algoritmni ishlab chiqish
4) Algoritm to’g’riligini tekshirish
5) Kodlashtirish
6) Dasturni tekshirish
7) Hujjatlashtirish
Algoritmlarni tuzish – bu ijodiy ish bo’lib, ixtiyoriy zaruriy algoritmni tuzish uchun
umumiy usullar mavjud emas, kishining ijodiy qobiliyatiga bog’liq.
Albatta, algoritmni aniq sxema bo’yicha tuzish zarur bo’lib qoladigan sodda
hollar ham mavjud. Bunday hollarda yechilish algoritmi avval biron kim tomonidan
olingan masalalarni misol keltirish mumkin. Masalan, differensial tenglamalarni
sonli integrallash uchun Eyler metodi. Bu metod masalani yechish uchun umumiy
holda ifodalangan algoritmdir.
Algoritmlar sifatini baholash uchun mezonlarni ko’raylik. Mavjud mezonlar
juda taxminlashgan. Masalan, algoritmni bajarishda bajaruvchining xotira
uskunalari hajmi yetarli bo’lmasa, u algoritm yomon deb hisoblanadi. Boshqa
mezon sifatida algoritmning bajarilishi uchun talab qilinadigan vaqtni ko’rsatish
mumkin. Vaqtni baholash bajaruvchining fizik xarakteristikalari hisobga olinishi
kerak. Chunki har bir operatsiya har xil o’zgaruvchilar bilan bajarilganda vaqt ham
har xil bo’ladi. Bunchalik aniq ma’lumotni har bir foydalanuvchi uchun yig’ib
bo’lmaganligi sababli odatda o’rtacha tezkorlik qabul qilinadi. Ketma-ket
bajarilayotgan operatsiyalar sonini aniqlab, uni o’rtacha tezkorlikka ko’paytirsa,
algoritm bajarilishining amalga yaqin bo’lgan vaqtini topishimiz mumkin.

---

Demak, algoritmlarni baholash uchun ikkita asosiy kretiriya mavjud ekan.
1) Algoritmni ishlash vaqti bo’yicha baholash
2) Algoritmni bajarish uchun xotiradan egallagan hajmi bo’yicha baholash