Laboratoriya ishi 25 Mavzu: np-to’liq masalalar. Ishdan maqsad

Nazariy qism
Optimallashtirish bilan bog‘liq masalalar bu – muayyan miqdordagi qiymatni maksimal darajada oshirish yoki minimallashtirish kerak bo‘lgan masalalardi. NP – to‘liqlik haqida savol berishdan oldin bunday masalalar, ularni hal qilish masalalariga aylantirilishi kerak. Shunday qilib, masalan, grafdagi eng qisqa yo‘lni topish masalasida optimallashtirish masalasini yechish masalasidan ruxsat berish masalasiga o‘tdik va yo‘l uzunligiga cheklov qo‘shdik. Agar transformasiyadan keyin NP – to‘liq masalasi yuzaga kelsa, unda asl muammoning qiyinligi ham belgilanadi. Ma'lumotlar taqdimoti
Kirish ma'lumotlarini (ya'ni I to‘plamning elementi) algoritmga kiritishdan oldin ularning qanday qilib “kompyuterga qulay” tarzda taqdim etilishi to‘g‘risida kelishib olish kerak. Dastlabki ma'lumotlar bitlar ketma-ketligi bilan kodlangan deb qabul qilamiz. Formal aytganda, S to‘plamining elementlarini ifodalash bu S dan e ni bitli satrlar to‘plamlariga tushishidir. Masalan, (0, 1, 2, 3,...) – butun sonlarni, odatda (0, 1, 10, 11, 100, ...) – bitli satrlar bilan ifodalanadi.
Taqdim qilingan ma'lumotlarni joylashtirb, mavhum masalani satrli ma'lumotga aylantiramiz, bu satirli ma'lumot uchun kirish ma'lumotlari, masalaning dastlabki ma'lumotlarini aks ettiruvchi bitli satir bo‘ladi. Kirish ma'lumotlari (bitli satr) n – uzunlikda bo‘lganida, algoritmning ishlash vaqti O(T(n)) – bo‘lsa, algoritm satirli masalani O(T(n)) vaqtda yechadi desak bo‘ladi. Agar k konstanta va O(T(n)) vaqt ichida bu masalani yechadigan algoritm mavjud bo‘lsa, satirli masala polinomial' deb ataladi. Murakkablik P sinfi – bu barcha satirli masalalar bo‘lib, polonomia' vaqt ichida yechilishi mumkin, ya'ni, O(n^k) vaqt ichida yechilishi mumkin, bu yerda k kirishga bog‘liq bo‘lmaydi.Polinomial abstrakt masalasining konsepsiyasini aniqlashni istagan holda, biz turli xil ma'lumotlarni taqdim etish mumkinligiga duch kelamiz. Xar bir taqdim qilingan e to‘plam uchun, I kirishlari bo‘lgan Q abstrakt masalaning satirli masalasini olamiz.Biroq, amalda (asosi 1 bo‘lgan raqamli tizim kabi “qimmat” vakillik usullarini istisno qilsak), tabiiy vakillik usullari odatda ekvivalentdir, chunki ularni bir-biriga ko‘p jihatdan aylantirish mumkin. A polinomial algoritmi mavjud bo‘lsa, f:{0,1}*→{0,1}* funksiyasi polinimial vaqt ichida hisoblab chiqiladi, u har qanday x∈ {0,1}* uchun f(x) natijani beradi.Ixtiyoriy abstrakt masala uchun I to‘plami sharitlarini ko‘rib chiqamiz. I to‘plamning е1 va е2 elementlari polinomial' bog‘langan deyiladi, agar polinomial' vaqtda hisoblash mumkin bo‘lgan ikkita f₁₂(e₁(i)) = e₂(i) va f₂₁(e₂(i)) = e₁(i), i ∈ I funsiyalar mavjud bo‘lsa. Bunday hollarda, polinomial' bog‘langan ikkita elementdan qaysi birini tanlash muhim emas.P, NP, NP-complete (NP-to‘liklik masalalari) sinflar orasidagi munosabatlar, NP-hard (NP-murakkab masalalar), P≠NP va P=NP bo‘lgan xollarda.
NP- tuliklik masalasi — algoritmlar nazariyasida NP – sinfdagi «ha» yoki «yo‘k» javobli masalani shu sinfdagi boshka masalaga polinomial' vakt oralgida moslashtirish mumkin (yani, boshlangich ma'lumotlar xajmiga boglanganlik darajasi ma'lum polinimdan katta bulmagan amallar yordamida bajariladi).
Shunday qilib, NP -to‘liq masalalar, ma'lum ma'noda, NP sinfidagi “tipik” masalalar to‘plamini shakllantiradi: agar ularning ba'zilari uchun "tezkor" yechim algoritmi topilsa, NP sinfidagi har qanday boshqa masalani xuddi shu tarzda hal qilish mumkin.