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

Algoritm qadamlari

Yuqorida aytganimizdek arrayda ikkita qism saralanmagan va saralangan qism bo’ladi. Algoritm boshida array butunligicha saralanmagan qismda bo’ladi va algoritm oxirida esa saralangan qismga o’tadi.

Array boshidan yurib chiqamiz. Har bir qadamda saralanmagan qismdagi eng kichik elementni topib uni saralanmagan qism boshidagi element bilan almashtiramiz. Saralangan qismni ko’rsatkichini bittaga oshiramiz. Oxirgi element avtomatik tarzda o’z joyida bo’lib qoladi.
34. Transport masalasining matematik modeli qanday?

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

35. Transport masalasini yechish algoritmida 𝑐_𝑖𝑗 o'zgaruvchi nimani ifodalaydi?

Masalani yechish algoritmi (Minimal xarajatlar usuli)

C matritsa I ustun j qator

1.

x₃₃=min (a₃ , b₃)=min (8,9)=8.

Bu holda x_3j=0, (j≠3) bo’ladi. Boshqacha aytganda 3-qator o’chiriladi va yangi C′ matritsa hosil bo’ladi. Bu matritsada

a₃¹=8-8=0,

b₃¹=9-8=1

bo’lib, C¹ matritsa quyidagi ko’rinishda bo’ladi:

2. C¹ matritsadagi elementlar ichida eng kichigini topamiz, ya’ni

U holda x₂₁=min (a₂, b₁)=min (11,5)=5. Demak, x₂₁=b₁=5.

Shuning uchun x_i1=0 (i≠2) bo’ladi, ya’ni 1-ustun o’chiriladi. Natijada yangi matritsa hosil bo’ladi.

Bu matritsa uchun =5-5=0, =11-5=6.

3. C^II matritsadagi elementlar ichida eng kichigini topamiz, ya’ni

Shuning uchun x₁₄=min (a₁, b₄)=min (11,7)=7. Bu erda 4-ustun o’chiriladi va =a₁-x₁₄=11-7=4 bo’ladi. Natijada yangi

matritsa hosil bo’ladi.

4. C^III matritsadagi elementlar ichida eng kichigini topiladi

Bu holda, x₂₂=min( ,b₂)=min(6,9)=6. Natijada 2-qator o’chiriladi va b₂ ning qiymati

=b₂-x₂₂=9-6=3

ga o’zgaradi va yangi C^IV matritsa-qator hosil bo’ladi:

C^IV=(8,5).

Shunday yo’l bilan 5-qadamda x₁₃=1 topilib, 3-ustun o’chiriladi. hosil bo’lgan X matritsa quyidagi ko’rinishga ega bo’ladi:

Bu matritsa berilgan transport masalasining bazis yechimidir.

36. Chiziqli dasturlash masalalarining matematik modellari

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

Masalaning iqtisodiy ma’nosi: yuk tashishning shunday rejasini tuzish kerakki: 1) har bir ishlab chiqarish punktidagi mahsulotlar to’la taqsimlansin ; 2) har bir iste’molchining mahsulotga bo’lgan talabi to’la qanoatlantirsin va shu bilan birga sarf qilinadigan yo’l xarajatlarining umumiy qiymati minimal bo’lsin.

Masalaning birinchi shartini quyidagi tenglamalar sistemasi orqali ifodalash mumkin:

(4.1)

Masalaning ikkinchi sharti esa quyidagi tenglamalar sistemasi ko’rinishida ifodalanadi:

(4.2)

Masalaning iqtisodiy ma’nosiga ko’ra noma’lumlar manfiy bo’lmasligi kerak, ya’ni

(4.3)

i-ishlab chiqarish punktidan j-iste’mol qiluvchi punktga rejadagi x_ij birlik mahsulotni yetkazib berish uchun sarf qilinadigan yo’l xarajati c_ij x_ij pul birligiga teng bo’ladi.

Rejadagi barcha mahsulotlarni tashish uchun sarf qilinadigan umumiy yo’l xarajatlari

funktsiya orqali ifodalanadi. Masalaning shartiga ko’ra bu funktsiya minimumga intilishi kerak, ya’ni

(4.4)

(4.1) - (4.4) munosabatlar birgalikda transport masalasining matematik modeli deb ataladi.

37. Fur`e qatorini trigonometrik va kompleks ko'rinishi?

38. Quydagi funktsiyaning (𝑥) = 𝑥² , Fure 𝑎₀, 𝑎_𝑛, 𝑏_𝑛 qiymatlarini hisoblang?

39. Fur`e qatorlari, MatLab dasturida signallar bilan ishlash tushunchasi

40. 𝑦 = 𝑘 ∙ sin(𝑥) funksiyaning Teylor-Makleron qatoriga yoyish algoritm va dasduri tuzing (k-jurnal nomer)?

41. Signal yetakchi garmonikalarini ajratish algoritmi

Signallarni bir nechta xabar manbalaridan uzatishda ushbu signallarni ajratishda har bir signalning har bir signaliga tegishli va uni qabul qiluvchiga yuborishi uchun ushbu signallarni ajratish kerak bo'ladi. Shunga o'xshash vazifa kodi signallari elementlari uzatilganda sodir bo'ladi. Telemexanik, signallarni ajratishning uchta asosiy usulida yoki ularning elementlari ishlatiladi: o'tkazuvchan (tutashtirish), vaqtinchalik va chastota.

vaqtincha ajratish (Muhr) signallarning har birining har bir manbai liniyani ta'minlaydi: vaqt oralig'ida birinchi manba, vaqt oralig'ida, vaqt oralig'i . Vaqtinchalik usulni amalga oshirish uchun Telemexik qurilmalarning xiyonat va xiyonatlari, hozirda aloqa bo'lmagan elementlar bo'lmagan ishlov berish moslamalari (distribyutorlar) yordamida aloqa liniyasi bilan bog'liq. chastotani ajratish (muhrlash) Xabarlarning har bir manbai ma'lum chastota diapazoni berilgan: 1 chastota diapazoni, ikkinchisining birinchi manbai, ikkinchisi - 1, ikkinchi va boshqalar. (Dol 2.11, a). Turli xabarlarni uzatishda ishlatiladigan chastota diapazoni bir-biriga mos kelmaydi. Shu bilan birga, barcha xabarlarning barcha manbalarining signallari bir vaqtning o'zida aloqa liniyasi orqali uzatiladi. 

42. Chiziqli dasturlash masalalarining yechishda simpleks usul algoritmi va uning tahlili

Dantsig yaratgan simpleks usul  har bir tenglamada bittadan ajratilgan no’malum (bazis o’zgaruvchi) qatnashishi shartiga asoslangan. Boshqacha aytganda, ChD masalasida m ta  o’zaro chiziqli erkli vektorlar mavjud deb qaraladi. Umumiylikni buzmagan holda bu vektorlar birinchi m ta P₁,P₂,…,P_m vektorlardan iborat bo’lsin, deylik. U holda masala quyidagi ko’rinishda bo’ladi:

(5.1)

  x₁≥ 0,  x₂ ≥ 0, …,  x_n ≥ 0,                (5.2)

Y = c₁x₁ + c₂x₂+ … + c_nx_n → min. (5.3)

(5.1)  sistemani vektor shaklida yozib olaylik:

P₁x₁ + P₂x₂+ … + P_mx_m + P_m+1x_m+1+ … + P_nx_n = P₀,  (5.4)

bu erda

 

,  , …, , ,…, , .

P₁, P₂, …, P_m vektorlar sistemasi m-o’lchovli fazoda o’zaro chiziqli erkli bo’lgan birlik vektorlar sistemasidan iborat. Ular m o’lchovli fazoning bazisini tashkil qiladi. Ushbu vektorlarga mos keluvchi x₁,x₂,…,x_m o’zgaruvchilarni «bazis o’zgaruvchilar» deb ataladi.

x_m+1, x_m+2,…, x_n – bazis bo’lmagan (erkli) o’zgaruvchilar. Agar erkli o’zgaruvchilarga 0 qiymat bersak, bazis o’zgaruvchilar ozod hadlarga teng bo’ladi. Natijada X₀ =(b₁,b₂,…,b_m, 0,…, 0) yechim hosil bo’ladi. Bu yechim boshlang’ich joiz yechim bo’ladi. Ushbu yechimga x₁P₁+x₂P₂+…+x_mP_m = P₀ yoyilma mos keladi. Bu yoyilmadagi P₁, P₂, …, P_m vektorlar o’zaro erkli bo’lganligi sababli topilgan joiz yechim bazis yechim bo’ladi.

Dantsig usulida simpleks jadval quyidagi ko’rinishda bo’ladi:

chiziqli funktsiyadagi koeffitsientlardan tashkil topgan vektor, ya’ni 

                               C_baz=(c₁,c₂,...,c_m)                      (5.5)

Jadvalda har bir P_j vektorning ustiga x_j noma’lumning chiziqli funktsiyadagi koeffitsienti c_j  yozilgan. m+1- qatorga esa x₁,x₂,…,x_m bazis o’zgaruvchilardagi chiziqli funktsiyaning qiymati

    (5.6)

hamda bazis yechimning optimallik mezonini baholovchi son

(i=1,…,m;  j=1,…,n)  (5.7)

yozilgan. Bazis o’zgaruvchilarga mos keluvchi  P₁, P₂, …, P_m vektorlar bazis vektorlar deb belgilangan. Bu vektorlar uchun ∆_j=Z_j-s_j=0 (j=1,…,m) bo’ladi. Agar barcha ustunlarda ∆_j ≤ 0 bo’lsa, u holda  X=( x₁,x₂,…,x_m) = (b₁,b₂,…,b_m) yechim optimal yechim bo’ladi. Bu yechimdagi chiziqli funktsiyaning qiymati Y₀ ga teng bo’ladi.

shartni qanoatlantiruvchi P_k vektorni  bazisga kiritib, bazisdan

(5.8)

shartni qanoatlantiruvchi P_l vektorni chiqarish kerak bo’ladi. Bu holda alk element hal qiluvchi element sifatida belgilandi. Shu element joylashgan l-qatordagi P_l vektor o’rniga u joylashgan ustundagi P_k vektor bazisga kiritiladi. P_l vektorning o’rniga P_k vektorni kiritish uchun simpleks jadval quyidagi formulalar asosida almashtiriladi.

Simpleks jadval almashgandan so’ng yana qaytadan ∆_j≤0 baholar aniqlanadi. Agar barcha j lar uchun ∆_j≤0 bo’lsa, optimal yechim topilgan bo’ladi. Aks holda topilgan bazis reja boshqa bazis reja bilan almashtiriladi.  Bunda quyidagi teoremalarga asoslanib ish ko’riladi:

5.1- teorema. Agar X=(x1,x2,…,xm) bazis reja uchun ∆j=Zj-sj≤0 (j=1,…,n) tengsizlik o’rinli bo’lsa, u holda bu reja optimal reja bo’ladi.

5.2- teorema. Agar X0 bazis rejada tayin bir j uchun ∆j=Zj-sj>0 shart o’rinli bo’lsa, u holda X0 optimal reja bo’lmaydi va shunday X1 rejani topish mumkin bo’ladiki, uning uchun 

Y(X₁)0)

tengsizlik o’rinli bo’ladi. Agar tayin bir j uchun ∆_j=Z_j-s_j>0 tengsizlik o’rinli bo’lsa, u holda 2- teoremaga asosan bu bazis rejani ham yangi bazis rejaga almashtirish kerak bo’ladi. Bu jarayon optimal reja topilguncha yoki masaladagi maqsad funktsiyaning quyidan chegaralanmagan ekanligi aniqlanguncha takrorlanadi.

Masalaning  optimal yechimining mavjud bo’lmaslik sharti quyidagicha:

Agar tayin j uchun ∆_j=Z_j-s_j>0 tengsizlik o’rinli bo’lib, bu  ustundagi barcha elementlar a_ij≤0 (i=1,…,m) bo’lsa,   u holda masalaning maqsad funksiyasi chekli ekstremumga ega bo’lmaydi.

Faraz qilaylik, simpleks jadvalda optimallik sharti (∆_j≤0, j=1,…,n) bajarilsin. Bu holda bu yechim 

(X₀=B^-1P₀)                     (5.9)

formula orqali topiladi. Bu erda B=(P₁, P₂, …, P_m) matritsa bazis vektorlardan tashkil

topgan matritsadir. 

Labotoriya topshirig‘i sharti. Masalani simpleks usul bilan yeching



Masalani yechish algoritmi (Simpleks usuli). Belgilashlar kiritamiz va simpleks jadvalni to’ldiramiz:

 

Simpleks usulning I bosqichida bazisga P₃ vektor kiritilib P₄ vektor chiqarildi, II bosqichida P₂ kiritildi va P₁ chiqarildi. Simpleks jadval (7) formulalar asosida almashtirilib borildi. III bosqichda optimal yechim topildi:

43. Ko'phadlar qiymatlarini hisoblashda Gorner sxemasi

P(x)=a₀xⁿ+a₁x^n-1+a₂x^n-2+...+a_n ko`phadni x-a ikkihadga bo`lishdagi qoldiqni hisoblashning Gorner (Xorner Uilyam (1786-1837) – ingliz matematigi) sxemasi deb ataluvchi usulini ko`rsatamiz.

P(x)=Q(x)(x-a)+r

bo`lsin. Bunda

Q(x)=b₀x^n-1+b₁x^n-2+b₂x^n-3+...+b_n-1.

(1) da x ning bir xil darajalari oldidagi koeffitsiyentlarni tenglashtirib quyidagiga ega bo`lamiz:

a₀=b₀ a₁=b₁-αb₀ a₂=b₂-αb₁

.......

a_n-1=b_n-1-αb_n-2 a_n=r-αb_n-1

Bundan ko`rinadiki, b₀=a₀, b_k=αb_k-1+a_k, k=1,2,..., n-1, r=a_n+αb_n-1.

Bo`linma va qoldiqni hisoblash quyidagi jadval yordamida topiladi.

	a0	a1	a2	...	an-1	an
α		αb0+a1	αb1+a2	...	αbn-2+an-1	αbn-1+an
	b0=a0	b1	b2	...	bn-1	r

2-misol. x³+4x²-3x+5 ko`phadni Gorner sxemasidan foydalanib, x-1 ga bo`lishni bajaramiz.

	1	4	-3	5
1	1	5	2	7

Demak, x³+4x²-3x+5=(x-1)(x²+5x+2)+7.

44. Dinamik dasturlash masalasi asosiy parametrlari

Динамик дастурлаш - вақтга боғлиқ ва кўп босқичли бош қарилувчи иқтисодий жараёнларни оптимал реж алаш тириш усулларини ўрганувчи математик дастурлаш нинг бир бўлимидир. Агар иқтисодий жараённинг кечишига таъсир кўрсатиш мумкин бўлса, бундай ж араён бошқарилувчи деб аталади. Ж араённинг кечишига таъсир этиш учун қабул қилинувчи қарорлар (ечимлар) тўпламига бошқариш деб аталади. Иқтисодий ж араёнларда бошқаришни режалаш тириш нинг ҳар бир босқичида воситаларни тақсимлаш , маблағ аж ратиш ва ш у кабилар билан ифода ланиш и мумкин. Чизиқли ва чизиқсиз дастурлаш масалаларида иқтисодий ж араён вақтга боғлиқ эмас деб қаралади, шунинг учун масаланинг оптимал ечими режалаш тириш нинг ф ақат бир босқичи учун топилади. Бундай масалалар бир босқичли масалалар номи билан аталади. Динамик дастурлаш масалаларида иқтисодий ж араён вақтга боғлиқ деб қаралади ҳамда бутун жараённниг оптимал ривожини таъминловчи бир қатор (кетма-кет, ҳар бир босқич учун алоҳида) оптимал ечимлар топилади. Динамик дастурлаш масалалари куп босқичли ёки кўп қадамли деб аталади.

45. Saralash usullari, algoritm va dasturlari(asosiy saralash qismi keltirilsin)?

Quiksort – tez saralash algoritmi

Bu algoritm “bo‘lib ol va egalik qil” tamoyilining yaqqol misolidir. Bu algotirm rekursiv bo‘lib, o‘rtacha N*log₂N ta solishtirish natijasida saralaydi. Algoritm berilgan massivni saralash uchun uni 2 taga bo‘lib oladi. Bo‘lib olish uchun ixtiyoriy elementni tanlab undan 2 ta qismga ajratiladi. Lekin o‘rtadagi elementni tanlab, massivning teng yarmidan 2 ga ajratgan ma’qul. Tanlangan kalit elementga nisbatan chapdagi va o‘ngdagi har bir element solishtiriladi. Kalit elementdan kichiklar chapga, kattalar o‘ng tomonga o‘tkaziladi (6.3-rasm). Endi massivning har ikkala tomonida xuddi yuqoridagi amallar takrorlanadi. Ya’ni bu oraliqlarning o‘rtasidagi elementlar kalit sifatida olinadi va h.k.

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");

}

Birlashtirish orqali (MergeSort) saralash.

MergeSort O(NlogN) da ishlaydigan optimal saralash algoritmlaridan biri. Eng yaxshi holatda ham, eng yomon holatda ham O(NLogN) assimptotikada ishlaydi. Hamda, u barqaror saralaydi, ya’ni sonlar ketma-ketligini buzmagan holda. Masalan, sonlardan tashqari, ularning kalit sonlari bo‘lsa, kalit soni 3 bo‘lgan 2 soni kalit soni 5 bo‘lgan 2 sonidan oldin kelsa, MergeSortda saralangandan so‘ng ham kalit soni 3 bo‘lgan 2 soni oldin keladi. QuickSort da doim ham bu shart bajarilavermaydi.

Algoritmning ishlash prinsipi quyidagicha: Massivni teng ikkiga bo‘lamiz. O‘ng tomonni alohida saralaymiz, chap tomonni alohida. So‘ng ikki saralangan qismni O(n)  ya’ni n ta operatsiyada qo‘shib, to‘liq saralangan massiv olamiz. Aynan shu operatsiya, ya’ni qo‘shish - Merge  ning hisobiga algoritm shunday nom olgan. Endi chap va o‘ng tomonlarini saralash uchun ham, ularni ikkiga bo‘lib xudi shu ishni bajaramiz va hk. Massivni bo‘lishni to unda 2 ta element qolguncha davom ettiramiz.

Shunday Merge funksiya asosida MergeSortni quyidagicha yozish mumkin.

#include

using namespace std;

int helper[1000001];

void Merge(int a[],int left,int middle,int right){

for(int i=left,j=middle,k=left;k

if(i==middle){ helper[k]=a[j++];continue;}

if(j==right ){ helper[k]=a[i++];continue;}

helper[k]=( a[i]< a[j])?a[i++]: a[j++];

}

for(int k=left;k

}

void MergeSort(int a[],int left,int right){

if(right-left==1)return;

int middle=(left+right)>>1;

MergeSort(a,left,middle);

MergeSort(a,middle,right);

Merge(a,left,middle,right);

}

int main(){

int a[10000], n , i;

cin>>n;

for(i=0;i>a[i];

MergeSort(a,0,n);

for(i=0;i

return 0;

}