Taqsimlangan algoritmlar va tizimlar

MUXAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
SAMARQAND FILIALI

KOMPYUTER TIZIMLARI KAFEDRASI

5330500- Kompyuter injiniring (Kompyuter injiniringi) ta'lim yo'nalishi

“Taqsimlangan algoritmlar va tizimlar” labartoriya fanidan

4-LABORATORIYA ISHI

Mavzu: Taqsimlangan tizimlarning matematik algoritmini ishlab chiqish.

Bajardi: 4-kurs talabasi O'sarov Fayzullo Qabul qildi: Xusanov K. Ishni bahosi: ___________ ball

Samarqand – 2022
Mavzu: Taqsimlangan tizimlarning matematik algoritmini ishlab chiqish.
Dinamik dasturlash ham matematik optimallashtirish usuli, ham kompyuter dasturlash usulidir. Usul 1950-yillarda Richard Bellman tomonidan ishlab chiqilgan va aerokosmik muhandislikdan iqtisodiyotgacha bo'lgan ko'plab sohalarda qo'llanilishini topdi .
Ikkala kontekstda bu murakkab muammoni rekursiv usulda oddiy kichik muammolarga bo'lish orqali soddalashtirishga ishora qiladi. Garchi ba'zi qarorlar bilan bog'liq muammolarni bu tarzda ajratib bo'lmasa-da, vaqt ichida bir necha nuqtalarni qamrab olgan qarorlar ko'pincha rekursiv ravishda ajralib chiqadi. Xuddi shunday, kompyuter fanida, agar muammoni kichik muammolarga bo'lish va keyin kichik muammolarning optimal echimlarini rekursiv ravishda topish yo'li bilan optimal tarzda echilishi mumkin bo'lsa, u optimal quyi tuzilishga ega deyiladi.
Agar kichik muammolar kattaroq muammolar ichida rekursiv tarzda joylashtirilsa, dinamik dasturlash usullari qo'llanilishi mumkin bo'lsa, u holda kattaroq muammoning qiymati va kichik muammolarning qiymatlari o'rtasida bog'liqlik mavjud. Optimallashtirish adabiyotida bu munosabat Bellman tenglamasi deb ataladi.

Dinamik dasturlash qo'llanilishi uchun muammo ikkita asosiy atributga ega bo'lishi kerak: optimal quyi tuzilma va bir-biriga mos keladigan kichik muammolar . Agar muammoni bir -biriga mos kelmaydigan kichik muammolarga optimal echimlarni birlashtirish orqali hal qilish mumkin bo'lsa, strategiya o'rniga " bo'lin va zabt et " deb ataladi . ^[1] Shuning uchun birlashtirish va tez tartiblash dinamik dasturlash muammolari sifatida tasniflanmaydi.

Optimal quyi tuzilma deganda, berilgan optimallashtirish muammosining yechimini uning kichik muammolarining optimal yechimlari kombinatsiyasi orqali olish mumkinligi tushuniladi. Bunday optimal pastki tuzilmalar odatda rekursiya yordamida tasvirlanadi . Masalan, G=(V,E) grafigi berilgan bo'lsa, u cho'qqidan v cho'qqigacha bo'lgan eng qisqa p yo'l optimal quyi tuzilmani ko'rsatadi: bu eng qisqa p yo'lda istalgan oraliq cho'qqi w ni oling . Agar p haqiqatan ham eng qisqa yo'l bo'lsa, uni u dan w gacha p ₁ va p ₂ pastki yo'llarga bo'lish mumkin .w dan v gacha shunday bo'ladiki, ular, o'z navbatida, mos keladigan cho'qqilar orasidagi eng qisqa yo'llardir ( Algoritmlarga kirishda tasvirlangan oddiy kesish va qo'yish argumenti bilan ). Shunday qilib, Bellman-Ford algoritmi yoki Floyd-Uorshall algoritmi bajaradigan rekursiv usulda eng qisqa yo'llarni topish uchun yechimni osongina shakllantirish mumkin .
Kichkina muammolarning bir-biriga o'xshashligi kichik muammolar maydoni kichik bo'lishi kerakligini anglatadi, ya'ni masalani yechishning har qanday rekursiv algoritmi yangi kichik muammolarni keltirib chiqarmasdan, bir xil kichik muammolarni qayta-qayta hal qilishi kerak. Misol uchun, Fibonachchi seriyasini yaratish uchun rekursiv formulani ko'rib chiqing: F _i = F _i -1 + F _i -2 , asosiy holat F ₁ = F ₂ = 1. Keyin F ₄₃ = F ₄₂ + F ₄₁ va F ₄₂ = F ₄₁ + F₄₀ . Endi F ₄₁ F ₄₃ va F ₄₂ ning rekursiv pastki daraxtlarida hal qilinmoqda . Kichik muammolarning umumiy soni aslida kichik bo'lsa ham (ulardan atigi 43 tasi), agar biz shunga o'xshash sodda rekursiv yechimni qabul qilsak, biz bir xil muammolarni qayta-qayta hal qilamiz. Dinamik dasturlash ushbu faktni hisobga oladi va har bir kichik muammoni faqat bir marta hal qiladi.