Algoritmlarni loyihalash Mavzu: Algoritmlarni loyihalash va tahlil qilish. Chiziqli dasturlash masalalari va ularni yechish algoritmlari

Algoritmlarni loyihalash Mavzu: Algoritmlarni loyihalash va tahlil qilish. Chiziqli dasturlash masalalari va ularni yechish algoritmlari.

Dars rejasi

• Algoritmlarni baholash kriteriyalari
• Matrisalarni ko’paytirish.
• Integrallarni taqribiy hisoblash usullari

Algoritmlarning qiyosiy bahosi

Algoritmlarni baholash uchun ikkita asosiy kretiriya mavjud.

• Algoritmni ishlash vaqti bo’yicha baholash
• Algoritmni bajarish uchun xotiradan egallagan hajmi bo’yicha baholash

Algoritmlarning qiyosiy bahosi

• 𝑭𝒂(𝒏) algoritmning qiyinligi deganda berilgan kirish ma’lumotlari uchun, aniq muammoani (masalani) yechish uchun, ushbu formal tizimda algoritmni tugallash uchun bajariladigan (𝑛) ta “elementar” amallar soni tushuniladi.

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.

• 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.

Algoritmning qiyinligi va vaqt bo’yicha bahosi

• Algoritmni yozish tilidagi elementlar operatsiyalar (amallar)
• Algoritmning qiyinlik funktsiyasini olishda quyidagi “elementar” amallar hisobga olinadi:
• 1. Oddiy ta’minlash: a←b;
• 2. Bir o’lchamli indekslash a[i]: ((a – xotira adresi)+i*[element uzunligi]);
• 3. Arifmetik amallar: (*, /, -, +);
• 4. Taqqoslash amallari: a, ≤, ≥, <>);
• 5. Mantiqiy amallar (or, and, not).
• Tahlilda ushbu operatsiyalardan, tarmoqlanish konstruktsiyasida taqqoslash operatsiyasi bilan bog’liqligini hisobga olib, adres bo’yicha o’tish komandasi chiqarib tashlanadi.

Dastur kodi. #include

• Dastur kodi. #include
• using namespace std;//ulchamlari bir xil bulgan matritsalar uchun
• int main()
• {
• int a[10][10],b[10][10],c[10][10],r,d,i,j,k;
• cout<<"satrlar soni=";
• cin>>r;
• cout<<"ustunlar soni=";
• cin>>d;
• cout<<"matritsa elementlarini kiriting=\n";
• for(i=1;i<=r;i++)
• { for(j=1;j<=d;j++) {
• cin>>a[i][j];} }
• cout<<"ikkinchi matritsa elementlarini kiriting=\n";
• for(i=1;i<=r;i++)
• { for(j=1;j<=d;j++)
• cin>>b[i][j];}
• for(i=1;i<=r;i++)
• { for(j=1;j<=d;j++)
• { c[i][j]=0;
• for(k=1;k<=d;k++)
• {
• c[i][j]+=a[i][k]*b[k][j]; } } }
• //natijani chop qilish
• for(i=1;i<=r;i++)
• {
• for(j=1;j<=d;j++)
• {
• cout<
• }
• cout<<"\n";
• }
• return 0;
• }

Chiziqli algoritm - “ketma-ketlik” konstruktsiyasi

• Bu algoritmning qiyinligi ketma-ket bajariladigan konstruktsiya bloklarining qiyinliklari yig’indisiga teng bo’ladi

Dastur kodi

• Dastur kodi
• #include
• #include
• using namespace std;
• double funk(double x)
• {
• return (1.0/(1+x*x));
• }
• int main()
• {
• double a,b,S=0, xa;
• int n=10;
• cout<<"integral chegarasini kiriting"<
• cin>>a>>b;
• xa=a+0.1;
• while (xa
• {
• S+=funk(xa);
• xa+=0.1;
• }
• S=S*fabs(b-a)/n;
• cout << S;
• return 0; }

Dastur kodi

• Dastur kodi
•  
• #include
• #include
• using namespace std;
• double funk(double x)
• {
• return (1.0/(1+x*x));
• }
• int main()
• {
• double a,b,S=0, xa;
• int n=10;
• cout<<"integral chegarasini kiriting"<
• cin>>a>>b;
• xa=a+0.1;
• while (xa
• {
• S+=funk(xa);
• xa+=0.1;
• }
• S=(a+b)/2+S;
• S=S*fabs(b-a)/n;
• cout << S;
• return 0; }

Mustaqil ishlash uchun savollar

• Ushbu darsda ko’rib chiqilgan misollar va ularni yechish algoritmlari uchun dastur tuzing, xulosalar chiqaring.