Ishlab chiquvchining ishi ko'pincha jumboqlarni hal qilish bilan taqqoslanishi mumkin

O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi

islom karimov nomidagi toshkent davlat texnika universiteti

“elektronika va avtomatika” fakulteti

“ishlab chiqarish jarayonlarni avtomatlashtirish” kafedrasi

“Avtomatik Boshqarish Nazariyasi” fanidan

MUSTAQIL ISH

Bajardi: 2-kurs Talabasi
Gr: 11S-21 TJA
Xamrayev Sohib Abduxamidovich

Qabul qildi: ………………………………………………..

Toshkent - 2022

Dinamik dasturlash nima

Ishlab chiquvchining ishi ko'pincha jumboqlarni hal qilish bilan taqqoslanishi mumkin. Haqiqiy jumboqda bo'lgani kabi, ishlab chiquvchi ma'lum bir yechimni amalga oshirish uchun emas, balki maqbul yondashuvni tanlash uchun katta resurslarni sarflashi kerak. Ba'zida muammo osongina va samarali tarzda hal qilinadi, ba'zan esa - faqat barcha mumkin bo'lgan variantlarni to'liq sanab o'tish orqali. Ushbu yondashuv ko'pincha sodda yechim deb ataladi. Uning muhim kamchiligi bor - vaqt xarajatlari.
Barcha belgilar kombinatsiyasini sinab ko'rish orqali parolni buzishga harakat qilayotgan xakerni tasavvur qiling. Agar parol 10 ta raqam, 26 ta kichik harf, 26 ta katta harf va 32 ta maxsus belgidan iborat boʻlsa (dollar belgisi kabi), paroldagi har bir belgi uchun 94 ta nomzod mavjud. Bu shuni anglatadiki, bir belgidan iborat parolni qo'pol kuch bilan buzish uchun 94 ta tekshiruv kerak bo'ladi. Agar parolda ikkita belgi bo'lsa - birinchi o'rin uchun 94 nomzod, ikkinchi o'rin uchun 94 nomzod - u holda siz 94 * 94 = 8836 ta mumkin bo'lgan juftlikdan o'tishingiz kerak bo'ladi. O'n belgidan iborat parol uchun allaqachon 94 ^ 10 kombinatsiya kerak bo'ladi.
Umuman olganda, N uzunlikdagi ixtiyoriy parolni buzish uchun O(94^N) operatsiyalari kerak bo'ladi. Bunday xarajatlar ko'pincha "eksponensial" deb nomlanadi: har bir yangi pozitsiyaning paydo bo'lishi bitimlar sonining 94 baravar ko'payishiga olib keladi. Parolni buzish ekzotik narsa kabi ko'rinishi mumkin, ammo barcha variantlarni to'liq sanab o'tishni talab qiladigan vazifalar umuman ekzotik emas, balki ma'yus haqiqatdir.
Eksponensial vaqt uzoq. Hatto O(2^N) ham juda uzun. Shu qadar uzoq vaqt davomida bunday algoritmni hatto oddiy ma'lumotlarda ham bajarish hech kimning xayoliga kelmaydi - axir, yuzta element bilan bunday muammoni hal qilish minglab, millionlab yoki milliardlab yillik hisob-kitoblarni talab qiladi. Va haqiqiy hayotda siz juda ko'p sonli elementlar bilan muammolarni hal qilishingiz kerak. Qanday bo'lish kerak?
Gap shundaki, samarali hal qilish algoritmi bo'lmagan ko'plab muammolarni bir hiyla - dinamik dasturlash yordamida jozibali vaqtda hal qilish mumkin.
• Dinamik dasturlash
• Muammoni hal qilish misoli
• Jami
• Foydalanish sohalari
Dinamik dasturlash
Dinamik dasturlash - bu muammoni hal qilishda maxsus yondashuv. Dinamik dasturlashning yagona ta'rifi yo'q, ammo shunga qaramay biz uni shakllantirishga harakat qilamiz. G'oya shundan iboratki, muammoni hal qilishning barcha mumkin bo'lgan usullarini ko'rib chiqish va ular orasidan eng yaxshisini tanlash orqali optimal echimni topish mumkin.
Dinamik dasturlash ishi oraliq yechimlarni eslab qolish bilan rekursiyaga juda o'xshaydi - bu rekursiyani memoizatsiya deb ham atashadi. Rekursiv algoritmlar katta masalani kichikroq kichik muammolarga ajratish va ularni hal qilishga moyildir. Dinamik algoritmlar muammoni qismlarga ajratadi va ularni birma-bir hisoblab, bosqichma-bosqich yechimlarni yaratadi. Shuning uchun dinamik algoritmlarni pastdan yuqoriga ishlaydigan rekursiya deb hisoblash mumkin.

Dinamik dasturlashning sehri kichik muammolar echimlarini oqilona boshqarishda yotadi. "Aqlli" bu kontekstda "bir xil kichik muammoni ikki marta hal qilmaslik" degan ma'noni anglatadi. Buning uchun kichik kichik vazifalarning echimlari biron bir joyda saqlanishi kerak. Ko'pgina haqiqiy dinamik dasturlash algoritmlari uchun bu ma'lumotlar strukturasi jadvaldir.

Eng oddiy hollarda, bu jadval faqat bitta qatordan iborat bo'ladi - oddiy massivga o'xshash. Bu holatlar bir o'lchovli dinamik dasturlash deb nomlanadi va O(n) xotirani iste'mol qiladi. Masalan, Fibonachchi raqamlarini samarali hisoblash algoritmi hisoblangan oraliq natijalarni saqlash uchun oddiy massivdan foydalanadi. Klassik rekursiv algoritm juda ko'p ma'nosiz ishlarni bajaradi - u qo'shni rekursiya tarmoqlarida allaqachon hisoblangan narsalarni millioninchi marta hisoblab chiqadi.
Eng keng tarqalgan hollarda, bu jadval tanish ko'rinadi va qatorlar va ustunlardan iborat. Excel jadvallariga o'xshash oddiy jadval. Bu 2D dinamik dasturlash deb ataladi, jadvalning n ta satri va n ta ustuni O(n*n) = O(n^2) xotirani sarflaydi. Masalan, 10 satr va 10 ustundan iborat kvadrat jadvalda 100 ta katak bo'ladi. Faqat quyida ushbu vazifa batafsil muhokama qilinadi.
Yechish uchun 3D-jadvallardan foydalanadigan murakkabroq muammolar mavjud, ammo bu kamdan-kam uchraydi - muammoni 3D-jadval yordamida hal qilish ko'pincha oddiygina arzon emas. 1024 satr va 1024 ustundan iborat kichik ikki o'lchovli jadval bir necha megabayt xotirani talab qilishi mumkin. Xuddi shu parametrlarga ega uch o'lchamli jadval allaqachon bir necha gigabaytni oladi.


Muammoni dinamik hal qilish uchun uning dastlabki ma'lumotlaridan tashqari nima kerak? Faqat uchta narsa:
• Oraliq natijalar kiritiladigan jadval. Ulardan biri algoritm oxirida javob sifatida tanlanadi
• Bo'sh jadval kataklarini allaqachon to'ldirilgan katakchalardagi qiymatlar asosida to'ldirishning bir necha oddiy qoidalari. Bu erda universal retsept yo'q va har bir vazifa o'z yondashuvini talab qiladi.
• Jadvalni to'ldirgandan so'ng yakuniy yechimni tanlash qoidasi
Keling, ushbu tamoyillarni misol bilan ko'rib chiqaylik.