O‘ZBEKISTON RESPUBLIKАSI
RAQAMLI TEXNOLOGIYALАR VАZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI
UNIVERSITETI SAMARQAND FILIALI
"Algoritmlarni loyihalash” fanidan
MUSTAQIL ISH №1
Mavzu:Chiziqli va tarmoqlanuvchi algoritmlar.
Bajardi: KIS21_01-guruh talabasi
Abdusamatov S.B.
Qabul qildi: Mamayev E.SH.
Samarqand– 2024
SAVOLLAR
1.Algoritm murakkabligini statik va dinamik o'lchovlari. Vaqt va
xotira hajimi bo'yicha qiyinchiliklar.
2.Algoritmlarni eng yomon va o’rtacha holatlarda baholash.
3.
Algoritmlarni vaqt va hajmiy murakkablik bo’yicha baholashda tekis va
logarifmik solishtirma mezonlar.
4.
Taqribiy integrallash usuli va aniqligi bo’yicha hisoblash.
Savollar javoblari:
1.
Mavjud algoritmlarning ko’pchilig xotira va tezlik o’rtasida tanlovni taklif
qiladi. Masala tez ishlashi va katta xotira egallashi yoki sekin ishlashi va kichik
xotira hajmini egallashi mumkin. Bu holatda eng odatiy misollardan biri eng
qisqa masofani topish masalasi bo’la oladi. Bunda siz o’zaro bog’liq bo’lgan
shahar orasidagi istalgan ikki nuqta orasidagi eng qisqa masofani topishingiz
kerak bo’ladi. Bunda biz barcha nuqtalar orasidagi qisqa masofalarni aniqlab
ularni jadval shaklida saqlab qo’yishimiz mumkin. Va biz eng qisqa masofani
aniqlashimizga to’g’ri kelganda shunchaki jadvaldan ma’lumotni olib
qo’yishimiz mumkin bo’ladi. Natijani shu
zahoti olishimiz mumkin, ammo bu
juda katta hajm talab qiladi. Masalan biror katta xaritada 10 minglab nuqtalar
bo’lishi mumkin va bizning jadvalimiz buning uchun 10 milliarddan ortiq
ma’lumotni saqlashiga to’g’ri keladi va bu taxminan 10GB ga yaqin xotirani
band etishi mumkin. Ushbu holatdan hajm-vaqt murakkabligi kelib chiqadi.
Shunda algoritm vaqt bo’yicha ishlash tezligi yoki hajm bo’yicha ishlash tezligi
bilan baholanadi. Biz asosiy e’tiborni vaqt bo’yicha murakkablikka qaratamiz
lekin shu bilan birga foydalaniladigan xotira hajmini
ham aniq belgilashimizga
to’g’ri keladi.
2.
Bitta masalani hal qilish uchun turli xil algoritmlarni ko'rib chiqsak, ular
qancha hisoblash resurslarini (ishlash vaqti, xotira) talab qilishini tahlil qilish va
eng samaralisini tanlash foydalidir. Albatta, biz hisoblashning qaysi turidan
foydalanilganligi to'g'risida kelishib olishimiz kerak .. Algoritmning ishlash vaqti
bilan biz bajaradigan elementar qadamlar sonini tushunamiz. Aytaylik,
psevdokodning bir qatorida belgilangan miqdordagi operatsiyalar talab qilinadi
(masalan, ba'zi murakkab harakatlarning og'zaki tavsifi bo'lmasa - masalan,
"hamma nuqtalarni x-koordinata bo'yicha saralash"). Qo'ng'iroq qilish (qo'ng'iroq
qilish) protsedurasini (ma'lum miqdordagi operatsiyalarni oladi) va uning
bajarilishini (bajarilishini) farqlashingiz kerak, ular uzoq davom etishi mumkin.
Algoritmning murakkabligi bu vazifaning o'lchamiga
qarab talab qilinadigan
manbaning kattaligi tartibini (vaqt yoki qo'shimcha xotira) aks ettiradigan
qiymatdir. Shunday qilib, biz algoritmning vaqtinchalik T (n) va fazoviy V (n)
murakkabligini ajratamiz. Murakkablikni baholashni ko'rib chiqishda biz
vaqtinchalik murakkablikdan foydalanamiz. Fazoviy murakkablik ham shunga
o'xshash tarzda baholanadi. Baholashning eng oson usuli bu eksperimental usul,
ya'ni algoritmni dasturlash va natijada olingan dasturni bir nechta vazifalar
bo'yicha
bajarish, dasturlarning bajarilish vaqtini baholash. Biroq, bu usul bir
qator kamchiliklarga ega. Birinchidan, eksperimental dasturlash, ehtimol qimmat
jarayon. Ikkinchidan, shuni yodda tutish kerakki, dasturlarning bajarilish vaqtiga
quyidagi omillar ta'sir qiladi:
1. Dastur algoritmining vaqt murakkabligi;
2. bajariladigan dasturning kompilyatsiya qilingan kodining sifati;
3. Dasturni bajarish uchun ishlatiladigan mashina ko'rsatmalari.
Ikkinchi va uchinchi omillarning mavjudligi algoritmning vaqt murakkabligini
o'lchashning tipik birliklaridan foydalanishga imkon bermaydi (soniya,
millisekundlar va boshqalar), chunki agar siz turli xil dasturchilar (har bir
algoritmni kim dasturlasa) bir xil algoritm uchun har xil baholarni olish mumkin.
o'z),
turli
xil
kompilyatorlar
va
turli
xil
kompyuterlar.
Ko'pincha, algoritmning vaqt murakkabligi kiritish hajmiga bog'liq. Odatda
algoritmning vaqt murakkabligi n o'lchamidagi kirish ma'lumotlarini T (n)
tartibiga to'g'ri keladi, deyiladi. Amaliyotda T (n) ning aniq qiymatini aniqlash
juda qiyin. Shuning uchun ular O-simvolizmidan foydalanib,
asimptotik
munosabatlarga
murojaat
qilishadi.Keyinchalik
muhokama
qilinadigan
algoritmning bajarilish vaqtini nazariy jihatdan hisoblaydigan usul mavjud.
3.
Algoritmlarni tahlil qilishning asosiy vazifasi kirish ma'lumotlari hajmining
oshib borishi bilan resurslarga bo'lgan talabni (vaqt va xotira xarajatlari) o'lchash
usullarini aniqlashdir. Shundan so'ng, o'sish sur'ati qonuniyatlarini tavsiflash
uchun zarur bo'lgan matematik mexanizm ishlab chiqiladi. Kirish ma'lumotlari
hajmini oshirish bilan turli xil funktsiyalar; "bitta funktsiya boshqasiga
qaraganda tezroq o'sadi" iborasi nimani anglatishini aniqlab olishga yordam
beradi. Ba'zi hollarda, yaxshi bajarilish vaqtiga erishish yanada murakkab
ma'lumotlar tuzilmalaridan foydalanishga bog'liq va bo'lim
oxirida biz bunday
ma'lumotlar strukturasining juda foydali misolini ko'rib chiqamiz: ustuvor
navbatlar
va
ularni
uyum(kucha,
heap)
asosida
amalga
oshirish.
Asosiy maqsad - hisoblash muammolarining samarali algoritmlarini izlash.
Ushbu umumiylik darajasida kompyuterni hisoblashning butun sohasi ushbu
mavzu bilan bog'liq bo'lib tuyuladi; bizning yondashuvimiz boshqalardan qanday
farq qiladi? Algoritmlarni ishlab chiqishda umumiy mavzular va loyihalash
tamoyillarini aniqlashga harakat qilamiz. Bizni samarali algoritmlarni
loyihalashning asosiy usullarini minimal ma'lumot bilan namoyish etuvchi
paradigmatik masalalar va usullar qiziqtiradi.Algoritmni
bajarilish qadami - bu
ijrochi tomonidan bitta ko‘rsatmaning bajarilishidir. Bir masalani hal etuvchi
ikkita algoritmdan kam qadam talab qilinayotgani samaraliroqdir. Samaradorlik
o‘lchovi - bu bor-yo‘g‘i qadamlar sonidir. Lekin chuqurroq e’tibor berib qarasak,
bu ta’rifdagi mujmal tomonlarni aniqlaymiz. Ba’zan avval uchragan
algoritmlardagidan ko‘ra vaziyat murakkabroq bo’ladi.Algoritmlar murakkabligi
bilan ham farqlanishi mumkin. Algoritmning murakkabligini uning matnidagi
satrlar soni bilan o‘lchaymiz.
4.
Oliy matematika kursidan malumki aniq integrallar asosan N‘yuton-Leybnits
formulasi bilan hisoblanadi. Yani quyidagi formula bilan hisoblanadi:Bu yerda
F(x) funktsiya f(x) funktsiyaning boshlangich funktsiyasi.
а-integralning quyi b-
esa yuqori chegarsi. Nyuton–Leybnits formulasi bizga ma‘lumki elementar
funktsiyalar uchun foydalanish qulayrok. Lekin har qanday f(x) funktsiyaning
boshlangich funktsiyasi elementar funktsiya bulavermaydi, yani integrallash
murakkab bo’ladi. Bunday aniq integrallarni N‘yuton-Leybnits formulasi bilan
hisoblab bulmaydi. Bunday hollarda integrallarni taqribiy
hisoblash usularidan
foydalanib integrallarning taqribiy kiymatlari topiladi.
Taxminiy integratsiya usullari
integralni aniq hisoblashning imkoni bo'lmaganda uning qiymatini baholash uchun
ishlatiladi. Taxminiy integratsiyaning bir necha usullari mavjud, jumladan, trapezoidal qoida
va Simpson qoidasi.
Trapezoidal qoida - bu mintaqani trapetsiyalarga bo'lish orqali egri chiziq ostidagi maydonga
yaqinlashadigan sonli integratsiya usuli. Trapetsiya qoidasi formulasi:
