Algoritmlarni loyihalash fanidan on savollari! Kvadratur formulalarining xatoligi? Transport masalasini yechish bosqichlari?

Masalani yechish algoritmi (Urinmalar(Nyuton) usuli). f(x)=e^x-10x-2 funksiya [-1;0] oraliqda 3.1-teoremaning barcha shartlarini qanoatlantiradi.

f''(x)=e^x >0, ­x[-1;0] va f(-1)=8.386>0

dan

f(-1) f''(-1)>0

bo‘lgani uchun a₀=-1 deb olinadi. f'(-1)=e^-1-10=-9.632 ni e’tiborga olib, birinchi yaqinlashish а₁ ni hisoblaymiz:

a₁=a- f(a)/f'(a)= a- f(-1)/f'(-1)= -1-8.386/(-9.632) = -0.131.

Yaqinlashish shartini tekshiramiz:

­­ a₁- a₀  = -0.131+1= 0.869>=0.01

bo‘lgani uchun ikkinchi yaqinlashish a₂ ni

a₂=a₁- f(a₁)/f'(a₁)

formula bilan topamiz.

f(a₁)=e^-0.131 + 10(0.131)-2=0.1895, f’(a₁)= e^-0.131 – 10= -9.123

lar asosida: a₂=-0.131- 0.1895/(-9.123) = -0.1104.

Yana a₂- a₁ = 0.0214 >  bo‘lgani uchun a₃ ni topamiz:

a₂=-0.1104, f(a₂)=0.0006 , f’(a₂)=-9.1046

lar asosida:

a₃= a₂ – f(a₂)/ f’(a₂)= -0.1104 – 0. 0006/(-0.1046) =-0.1104;

yaqinlashish sharti a₃-a₂< =0.01 bajarilganligi uchun tenglamaning =0.01 aniqlikdagi taqribiy yechimi:

x a₃= -0.1104

bo‘ladi.

Masaladagi berilganlar asosida ko‘rsatilgan usulda hisoblashning algoritmini 3.2-jadvalda beramiz :

3.2-jadval

Berilganlar	Belgilashlar
	matn bo‘yicha	dastur bo‘yicha
Tenglama funksiyasi	f(x)=e^x-10x-2	FNF(x)=exp(X)-10*X -2
Tenglama funksiyasining birinchi hosilasi	f '(x)=e^x-10	FNF1(x)=exp(X)-10
Tenglama funksiyasining ikkinchi hosilasi	f '' (x)=e^x	FNF2(x)=exp(X)
Ildiz yotgan kesma shegarasi	a=-1, b=0	a=-1, b=0
Kesmani bo‘linish qadami	H=0.1	H=0.1
Ildiz yotgan kesma	(x1, x2)=(x1, x1+h)	(x1, x2)=(x1, x1+h)
Ildiz yotgan kesmani aniqlash sharti	f(x1)·f(x2)<0	fnf(x1)*fnf(x2)<0
Urinmalar usulini qo‘llash sharti	f(x) f ''(x)>0	fnf(x)*fnf2(x)>0
Urinmalar usulida hisoblash formulasi	x1= x1 – f(x1)/ f '(x1)	X=X-(A-X)*FNF(X)/FNF1(X)
Ildizga yaqinlashish sharti	x1 –x2<	ABS(x1-x2)<=E yoki FNF(X)<=E

#include

using namespace std;

float f1(float a)

{

return (exp(a) - 10*a-2);

}

float f2(float a)

{

return (exp(a) - 10);

}

float f3(float a)

{

return exp(a);

}

float a, b, h = 0.1, x1, x2, x, EPS = 0.001;

int i = 1;

int main()

{

cout <<"Ildiz yotgan Kesma (a,b)= ";

cin >> a;

cin >> b;

cout <<"URINMALAR usulida hisoblash\noraliq va ildiz\n";

// cout <<"Ildiz yotgan oraliqlarni izlash qadami - h= ";

// cin >> h;

// cout << "Ildiz yotgan oraliq va ildiz\n";

x1 = a;

a1:

x2 = x1 + h;

x = x1;

a = x2;

if(x2 > b)

goto a4;

if(f1(x1)*f1(x2) > 0)

goto a3;

if(f1(x1)*f3(x1) > 0)

goto a2;

cout <

x = x2;

a = x1;

a2:

x = x - f1(x)/f2(x);

if(fabs(f1(x)) > EPS)

goto a2;

cout <

i++;

a3:

x1 = x2;

goto a1;

a4:

return 0;

}

22. Algebraik tenglamani yechishda x⁴-x³-2x²+3x-3=0 ,Kesmani teng ikkiga bo'lish usuli algoritm va dasturi?

Namuna

Berilganlar	Belgilashlar
	matn bo‘yicha	dastur bo‘yicha
Tenglama funksiyasi	f(x)=e^x-10x-2	FNF(x)=EXP(X)-10*X -2
Ildiz yotgan soha	a=-1, b=0	a=-1, b=0
Kesmani bo‘linish qadami va aniqlikda	H=0.1, =0.01	H=0.1: E=0.01
Ildiz yotgan kesma	(x1, x2)	(x1, x2)
Ildiz yotgan kesmani aniqlash sharti	f(x1)·f(x2)<0	fnf(x1)*fnf(x2)<0
kesmani teng ikkiga bo‘lish va ildiz yotgan kesmani aniqlash	t =(x1+x2)/2 va (t, x2) da f(t)·f(x2)<0	X=(X1+X3)/2 fnf(x)*fnf(x2)<0
Ildizga yaqinlashish sharti	t –x2<	ABS(t-x2)<=E yoki FNF(X)<=E

#include

using namespace std;

float f1(float x)

{

return exp(x)-10*x-2;

}

float a, b ,h, EPS, x1, x2, x3, x4, x;

int i = 1;

int main()

{

cout <<"Ildiz yotgan oraliq chagaralarini kiriting (a,b)= ";

cin >> a;

cin >> b;

cout <<"Aniqlik E ni kiriting = ";

cin >> EPS;

h = 0.1;

x1 = a;

a1:

x2=x1+h; x3=x1; x4=x2;

if(x2 > b)

goto a6;

if(f1(x1)*f1(x2) > 0)

goto a5;

a2:

x = (x3+x4)/2;

if(f1(x) < EPS)

goto a4;

if(f1(x)*f1(x3) < 0)

goto a3;

x3 = x;

goto a4;

a3:

x4 = x;

goto a2;

a4:

cout <<"Ildiz yotgan oraliq va ildiz\n";

cout << setprecision(4)<

Chapdagi i-elementni key bilan solishtiramiz. Agar key kichik bo‘lsa, keyingi qadamga o‘tamiz. Aks holda i++ va shu qadamni takrorlaymiz.

O‘ngdagi j-element bilan key solishtiriladi. Agar key katta bo‘lsa, keyingi qadamga o‘tamiz, aks holda j-- va shu qadamni takrorlaymiz.

i- va j-elementlarning o‘rni almashtiriladi. Agar i<=j bo‘lsa, 3-qadamga o‘tiladi.

Birinchi o‘tishdan keyin tanlangan element o‘zining joyiga kelib joylashadi.

6. 
   Endi shu ko‘rilayotgan oraliqda key kalitning chap tomonida elementlar mavjud bo‘lsa, ular ustida yuqoridagi amallarni bajarish lozim, ya’ni ko‘riladigan oraliq 0 dan key-1 gacha deb belgilanadi va 2-qadamga o‘tiladi. Aks holda keyingi qadamga o‘tiladi.
   
7. 
   Endi shu ko‘rilayotgan oraliqda key kalitning o‘ng tomonida elementlar mavjud bo‘lsa, ular ustida yuqoridagi amallarni bajarish lozim, ya’ni ko‘riladigan oraliq key+1 dan n-1 gacha deb belgilanadi va 2-qadamga o‘tiladi. Aks holda algoritm tugaydi.
   

Shu algoritmga misol ko‘rib chiqamiz.

Misol: Talabalar ism-sharifi va tartib raqamidan iborat jadvalni quicksort algoritmi bilan saralang va nechta o‘rinlashtirish amalga oshirilganini aniqlang.

Dastur kodi

#include

#include

using namespace std;

struct table{

int t;

string FIO;

};

int q=0;

void qs(table *a,int first,int last){

int i = first, j = last;table x =a[(first + last) / 2];

do {

while (a[i].FIO < x.FIO) i++;

while (a[j].FIO > x.FIO) j--;

if(i <= j) {

if (i < j){ swap(a[i], a[j]);q++;}

i++;

j--;

}

} while (i <= j);

if (i < last)

qs(a,i,last);

if (first < j)

qs(a,first,j);

}

int main(int args, char *argv[])

{ int n;cout<<"n=";cin>>n;

table talaba[n];

for(int i=0;i

talaba[i].t=i+1;

cin>>talaba[i].FIO;

}

qs(talaba,0,n-1);

for(int i=0;i

cout<

cout<<"quicksort algoritmi "<

system("PAUSE");

}

26. Chiziqli dasturlash. Optimallash masalasi. Maqsad funktsiyasi

Чизиқли дастурлаш математик дастурлашнинг бир йўналиши бўлиб, у чегараланган ресурслар(хом ашё, техника воситалари, капитал қўйилмалар, ер, сув, минерал ўғитлар ва бошқалар)ни рациона л тақсимлаб энг куп фойда олиш йўлларини ўргатади. Чизиқли дастурлаш чизиқли функциянинг, унинг таркибига кирувчи номаълумларга чегараловчи шартлар қўйилгандаги, энг катта ва энг кичик қийматини излаш ва топиш услубини ўргатувчи фандир. Номаълумларга чизиқли четламалар қўйилган чизиқли функциянинг экстремумини топиш масаласи чизиқли дастурлаш масаласи ҳисобланади. Шундай қилиб, чизиқли дастурлаш чизиқли функциянинг шартли экстремумини топиш масалалари туркумига киради. Чизиқли дастурлаш усулларини қўллаб иқтисодий жараёнларнинг ўзига хос қонуниятларини ўрганиш учун, биринчи навбатда, бу жараёнларни тавсифловчи математик моделларни тузиш керак. ўрганилаётган иқтисодий жараённинг асосий хоссаларини математик муносабатлар ёрдамида тавсифлаш тегишли иқтисодий жараённинг математик моделини тузиш деб аталади.

27. Chiziqli dasturlashning maxsus masalalari. Transport masalasi

Transport masalasi chiziqli dasturlash masalalari ichida nazariy va amaliy nuqtai nazardan eng yaxshi o’zlashtirilgan masalalardan biri bo’lib, undan sanoat va qishloq xo’jalik mahsulotlarini tashishni optimal rejalashtirish ishlarida muvaffaqiyatli ravishda foydalanilmoqda.

Transport masalasi maxsus chiziqli dasturlash masalalari sinfiga tegishli bo’lib, uning chegaralovchi shartlaridagi koeffitsientlardan tuzilgan (a_ij) matritsaning elementlari 0 va 1 raqamlardan iborat bo’ladi va har bir ustunda faqat ikkita element 0 dan farqli, qolganlari esa 0 ga teng bo’ladi. Transport masalasini yechish uchun uning maxsus xususiyatlarini nazarga oluvchi usullar yaratilgan bo’lib, quyida biz ular bilan tanishamiz.

Transport masalasining matematik modeli va xossalari

Faraz qilaylik, A₁, A₂, . . . A_m punktlarda bir xil mahsulot ishlab chiqarilsin. Ma’lum bir vaqt oralig’ida har bir Ai(i=1..m) punktda ishlab chiqariladigan mahsulot miqdori a_i birlikka teng bo’lsin. Ishlab chiqariladigan mahsulotlar B₁, B₂, ..., B_n punktlarda iste’mol qilinsin hamda har bir B_j(j=1,n) iste’molchining ko’rilayotgan vaqt oralig’ida mahsulotga bo’lgan talabi b_j(j=1,n) birlikka teng bo’lsin.

Bundan tashqari A₁, A₂, ..., A_m punktlarda ishlab chiqariladigan mahsulotlarning umumiy miqdori B₁ ,B₂ ,..., B_n punktlarning mahsulotga bo’lgan talablarining umumiy miqdoriga teng, ya’ni

tenglik o’rinli bo’lsin deb faraz qilamiz . Deylik, har bir ishlab chiqarish punkti A_i dan hamma iste’mol qiluvchi punktga mahsulot tashish imkoniyati mavjud, hamda A_i punktdan B_j punktga mahsulotni olib borish uchun sarf qilinadigan xarajat C_ij pul birligiga teng bo’lsin.

x_ij bilan rejalashtirilgan vaqt oralig’ida A_i punktdan B_j punktga olib boriladigan mahsulotning umumiy miqdorini belgilaymiz.

Transport masalasining berilgan parametrlarini va belgilangan noma’lumlarni quyidagi jadvalga joylashtiramiz.

Bj Ai	B1	B2	…	Bn	Taklif miqdori
A1	C11 X11	C12 X12	…	C1n X1n	a1
A2	C21 X21	C22 X22	…	C2n X2n	a2
…	…	…	…	…	…
Am	Cm1 Xm1	Cm2 Xm2	…	Cmn Xmn	am
Talab miqdori	b1	b2	…	bn

28. Diskret dasturlash. Resurslar haqidagi masalani shakllantirish.

1. 
   Diskret dasturlash (diskret optimallashtirish) bu matematik dasturlash bo'limi.
   
2. 
   Uzluksiz o'zgaruvchilar bilan optimallashtirish muammolaridan farqli o'laroq, diskret dasturlash masalalaridagi o'zgaruvchilar faqat diskret qiymatlarni oladi, masalan, butun son qiymatlari.
   
3. 
   Kombinatorial optimallashtirish masalalarini diskret dasturlash usullari yordamida echish mumkin. Ayrim dasturlash masalalarini echishning asosiy usullaridan ba'zilari bu kesilgan usul, tarmoqlangan va bog'langan usul va dinamik dasturlash.
   

“Iqtisodiy-matematik usullar va modellar” o‘quv fanini o‘zlashtirish jarayonida
amalga oshiriladigan masalalar doirasida talaba:
- zamonaviy bozor iqtisodiyotida optimal qarorlar qabul qilish mexanizmining nazariy
asoslarini; matematik modellashtirish tamoyillarini; zamonaviy axborot texnologiyalaridan
foydalana olish imkoniyatlarini; iqtisodiy jarayonlarning matematik funksiyalarini
kompyuterda maxsus dasturlar asosida hisoblashni; tavakkalchilik va noaniqlik sharoitida
matematik modellashtirish vositalaridan foydalanib, korxonalarning iqtisodiy
ko‘rsatkichlarini optimallashtirish bo‘yicha ssenariylar tuzishni; barqaror iqtisodiy o‘sishni
ta’minlashda qo‘llaniladigan makroiqtisodiy modellardan foydalanishni; raqobat va
tavakkalchilik sharoitida optimal boshqaruv qaror qabul qilish usullarini bilishi;
- turli mulkchilik korxonalarining statistik ma’lumotlari asosida ular holatini tahlil qilish
va sintezlash; ishlab chiqarish jarayonlari ma’lumotlari asosida turli matematik funksiyalarni
tuzish va ular asosida korxona holatini son va sifat jihatdan tahlil qilish; korxona va firmalar
faoliyatini zamonaviy kompyuter texnologiyalari yordamida ko‘p variantli yechimlarini olish
va ilmiy asoslangan xulosalar chiqarish; ishlab chiqarish korxonalarini ishbilarmon
o‘yinlarni tashkil etish asosida rivojlantirish yo‘llarini tahlil qilish hamda xulosalar chiqarish
ko‘nikmalariga ega bo‘lishi;
- makro va mikro jarayonlarni tahlil qilish; biznes korxonalarida taqchil resurslardan
optimal foydalanish; chiziqli funksiyalar va ularning xususiyati hamda parametrlarini
aniqlash; talab va taklif funksiyalari, ular asosida bozor sig‘imini hamda muvozanat
baholarni hisoblash; ishlab chiqarish jarayonlarini tahlil qilish; iqtisodiy jarayonlarni
matematik modellashtirish; korxona va firmalar faoliyati tahlilida axborot va kompyuter
texnologiyalaridan foydalana olish; korxonalarning ishlab chiqarish samaradorligi va
unga ta’sir qiluvchi omillarni tahlil qilish malakalariga ega bo‘lishi kerak.

29. Kvadratur formulalarining xatoligi?

30. Tarmoqlanuvchi algoritmlar to'liq va qisqa shakliga doir misol va algoritm tuzish?

31. Algebraik va transtsendent tenglamalarni taqribiy yechish usullari?

Algebraik va trantsendent tenglamalarni taqribiy yechish usullari, kesmani ikkiga bulish usuli Algebraik va trantsendent tenglamalar ildizlari yotadigan oraliklar ajratib olingandan sung tenglamaning ildizini taqribiy hisoblash uchun, taqribiy hisoblash usullaridan biri kullaniladi.Demak tenglama berilgandan sung, tenglamaning ildizlari yotgan oraliklar ajratib olinadi, taqribiy ildizni topish usuli tanlanadi, tanlangan usulga mos ravishda algorimning blok–sxemasi va biror bir dasturlashtirish tilida blok–sxemaga mos ravishda dastur tuziladi. Dastur kompyuterga terilib, natijalar olinadi va taxlil kilinadi.Tenglamalarning ildizlarini taqribiy yechish usullaridan biri bu kesmani teng ikkiga bulish usulidir. Bunda berilgan [a;b] kesma teng ikkiga bulinib [a;с] yoki [с;b] kesmalarda f(a)∙f(c)<0 yoki f(c)∙f(b)<0 shart tekshiriladi va с=(a+b)/2 qilib olinadi va ildiz b-a≤ε shart bajarulgunga kadar davom etirilib topiladi.

Vatarlar usuli va iteratsiya usuli Vatarlar usulida f(х) funktsiyaning [a;b] kesmaga tutashtiruvchi vatar utkaziladi. Tenglamaning taqribiy ildizini topish у=f(х) funktsiyaning birinchi va ikkinchi tartibli hosilalarining ishoralariga boglik. Agar f ^|(x) <0 va f ^||(x) <0 yoki f ^|(x) >0 va f ^||(x) <0 shartlar bajarilsa boshlangich kadam, ya‘ni boshlangich yechim qilib x₀=b deb olinadi, boshqa hollarda x₀=а deb olinadi.

x₀=а bo’lganda x=b nuqta kuzmas nuqta bo’ladi va ildiz

formula bilan hisoblanadi. x₀=b boshlangich ildiz bo’lganda esa x=а kuzgalmas nuqta deb olinadi va ildiz

formula bilan hisoblanadi. Ildizlarni taqribiy hisoblash jarayoni | xn-xn-1 |≤ε shart bajarulgunga kadar davom etiriladi. Bu yerda ε taqribiy ildizni topish aniqligi. Bu usullardan tashkari tenglamalarni taqribiy yechishning iteratsiya usuli ham mavjud.

32. Transport masalasini yechish bosqichlari?

Minimal xarajatlar usulining g’oyasi quyidagilardan iborat:

1. 
   Transport masalasi xarajatlaridan tashkil topgan matritsa belgilab olinadi, ya’ni
   
2. 
   
   

Bu matritsaning minimal elementini topib belgilaymiz

U holda quyidagicha aniqlanadi

Bu erda ikki hol bo’lishi mumkin:

1)

2)

Birinchi holda bo’lganda qatorning barcha (j≠j₁) elementlari 0 ga teng, ya’ni

bo’ladi, bunday holda i₁ qator o’chiriladi deb aytamiz. Ikkinchi holda

va j₁ ustunning barcha (i≠i₁) elementlari 0 ga teng, ya’ni

tenglik o’rinli bo’ladi, bunday holda j₁ ustun o’chiriladi deb aytamiz.

2. Faraz qilaylik, C′ matritsa C matritsaning i₁ qatorini (1-hol) yoki j₁ ustunini (2-hol) o’chirish natijasida hosil bo’lgan matritsa bo’lsin.

Yangi matritsa uchun

,

bo’lsin.

Ma’lumki, C′ matritsadagi ustun va qatorlar soni C matritsanikidan bittaga kam bo’ladi. Ikkinchi qadamda yuqoridagi C matritsa uchun bajarilgan ishlar C′ matritsa va , miqdorlar uchun bajariladi. Natijada rejalardan tashkil topgan X=(x_ij) matritsaning yana bir qatori yoki ustuni to’ldiriladi. Bu jarayon C matritsaning hamma qator va ustunlari o’chirilguncha, ya’ni X matritsaning hamma qator va ustunlari to’ldirilguncha takrorlanadi.

m ta ishlab chiqaruvchi punktni n ta iste’mol qiluvchi punktga bog’lovchi transport masalasining boshlang’ich bazis rejasini topish uchun minimal xarajatlar usulida n+m-1 ta qadamdan iborat ishlarni bajarish kerak bo’ladi.

Quyidagi transport masalasining boshlang’ich bazis yechimini toping.

bj ai	3	6	2	1
4	2	5	9	5
2	8	3	5	8
3	7	3	1	4
3	5	9	7	2

Masalani yechish algoritmi (Shimoliy-g’arbiy burchak usuli).

1-qadam.

x₁₁=min(4,3)=3

Shuning uchun b′₁=0 va a₁=4-3=1 , x₂₁=x₃₁=x₄₁=0

2-qadam.

x₁₂=min(1,6)=1.

Bunda a′₁=0 va b′₂=6-1=5 , x₁₃=x₁₄=0.

3-qadam.

x₂₂=min(2,5)=2.

Bunda a′₂=0 va b′₂=5-2=3 , x₂₃=x₂₄=0.

4-qadam.

x₃₂=min(3,3)=3.

Bunda a′′₂=b′′₂=0 bo’ladi hamda x₃₃=x₃₄=0, x₄₂ =0.

5-qadam.

x₄₃=2, a′₄=3-2=1.

6-qadam.

x₄₄ =min (1,1)=1

Bunda a′₄=b′₄=0 bo’ladi va masalani yechish jarayoni tugaydi. Topilgan boshlang’ich bazis yechim quyidagi ko’rinishda bo’ladi:

bj ai	3	6	2	1
4	2 3	5 1	9	5
2	8	3 2	5	8
3	7	3 3	1	4
3	5	9	7 2	2 1

Topilgan boshlang’ich bazis yechimdagi noldan farqli bo’lgan noma’lumlar soni 6 ta bo’lib, u m+n-1=7 dan kichik. Agar masalaning bazis rejadagi noldan farqli bo’lgan x_ij noma’lumlar soni m+n-1 dan kichik bo’lsa, bunday rejani xos reja deb ataymiz.

33. Selection sort saralash usuli, algoritm va dasturlari?

Selection sort g’oyasi juda ham oddiy: har qadamda arrayning saralanmagan qismidagi eng kichik (yoki eng katta) elementni topib saralangan qism oxiriga qo’shib ketish. Selection sort eng oddiy saralash algoritmlaridan bo’lib O(n²) vaqt tezligida ishlaydi. Ya’ni, algoritm barcha elementlarni ko’rib chiqish (n-1) mobaynida, har bir qadamda eng kichik elementni topish uchun qolgan elementlarni ko’rib chiqishi kerak bo’ladi. Matematik ko’rinishda quyidagicha bo’ladi: