|
Ajrat va hukmronlik qil
|
| bet | 1/3 | | Sana | 27.05.2024 | | Hajmi | 26,91 Kb. | | #254608 |
Bog'liq Ajrat va hukmronlik qil
“Ajrat va hukmronlik qil” tilidagi algoritmlar
REJA:
Kirish.
Ajrat va hukmronlik qil tilidagi algoritmlar haqida.
Asosiy qism:
Algoritm qadamlari va dasturiy tadbiqi.
Kesh xotira bilan ishlash.
Qo’llanish muammolari.
Xulosa.
Foydalanilgan adabiyotlar.
Ajrat va hukmronlik qil tilidagi algoritmlar haqida.
Dasturlashda, ajrat va hukmronlik qil — bu algoritmik paradigm bo’lib, bu paradigmaning asosiy g’oyasi algoritmik masalalarni bosh masalaga o’xshash kichik qismlarga bo’lib tashlab, ularni rekursiv hal qilishdan iborat. Bu paradigmada masala qismlarga bo’linganligi sababli, qism masalalar bosh masalaga qaraganda kichikroq bo’lishi va bu bo’linish to’xtashi uchun asos holat bo’lishi kerak. Barcha turdagi bo’lib tashla va hukmronlik qil algoritmlari 3 ta bosqichdan iborat bo’ladi:
Ajrat bosqichi. Bunda bosh masala xuddi 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, ajrat hukmronlik qil paradigmasini 3 ta jumla bilan eslab qolish mumkin:
ajrat;
hukmronlik qil;
birlashtir.
Ajrat va hukmronlik qil paradigmasi dasturlashning mashhur algoritmlari asosini tashkil qiladi:
Quick Sort
Merge Sort
Eng yaqin ikki nuqta (Closest two points)
Strassen ko’paytirishi (Strassen multiplication)
Karatsuba algoritmi (Karatsuba algorithm)
Cooley-Tukey algoritmi (Cooley-Tukey Algorithm)
qiyin masalalarni osonlik bilan yechishga imkon beradi.
Algoritmlar nazariyasida “bo‘l va hukmronlik qil” tamoyili Algoritmlarning integral sinfi mavjud. “Ajralish” va “hukmronlik qilish” paradigmasi ikkita yoki undan ko’p birinchi murakkab masalalarni hal qiladi nisbatan oddiy masalalarga bo’linadigan algoritmlarni birlashtiradi. Bu keyin oddiy masalalarni yechishga asoslangan dastlabki masalani yechish qurilgan. Hozirgi vaqtda algoritmlashning ushbu prinsipi ko’p yo’nalishlarda mavjud muvaffaqiyatli qo’llanildi.
|
| |
