O’zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti tad kafedrasi: Algoritmlarni loyihalash fanidan Mustaqil ish Mavzu

Bo’lib tashla 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)
   

Bo’lib tashla va hukmronlik qil paradigmasi afzalliklari.

• 
  Qiyin masalalarni osonlik bilan yechishga imkon beradi
  
• 
  Bu paradigmaga asoslangan algoritmlar oddiy yechimlardan ko’ra tezroq ishlaydi. 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.
  

Bo’lib tashla va hukmronlik qil paradigmasi kamchiliklari

• 
  Bunday paradigma asosida ishlaydigan algoritmlar rekursiyadan foydalanadi va bu narsa ularni ishlashini ma’lum miqdorga sekinlashtiradi. Buning ustiga kichik bir xato yechimni cheksiz takrorlanishga tushirib qo’yishi mumkin.
  
• 
  Asos shartni tanlashda yo’l qo’yilgan xato barcha qism masalalarda xatolik va ortiqcha xotira ishlatilishiga olib keladi.
  

Kesh xotira bilan ishlash.

Kesh - bu shaxsiy kompyuter protsessoridan tez-tez so'raladigan ma'lumotlarni ma'lum vaqt davomida saqlash uchun foydalanadigan yuqori tezlikda ishlaydigan xotira. Bu samaradorlikni sifat jihatidan oshiradi, chunki u protsessorga kerakli ma'lumotlarni qidirish va ma'lumotlarni eng tezkor ravishda qanday olish kerakligini ko'rsatib beradi.

Kesh - bu yuqori tezlikda ishlaydigan xotira, bu sizga protsessorga kerakli ma'lumotlarni tezda olish imkonini beradi, buning natijasida shaxsiy kompyuterning ishlashi sifat jihatidan oshadi. Kesh brauzerlar tomonidan ham qo'llaniladi va oddiy tozalash tartibini talab qiladi. Kesh - tezkor xotira bilan talab qilinishi mumkin bo'lgan ma'lumotni o'z ichiga olgan tezkor kirish bilan, masalan, operatsion. Keshdagi ma'lumotlarga kirish tashqi xotiradan ma'lumotni olish yoki uni qayta hisoblashdan ko'ra tezroq, bu esa kirishning o'rtacha vaqtini kamaytiradi.

Protsessor ishlash uchun o‘z ma’lumotlarini operativ xotiradan oladi. Bunda mikrosxema ichida signallar juda katta chastotada (bir necha yuz MGts) ishlanadi, operativ xotiraga murojaatlarning hammasi esa bir necha marta kam chastotada sodir bo‘ladi. Chastotaning ichki ko‘paytirish koeffitsienti qanchalik yuqori bo‘lsa, protsessor, tashqarida saqlanayotgan ma’lumotlarga qaraganda, o‘zining ichida saqlanayotgan ma’lumotlar bilan shunchalik samaraliroq ishlaydi. Odatda protsessor o‘zining ichida deyarli hech narsani saqlamaydi. Unda ma’lumotlarga ishlov beriladigan yacheykalar (bu “ishchi” yacheykalar registrlar deb ataladi) juda kam. Shuning uchun protsessor ishini tezlatish uchun ancha oldin (4-avloddan boshlab) keshlash texnologiyasi taklif qilingan.

Kesh - bu bufer vazifasini bajaruvchi xotira yacheykalarining nisbatan katta bo‘lmagan to’plamidir. Umumiy xotiradan biror narsa o‘qilayotganda yoki unga yozilayotganda ma’lumotlarning nusxa (копия)si kesh-xotiraga ham kiritiladi. Agar shu ma’lumotlarning o‘zi yana zarur bo‘lib qolsa, ularni uzoqdan chaqirib olish zarur bo‘lmaydi - ularni buferdan olish ancha tezroq bo‘ladi. Kesh-xotiradan foydalanish kompyuter tizimi unumdorligini sezilarli oshirish imkonini berdi.
Quiksort–tez saralash algoritmi.

Quiksort–tez saralash algoritmi “bo’lib tashla va hukmronlik qil” tamoyilining yaqqol misolidir. Bu algotirm rekursiv bo’lib, o’rtacha N*log2N 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.
Merge Sort algoritmi va uning ishlash prinsipi.

"Bo'lib tashla va hukmronlik qil" usulining eng mashhur saralash algoritmlaridan biri Merge Sort (Birlashtirib saralash)dir. Merge Sort algoritmi bu saralanmagan massivni taqqoslashga asoslangan holda saralovchi algoritm bo'lib, uning ishlash printsipida to'liq bo'lib tashla va hukmronlik qil g’oyasini uchratish mumkin.

Chiziqli qidirish algoritmi.

Chiziqli qidirish algoritmi juda oddiy algoritm bo'lib, u massivdagi har bir elementni qidirilayotgan element bilan birma-bir solishtirib chiqadi. Algoritm murakkabligi O(n) bo'lib, bu real hayotda juda ham sekin bo'lishi mumkin. Tasavvur qilaylik Facebookning 1 mlrd foydalanuvchisi bor va foydalanuvchi o'z profiliga kirmoqchi. Bunda Facebook foydalanuvchi loginini chiziqli qidirishdan foydalanib tekshiradigan bo'lsa va bunda kompyuter sekundiga 10⁶ ta loginni tekshirgan taqdirda ham, o'sha foydalanuvchi profiliga kirishi uchun 1000 soniya (16.6 daqiqa) kutishi kerak bo'lardi. Shu sababli ham bunday holatlar uchun bizga samaraliroq algoritmlar kerak bo'ladi.

Ikkilik qidirish algoritmi to'g'ri ishlashi uchun massiv saralangan bo'lishi shart! Bizda n ta elementli saralangan massiv bor va biz undan x elementni qidirmoqdamiz. Biz qidirish chegarasini belgilash uchun l (left) va r (right) ko'rsatkichlardan foydalanamiz. Ular massiv indekslarini ko'rsatib turadi. Mid o’zgaruvchi bizda qidirilayotgan sohaning o’rtadagi elementi indeksini ko’rsatadi.
Quyidagi masalani Quiksort - tez saralash algoritmi asosida ko’rib chiqamiz.

Tasodifiy sonlar bilan to’ldirilgan massiv hosil qiling va uni saralang.