Mavzu: n-to’liq masalalarni yechish algoritmlarini qiyinligini baxolash

13-mavzu: np to’liq masalalar. Hisoblashda yechilmaslik hollari

Mavzu: N-To’liq masalalarni yechish algoritmlarini qiyinligini baxolash..

Algoritmlarni loyihalash fanidan

Reja:

• 
  1. Hisoblash murakkabligini qanday baholash mumkin?
  
• 
  2. Masala murakkabligining nazariy chegarasi
  
• 
  3. Masalalarning murakkabligi sinflari
  

Algoritmni va uning murakkabligini tahlil qilish

Hisoblash murakkabligini qanday baholash mumkin?

Masala murakkabligining nazariy chegarasi

Masala murakkabligining nazariy chegarasi

Masala murakkabligining nazariy chegarasi

Xo'sh, murakkablik nazariyasini o'rganish va muammolarni NP-to'liqligi nuqtai nazaridan

tasniflashning amaliy ma'nosi nimada? Javob aniq - ko'rib chiqilayotgan muammoning NP-komplekt

sinfiga mansubligini isbotini topish va shunga muvofiq vaqtni sarflashdan ko'ra etarlicha aniq taxminiy

algoritmlarni izlash ancha oqilona va samaraliroq bo'ladi. uni echish uchun polinom algoritmlarini

topish. Bu erda markaziy rolni aynan NP bilan to'ldirilgan muammolar egallashi aniq - nuqta shundaki,

polinomiya vaqti birinchisi bo'lsa ham, ammo "amaliy masalalarni echish qobiliyati" tushunchasiga

etarlicha yaxshi yaqinlashadi.

Masalalarning sinflar bo’yicha murakkabligi

• 
  1960-yillarning boshlarida amaliy muammolarni hal qilishda kompyuter texnologiyalaridan keng foydalanishni boshlanishi bilan bog'liq holda, uning o'lchamiga cheklovlar ma'nosida muammoni yechish uchun ushbu algoritmni amaliy chegaralar doirasida qo'llanilishi yuzasidan savol tug'ildi. Haqiqiy vaqtda kompyuterda qanday vazifalarni hal qilish mumkin?
  
• 
  Ushbu savolga Alan Kobxem (1964) va Jek Edmonds (1965) javob berishdi, bu yerda murakkablik muammosi sinflari kiritilgan.
  
• 
  1) P sinf (polinom murakkabligi bilan bog'liq muammolar). Muammo polinom deb ataladi, ya'ni agar masalani yechishning (n) = O () algoritmi bilan o’zgarmas k bo'lsa, P sinfiga kiradi, bu yerda n bitlarga kiritiladigan algoritmning uzunligi n = | D |. P sinfidagi muammolar intuitiv, muammolar real vaqtda yechiladi.
  

•