2-mustaqil ish mavzusi. Chiziqli dasturlash masalalari va ularni yechish algoritmlari. Mustaqil ishni bajarish uchun namuna

Ikkinchi nazariy savol javobi

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.

3. 
   Uchinchi nazariy savol javobi
   
4. 
   To’rtinchi nazariy savol javobi
   
5. 
   
6. 
   
7. 
   

2. 
   1-Laboratoriya ishi topshiriqlari
   

Quyidagi masalalar uchun algoritm va dastur tuzing

1. 
   1.1-Laboratoriya mashg‘uloti mavzusi: Algoritmlarni loyihalash. Algoritm korrekt va samaradorligini baholash.
   

Ishning maqsadi: Berilgan masalalar uchun algoritm tuzish, ularni baholash kriteriyalari bo’yicha tahlil qilish, qiyinlik darajasini baholashni o’rganish
1-topshiriq.
Masala. Ikkita butun musbat a va b sonlar berilgan. Ularning eng katta umumiy bo’luvchisini topish talab qilinadi. Ya’ni, eng katta butun musbat son topish kerakki, unga a va b ni bo’lganda butun son chiqsin.