Kiruvchi elementlar soni (n = 100) uchun murakkabliklar bo'yicha qadamlar sonini aniqlayamiz
Download 54.78 Kb.
|
Algoritmlarni loyihalash javoblari
|
1] Kiruvchi elementlar soni n=100 bo'lganda 0(1),O(logN),O(NlogN),O(n^3),O(2^n) murakkabliklar uchun qadamlar sonini aniqlang Kiruvchi elementlar soni (n = 100) uchun murakkabliklar bo'yicha qadamlar sonini aniqlayamiz: O(1): Bu murakkablikning qadam soni dasturda o'zgaradigan n ga bog'liq emas. Shu sababli, qadam soni 1 bo'ladi. Buning ma'nosi, kiruvchi elementlar soni o'sishi bilan almashtirish qadam sonini o'zgartirmaydi. O(logN): Logarifmik murakkablikda, qadam soni kiruvchi elementlar sonining logarifmik kattaligi bilan bog'liq bo'ladi. Kiruvchi elementlar soni 100 bo'lganda, log100 = 2. Bu sababli, qadam soni 2 bo'ladi. Buning ma'nosi, kiruvchi elementlar soni o'ssa ham, qadam soni faqatgina o'sadi. O(NlogN): Bu murakkablikda, qadam soni kiruvchi elementlar soni va uni logarifmik kattaligi bilan o'zgaradi. Kiruvchi elementlar soni 100 bo'lganda, NlogN = 100 * log100 = 200 bo'ladi. Buning ma'nosi, kiruvchi elementlar soni o'ssa ham, qadam soni tezroq o'sadi. O(n^3): Kvadratik murakkablikda, qadam soni kiruvchi elementlar sonining kvadrati bilan bog'liq bo'ladi. Kiruvchi elementlar soni 100 bo'lganda, 100^3 = 1,000,000 bo'ladi. Buning ma'nosi, kiruvchi elementlar soni o'ssa ham, qadam soni tezroq o'sadi. O(2^n): Exponential murakkablikda, qadam soni kiruvchi elementlar sonining 2-ning darajasi bilan bog'liq bo'ladi. Kiruvchi elementlar soni 100 bo'lganda, 2^100 juda katta sonni beradi va aniqlanishi to'g'risida juda ko'p vaqt talab qiladi. Bunday murakkablikning qadam sonini amaliyotda aniqlash kuzatiladigan vaqt va resurslar miqdorini oshiradi. Shu sabablarga ko'ra, kiruvchi elementlar soni (n = 100) bo'yicha murakkabliklar uchun qadamlar soni quyidagicha bo'ladi: O(1): 1 O(logN): 2 O(NlogN): 200 O(n^3): 1,000,000 O(2^n): Katta son va tezroq aniqlanishi sababli amaliyotda qadam soni talab qiladi. 2] Integrallarni taqribiy hisoblashda to'rtburchak usuli,algoritmi,formulasini keltiring Integrallarni taqribiy hisoblashda odatda to'rtburchak usuli (rectangle method) yoki to'rtburchaklarni tashkil etish usuli ishlatiladi. Bu usulning algoritmi quyidagicha bo'ladi: Belgilangan integralning tartiblanadigan chegaralarini a va b deb o'zlashtirib olamiz. Integralning tartiblanadigan chegaralarini bir nechta teng bo'lgan n ta bo'luvchilarga ajratamiz. Har bir bo'luvchi uchun kvadrat yoki to'rtburchak shaklini yaratamiz. Har bir to'rtburchakning yuzini hisoblaymiz. Bu uchun to'rtburchakning eni bilan bo'yi ni yig'indisini hisoblaymiz va shu yuzini integralning natijasiga qo'shamiz. Har bir to'rtburchakning yuzini integralga qo'shib natijalarni yig'ib chiqamiz. Yig'indini tartiblash uchun yuqoridagi natijalarni integralni to'rtburchak usuli bilan hisoblangan yuzasidan ko'paytirib olishimiz kerak. Natija, taqribiy integral qiymatini beradi. To'rtburchak usuli formulasi quyidagicha: ∫[a, b] f(x) dx ≈ Δx * (f(x1) + f(x2) + ... + f(xn)) bu yerda Δx = (b - a) / n to'rtburchaklar soni, x1, x2, ..., xn - to'rtburchakning markazidagi nuqtalar, f(x1), f(x2), ..., f(xn) - integraldagi funktsiya qiymatlari. To'rtburchak usulini soddaroq tushuntirish uchun quyidagi misolni ko'rib chiqamiz: Misol: ∫[0, 4] x^2 dx ni to'rtburchak usuli bilan hisoblang. Tartiblanadigan chegaralar a = 0 va b = 4 deb berilgan. Bo'luvchilar soni n = 4 deb tanlanadi (to'rt ta bo'luvchi). To'rtburchaklarni hosil qilamiz: Δx = (4 - 0) / 4 = 1 To'rtburchaklar: [0, 1], [1, 2], [2, 3], [3, 4] Yuzlar hisoblanishi: [0, 1] uchun f(x) = x^2. Yuzi: 1^2 = 1 [1, 2] uchun f(x) = x^2. Yuzi: 2^2 = 4 [2, 3] uchun f(x) = x^2. Yuzi: 3^2 = 9 [3, 4] uchun f(x) = x^2. Yuzi: 4^2 = 16 Yuzlarni yig'ib chiqamiz: 1 + 4 + 9 + 16 = 30 Yig'indini tartiblash uchun 30 ni Δx = 1 bilan ko'paytiramiz: 30 * 1 = 30 Natija: ∫[0, 4] x^2 dx ≈ 30 Shunga ko'ra, taqribiy hisoblash natijasiga ko'ra, integral ∫[0, 4] x^2 dx qiymati taqriban 30 ga teng bo'ladi. 3] Integrallarni taqribiy hisoblashda trapetsiya usuli, algoritmi, formulasini keltiring. Integrallarni taqribiy hisoblashda trapetsiya usuli (trapezoidal method) ishlatiladi. Bu usulning algoritmi quyidagicha bo'ladi: Belgilangan integralning tartiblanadigan chegaralarini a va b deb o'zlashtirib olamiz. Integralning tartiblanadigan chegaralarini bir nechta teng bo'lgan n ta bo'luvchilarga ajratamiz. Har bir bo'luvchi uchun trapetsiya shaklini yaratamiz. Har bir trapetsiyaning yuzini hisoblaymiz. Bu uchun trapetsiyani yuza formula bilan hisoblaymiz: ((f(x1) + f(x2)) / 2) * Δx, burada x1 va x2 - trapetsiyaning chegaralaridagi nuqtalar, f(x1) va f(x2) - integraldagi funktsiya qiymatlari, Δx = (b - a) / n - trapetsiyalarning enining o'lchami. Har bir trapetsiyaning yuzini integralga qo'shib natijalarni yig'ib chiqamiz. Yig'indini tartiblash uchun yuqoridagi natijalarni integralni trapetsiya usuli bilan hisoblangan yuzasidan ko'paytirib olishimiz kerak. Natija, taqribiy integral qiymatini beradi. Trapetsiya usuli formulasi quyidagicha: ∫[a, b] f(x) dx ≈ Δx * [(f(x1) + f(x2)) / 2 + (f(x2) + f(x3)) / 2 + ... + (f(xn-1) + f(xn)) / 2] bu yerda Δx = (b - a) / n trapetsiyalarning enining o'lchami, x1, x2, ..., xn - trapetsiyaning chegaralaridagi nuqtalar, f(x1), f(x2), ..., f(xn) - integraldagi funktsiya qiymatlari. Trapetsiya usulini soddaroq tushuntirish uchun quyidagi misolni ko'rib chiqamiz: Misol: ∫[0, 4] x^2 dx ni trapetsiya usuli bilan hisoblang. Tartiblanadigan chegaralar a = 0 va b = 4 deb berilgan. Bo'luvchilar soni n = 4 deb tanlanadi (to'rt ta trapetsiya). Trapetsiyalarni hosil qilamiz: Δx = (4 - 0) / 4 = 1 Trapetsiyalar: [0, 1], [1, 2], [2, 3], [3, 4] Yuzlar hisoblanishi: [0, 1] uchun f(x) = x^2. Yuzi: ((0^2 + 1^2) / 2) * 1 = 0.5 [1, 2] uchun f(x) = x^2. Yuzi: ((1^2 + 2^2) / 2) * 1 = 1.5 [2, 3] uchun f(x) = x^2. Yuzi: ((2^2 + 3^2) / 2) * 1 = 4.5 [3, 4] uchun f(x) = x^2. Yuzi: ((3^2 + 4^2) / 2) * 1 = 9.5 Yuzlarni yig'ib chiqamiz: 0.5 + 1.5 + 4.5 + 9.5 = 16 Yig'indini tartiblash uchun 16 ni Δx = 1 bilan ko'paytiramiz: 16 * 1 = 16 Natija: ∫[0, 4] x^2 dx ≈ 16 Shunga ko'ra, taqribiy hisoblash natijasiga ko'ra, integral ∫[0, 4] x^2 dx qiymati taqriban 16 ga teng bo'ladi. 5] Integrallarni taqribiy hisoblashda Simpson usuli, algoritmi, formulasini keltiring. Integrallarni taqribiy hisoblashda Simpson usuli (Simpson's rule) ishlatiladi. Bu usulning algoritmi quyidagicha bo'ladi: Belgilangan integralning tartiblanadigan chegaralarini a va b deb o'zlashtirib olamiz. Integralning tartiblanadigan chegaralarini bir nechta teng bo'lgan n ta bo'luvchilarga ajratamiz. n soni toq son bo'lishi kerak. Har bir bo'luvchi uchun Simpson formulasi orqali yuzni hisoblaymiz. Simpson formulasi: Δx / 3 * [f(x0) + 4f(x1) + 2f(x2) + 4f(x3) + ... + 2f(xn-2) + 4f(xn-1) + f(xn)], burada Δx = (b - a) / n integralning bo'luvchilar o'lchami, x0, x1, ..., xn - integralning chegaralaridagi nuqtalar, f(x0), f(x1), ..., f(xn) - integraldagi funktsiya qiymatlari. Har bir bo'luvchakning yuzini hisoblaymiz. Yuzlarni yig'ib chiqamiz. Natija, taqribiy integral qiymatini beradi. Simpson usuli formulasi quyidagicha: ∫[a, b] f(x) dx ≈ Δx / 3 * [f(x0) + 4f(x1) + 2f(x2) + 4f(x3) + ... + 2f(xn-2) + 4f(xn-1) + f(xn)] bu yerda Δx = (b - a) / n integralning bo'luvchilar o'lchami, x0, x1, ..., xn - integralning chegaralaridagi nuqtalar, f(x0), f(x1), ..., f(xn) - integraldagi funktsiya qiymatlari. Simpson usulini soddaroq tushuntirish uchun quyidagi misolni ko'rib chiqamiz: Misol: ∫[0, 4] x^2 dx ni Simpson usuli bilan hisoblang. Tartiblanadigan chegaralar a = 0 va b = 4 deb berilgan. Bo'luvchilar soni n = 4 deb tanlanadi (to'rt ta bo'luvchi, toq son). Δx = (4 - 0) / 4 = 1 integralning bo'luvchilar o'lchami. x0 = 0, x1 = 1, x2 = 2, x3 = 3, xn = 4 Yuzlar hisoblanishi: f(x0) = f(0) = 0^2 = 0 f(x1) = f(1) = 1^2 = 1 f(x2) = f(2) = 2^2 = 4 f(x3) = f(3) = 3^2 = 9 f(xn) = f(4) = 4^2 = 16 Yuzlarni hisoblaymiz: Δx / 3 * [0 + 41 + 24 + 4*9 + 16] = 21.3333 Natija: ∫[0, 4] x^2 dx ≈ 21.3333 Shunga ko'ra, taqribiy hisoblash natijasiga ko'ra, integral ∫[0, 4] x^2 dx qiymati taqriban 21.3333 ga teng bo'ladi. 6] Tenglamalarni taqribiy yechishda oraliqni ikkiga bo'lish usuli, algoritmi, formulasini keltiring. Tenglamalarni taqribiy yechishda oraliqni ikkiga bo'lish usuli (bisection method) ishlatiladi. Bu usulning algoritmi quyidagicha bo'ladi: Tenglamani yechishning tartiblanadigan chegaralarini a va b bilan belgilaymiz. Tenglamaning o'rtasidagi nuqtani topish uchun x = (a + b) / 2 formulani ishlatamiz. x qiymatini tenglamaga kiriting va uning natijasini hisoblaymiz. Natijani tekshirib, agar natija etiborli tolalikka yetmasa, natijani qabul qilib qayta hisoblash uchun yangi chegaralar belgilaymiz. Agar natija manfiy bo'lsa, a qiymatini x ga o'zlashtirib qo'yamiz. Agar natija musbat bo'lsa, b qiymatini x ga o'zlashtirib qo'yamiz. a va b chegaralarining orasidagi masofani 2 ga bo'lib, yana x qiymatini hisoblaymiz. Natijani tekshirib, agar natija etiborli tolalikka yetmasa, natijani qabul qilib qayta hisoblash uchun yangi chegaralar belgilaymiz. Usulni bir necha marta takrorlaymiz, toki natija etiborli tolalik miqdoridan kichikroq bo'lmasa. Natija, taqribiy yechingan tenglama qiymatini beradi. Bisection usuli formulasi quyidagicha: x = (a + b) / 2 Bu formulada x, a va b orasidagi o'rtacha nuqta hisoblanadi. Bisection usulini soddaroq tushuntirish uchun quyidagi misolni ko'rib chiqamiz: Misol: f(x) = x^2 - 4, [1, 3] oraliqdagi yechimni toping. Tartiblanadigan chegaralar a = 1 va b = 3 bilan belgilangan. O'rtacha nuqtani hisoblaymiz: x = (1 + 3) / 2 = 2 f(x) = f(2) = 2^2 - 4 = 0 Natija 0 ga teng bo'lmaganligini tekshiramiz. Agar f(x) manfiy bo'lsa, a qiymatini x ga o'zlashtiramiz: a = 2 Agar f(x) musbat bo'lsa, b qiymatini x ga o'zlashtiramiz: b = 2 Yangi o'rtacha nuqtani hisoblaymiz: x = (1 + 2) / 2 = 1.5 f(x) = f(1.5) = 1.5^2 - 4 = -1.75 Yangi natija -1.75 manfiy bo'ldi, shuning uchun a qiymatini x ga o'zlashtiramiz: a = 1.5 O'rtacha nuqtani hisoblaymiz: x = (1.5 + 2) / 2 = 1.75 f(x) = f(1.75) = 1.75^2 - 4 = -0.5625 Yangi natija -0.5625 manfiy bo'ldi, shuning uchun a qiymatini x ga o'zlashtiramiz: a = 1.75 O'rtacha nuqtani hisoblaymiz: x = (1.75 + 2) / 2 = 1.875 f(x) = f(1.875) = 1.875^2 - 4 = -0.265625 Natija -0.265625 manfiy bo'ldi, shuning uchun a qiymatini x ga o'zlashtiramiz: a = 1.875 O'rtacha nuqtani hisoblaymiz: x = (1.875 + 2) / 2 = 1.9375 f(x) = f(1.9375) = 1.9375^2 - 4 = -0.06640625 Natija -0.06640625 manfiy bo'ldi, shuning uchun a qiymatini x ga o'zlashtiramiz: a = 1.9375 O'rtacha nuqtani hisoblaymiz: x = (1.9375 + 2) / 2 = 1.96875 f(x) = f(1.96875) = 1.96875^2 - 4 = -0.015625 Natija -0.015625 manfiy bo'ldi, shuning uchun a qiymatini x ga o'zlashtiramiz: a = 1.96875 O'rtacha nuqtani hisoblaymiz: x = (1.96875 + 2) / 2 = 1.984375 f(x) = f(1.984375) = 1.984375^2 - 4 = -0.00390625 Natija -0.00390625 manfiy bo'ldi, shuning uchun a qiymatini x ga o'zlashtiramiz: a = 1.984375 O'rtacha nuqtani hisoblaymiz: x = (1.984375 + 2) / 2 = 1.9921875 f(x) = f(1.9921875) = 1.9921875^2 - 4 = -0.0009765625 Natija -0.0009765625 manfiy bo'ldi, shuning uchun a qiymatini x ga o'zlashtiramiz: a = 1.9921875 O'rtacha nuqtani hisoblaymiz: x = (1.9921875 + 2) / 2 = 1.99609375 f(x) = f(1.99609375) = 1.99609375^2 - 4 = -0.000244140625 Natija -0.000244140625 manfiy bo'ldi, shuning uchun a qiymatini x ga o'zlashtiramiz: a = 1.99609375 O'rtacha nuqtani hisoblaymiz: x = (1.99609375 + 2) / 2 = 1.998046875 f(x) = f(1.998046875) = 1.998046875^2 - 4 = -6.103515625e-05 Natija ehtimol, etiborli tolalik miqdoridan kichikroq bo'ldi. Shuning uchun natijani qabul qilamiz. Natija: Tenglamaning yechimi 1.998046875 ga yaqinroq bo'ladi. Shunga ko'ra, tenglamani taqribiy yechishda oraliqni ikkiga bo'lish usuli bilan, [1, 3] oraliqdagi yechim taqriban 1.998046875 ga yaqinroq bo'ladi. 7] Tenglamalarni taqribiy yechishda Vatarlar usuli, algoritmi, formulasini keltiring. Tenglamalarni taqribiy yechishda Vatarlar usuli (Newton's method) ishlatiladi. Bu usulning algoritmi quyidagicha bo'ladi: Tenglamaning bir boshlang'ich taxminini x0 bilan belgilaymiz. Tenglamaning x qiymatini hisoblash uchun quyidagi formulani ishlatamiz: x = x0 - f(x0) / f'(x0), bu yerda f(x0) tenglama qiymati, f'(x0) esa tenglama o'zgaruvchanining (x0)ga qarab olingan turlash tomonidan olinadigan o'zgaruvchan hisoblanadi. x qiymatini yangi boshlang'ich taxmin sifatida belgilaymiz: x0 = x. Natija etiborli tolalikka yetmasa, 2-3 qadamni takrorlaymiz. Natija, taqribiy yechingan tenglama qiymatini beradi. Vatarlar usuli formulasi quyidagicha: x = x0 - f(x0) / f'(x0) Bu formulada x, x0 boshlang'ich taxmin, f(x0) tenglama qiymati, f'(x0) esa tenglama o'zgaruvchanining (x0)ga qarab olingan turlash tomonidan olinadigan o'zgaruvchan hisoblanadi. Vatarlar usulini soddaroq tushuntirish uchun quyidagi misolni ko'rib chiqamiz: Misol: f(x) = x^2 - 4, [1, 3] oraliqdagi yechimni toping. Boshlang'ich taxmin sifatida x0 = 2 ni belgilaymiz. x qiymatini hisoblaymiz: x = x0 - f(x0) / f'(x0) x = 2 - (2^2 - 4) / (2 * 2) x = 2 - (4 - 4) / 4 x = 2 - 0 / 4 x = 2 Yangi boshlang'ich taxmin sifatida x0 = 2 ni belgilaymiz. Natija etiborli tolalikka yetmasa, 2-3 qadamni takrorlaymiz. x = 2 - (2^2 - 4) / (2 * 2) x = 2 - (4 - 4) / 4 x = 2 - 0 / 4 x = 2 Natija, taqribiy yechingan tenglama qiymatini beradi. Shunga ko'ra, taqribiy hisoblash natijasiga ko'ra, tenglamning [1, 3] oraliqdagi yechimi 2 ga teng bo'ladi. 8] Tenglamalarni taqribiy yechishda Nyuton usuli, algoritmi, formulasini keltiring. Tenglamalarni taqribiy yechishda Nyuton usuli (Newton's method) ishlatiladi. Bu usulning algoritmi quyidagicha bo'ladi: Tenglamaning bir boshlang'ich taxminini x0 bilan belgilaymiz. Tenglamaning x qiymatini hisoblash uchun quyidagi formulani ishlatamiz: x = x0 - f(x0) / f'(x0), bu yerda f(x0) tenglama qiymati, f'(x0) esa tenglama o'zgaruvchanining (x0)ga qarab olingan turlash tomonidan olinadigan o'zgaruvchan hisoblanadi. x qiymatini yangi boshlang'ich taxmin sifatida belgilaymiz: x0 = x. Natija etiborli tolalikka yetmasa, 2-3 qadamni takrorlaymiz. Natija, taqribiy yechingan tenglama qiymatini beradi. Nyuton usuli formulasi quyidagicha: x = x0 - f(x0) / f'(x0) Bu formulada x, x0 boshlang'ich taxmin, f(x0) tenglama qiymati, f'(x0) esa tenglama o'zgaruvchanining (x0)ga qarab olingan turlash tomonidan olinadigan o'zgaruvchan hisoblanadi. Nyuton usulini soddaroq tushuntirish uchun quyidagi misolni ko'rib chiqamiz: Misol: f(x) = x^2 - 4, [1, 3] oraliqdagi yechimni toping. Boshlang'ich taxmin sifatida x0 = 2 ni belgilaymiz. x qiymatini hisoblaymiz: x = x0 - f(x0) / f'(x0) x = 2 - (2^2 - 4) / (2 * 2) x = 2 - (4 - 4) / 4 x = 2 - 0 / 4 x = 2 Yangi boshlang'ich taxmin sifatida x0 = 2 ni belgilaymiz. Natija etiborli tolalikka yetmasa, 2-3 qadamni takrorlaymiz. x = 2 - (2^2 - 4) / (2 * 2) x = 2 - (4 - 4) / 4 x = 2 - 0 / 4 x = 2 Natija, taqribiy yechingan tenglama qiymatini beradi. Shunga ko'ra, taqribiy hisoblash natijasiga ko'ra, tenglamning [1, 3] oraliqdagi yechimi 2 ga teng bo'ladi. 9] Tenglamalarni taqribiy yechishda iteratsiya usuli, algoritmi, formulasini keltiring Tenglamalarni taqribiy yechishda iteratsiya (iteration) usuli ishlatiladi. Bu usulning algoritmi quyidagicha bo'ladi: Tenglamaning bir boshlang'ich taxminini x0 bilan belgilaymiz. Tenglamaning x qiymatini hisoblash uchun quyidagi formulani ishlatamiz: x = g(x0), bu yerda g(x0) o'zgaruvchini olish uchun f(x0)ga birorta ifoda qo'llanadi. x qiymatini yangi boshlang'ich taxmin sifatida belgilaymiz: x0 = x. Natija etiborli tolalikka yetmasa, 2-3 qadamni takrorlaymiz. Natija, taqribiy yechingan tenglama qiymatini beradi. Iteratsiya usuli formulasi quyidagicha: x = g(x0) Bu formulada x, x0 boshlang'ich taxmin, g(x0) esa o'zgaruvchini olish uchun f(x0)ga birorta ifoda qo'llanadi. Iteratsiya usulini soddaroq tushuntirish uchun quyidagi misolni ko'rib chiqamiz: Misol: f(x) = x^2 - 4, [1, 3] oraliqdagi yechimni toping. Boshlang'ich taxmin sifatida x0 = 2 ni belgilaymiz. x qiymatini hisoblash uchun g(x0) ni hisoblaymiz: x = g(x0) = x0 - f(x0) x = 2 - (2^2 - 4) x = 2 - (4 - 4) x = 2 - 0 x = 2 Yangi boshlang'ich taxmin sifatida x0 = 2 ni belgilaymiz. Natija etiborli tolalikka yetmasa, 2-3 qadamni takrorlaymiz. x = g(x0) = x0 - f(x0) x = 2 - (2^2 - 4) x = 2 - (4 - 4) x = 2 - 0 x = 2 Natija, taqribiy yechingan tenglama qiymatini beradi. Shunga ko'ra, taqribiy hisoblash natijasiga ko'ra, tenglamning [1, 3] oraliqdagi yechimi 2 ga teng bo'ladi. 10] Chiziqli dasturlash masalasining qo'yilishi. Chiziqli dasturlash masalalari amaliyotga asoslangan muammolardir, bu muammolarni chiziqli dasturlash tilida yechishni talab qiladi. Ular matematik, statistika, kriptografiya, grafiklar, mashinalarning o'qitishida va boshqa bir qancha sohalarida paydo bo'lishi mumkin. Bu muammolar quyidagi tartibda yechiladi: Muammo tushuniladi: Muammoga oid tafsilotlar va kerakli ma'lumotlar beriladi. Muammo qanday yechishning talab qilindiği aniqlanishi lozim. Muammo modeli yaratiladi: Muammo matematik, statistika, grafiklar yoki boshqa usullar orqali ifodalangan qonuniyatlar va aloqador o'zgaruvchilarni o'z ichiga olgan dastur yoki formulalar bilan ifodalangan model yaratiladi. Muammo yechish algoritmi tuziladi: Muammo uchun yechish algoritmi yaratiladi, bu algoritm muammoga oid modelning bajarilishi uchun qadam-qadam bo'lgan jarayonlarni ifodalaydi. Muammo yechiladi: Yaratilgan algoritmda belgilangan bo'lgan kerakli ma'lumotlar bilan muammo yechiladi. Dastur yoki formulalar orqali hisoblamalar bajariladi va natijaviy javob olinadi. Natija tekshiriladi: Muammo yechishning to'g'ri natijaga yetishishini tekshirish uchun olingan javob natija to'g'risidagi ma'lumotlar bilan solishtiriladi. Javob taqdim etiladi: Muammoga oid natijaviy javob ma'lumotlari yoki o'zgaruvchilar taqdim etiladi. Chiziqli dasturlash masalalari yaratilgan modellarga va muammo xususiyatlariga qarab o'zgaradi, shuning uchun har bir muammo o'ziga xos tuzilish va yechish usullari talab qiladi. Masalan, matematik formulalari yoki ma'lumotlarni hisoblash uchun dasturlar yordamida yechish mumkin. Chiziqli dasturlash masalalari yuqori darajada hisoblanuvchi mashinani, texnologik vositalarni yoki dasturiy ta'minotlarni talab qiladi. 11] Chiziqli dasturlash masalasini yechishda grafiklar usuli. Grafiklar usuli chiziqli dasturlash masalalarini yechishda juda mashhur va foydali bo'lgan bir usuldur. Bu usul grafiklarni tahlil qilish, vizualizatsiya qilish va muammolarni aniqlash uchun ishlatiladi. Grafiklar usulining boshqa usullarga nisbatan bir qancha afzalliklari mavjud: Ma'lumotlarni tahlil qilish: Grafiklar, muammolarni tahlil qilishda yordam beradi. Ma'lumotlarni vizualizatsiya qilish orqali, muammolarni ko'rib chiqish, o'zgaruvchanliklarni aniqlash va o'zgarishlarni tasavvur qilishga imkon beradi. Aniq vaqt oralig'i: Grafiklar usuli orqali muammolarni yechishda va muammo yechimlarining aniqlanishida vaqt oralig'i juda qisqa vaqt talab etadi. Grafiklar orqali ma'lumotlarni ko'rish, aniqlash va natijalarni topish tez va oson bo'ladi. Nisbi o'zgaruvchiliklar: Grafiklar usuli orqali muammolarni o'zgaruvchanliklarga qarab tahlil qilishga imkon beradi. Grafiklar orqali o'zgaruvchanliklarning o'zaro bog'lanishlarini, tendentsiyalarini va ulardan kelib chiqadigan oqibatlarni tahlil qilish mumkin. Natijalarni vizualizatsiya qilish: Grafiklar, muammolarni natijalarini vizualizatsiya qilishda juda qulay bo'ladi. Natijalarni grafiklar yordamida vizual ravishda ko'rsatish, taqqoslash, solishtirish va ma'lumotlarni ta'riflash oson va aniqligi ko'proq bo'ladi. Grafiklar usulining amaliyotdagi algoritmi quyidagicha bo'ladi: Muammo tushuniladi: Muammoga oid tafsilotlar va kerakli ma'lumotlar beriladi. Ma'lumotlarni tahlil qilish: Muammo uchun kerakli ma'lumotlar to'plami tahlil qilinadi. Grafik tuzish: Ma'lumotlar, grafik koordinatalarida ifodalanadi. X o'qi o'zgaruvchilar, y o'qi esa muammolarni ifodalaydi. Grafikni yaratish: Ma'lumotlarni o'rganishdan keyin, ma'lumotlar grafikga joylashtiriladi va grafik yaratiladi. Grafikni tahlil qilish: Yaratilgan grafik tahlil qilinadi, o'zgaruvchanliklar, tendentsiyalar, o'zgarishlar va asosiy muammolar aniqlanadi. Natijalar: Grafiklar orqali natijalar, muammolarning yechimi yoki tahlili beriladi. Grafiklar usuli muammolarni tahlil qilish, natijalarini vizualizatsiya qilish va fikrlarni tushunarli ko'rsatishda katta yordam beradi. Ushbu usul statistika, matematik, kriptografiya, marketing, hisob-kitob va boshqa sohalar bilan bog'liq muammolarni yechishda keng qo'llaniladi. 12] Chiziqli dasturlash masalasini yechishda Simpleks usuli algoritmi. Chiziqli dasturlash masalalarini yechishda Simpleks usuli algoritmi foydalaniladi. Bu algoritm lineyni optimizatsiya masalalarini, ya'ni ma'lumotlar va chegaralar bo'yicha eng yaxshi qiymatni topishda ishlatiladi. Simpleks usuli algoritmi quyidagi tartibda ishlaydi: Aniqlovchi vektorlar tayyorlash: Masalada berilgan aniqlovchi vektorlar tayyorlanadi. Aniqlovchi vektorlar masalada o'zgaruvchilar uchun chegaralar va ma'lumotlar beradigan holatlarni ifodalaydi. Boshlang'ich to'rtburchak (simpleks) tuzish: Aniqlovchi vektorlar asosida boshlang'ich to'rtburchak (simpleks) tuziladi. Simpleks boshlang'ich to'rtburchakni olganda, har bir burchak aniqlovchi vektorni ifodalaydi. Maksimum qiymatni topish: Boshlang'ich to'rtburchakda har bir burchak uchun maqsad funksiya qiymati hisoblanadi. Maksimum qiymatni topish uchun eng yuqori qiymatni topishga harakat qilinadi. Simpleksning yurishini o'zgartirish: Simpleks burchaklari orasidagi o'zgarishlarni hisoblash uchun yeni burchaklar aniqlanadi. Burchaklar o'zgarishlari to'rtburchakning eng yomon qiymatni olib tashlanib, eng yaxshi qiymatni topishga harakat qiladi. Yangilash va qayta hisoblash: Burchaklar o'zgarishlari bilan yangilanadi va yangi simpleksni hisoblash uchun qayta hisoblash jarayoni boshlanadi. Bu jarayon burchaklar o'zgarishlari bilan davom etadi. Natijani tekshirish: Simpleks algoritmi natijalarni tekshirish uchun maqsad funksiya qiymatlarini taqqoslash va eng yaxshi qiymatni aniqlashni davom ettiradi. Agar natija belgilangan chegaralarga erishgan bo'lsa, algoritm tugatiladi, aks holda 3-6 qadamlar takrorlanadi. Simpleks usuli algoritmi lineyni optimizatsiya masalalarini yechishda foydali bo'ladi. U masalalarni tez, oson va ishonchli tarzda yechish imkonini beradi. Shuningdek, bu algoritm o'zgaruvchilar va chegaralar miqdorini kengaytirish, korxonalarni optimallashtirish, resurslarni ishlatish va boshqa chiziqli dasturlash muammolarni yechishda yordam beradi. 13] Funksiyalarni Furye qatoriga yoyish formulasi Funksiyalarni Furie qatoriga yoyish formulasi kompleks sonlarni tahlil qilishda foydalaniladi. Bu formulaga asosan ikkita formula yoyiladi: biri orqali funksiyaning amplituda, ikkinchisi orqali esa fazasi ifodalaydi. Funksiyani Furie qatoriga yoyish formulasi quyidagicha ko'rinishga ega: F(k) = ∫ [f(t) * e^(-i2πkt)] dt Bu formulada: F(k) bu kompleks son bo'ladi va k funksiya tahlilidagi k-turli komponentni ifodalaydi. f(t) asosiy funksiya bo'ladi, qatorga yoyishni talab qilgan funksiya. e^(-i2πkt) eksponental funksiya bo'ladi, bu funksiya sinus va kosinus funksiyalarini ifodalaydi. ∫ integral belgisini ifodalaydi va funksiyaning belli bir oraligida integralni hisoblashni anglatadi. t asosiy o'zgaruvchi bo'ladi, funksiyaning o'zgaruvchanligi yoki vaqti ifodalaydi. i kompleks sonning imaqtalik qismini ifodalaydi. π radianlar miqdorini ifodalaydi. Furie qatoriga yoyish formulasi, funksiyaning zamonga bog'liqlik va shaklni ifodalaydi. Uning natijaviy qiymatlar, amplituda va fazaning funksiya tarkibidagi tushunmovchilikni yoyadi. Bu formulani foydalanib, orijinal funksiyani komponentlarga yoyish, tahlil qilish, frekanslarni aniqlash va boshqa maqsadlar uchun ishlatish mumkin. 14] Funksiyalarni Furye qatoriga yoyishda A0 va An koeffitsenti formulasi Funksiyalarni Furie qatoriga yoyishda A0 (DC komponent) va An (Harmonik komponentlar) koeffitsentlari formulasi foydalaniladi. Bu koeffitsentlar, Furie transformatsiyasi orqali funksiyaning komponentlarini ifodalayadi. A0 (DC komponent) koeffitsenti formulasi: A0 = (1/N) * ∫[f(t)] dt Bu formulda: A0 DC (daraja nol) komponentni ifodalaydi. N funksiyaning uzunligi (o'zgaruvchanliklar soni) bo'ladi. f(t) asosiy funksiya bo'ladi. A0 koeffitsenti, funksiyaning ortasidagi (DC) komponentning amplitudasini ifodalayadi. Uning qiymati funksiyaning o'rtacha qiymatini anglatadi. An (Harmonik komponentlar) koeffitsenti formulasi: An = (2/N) * ∫[f(t) * cos(nωt)] dt Bu formulda: An harmonik komponentlarni ifodalaydi. N funksiyaning uzunligi (o'zgaruvchanliklar soni) bo'ladi. f(t) asosiy funksiya bo'ladi. n komponent tartib raqami (harmonik tartib raqami) bo'ladi. ω fundamental chastota bo'ladi (2π/T, T - funksiyaning davomiyligi). An koeffitsenti, funksiyaning n-turli harmonik komponentning amplitudasini ifodalayadi. Uning qiymati funksiyaning sinusoidal komponentining amplitudasini anglatadi. A0 (DC komponent) va An (Harmonik komponentlar) koeffitsentlari, Furie transformatsiyasi yordamida funksiyaning komponentlarini ifodalayadi. Ular funksiyaning frekans tarkibini va komponentlarining amplitudalarini taqqoslash va tahlil qilishda foydalaniladi. 15] Funksiyalarni Furye qatoriga yoyishda Bn koeffitsenti formulasi Funksiyalarni Furie qatoriga yoyishda Bn koeffitsenti, harmonik komponentlarning sinussal qismidagi amplitudani ifodalayadi. Bn koeffitsenti quyidagi formulaga asoslanadi:
Bn harmonik komponentlarni ifodalaydi. N funksiyaning uzunligi (o'zgaruvchanliklar soni) bo'ladi. f(t) asosiy funksiya bo'ladi. n komponent tartib raqami (harmonik tartib raqami) bo'ladi. ω fundamental chastota bo'ladi (2π/T, T - funksiyaning davomiyligi). Bn koeffitsenti, funksiyaning n-turli harmonik komponentning sinussal qismidagi amplitudasini ifodalayadi. Uning qiymati funksiyaning sinussal komponentining amplitudasini anglatadi. Furie transformatsiyasi yordamida funksiya, Bn koeffitsentlari orqali sinusoidal komponentlarga aylanadi. Bu komponentlar funksiyaning sinusdal qismlarini ifodalayadi va funksiyaning frekans tarkibini yoyadi. Bn koeffitsenti, Furie transformatsiyasini amalga oshirishda funksiyaning sinussal qismini aniqlash va tahlil qilishda foydalaniladi. Ular signal ishlanishida, frekans analizida, filtratsiyada va boshqa amaliyotlarda qo'llaniladi. 16] Statistik modellashtirishda chiziqli regressiya tenglamasi, b koeffitsent Chiziqli regressiya modelida b koeffitsenti, ba'zi o'zgaruvchilar (masalan, x) va bog'liqli o'zgaruvcha (masalan, y) orasidagi o'zaro bog'lanishni ifodalaydi. B koeffitsenti, regressiya modellasi orqali aniqlangan o'zgaruvchilar orasidagi y o'zgaruvchani o'zgaruvchilar bo'yicha qanday o'zgarishi bilan ta'minlaydi.
y, bog'liqli o'zgaruvcha (dependent variable) yoki natija o'zgaruvchani ifodalaydi. x, o'zgaruvchilar to'plamiga (independent variables) tegishli o'zgaruvchani ifodalaydi. b0, tenglama burchak (intercept) koeffitsenti. U regressiya liniyasining y o'zgaruvchasini qanday ta'minlashni ifodalaydi, x o'zgaruvchalarining qiymati 0 bo'lganda. b1, o'zgaruvchilar o'rtasidagi bog'lanishning koeffitsenti (slope coefficient). U regressiya liniyasining e'tiboriga x o'zgaruvchalaridagi o'zgarishlarni ifodalaydi. e, noma'lum xatolik (error term). Bu regressiya modelining ta'siriga kiritilmagan faktorlardan kaynaklanan tashqi o'zgaruvchidir. B koeffitsenti (b1) regressiya modelini tafsilotlari bilan tasvirlaydi. U o'zgaruvchilar o'rtasidagi bog'lanish darajasini ifodalaydi. Agar b1 koeffitsenti musbat bo'lsa, x o'zgaruvchalarining o'sishi bilan bog'liq y o'zgaruvchasining ham o'sishini anglatadi. Agar b1 koeffitsenti manfiy bo'lsa, x o'zgaruvchalarining o'sishi bilan bog'liq y o'zgaruvchasining kamayishini anglatadi. B koeffitsenti, regressiya modellashtirishda o'zgaruvchilar va bog'liqli o'zgaruvcha orasidagi statistikiy bog'lanishni ifodalaydi. Uning hisoblanishi statistik metodlar, ma'lumotlar analizi yoki regressiya analizi bilan amalga oshiriladi. Koeffitsentning qiymati va ta'rifidagi yo'nalish, o'zgaruvchilar va bog'liqli o'zgaruvcha o'rtasidagi bog'lanish darajasini tushuntiradi. 17] Chiziqli regressiya tenglamasida a va b koeffitsentlarni toppish Chiziqli regressiya tenglamasidagi a va b koeffitsentlarni topish uchun mavjud ma'lumotlar to'plami yordamida statistikiy formulalardan foydalaniladi. Quyidagi formulalar regressiya modellasi koeffitsentlarini hisoblashda keng qo'llaniladi: b koeffitsenti (o'zgaruvchilar o'rtasidagi bog'lanish koeffitsenti): b = Σ((xi - x̄)(yi - ȳ)) / Σ((xi - x̄)^2) Bu formulda: xi va yi, ma'lumotlar to'plamidagi i-talimli elementlardir. x̄, x o'zgaruvchalarining o'rtacha qiymatidir. ȳ, y o'zgaruvchalarining o'rtacha qiymatidir. Σ, sigma belgisi, elementlarning summalarini ifodalaydi. a koeffitsenti (tenglama burchagi): a = ȳ - b * x̄ Bu formulda: ȳ, y o'zgaruvchalarining o'rtacha qiymatidir. x̄, x o'zgaruvchalarining o'rtacha qiymatidir. b, o'zgaruvchilar o'rtasidagi bog'lanish koeffitsentidir. Chiziqli regressiya tenglamasidagi a va b koeffitsentlari, ma'lumotlar to'plami yordamida hisoblanadi. Ular statistikiy metodlar bilan aniqlovchi formulalar orqali topiladi. Koeffitsentlar, o'zgaruvchilar va bog'liqli o'zgaruvcha o'rtasidagi bog'lanish darajasini ifodalaydi. Regressiya modellashtirish va ma'lumotlar analizida a va b koeffitsentlari qo'llaniladi. 18] "Ajrat va hukmronlik qil" prinsipida eng katta elementni toppish (Max) funksiyasi . "Ajrat va hukmronlik qil" prinsipida eng katta elementni topish uchun Max (maksimum) funksiyasidan foydalaniladi. Max funksiyasi berilgan bir nechta elementlarning orasidan eng katta (maksimum) qiymatni qaytaradi. Matematik hisob-kitoblarda Max funksiyasi quyidagi ko'rinishda ifodalangan bo'ladi: Max(x1, x2, x3, ..., xn) = max(x1, x2, x3, ..., xn) Bu formulda: x1, x2, x3, ..., xn berilgan elementlar to'plamidagi elementlardir. max(a, b) ikkita qiymatning eng kattasini qaytaruvchi funksiya hisoblanadi. Max funksiyasi orqali berilgan bir nechta elementlarning orasidan eng katta (maksimum) qiymatni topish mumkin. Masalan, berilgan sonlar to'plamidan eng katta elementni topish uchun max(a, b, c) formulasi foydalaniladi. Natijada, Max funksiyasi eng katta qiymatni qaytaradi. "Ajrat va hukmronlik qil" prinsipida eng katta elementni topishda Max funksiyasi foydalaniladi, chunki u eng yuqori qiymatni aniqlashga imkon beradi. Download 54.78 Kb. Do'stlaringiz bilan baham: 
|