Mustaqil ishi qabul qildi: Ergashev. O topshirdi: Shamsuddinov. H mavzu: np- to’liq masalalar. Hisoblashda yechilmaslik hollari. Reja: np-to‘liklik masalasi

NP – to’liq masalalarni yechish usullari
Aniq usullar
Taqribiy usullar
To’liq qayta tanlash
Dinamik dasturlash
Tarmoqlar va chegaralar
Ochko’z va gradiyent usullar
Tasodifiy usullar
FF turidagi usullar
NP-to'liq masalalarning namunalari:

• 
  Bool formulalarining bajarilish masalasi
  
• 
  “O’n beshlik” o'yinining eng qisqa yechimi
  
• 
  Kommivoyajer masalasi
  
• 
  Shteyner muammosi
  
• 
  Grafni bo'yash muammosi
  
• 
  Graf cho’qqisini qoplash masalasi
  
• 
  To’plamni qoplash masalasi
  
• 
  Graf cho’qqilarining mustaqil to’plamlari masalasi
  
• 
  Saper o’yini
  
• 
  Tetris o’yini
  

NP-murakkab masalalarni hal qilish usullari quyidagilarga bo'linadi:

• 
  aniq
  
• 
  evristik
  
• 
  metaevristik usullari
  

Aniq usullar barcha mumkin bo'lgan yechimlarni to'liq ko’rib chiqishga asoslanadi va bu o'z navbatida ularning samadorligini kamaytiradi.
Evristik usullar yechimlarni nisbatan cheklangan qidirishga olib keladi va odatda maqbul vaqt ichida juda yaxshi yechimni topadi. Ammo bu usullar ham kamchilikka ega, ya'ni ular taxminiydir. Metaevristik usullar eng samarali hisoblanadi, ammo bu usullarda natijaga bevosita ta'sir qiladigan parametr mavjud, kirish ma'lumotlariga asoslanib, amalda har safar ushbu parametrni qayta hisoblash kerak
To'liq qayta tanlash(Полный перебор) usuli
Umumiy holatda bu usul, aksariyat shafqatsiz kuch usullari kabi samarasiz bo'lsa ham, ba'zi holatlarda bu juda maqbuldir. To'liq qayta tanlash (yoki shafqatsiz kuch) usuli bu matematik masalalarni hal qilish usulidir. Bu barcha variantlarni ko’rib chiqib, yechim topish usullari sinfiga tegishli. To'liq qayta tanlashning murakkabligi muammoni hal qilishning barcha mumkin bo'lgan yechimlari soniga bog'liq. Agar qaror qabul qilish maydoni juda katta bo'lsa, unda to'liq qayta tanlash bir necha yil yoki hatto asrlar davomida natijalarga olib kelmasligi mumkin.
NP sinfidagi har qanday muammoni to'liq qayta tanlash usuli orqali hal qilish mumkin. Bu holda, har qanday aniq yechimdan maqsad funktsiyani hisoblash polinomial vaqt ichida amalga oshirilishi mumkin bo'lsa ham, barcha mumkin bo'lgan echimlarning soniga qarab to'liq qayta tanlash eksponensial vaqtni talab qilishi mumkin.
Kriptografiyada shifrlarning kriptografik mustahkamlik to'liq qayta tanlashning hisoblash murakkabligiga asoslanadi. Xususan, shifrlash kriptografik mustahkam hisoblanadi, agar barcha kalitlarning to'liq qayta tanlanishidan ancha tezroq ishlaydigan «buzish» usuli bo'lmasa. To'liq qayta tanlash usuliga asoslangan kriptografik hujumlar eng universal, ammo eng uzoq vaqtda ishlaydigan usullardir.
To'liq qayta tanlash usulining mohiyati shundan iboratki:
a) barcha mumkin bo'lgan holatlarni ko'rib chiqish;
b) berilgan masalaning shartini qanoatlantiradigan yechimlarni topish;
c) boshqa yechimlar yo'qligini ko'rsatish.
Masalan, massivda maksimal sonni qidirish, ma'lumotlar faylidagi kerakli yozuvni qidirish va h.k. Bunday qidirish ma'lumotlar strukturasining barcha elementlarini sanab chiqish va ularni qidirish holatini qondirish uchun tekshirish orqali amalga oshiriladi. Tarkibning barcha elementlari ko'rib chiqilgan qidiruv to’liq qayta tanlash deyiladi.
To'liq qayta tanlash sxemasi doimo bir xil bo'ladi:

• 
  birinchidan, sanab o’tiladigan elementlarni tartiblash kerak (xususan, qaysi biri birinchi va oxirgisi bo'lishini aniqlash);
  
• 
  ikkinchidan, ixtiyoriy elementdan bevosita keyingisiga qanday o'tish kerakligini o’rganish (ya'ni, bunda X1 < X2 bo’lsin hamda X1 va X2 elementlar o'rtasida boshqa elementlar mavjud bo'lmasin).