Toshkent 2023 Mavzu: p va np sinflar, np- to‘liq masalalar tushunchasi Reja: p va np sinflarining tengligi muammosi

Ushbu sinfga quyidagi vazifalar kiradi:
• texnik-iqtisodiy muammo: CNF-da berilgan buul formulasi uchun haqiqatni taqsimlash mavjudmi: haqiqat muhim bo'lgan qadriyatlarmi?
• Sayohat qilish bilan bog'liq muammo (Sayohat qiluvchi sotuvchi har bir shaharni bir marta borib, sayohat boshlangan shaharga qaytib borishni xohlaydi. Ma'lumki, i shahridan j shahriga o'tish j (i, j) rubldan boshlanadi. Buning uchun yo'l topish kerak.) minimal xarajat.);
• butun sonli o'zgaruvchilar bilan tenglamalar sistemalarini yechish;
• ma'lum shartlarni hisobga olgan holda jadvalni tuzish;
• xizmat ko'rsatish markazlarini (telefon; televidenie, shoshilinch xizmatlar) eng kam miqdordagi mijozlar uchun joylashtirish;
• eng kam xarajat bilan (yuk xalta, poezd, kema, samolyot) optimal sig'im;
• optimal kesish (qog'oz, karton, prokat, quyma), havo bo'shlig'i yo'nalishlarini, investitsiyalarni, mashinalarni optimallashtirish;
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.