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” amaliyot fanidan

2-AMALIY ISH

Mavzu: Taqsimlangan tizimlarning matematik algoritmini ishlab chiqish.

Bajardi: Xushvaqtov A. Qabul qildi: Xusanov K. Ishni bahosi: ___________ ball

Samarqand – 2022
Dinamik dasturlash: xususiyatlari, misoli, afzalliklari, kamchiliklari
Dinamik dasturlash Bu algoritm modeli bo'lib, uni natijalarni qayta hisoblab chiqishga yo'l qo'ymaslik uchun ularni natijalarini saqlash, uni subprolemlarga ajratish bo'yicha murakkab muammoni hal qiladi.
Ushbu jadval sizga o'xshash subproblemlarga bo'linishi mumkin bo'lgan muammolarga duch kelganingizda, natijada ularning natijalarini qayta ishlatishda foydalaniladi. Ko'pincha, ushbu jadval optimallashtirish uchun ishlatiladi.

Mavjud pastki muammolarni echishdan oldin, dinamik algoritm ilgari echilgan pastki muammolarning natijalarini tekshirishga harakat qiladi. Eng yaxshi echimga erishish uchun pastki muammolarga echimlar birlashtiriladi.
Bir xil subproblemni qayta-qayta hisoblash o'rniga, ushbu kichik muammoga duch kelganingizda o'zingizning echimingizni xotirada saqlashingiz mumkin. Boshqa subproblemni echish paytida yana paydo bo'lganda, xotirada allaqachon saqlangan yechim olinadi.

Dinamik dasturlash xususiyatlari

Dinamik dasturlashni amalga oshirishdan oldin quyidagi muhim xususiyatlarga duch kelishingiz kerak:

Optimal pastki tuzilish

Ushbu xususiyat optimallashtirish masalasini, uni o'z ichiga olgan ikkilamchi muammolarning optimal echimlarini birlashtirib hal qilish mumkinligini bildiradi. Ushbu maqbul pastki tuzilmalar rekursiya bilan tavsiflanadi.
Masalan, grafada s tepalikdan t tepalikka boradigan eng qisqa r yo'lda optimal pastki tuzilma taqdim etiladi:
Ya'ni, bu eng qisqa yo'lda r har qanday oraliq tepalikni olish mumkin. Agar r haqiqatan ham eng qisqa marshrut bo'lsa, uni r1 (s dan i gacha) va r2 (i dan t gacha) pastki marshrutlarga bo'lish mumkin, shunday qilib ular tegishli tepaliklar orasidagi eng qisqa marshrutlardir.
Shuning uchun eng qisqa yo'llarni topish uchun echimni rekursiv tarzda osonlikcha shakllantirish mumkin, bu Floyd-Uorshall algoritmi tomonidan amalga oshiriladi.
Bu xotira vaqtini aniqlash uchun ajoyib g'oya, bu erda qo'shimcha joydan foydalanish echim topish uchun zarur bo'lgan vaqtni yaxshilashi mumkin.