Texnalogiyalari universiteti 030-20 guruh talabasi Xayridinov Vohidjonning
Download 260.28 Kb. Pdf ko'rish
|
Мустакил иш
|
NP-to’liqlik masalasi
Amaliy nuqtai nazardan qiziq bo‘lgan vazifalarning aksariyati, polinomial' (polinomial' vaqt mobaynida ishlovchi) algoritmlar. Ya'ni, n uzunlikdagi kirishda algoritmning ishlash vaqti doimiy k (kirish uzunligidan mustaqil) uchun O(nk) dan oshmaydi. Har bir masalada ushbu xususiyatni qondiradigan yechim algoritmi mavjud emas. Ba'zi masalalarni umuman biron bir algoritm yordamida hal qilib bo‘lmaydi. Bunday masalaning klassik misoli bu “to‘xtash muammosi” (berilgan dastur berilgan kirishda to‘xtashini bilish). Bundan tashqari, ularni hal qiladigan algoritm mavjud bo‘lgan masalalar mavjud, har qanday bunday algoritm uzoq vaqt ishlaydi – uning ishlash vaqti har qanday fiksirlangan k soni uchun O(nk) bo‘la olmadi. Agar biz amaliy algoritmlar va faqat nazariy qiziqish algoritmlari o‘rtasida qo‘pol, ammo rasmiy chegara chizishni istasak, unda ko‘plikli vaqt ichida ishlaydigan algoritmlar sinfi birinchi o‘rinda turadi. NP -to‘liq deb nomlangan masalalar sinfini ko‘rib chiqamiz. Ushbu masalalar uchun hech qanday polinomial' algoritmlar topilmagan, ammo bunday algoritmlar mavjud emasligi isbotlanmadi. NP bilan bog‘liq muammolarni o‘rganish “P = NP” deb nomlangan savol bilan bog‘liq. Bu savol 1971 yilda berilgan va hozirda hisoblash nazariyasida eng qiyin masalalardan biri hisoblanadi. Nima uchun dasturchi NP – tugallangan masalalar haqida bilishi kerak? Agar biron bir NP – to‘liqlik uchun uning to‘liqligini isbotlash mumkin bo‘lsa, uni deyarli hal qilib bo‘lmaydi deb hisoblash uchun asos bor. Bunday holda, uni aniq hal qiladigan tezkor algoritmni qidirishni davom ettirishdan ko‘ra, taxminiy algoritmni tuzishga vaqt sarflash yaxshiroqdir. Polinom vaqti. Abstrakt masalalar Yuqorida aytib o‘tilganidek, ko‘p jihatdan hal qilinadigan (polinomial) masalalar konsepsiyasi amalda yechilishi mumkin bo‘lgan masalalar g‘oyasini takomillashtirish hisoblanadi. Ushbu kelishuvni nima tushuntiradi? Birinchidan, amalda ishlatiladigan ko‘paytirilgan algoritmlar, odatda juda tez ishlaydi. Ikkinchidan, polinomial algoritmlar sinfini ko‘rib chiqish, bu sinfning hajmi ma'lum bir hisoblash modelini tanlashdan deyarli mustaqil bo‘lishidir. Masalan, tasodifiy tasodifiy kirish mashinasida (RAM) ko‘paytirilgan vaqt ichida yechilishi mumkin bo‘lgan masalalar sinfi T'yuring mashinalarida polinomal yechiladigan masalalar sinfiga to‘g‘ri keladi. Sinf parallel hisoblash modeli uchun bir xil bo‘ladi, prosessorlar soni, kirish uzunligi polinomi bilan cheklangan. Uchinchidan, polinomal yechiladigan masalalar sinfi tabiiy yopiqlik xususiyatlariga ega. Masalan, ikkita algoritmning tarkibikompozisiyasi ham polinomial vaqtli ishlaydi. Buning sababi, ko‘pxadlarning yig‘indisi, ko‘paytmasi va kompozisiyasi ko‘pxadrdir. Quyida hisoblash masalasining abstrakt modelini keltirilgan. Buni abstrakt masala deb nomlaymiz, Q – ikkita to‘plam elementlari orasidagi ixtiyoriy binar munosabat: I – shartlar to‘plami va S – yechimlar to‘plami. Masalan, G=(V,E) yo‘naltirilmagan grafning berilgan ikkita uchlari orasidagi eng qisqa yo‘lni topish masalasida, shart (element I) uch element, graf va ikkita qirradan iborat va yechim (S element) – bu grafda kerakli yo‘lni tashkil etuvchi vertikallarning ketma-ketligi. NP to‘liqligi nazariyasida faqat hal qilish masalalari ko‘rib chiqiladi – muayyan savolga “ha” yoki “yo‘q” deb javob berish kerak bo‘lgan masalalar. Rasman, I to‘plam shartlarini {0,1} to‘plamga to‘g‘ri keladigan funksiya sifatida ko‘rib chiqilishi mumkin. Masalan, G=(V,E) grafdagi eng qisqa yo‘lni topish masalasi bilan berilgan G=(V,E) graf yordamida ikkita tugun u, v∈V va natural k butun sonlar u va v tugunlari orasida undan katta bo‘lmagan hamda G grafda yo‘l bor yoki yo‘qligi masalasini yeching. 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(nk) 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 f12(e1(i)) = e2(i) va f21(e2(i)) = e1(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. Formal' ta'rif Alifbo deganda har qanday cheklangan belgilar to‘plami tushuniladi (masalan, {0, 1} yoki {a, b, c}). Ixtiyoriy ∑ alifbosidan tuzilgan barcha so‘zlar to‘plami (yozilgan satirlar, ushbu alifboning belgilaridan tashkil topadi) ∑* bilan belgilanadi. ∑ alfavit yordamida yaratilgan ixtiyoriy L tili bu ∑^* to‘plamning L to‘plam ostisi, ya'ni L⸦∑^*. L uchun tanib olish vazifasi berilgan so‘z L tiliga tegishli yoki yo‘qligini aniqlashdir. ∑ alifbo ustida va - ikkita til bo‘lsin. tiliga (Karp bo‘yicha) L2 tiliga qisqartirish deyiladi, agar funksiyasi mavjud bo‘lsa, bu funksiyani polinomial' vaqt bilan hisoblash mumkin bo‘lsa, quyidagi xususiyatga yega: : x ∈ L1, , agar va faqat agar . Karp bo‘yicha qisqartirish L1≤pL2 bilan belgilanadi. Agar NP-dan biron bir til unga qisqartirilsa, tili NP-to‘liq deb nomlanadi. Til NP-mukammal deb nomlanadi, agar u NP-qiyin bo‘lsa va shu bilan birga o‘zi NP sinfida bo‘lsa. A masala B masalasiga qisqartirilganligi, A masala B masalasidan ko‘ra “murakkabroq” ekanligini anglatadi (chunki agar biz B masalani yechilishi, A masalanini ham yechilishini bildiradi). Shunday qilib, NP bilan bog‘liq qiyinchiliklar sinfga NP bilan bog‘liq masalalar va ular uchun "ancha qiyin" bo‘lgan masalalar kiradi (ya'ni NP bilan bog‘liq masalalarni kamaytirish mumkin bo‘lgan masalalar). NP sinf NP to‘liq masalalarni va ulardan "osonroq" bo‘lgan masalalarni o‘z ichiga oladi (ya'ni, NP-to‘liq masalalarga qisqartirishgan masalalar). Ta'rifdan shunday xulosa kelib chiqadiki, agar NP-to‘liq masalasi polinomial' vaqtda hal qiladigan algoritm topilsa, unda barcha NP-to‘liq masalalar P sinfga joylashtiriladi, ya'ni ular polinomial' vaqtda yechiladi. Download 260.28 Kb. Do'stlaringiz bilan baham: 
|