13-ma'ruza. Np bilan bog'liq muammolar. Hisoblash qobiliyatsizligi Maruzachi o’qituvchi: katta o’qituvchi Ganihodjayeva Dilfuza Ziyavutdinovna Reja

NP bilan bog'liq muammolarni hal qilish yo'llari.

1. Taxminiy echimni qidirish (masalan, sayohat qiluvchi sotuvchi, xalta bilan bog'liq muammolarni hal qilishda ochko'z algoritmlardan foydalanish);

2. "Aqlli" qidiruv strategiyasini tashkil qilish (masalan, filial va bog'langan usul);

3. N P-to'liq muammolarni bir-birlariga kamaytirish (masalan, sayohat qiluvchi sotuvchi muammosini chiziqli dasturlash muammosiga qadar kamaytirish);

4. Samarali hal qilinadigan maxsus ishlarning NP-to'liq muammosidan ajratish.

Vaqtinchalik hisob-kitoblarni e'tiborsiz qoldirish mumkin.

• Agar yaratilgan dastur bir necha bor ishlatilsa, dasturni yozish va disk raskadrovka qilish qiymati ushbu dasturning umumiy qiymatidan oshib ketadi.

• Agar dastur faqat "kichik" kirish ma'lumotlari bilan ishlasa, unda ish vaqtining ko'payishi darajasi ish vaqti formulasida mavjud bo'lgan doimiydan kamroq ahamiyatga ega bo'ladi.

Agar tayyor dasturlar ularni tushunishga qodir bo'lmagan odamlar tomonidan qo'llab-quvvatlansa, samarali, ammo murakkab algoritmlar kerak bo'lmasligi mumkin.

• Samarali algoritmlar shu qadar katta hajmdagi kompyuter xotirasini talab qiladigan bir nechta misollar mavjudki, bu omil ularning afzalliklarini inkor etadi.

Raqamli algoritmlarda aniqlik va barqarorlik vaqtinchalik samaradorligidan kam emas.