|
2.2. Eksponensial murakkablikga ega algoritmlar
Algoritmning ko'paytirilgan yoki eksponensial xarakteri kirish ma'lumotlari (ikkilik, o'nlik yoki boshqa sonlar tizimi) shakliga nisbatan o'zgarmasdir.
Agar ishlaydigan vaqt, ya'ni vaqtning murakkabligi yuqoridan ma'lum darajadagi ko'p darajali polinomiya bilan chegaralangan bo'lsa, algoritm deyiladi. T(N)= O(Nm) ... Shunda bunday algoritm yordamida echiladigan barcha muammolar P-klass muammolarini hosil qiladi. Ushbu vazifalar R ga kiritilishi aytiladi.
Eksponensial vaqtning murakkabligi bilan bog'liq muammolar ( T(N)= O(KN) ) R ga kirmaydi.
Chiziqli murakkablikdagi muammolar P-ga kiritilganligini ko'rsatish mumkin
T(N)= O(N1 )
Keling, aniqlanmaydigan algoritm yordamida ko'paytirilgan vaqt ichida echilishi mumkin bo'lgan NP-muammolar sinfini keltiramiz.
Algoritm holatini hozirgi vaqtda bajarilayotgan buyruq manzili va barcha o'zgaruvchilarning qiymatlari deb ataymiz, bu jarayon holati vektoriga tengdir. Shuning uchun ko'pgina algoritmlar deterministikdir, ya'ni ularda har qanday holat uchun faqat bitta yo'l qo'yiladigan keyingi holat mavjud (shart va tanlash operatsiyalari). Bu shuni anglatadiki, bunday algoritm bir vaqtning o'zida bitta narsani bajarishi mumkin.
IN aniqlanmaydigan algoritm (NDA) har qanday berilgan holat uchun bir nechta maqbul keyingi holatlar bo'lishi mumkin, ya'ni bunday algoritm bir vaqtning o'zida bir nechta operatorlarni bajarishi mumkin.
NDA tasodifiy yoki ehtimoliy algoritm emas. Bu ko’plab shtatlarda bo’lishi mumkin bo’lgan algoritmdir. Bu ko’pgina parametrlarga parallel ravishda muammoni yechishga teng keladi.
A deterministik algoritm (DA) ushbu muammoni ketma-ket hal qiladi (barcha variantlarni ro'yxati, A0 alternativasini tanlamaguncha K0 optimalligi mezoni bilan taqqoslash).
NDA bir vaqtning o'zida (parallel ravishda) barcha muqobillarni olishi va K0 bilan taqqoslashi mumkin, mustaqil ravishda bajariladigan har bir alternativa uchun alohida jarayon sifatida nusxa ko'chiradi.
Bunday holda, agar biron-bir nusxada noto'g'ri natija olingan yoki natija olinmaganligi aniqlansa, u uning bajarilishini to'xtatadi. Agar nusxa K0 ni qoniqtiradigan echimni topsa, u muvaffaqiyat to'g'risida e'lon qiladi va boshqa barcha nusxalar ishlashni to'xtatadi.
T. haqida. NDA uch parametr bilan tavsiflanadi:
1. tanlash - qiymatlari S to'plamining elementlari bo'lgan ko'p qiymatli funktsiya;
2. muvaffaqiyatsizlik algoritm nusxasini tugatishga olib keladi;
3. muvaffaqiyat algoritmning barcha nusxalarini to'xtatish va natijani keltirib chiqaradi.
Shubhasiz, biron bir jismoniy qurilma cheksiz aniqlanmaydigan xatti-harakatlarga qodir emas, bu NDA nazariy usul ekanligini anglatadi.
Ikkinchi muammo algoritmlarni vaqt murakkabligi nuqtai nazaridan tasniflash bilan bog'liq. T (V) funktsiyasi odatda V. bilan o'sadi, u qanchalik tez o'sadi? T ning V ga chiziqli bog'liqligi (ko'rib chiqilgan misollarda bo'lgani kabi), kvadratik va yuqori darajadagi bog'liqlik bilan algoritmlar mavjud. Bunday algoritmlarga ko`pxotinlilik deyiladi. Va algoritmlar mavjud bo'lib, ularning murakkabligi har qanday polinomga qaraganda tezroq o'sadi. Teoristlar - algoritmlarni o'rganuvchilar ko'pincha hal qiladigan savol quyidagi savolga bog'liq: berilgan muammo uchun ko'paytirilgan algoritm mumkinmi?
Algoritmlarni tahlil qilishda tez-tez uchraydigan funktsiyalar:
jurnal n(logarifmik vaqt),
n (chiziqli vaqt),
n jurnal n,
n 2 (kvadratik vaqt),
2 n (eksponent vaqti).
Dastlabki to'rtta funktsiyalar past o'sish sur'atlariga ega va ularning ishlash muddati ushbu funktsiyalar tomonidan hisoblab chiqilgan tez hisoblanishi mumkin. Eksponensial funktsiyaning o'sish sur'ati ba'zan "portlovchi" deb ta'riflanadi. Taqqoslash uchun, algoritmlar bor deb faraz qilaylik, ularning murakkabligi (operatsiyalar soni) ushbu funktsiyalar tomonidan aniq aks ettirilgan.
Kompyuter fanlari, vaqtning murakkabligi bo'ladi hisoblash murakkabligi kompyuterni ishga tushirish vaqtini tavsiflovchi algoritm. Vaqtning murakkabligi odatda algoritm tomonidan bajarilgan elementar operatsiyalar sonini hisoblash bilan baholanadi, chunki har bir elementar operatsiyani bajarish uchun belgilangan vaqt kerak bo'ladi. Shunday qilib, algoritm tomonidan bajarilgan vaqt miqdori va elementar operatsiyalar soni eng ko'p a bilan farq qilish uchun qabul qilinadi doimiy omil.
Algoritmning ishlash vaqti bir xil o'lchamdagi turli xil yozuvlar orasida farq qilishi mumkinligi sababli, odatda eng yomon vaqt murakkabligi, bu ma'lum hajmdagi kirish uchun zarur bo'lgan maksimal vaqt. Kamroq tarqalgan va odatda aniq ko'rsatilgan, bu o'rtacha holatdagi murakkablik, bu ma'lum bir o'lchamdagi kirishlarga sarf qilingan vaqtning o'rtacha qiymati (bu mantiqiydir, chunki ma'lum hajmdagi mumkin bo'lgan kirishlarning faqat cheklangan soni mavjud). Ikkala holatda ham vaqt murakkabligi odatda a sifatida ifodalanadi funktsiya kirish kattaligi.
Ushbu funksiyani umuman aniq hisoblash qiyin bo'lgani uchun va kichik kirish uchun ishlash vaqti odatda natija bermaganligi sababli, odatda kirish hajmi kattalashganda murakkablik xatti-harakatiga e'tibor qaratiladi, ya'ni asimptotik xatti-harakatlar murakkablik. Shuning uchun vaqt murakkabligi odatda foydalanib ifoda etiladi katta O yozuvlari, odatda va boshqalar, qaerda n ning birlikdagi kirish kattaligi bitlar kirishni ifodalash uchun zarur.
Algoritmik murakkabliklar katta O yozuvida paydo bo'ladigan funktsiya turiga qarab tasniflanadi. Masalan, vaqt murakkabligi bilan algoritm a chiziqli vaqt algoritmi va vaqt murakkabligi bilan algoritm ba'zi bir doimiy uchun a polinom vaqt algoritmi.
XULOSA
Algortim asosida masala va misollar yechib, o’quvchilarning mustaqil fikrlashlari, mavjud bilimlarni tatbiq etish faoliyati matematika o’qitish jarayonida izchillik, ilmiylik kabi didaktik tamoyillardan o’rinli foydalanib, ularning tadqiqiy faoliyati metodik jihatdan to’g’ri tashkil qilindi va matematika o’qitishdagi barcha ko’rinishlar, metodlar, vositalar umumta’lim maktablari o’quvchilari va o’rta maxsus kasb – hunar ta’limi talabalari ko’nikmalarini shakllantirishga qaratildi.
Algoritmning tadqiqiy ko’nikmalarini shakllantirishga erishdik. Umuman olganda, ushbu mavzu menda katta tassurot qoldirdi. Shuning uchun qolgan talabalarga ham bu mavzuni o’rganib chiqishni va shu sohada ilmiy izlanishlar olib borishlarini maqsadga muvofiq deb o’ylayman.
Men ushbu kurs ishini bajarish mobaynida eng qisqa yo'llarini topish algoritmlarini bu yo’llar kimlar tomonida o’ylab topilganini bu yo’llarni nima sababdan o’ylab topilganini bu yo’llarni turlarini o’rgandim.
Do'stlaringiz bilan baham: | 
