• Mavzu: Taqsimlangan tizimlarning matematik algoritmini ishlab chiqish.
  • Mavzu: Taqsimlangan tizimlarning matematik algoritmini ishlab chiqish. Dinamik dasturlash
  • Taqsimlangan algoritmlar va tizimlar




    Download 8,62 Kb.
    bet1/3
    Sana24.05.2024
    Hajmi8,62 Kb.
    #252893
      1   2   3
    Bog'liq
    Taqsimlangan algoritmlar va tizimlar-hozir.org (1)


    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 tizimlarlabartoriya 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 1 va 2 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: i = i -1 + i -2 , asosiy holat 1 = 2 = 1. Keyin 43 = 42 + 41 va 42 = 41 + F40 . Endi 41 43 va 42 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.

    Download 8,62 Kb.
      1   2   3




    Download 8,62 Kb.

    Bosh sahifa
    Aloqalar

        Bosh sahifa



    Taqsimlangan algoritmlar va tizimlar

    Download 8,62 Kb.