Texnologiyalari universiteti infokomunikatsiya fakulteti Algoritm va matematik modellashtirish kafedrasi algoritmlarni loyihalash fanidan

Ajrat bosqichi. Bunda bosh masala huddi shu masalaga o’xshash kichikroq masalalarga bo’lib chiqiladi.

Hukmronlik bosqichi. Asos holatimizga mos kelib qolgan qism masalalar huddi u kabi yechiladi.

Birlashtirish bosqichi. Bu bosqichda yechilgan kichik qism masalalar qaytib birlashtirib chiqiladi va bu bosh masala yechimi bo’ladi.

Shu sababli, bo’lib tashla hukmronlik qil paradigmasini 3 ta jumla bilan eslab qolish mumkin: ajrat, hukmronlik qil, birlashtir. Oddiy, bittagina qadamdan iborat “bo’lib tashla va hukmronlik qil” algoritmi qanday ishlashini ko’raylik(1-rasm):

1-rasm. Bir qadamdan iborat “ajrat va hukmronlik qil” algoritmining ishlash printsipi.

Agar biz qadamlar sonini oshiradigan bo’lsak, paradigma tasviri quyidagicha ko’rinish oladi.

Agar biz qadamlar sonini oshiradigan bo’lsak, paradigma tasviri quyidagicha ko’rinish oladi
2- rasm. Ko’p qadamdan iborat “ajrat va hukmronlik qil” algoritmining ishlash printsipi

Ajrat va hukmronlik qil paradigmasi asosiy masalalari
Bu paradigma dasturlashning juda mashhur algoritmlari asosini tashkil qiladi:

1. 
   Ikkilik qidirish (Binary Search)
   
2. 
   Merge Sort
   
3. 
   Quick Sort
   
4. 
   Eng yaqin ikki nuqta (Closest two points)
   
5. 
   Strassen ko’paytirishi (Strassen multiplication)
   
6. 
   Karatsuba algoritmi (Karatsuba algorithm)
   
7. 
   Cooley-Tukey algoritmi (Cooley-Tukey Algorithm)
   

Ajrat va hukmronlik qil paradigmasi afzalliklari

• 
  qiyin masalalarni osonlik bilan yechishga imkon beradi
  
• 
  bu paradigmaga asoslangan algoritmlar oddiy yechimlardan ko’ra tezroq ishlaydi. Masalan: oddiy saralash bo’lgan Bubble Sortning tezligi O(n²) bo’lsa, MergeSortniki O(n*logn)
  
• 
  bunday algoritmlarni parallel hisoblovchi sistemalarda hech qanday o’zgarishsiz ishlatish mumkin
  
• 
  bunday algoritmlarni qo’llashda xotira keshidan unumli foydalanish mumkin. Chunki masalalar bo’linish jarayonida shunday kichik qismlarga ajraladiki, ularni keshni o’zida turib yechish mumkin bo’ladi.
  
• 
  haqiqiy sonlar uchun bunday algoritmlar aniqroq ishlaydi, chunki qism yechimlardagi haqiqiy sonlar ustidagi amallar aniqroq bajariladi (masalan, ko’paytirish algoritmlarida)