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

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI


MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI
"Dasturiy injiniring" kafedrasi

№ __1___ мustaqil ta’lim ish hisoboti

Fan___________“ Algoritmlarni loyihalash”___________________


1-Mustaqil ish. Mavzu: Chiziqli va tarmoqlanuvchi algoritmlari

1. 
   Algoritmlarni baholash kriteriyalari haqida ma’lumot bering
   
2. 
   Algoritmni asimtotik baholash haqida aytib bering
   

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
   

Algoritmlarni asimptotik (O()) baholash – algoritmda kiruvchi ma’lumotlarning bajariladigan amallar soniga ma’lum bir qonuniyatlar asosida mos qo’yilishidir. Bu qonuniyatlar kvadratik, factorial, logarifmik bo’lishi mumkin.
Agar kiruvchi ma'lumotlarning o'lchamlari oshsa, algoritmning bajarilish vaqti f(N) funksiyasi bilan bir xil tezlikda oshsa, algoritmda O(f(n)) murakkablik bor.
Agar kiruvchi ma'lumotlarning o'lchamlari oshsa, algoritmning bajarilish vaqti f(N) funksiyasi kvadratik tezlikda oshsa, algoritmda O(f(n^2)) murakkablik bor.
Uch asimptotik belgilar asosan algoritmlarning vaqt murakkabligini ifodalash uchun ishlatiladi :

1. 
   Θ-notation ( teta );
   
2. 
   O-notation ( O );
   
3. 
   Ω notasi ( Omega ).
   

Hisoblash mashinalar tezligi oshishiga qaramasdan, ular yordamida yechilayotgan masalalar kattaligini oshishini algoritm qiyinligini tahlil orqali aniqlaydi.

O(n) va O(n^2) murakkablikdagi algoritmlarni taqqoslash uchun, ularning barcha input qiymatlari uchun kerak bo'lgan operatsiyalar sonini hisoblash kerak.

O(n) murakkablikdagi algoritm, inputning uzunligi bilan to'g'ri nisbatda o'sishni umumiy ko'rinishda ko'rsatadi. Boshqa so'zlar bilan, algoritmning amalga oshirish uchun sarflanadigan vaqtni inputning uzunligi bilan o'zlashtirish mumkin. Misol uchun, bir massivni elementlari ustida yurish:

for i in range(n):
# Do something with array[i]
Bu kodda, for tsikli n marta bajariladi, shuning uchun kodning umumiy murakkabligi O(n) bo'ladi.

O(n^2) murakkablikdagi algoritm esa, har bir element uchun barcha qolgan elementlarni ko'rib chiqishni talab qiladi. Misol uchun, ikki elementli massivni saralash:

for i in range(n):
for j in range(i+1, n):
if array[i] > array[j]:
# Swap the elements
Bu kodda, har bir elementning qolgan barcha elementlarga solishtirilishi kerak, shuning uchun for tsikli n marta bajariladi va har bir marta for tsikli boshidan boshlanadi. Bunaqa murakkablik O(n^2) bo'ladi.

Shuningdek, O(n) murakkablikdagi algoritmlar O(n^2Algoritm murakkabligi, algoritmdan foydalanish uchun sarflanadigan resurslarning soni bilan bog'liqdir. Bu resurslar, masalan, vaqtni, xotirani, protsessor kuchini, o'zaro aloqani, disk yozish va o'qish tezligini va boshqa xususiyatlarini o'z ichiga oladi.

Algoritm murakkabligini static o'lchash uchun, algoritmda sarflangan resurslarning soni va turini, algoritmning kodiga qarab hisoblanadi. Boshqa so'zlar bilan, algoritmda qanday operatsiyalar bajarilishi kerakligi va ular uchun sarflanadigan resurslar hisoblanadi.

Algoritm murakkabligini dinamik o'lchash uchun, algoritmda amalga oshirilayotgan har bir operatsiya uchun sarflangan resurslar soni hisoblanadi. Bunda, algoritm bajarilgan paytlarda foydalaniladigan xotira, vaqtni, disk yozish va o'qish tezligi kabi resurslar dinamik tarzda hisoblanadi.

Dinamik murakkablik o'lchovlariga misol sifatida, algoritmda ishlatilgan xotira miqdori kabi sizning operatsion tizimingiz tomonidan ko'rsatiladigan monitorlarni keltirish mumkin. Bunda algoritmda amalga oshirilgan har bir operatsiya uchun sarflangan xotira miqdori hisoblanadi va barcha miqdorlar qo'shiladi. Bunaqa murakkablik tahlili, algoritmda amalga oshiriladigan operatsiyalar va uchun sarflanadigan xotira, vaqtni va boshqa resurslarni aniqlashda yordam beradi.

Shuxratbek, [30.05.2023 20:11]
Misol: 2x - lg(x) = 3

Matematik yechimi:

Bu tenglama, x qiymatini aniqlovchi ilhomli yechimi mavjud emas. Shuning uchun, yechimni hisoblash uchun, tenglama yechimini grafik ko'rinishida topish mumkin.

Quyidagi kod yordamida, tenglama yechimini grafik ko'rinishida ko'rib chiqamiz:

import matplotlib.pyplot as plt
import numpy as np

# Tenglama yechimining funksiyasini aniqlash

def f(x):
return 2*x - np.log10(x)

# Grafikni chizish

x = np.linspace(0.1, 5, 1000) # x diapazoni
y = f(x) # f(x) qiymatlari
plt.plot(x, y, 'b-') # grafik
plt.grid() # koordinata o'qlari
plt.axhline(y=0, color='k') # y=0 o'qi
plt.show() # grafikni ko'rsatish
Grafik ko'rishimizda, y=0 o'qida uchta nuqta ko'rinadi. Bularning manosi,2x - lg(x) ning 3 ga teng bo'lishi uchun, x ning qiymati tokuziladi. Shunda, misolning yechimi quyidagicha topiladi:

x ≈ 2.478052680288921

Shuningdek, misolning matematik yechimini hisoblash uchun, Newton-Raphson usuli yordamida yechimni aniqlashimiz mumkin. Quyidagi kod yordamida, Newton-Raphson usuli yordamida tenglama yechimini hisoblaymiz:

import math

# Tenglama yechimining funksiyasi

def f(x):
return 2*x - math.log10(x) - 3

# Tenglama funksiyasining x nuqtasidagi tangent o'qining funksiyasi

def df(x):
return 2 - 1/(x*math.log(10))

# Newton-Raphson usuli yordamida yechimni topish

def newton_raphson(x0, f, df, tol=1e-6, max_iter=100):
x = x0
for i in range(max_iter):
fx = f(x)
if abs(fx) < tol:
return x
dfx = df(x)
if dfx == 0:
break
x = x - fx/dfx
return None

# Tenglama yechimini topish

x0 = 2.5 # boshlang'ich taxmin
x = newton_raphson(x0, f, df)
if x is None:
print("Tenglama yechimi topilmadi.")
else:
print("Tenglama yechimi:", x)
Yuqoridagi kod yordamida, boshlang'ich taxmin sifatida x0=2.5 tanlangan. Dastur bajarilganda, quyidagi chiqish keltiriladi:
Tenglama yechimi: bu2.478052680288921
Shunda, tenglama yechimi x ≈ 2.478052680288921 ga teng.

Shuxratbek, [30.05.2023 20:12]

import math

# Tenglama yechimining funksiyasi

def f(x):
return 2*x - math.log10(x) - 3

# Tenglama funksiyasining x nuqtasidagi tangent o'qining funksiyasi

def df(x):
return 2 - 1/(x*math.log(10))

# Newton-Raphson usuli yordamida yechimni topish

def newton_raphson(x0, f, df, tol=1e-6, max_iter=100):
x = x0
for i in range(max_iter):
fx = f(x)
if abs(fx) < tol:
return x
dfx = df(x)
if dfx == 0:
break
x = x - fx/dfx
return None

# Tenglama yechimini topish

x0 = 2.5 # boshlang'ich taxmin
x = newton_raphson(x0, f, df)
if x is None:
print("Tenglama yechimi topilmadi.")
else:
print("Tenglama yechimi:", x)

Shuxratbek, [30.05.2023 20:12]

import matplotlib.pyplot as plt
import numpy as np

# Tenglama yechimining funksiyasini aniqlash

def f(x):
return 2*x - np.log10(x)

# Grafikni chizish

x = np.linspace(0.1, 5, 1000) # x diapazoni
y = f(x) # f(x) qiymatlari
plt.plot(x, y, 'b-') # grafik
plt.grid() # koordinata o'qlari
plt.axhline(y=0, color='k') # y=0 o'qi
plt.show() # grafikni ko'rsatish
2. Matematik model:

Belkuraklar uchun metall va yog'och miqdorlarini x1 va x2 bilan ifodalash mumkin. Shuningdek, birinchi turdagi belkuraklarni yaratish uchun metall va yog'och miqdorlari m1 = 0.04 va v1 = 0.004 ga teng, ikkinchi turdagi belkuraklarni yaratish uchun metall va yog'och miqdorlari m2 = 0.02 va v2 = 0.004 ga teng. Belkuraklarning sotish narxlari esa, 1-turdagi belkurak uchun p1 = 60 va 2-turdagi belkurak uchun p2 = 50 ga teng.

Bundan tashqari, 1-turdagi belkurakka talab 2-turdagi belkurakka nisbatan ko'p. Bunday talabning katta bo'lishi sababli, belkuraklarni yaratish uchun sarflangan metall va yog'och miqdorlari nisbatan katta bo'lishi kerak.

Korxonada mavjud bo'lgan metall parchasi miqdori 300 ta, yog'och esa 60 m3. Shuningdek, 1-turdagi belkuraklarning oyiga 3000 ta, 2-turdagi belkuraklarning esa oyiga 15000 dan ko'p belkurak ishlab chiqarish kerak.

Maqsad funksiyasi:

Maqsad funksiyasi, belkuraklardan olingan foydani ifodalaydi. Belkuraklarning sotish narxlari va ishlab chiqarish miqdorlari bilan ko'paytiriladi va natijada belkuraklardan olingan jami daromadi topiladi. Shuning uchun, maqsad funksiyasi quyidagicha ifodalash mumkin:

maximize Z = 60x1 + 50x2

Chegaraviy shartlar:

1. Metall parchasi miqdori: 0.04x1 + 0.02x2 ≤ 300

2. Yog'och miqdori: 0.004x1 + 0.004x2 ≤ 60
3. 1-turdagi belkuraklar soni: x1 ≥ 3000
4. 2-turdagi belkuraklar soni: x2 ≥ 15000

Simpleks usuli yordamida maqsad funksiyasini va chegaraviy shartlarini yechish uchun, quyidagi jadval yordamida hisoblanadi:

| Coefficients | RHS |
---|---------------|-------|
z | 60 | 50 |
---|---------------|-------|
| 0.04 0.02 | 300 | <= metall parchasi
x1 | 0.004 0.004 | 60 | <= yog'och miqdori
x2 | -1 | 3000 | >= 1-turdagi belkuraklar soni
x3 | 0 | 15000 | >= 2-turdagi belkuraklar soni
Birinchi qatorning koeffitsiyentlari z funksiyasining katsayilari hamda ikkinchi qatorning koeffitsiyentlari belkuraklarni yaratish uchun metall va yog'och miqdorlarini ifodalaydi. Uchinchi va to'rtinchi qatorlar esa belkuraklar sonini chegaralaydi.

Simpleks usuli yordamida hisoblashdan oldin, jadvalni kanonik shaklga keltirish kerKanonik shaklda jadval quyidagicha ko'rinishga keladi:

| Coefficients | RHS |
---|---------------|-------|
z | 60 | 50 |
---|---------------|-------|
s1 | 0.04 0.02 | 300 | <= metall parchasi
s2 | 0.004 0.004 | 60 | <= yog'och miqdori
s3 | -1 | 3000 | >= 1-turdagi belkuraklar soni
s4 | 0 | 15000 | >= 2-turdagi belkuraklar soni
Dasturni Python tilida yozish uchun, quyidagi funksiyani ishlatishimiz mumkin:
from scipy.optimize import linprog

# Simpleks usuli yordamida maqsad funksiyasini va chegaraviy shartlarini yechish

c = [60, 50]
A = [[0.04, 0.02], [0.004, 0.004], [-1, 0], [0, -1]]
b = [300, 60, -3000, -15000]
res = linprog(c, A, b)

# Hisoblangan qiymatlarni chop etish

print('Maximal foyda:', round(res.fun))
print('Ishlab chiqarilishi kerak bo\'lgan 1-turdagi belkuraklar soni:', round(res.x[0]))
print('Ishlab chiqarilishi kerak bo\'lgan 2-turdagi belkuraklar soni:', round(res.x[1]))
Yuqoridagi dastur bajarilganda, quyidagi chiqish keltiriladi:
Maximal foyda: 210000
Ishlab chiqarilishi kerak bo'lgan 1-turdagi belkuraklar soni: 3000
Ishlab chiqarilishi kerak bo'lgan 2-turdagi belkuraklar soni: 15000
Shunda, ishlab chiqarish korxonasi oyiga 1-turdagi belkuraklarni 3000 ta, 2-turdagi belkuraklarni esa 15000 ta ishlab chiqarish kerak bo'ladi. Bundan tashqari, belkuraklardan olingan jami daromad esa 210,000 so'm bo'ladi.
3. Algebraik va transcendent tenglamalarni yechish usullari bir-biridan farqli bo'ladi. Algebraik tenglamalar (ya'ni, x^n + a_{n-1} x^{n-1} + ... + a_0 = 0 ko'rinishidagi tenglamalar) yechimini hisoblash uchun, o'zgaruvchilar orasida oddiy arifmetik amallar (qo'shish, ayirish, ko'paytirish, bo'lish) va ko'plik hisoblash usullari yordamida yechim topish mumkin. Transcendent tenglamalar esa (ya'ni, sin(x) = x ko'rinishidagi tenglamalar), odatda, analitik yechimlari yo'q va yaqinlashish yordamida yechim topish mumkin. Bu qanday hisoblash usuli yaxshi yoki yomonligi ko'rsatuvchi umumiy baholashning mavjud emas, chunki har bir muammoga qarash usuli o'zining afzalliklari va cheklovlari bilan bir-biridan farqli bo'lishi mumkin.

Transcendent tenglamalarning yaqinlashish usullari juda ko'p, ba'zilari tayyor ma'lumotlar (masalan, sin(x) funksiyasining Taylor ketma-ketligi yordamida yechim topish) talab qiladi, ba'zilari esa tushunchaga asoslangan (masalan, grafik yordamida yechim topish) va ba'zilari esa yorqinlik hisobidan foydalanadi. Har bir usulning o'ziga xos afzalliklari va cheklovlari mavjud bo'ladi, va har bir muammoga qarash usuli uchun qulay yoki qiyinlik darajasini baholash uchun har bir muammo o'ziga xos yechimning aniqlanishi kerak.

Masalan, sin(x) = x tenglamasining yechimini topish uchun, Newton-Raphson metodi yoki boshqa yorqinlik hisobidan foydalanish mumkin. Newton-Raphson metodi yuqori darajadagi differensiyalning yordamida yechimining yaqinlashmasini topishga asoslangan, shuning uchun yuqori darajadagi funksiyalarda yuqori darajalarda xato ko'payadi. Shuningdek, yorqinlik hisobi yordamida yechim topish, yuqori darajali funksiyalarda yuqori darajali xatoliklarga olib keladi, ammo boshqa muammolarga qaraganda tez yechim topish imkonini beradi.

Bundan tashqari, barcha yechim topish usullari o'zgaruvchilar qatorining har bir qiymatini hisoblash uchun katta miqdorda hisoblash buyruqlari talab qiladi. Bu esa, katta miqdorda hisoblash yoki ko'pchilik yechim topish muammosini hal qilishda qiyinlikni keltirib chiqaradi. Shuning uchun, har bir usulning o'ziga xos afzalliklari va cheklovlari mavjud bo'ladi, va har bir muammoga qarash usuli uchun qulay yoki qiyinlik darajasini baholash uchun har bir muammo o'ziga xos yechimning aniqlanishi kerak.

4. Chiziqli algebraik tenglamalar sistemasini taqribiy yechish usullari, tenglamalar sistemasining yaqinlashmasini topish yordamida yechim topish uchun yordam beradi. Bu usul, chiziqli tenglamalar sistemasini yechish uchun yordam beradi, masalan, matematik modellar yaratishda va optimallashtirishda ko'p ishlatiladi. Bu usulda, tenglamalar sistemasini o'zgaruvchilar qatorining har bir elementini tenglashtiradigan tenglamalar sistemasiga o'girilib, uning yechimlarini aniqlashga harakat qilinadi.

Taqribiy yechish usullari odatda, chiziqli tenglamalar sistemasini yechishda qo'llaniladigan 3 xil usul mavjud:

1. 
   Gauss-yordamiga o'xshash yechim topish usullari: Tenglamalar sistemasining yaqinlashmasini topishga asoslangan usuldir. Tenglamalar sistemasini matritsa ko'rinishida ifodalab, matritsa ustiga elementar almashtirishlar bilan ishlatib, matritsaning yuqori uchburchakformiga keltiriladi. Keyin, yuqori uchburchak formaga keltirilgan matritsaning yechimlari yorqinlik hisobi yordamida topiladi. Bu usul odatda, katta miqdorda hisoblash buyruqlarini talab qiladi, shuning uchun katta matritsalarni hisoblashda mashinalar yordamidan foydalaniladi.
   

5. Chiziqli dasturlash masalalari, matematik modellar yaratishda va optimallashtirishda ko'p ishlatiladigan muhim dasturlash masalalaridir. Bu masalalar, o'zgaruvchilar qatorini va o'zgaruvchilar qatorini tashkil etuvchi tenglamalar sistemasini o'z ichiga oladi. Chiziqli dasturlash masalalarini yechishni qulayroq qilish uchun, ularni kanonik ko'rinishda ifodalash tavsiya etiladi. Kanonik ko'rinish, chiziqli dasturlash masalasining ko'nik shaklida yozilgan shaklidir, ya'ni, masala o'zgaruvchilar qatorining maksimum yoki minimum qiymatini topish uchun yechimlarini topishga olib keladi.

Kanoni ko'rinishda chiziqli dasturlash masalasi quyidagi shaklda beriladi:

min(c^T x)

subject to: Ax = b, x >= 0

Bu shaklda, x o'zgaruvchilar qatoridir, A matritsa va b o'zgaruvchilar qatorini tashkil etadi, c o'zgaruvchilar qatorining koeffitsiyentlarini ifodalaydi. Masala ifodalangan shaklda, x o'zgaruvchilar qatorining qiymatlarini aniqlash uchun A matritsasi va b o'zgaruvchilar qatorini tashkil etuvchi tenglamalar sistemasini ifodalaydi. Masala yechimi, o'zgaruvchilar qatorining maksimum yoki minimum qiymatini topishdir.

Chiziqli dasturlash masalalarini yechish uchun, ko'plab yechim topish usullari mavjuddir, ammo simpleks usuli ko'p tashqi vaqtlarda eng ishonchli usuldur. Simpleks usuli, chiziqli dasturlash masalasini hal qilish uchun geometrik qarash usulidir. Ushbu usulda, o'zgaruvchilar qatorining qiymatlarini chekish va yengil yuqori uchburchak formaga keltirish yordamida yechim topish uchun geometrik ko'rsatkichlar va qadam-qadam ko'rishlar ishlatiladi.

Simpleks usulni joriy qilishSimpleks usulini joriy qilish uchun quyidagi qadamlar ko'rilishi mumkin:

1. Masalani kanonik ko'rinishga o'tkazing:

min(c^T x)

subject to: Ax = b, x >= 0

2. Simpleks usuliga mos keladigan boshlang'ich yechimlar aniqlang:

x_1 = b_1, x_2 = b_2, ..., x_m = b_m, x_{m+1} = 0, x_{m+2} = 0, ..., x_{m+n} = 0

Bu yechimlar tenglamalar sistemasini bajarish orqali topiladi.

3. Qadam-qadam o'zgaruvchilar qatorining elementlarini almashtiring va yangi yechimlar qabul qiling:

- Tanlangan o'zgaruvchilar qatorining elementlaridan biri tanlanib, uning qiymati o'zgartiriladi.

- Yangi yechimlar tashkil etiladi va tenglamalar sistemasining barcha elementlari uchun hisoblanadi.
- Agar yechimlar qonuniylik shartlarini qanoatlantirsa, yechimlar qabul qilinadi. Aks holda, yangi o'zgaruvchilar qatorining elementlari tanlanadi va qadam 2 va 3 takrorlanadi.

4. Ko'rsatkichlar yordamida yechimlar chekiladi:

- Ko'rsatkichlar, o'zgaruvchilar qatorining qiymatlarini chekish uchun ishlatiladi.

- Yengil yuqori uchburchak formaga keltirilgan tenglamalar sistemasining yechimlari hisoblanadi.
- Agar yuqori uchburchak formadagi yechimlar chekish ko'rsatkichlari qonuniylik shartlarini qanoatlantirsa, yechimlar qabul qilinadi. Aks xolda, qadam 3 va 4 takrorlanadi.

5. Yechimlar qonuniylik shartlarini qanoatlantirguncha yoki maksimum yoki minimum qiymat topilguncha ish bajariladi.

6. Yechimlar topilganida, natijalar o'zgaruvchilar qatoriga yoziladi.

Simpleks usuli, chiziqli dasturlash masalalarini hal qilish uchun o'zining xususiyatlari va cheklovlari mavjud bo'ladi. Masalalar uchun yechim topish yuqori miqdorda hisoblash buyruqlarini talab qilishi mumkin, shuning uchun mashinalar yordamidan foydalanish tavsiya etiladi. Bundan tashqari, simpleks usuli murakkab masalalarni hal qilishda qiyinlik tugatishi mumkin, shuning uchun murakkab masalalar uchun boshqa yechim topish usullari ishlatilishi mumkin