Dag‘al kuch” usuli. Xasis algoritmlar “Dag`al kuch” usuli bilan tartiblash. Kommuvoyajer masalasi

y=f(f(f…(x))…).
Bu holda murakkab muammoli masala, bir qator oddiy ketma- ket yechiladigan masalalarga ajratilish imumkin.
Hozirgi vaqtda o`z ichida bir qator bir hilt oifadagi masalala paydo bo`lib, ularni bir-biriga bog`liq bo`lmagan holda yechish mumkin. Bunday masalalar parallellash mumkin bo`lgan masalalar turkumiga tegishli bo`ladi. Bu masalalarni yechish uchun biz ko`p prosessorli hisoblash komplekslaridan (tizimlaridan) foydalanishimiz mumkin, bunda xar bir kichik masala alohida prosessorda boshqalardan mustaqil ravishda, lekin ular bilan bir vaqtda yechiladi. Bunday jarayonlar haqida tasavvurga ega bo`lish uchun matrisalarni ko`paytiris hmasalasini ko`rib chiqamiz:

Bu masalani A matrisa qatorini V matrisaga ko`paytirishdek m ta masala ko`rinishga keltirishimiz mumkin:

Buning natijasida qator matrisasi hosil bo`ladi:
(1)
(2)
Hisoblashlar (2) formulalar orqali i=1,2,…,m uchun avtonom ravishda m ta prosessorda bajarishi mumkin. Bu turdagi parallellashtirish masalalari matematik fizikaning ikki o`lchovli masalalarini chekli-ayirma usullari bilan yechishda hosil bo`ladi. Xotima sifatida Xanoy minorasini ko`chirish bo`yicha yana bitta “jumboq” (boshqotirma) li masalani ko`rib chiqamiz.Masalaning eng sodda variantini ko`raylik. Uchta A, B, C minora berilgan, ularning birinchisida uchta har xil radiusli halqalar o`rnatilgan bo`lib, halqalar kamayish tartibida joylashtirilgan. Har bir qadamda faqat bitta halqani siljitish orqali halqalarni xuddi shu tartibda C minoraga o`rnatish kerak bo`ladi. Boshlang`ich ko`rinishi quyidagi rasmda ko`rsatilgan.


z

y

x
A B C

Siljitish algoritmi

1. 
   2) 3) 4) 5) 6) 7)
   

Eslatma: Har bir qadamda halqalarning joylashish radiuslari kamayish tartibida bo`lishi kerak. To`rt halqa uchun masalani mustaqil yeching.
R kursi va lgoritmlarga faktorialni hisoblash masalasini kiritishimiz mumkin. Agar bo`lsa, u xolda bo`ladi. Determinantni hisoblash masalasida esa n-tartibli determinantni hisoblashni (n-1) tartibli determinantni hisoblash formulasiga keltirish mumkin bo`ladi.