Deklarativ dasturlash fanida mustaqil ishi mavzu
Download 437.27 Kb. Pdf ko'rish
|
DP - Haskell
- Bu sahifa navigatsiya:
- Overlapping sub problems
- Oddiy rekursiv yoki sodda.
- N bilan ishlash vaqtlari va kosmik foydalanish degradatsiyasi
- 2. Yuqoridan pastga rekursiv
- 4. Pastdan yuqoriga bo‘sh joy optimallashtirildi
|
O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARNI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI “DIF” fakulteti “ATDT” kafedrasi Deklarativ dasturlash fanida MUSTAQIL ISHI Mavzu: Hakelldagi funktsional uslubda muammolarni hal qilish. Bajardi: 301-22 guruh talabasi Akbarov S.U. Toshkent – 2023 Haskell bu funksional dasturlashga mo`jallangan bo`lib dasturni funsional tarzda yozishimiz mumkin ya’ni tilda hech qanday OOP prinsiplari mavjud bo`lmaydi. Shuning uchun ham funksiyanlarimiz lazy evaluation boshqacha qilib aytganda chaqirsagina amalga oshiriladiga tarzda dastur yozsak bo`ladi. Biz funksiyanal dasturlash yordamida hamma obyetga yo`naltirilgan dastulashda bo`lgani muammolarni yecha olamiz. Misol uchn fibnanachi sonlari bo`lsin. Sof FPda dinamik dasturlash algoritmlarini amalga oshirish uchun Haskell xususiyatlari. Ushbu maqola 3 qismdan iborat va: • Dinamik dasturlash (DP) yoki Funktsional dasturlash (FP) yoki Haskell yoki Monadlar haqidagi asoslarni qamrab olmaydi . • Yodga olish (STArray) va holatli hisoblashlar (ST Monad) yordamida DP muammosini hal qilish uchun Haskelldagi FP mexanizmini qamrab oladi . Dinamik dasturlash ikkita xususiyatni qondiradigan muammolarni hal qilish uchun paradigmadir: • Optimal Sub-Structure: muammoni kichik qismlarga bo'lish va kichikroq qismlarni echishda rekursiv usuldan foydalanish imkonini beradi. • Overlapping sub problems: takroriy hisoblashni oldini olish uchun qayta ishlatilishi mumkin bo'lgan kichik kichik muammolar natijalarini saqlashga imkon beradi. Biz shunday muammolardan birini (buzilishlarni sanash) sof funktsional usulda qanday hal qilishni o'rganish uchun foydalanamiz. Muammoning juda batafsil tushuntirishi bu yerda berilgan. Oddiy misol sifatida, agar bizda uchta ABC alifbosi bo'lsa. Mumkin bo'lgan buzilishlar faqat BCA va CAB. Ammo ACB (asl holatida A), CBA (B asl holatida) va BAC (asl holatida C) haqiqiy buzilishlar emas, chunki muammo ta'rifiga ko'ra hech qanday alifbo o'zining asl holatida bo'lmasligi kerak. f(x) uchun hisoblar, bunda x = 1,2,3,…,n f (n) yechimning dinamik dasturlash xususiyatiga ishora qiladi va bizning rekursiya uchun asos bo'ladi va pastdan yuqoriga yondashuv formulasi bo'ladi. Dasturiy jihatdan buni 4 xil usulda hal qilish mumkin. 1. Oddiy rekursiv yoki sodda. Ushbu versiya oddiy, lekin u bir xil "n" uchun baholashni bir necha marta takrorlaydigan hisob-kitoblar daraxtini ishlab chiqaradi. Rasmdan ko'rinib turibdiki, f(5) uchun biz f(3) 2 marta, f(2) 3 marta va f(1) 2 marta hisob-kitoblarni takrorlaymiz. Kichkina o'zgarishlar uchun ham makon va vaqt yomonlashadi. N bilan ishlash vaqtlari va kosmik foydalanish degradatsiyasi Yuqoridagi jadval n ning ortishi bilan bo'sh joy iste'moli oddiy rekursiv versiyada juda yomon ekanligini ko'rsatadi. Har qanday amaldagi DP nomzodida bo'lgani kabi, uni memoizatsiya yordamida yuqoridan pastga yoki pastdan yuqoriga yondashuvlar yordamida yaxshilash mumkin. 2. Yuqoridan pastga rekursiv — oraliq natijalarni saqlash va undan qayta foydalanish uchun massiv yoki vektor yoki shunga o'xshash ma'lumotlar strukturasidan foydalanish. (Biz Haskell tomonidan taqdim etilgan STArray-dan foydalanamiz) 3. Pastdan yuqoriga — massivdan foydalanish va hisoblar natijalarini 1 dan n gacha saqlash, natijalar bir yoki ikkita asosiy holat uchun oldindan belgilangan ( bu holda arr(1) = 0, arr(2) = 1) (Yana, biz STArray dan foydalaning) 4. Pastdan yuqoriga bo‘sh joy optimallashtirildi — pastdan yuqoriga hisoblar uchun massiv o‘rniga atigi 3 ta “o‘zgaruvchi”dan foydalanish. (Biz runST bilan birga StateT Monaddan foydalanamiz) Xavfsiz o'zgaruvchanlik va monadlar Sof FPda biz monada mumkin bo'lgan monadlardan foydalanamiz • izchil tarzda boshqarilishi mumkin bo'lgan "kontekst" qiymati bo'lsin • xavfsiz bo'ling, sof funktsional dasturlashda referent shaffofligini ta'minlang • IO/Async/tasodifiylik va hokazo kabi xavfli dastur xatti-harakatlarini inkapsulyatsiya qilish uchun ishlatiladi. Bundan tashqari hamma bilgan dijkstras algoritimini Haskell yordamida amalga oshirishimiz mumkin. U quydagicha bo`ladi: Download 437.27 Kb. Do'stlaringiz bilan baham: 
|