Matematik asoslar va raqamli modellashtirish usullari

KOMPYUTER TADQIQOTLARI VA MODELLASHTIRISH
Algoritmlar va dasturlarni parallelizatsiyalashga kirish
255
Belgilash
S
i
k
operatorning "reenkarnatsiyasi" uchun ishlatiladi
S
k
haqida
tsiklning i-iteratsiyasi.
Quyidagi operatorlarning bunday kengaytirilgan ketma
-ketligida ma'lumotlar bilan bog'liq holda ularning to'plamini tahlil qilish mumkin.
Biz ularni osonlik bilan o'zgaruvchilar qayta nomlash orqali bartaraf qilinishi mumkin, deb bilaman, chunki tahlil, biz, dam
olish kunlari bog'liq manfaatdor bo'lmaydi. Shuning uchun, biz ishonamiz, tsikl tanasida bir operator uchun
, qator a element uchun murojaat kiritish o'zgaruvchilar majmui kiritilgan, va boshqa-
chiqish elementlari majmui.
Jamiyatni cheklamasdan, biz tsiklni qo'lga kiritamiz:
do j = 1, jfin
S
1
:
A[f(j)] =
. . .
S
2
:
. . .
=
. . .
A[g(j)]
. . .
enddo
Yoki kengaytirilgan shaklda:
S
1
1
:
A[f(1)] =
. . .
S
1
2
:
. . . = . . .
A[g(1)]
. . .
S
2
1
:
A[f(2)] =
. . .
S
2
2
:
. . .
=
. . .
A[g(2)]
. . .
. . .
S
jfin
1
:
A[f(jfin)] =
. . .
S
jfin
2
: . . .
=
. . .
A[g(jfin)]
. . .
Bernsteinning shartlari quruq bo'lsa, buzilgan bo'lishi mumkinligini ko'rish oson-
iterativ o'zgaruvchining qiymatlari"
j " l va k,
1
≤ l ≤ jfin, 1 ≤ k ≤ jfin
f
(λ) = g(κ). Bunday qadriyatlar mavjudligini bilish uchun
, belgilangan cheklovlar bilan butun sonlarda berilgan tenglamani hal qilish kerak. Biz Diofant vazifasiga keldik.
Umuman olganda, Diofant tenglamalarini echish qobiliyati Guilbert muammosining
yuz yilligini tashkil etadi, 1970 da algoritmik hal etilmaydigan qism Yuriy Matiyasevich tomonidan tasdiqlangan. . .
Oddiy hollarda, masalan, qachon
f va g-lineer funktsiyalar,
echim borligini va, albatta, nima bo'lishi mumkinligini aniqlash uchun, lekin umuman olganda-yo'q. Agar echimlar
mavjud bo'lmasa, tarqatilgan tsiklning barcha operatorlari bir-biridan mustaqil
bo'lib, turli ijrochilar tomonidan bir vaqtning o'zida bajarilishi mumkin, masalan, tsiklning har bir iteratsiyasi —
ijrochiga. Desert mavjud va biz tegishli k va l ni topdik. Bernsteinning shartlari
buzilgan-operatorlar orasida qaramlik. Bunday holda, operator
S
κ
1
(bu erda mas elementi-
Siva a-chiqish o'zgaruvchisi) qaramlikning manbai (manba) va operator deb ataladi
S
λ
2
(bu erda
bir qator element a-kirish o'zgaruvchilar) deb ataladi oqimi (sink) qaramlik.
Qiymati hisoblang
D
= λ
− k(oqim iteratsiyasidan manba iteratsiyasini olib tashlaymiz). Ushbu qiymat qabul qilinadi
tsiklga qaramlik holatini chaqiring.
Bir vaqtning o'zida tsiklni tahlil qilishda qaramlik masofasi muhim rol o'ynaydi. Uning
ma'nosi ma'lumotlar va yuzaga keladigan qaramlikning turini aniqlashga imkon
beradibir vaqtning o'zida bajarilishi uchun javobgarlik zonalariga iteratsiya maydonini ajratish.
Keling, bir nechta misolni ko'rib chiqaylik.