1-Mustaqil ish. Mavzu: Chiziqli va tarmoqlanuvchi algoritmlar. Savollarga nazariy javob bering

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. 
   

1-amaliy mashg’ulot
1-topshiriq
Quyidagi masalalar uchun algoritm va dastur kodini yozing. Har bir talaba o’zining jurnaldagi raqami bo’yicha bittadan masalani yechadi. Masalalar kam bo’lganda sanoq tartib boshidan boshlanadi. Masalan, 20 masala bo’lsa, 21-o’rindagi talaba 1-masalani, 22-o’rindagi talaba 2-masalani yechadi.

1. 
   Uchburchakning tomonlari a,b,c bo’lib, butun musbat sonlardan iborat bo’lsa, shu uchburchakning burchaklari bo’yicha turini aniqlang.
   

Dastur kodi

1. 
   #include
   
2. 
   using namespace std;
   
3. 
   int main()
   

4. { int m,n,r;

1. 
   cin>>m>>n;
   
2. 
   while(n!=0)
   
3. 
   { r=m%n;
   
4. 
   m=n;
   
5. 
   n=r;
   
6. 
   }
   
7. 
   cout<