Algoritimlarni loyihalash fani bo`yicha
Mustaqil ish
Mavzu: p va np sinflari. Np to’liq
masala tushunchasi
Variant: 15
Guruh: 653-20
Bajardi: Nazirov Otabek
Reja:
1.
P va NP sinflar muammosi.
2.
Muammo
NP-tugaganligini isbotlash
3.
NP to’liq masala tushunchasi
P
va NP muammosi
Har bir informatika talabasi P va NP muammolari haqida eshitishi kerak. Aytish
mumkinki, bu kompyuter fanidagi eng mashhur echimsiz muammo. Clay Matematika
Instituti tomonidan tanlangan 7 ming yillik
mukofot muammosidan biri
, birinchi to'g'ri
echim uchun 1 million dollar mukofotni olib yurish va hozir ham ochiq. P = NP
muammosini
isbotlash yoki
echish
informatika,
matematika
,
kriptografiya,
AI,
multimedia ishlov berish
, iqtisodiyot va boshqa sohalarda chuqur ta'sir ko'rsatishi
mumkin. Ushbu muammo noaniq tarzda aytilishi mumkin
"Kompyuter tomonidan tezda tekshirilishi mumkin bo'lgan har qanday muammoni
kompyuter ham tezda hal qiladimi?".
Garchi bu masalaning mavjudligi 1950-yillarda Jon Nesh va Kurt Godel tomonidan
muhokama qilingan bo'lsa-da, ushbu muammoni 1971 yilda Stefan Kuk o'zining
mashhur "Teoremalarni tayyorlash protseduralarining murakkabligi" nomli maqolasida
rasmiy ravishda kiritgan. Rasmiy bayonotga va muammoni tushuntirishga sho'ng'ishdan
oldin, avval mavzu bilan bog'liq ba'zi ta'riflarni ko'rib chiqamiz.
Tegishli atamalar va ta'riflar: -
•
Yuqoridagi noaniq bayonotda ishlatiladigan kompyuter so'zi Deterministik Turing
Machine (DTM) ga tegishli. Oddiy so'z
bilan aytganda
, bu faqat bitta keying
bosqichga o'tishni tanlashi mumkin bo'lgan mashina. Dallanmagan mashina [3].
Har bir mavjud kompyuter shunday ishlaydi.
•
Polinom - ba'zi kuchlarga va ularning koeffitsientlariga ko'tarilgan
o'zgaruvchilardan tashkil topgan ibora.
Masalan, ax² + bx + c shaklidagi ikkinchi
darajali ko'paytma.
•
Algoritm vaqt murakkabligi - kirishning uzunligi funktsiyasi sifatida bajarilishi
uchun algoritm olgan vaqt. Katta O belgi yordamida umumiy ifodalanadi.
Masalan, 2n o'lchamdagi barcha elementlarni birma-bir bosib chiqarish
uchun
algoritm yozsak
, uning vaqt murakkabligi O (n) bo'ladi.
•
Polinomial vaqt murakkabligi - algoritmning vaqt murakkabligi n ^ {O (1)}
•
P = Deterministik Turing mashinasi tomonidan ko'paytirilgan vaqt ichida
echiladigan muammolar to'plami.
•
NP = noaniq bo'lmagan polinomik vaqt ichida yechilishi mumkin bo'lgan echimlar
muammolarining to'plami (javob ha yoki yo'q) i.e ko'p bo'lmagan vaqt ichida
noaniqsiz Turing Machine [4] tomonidan hal qilinishi mumkin.
•
Nondeterministic Turing Machine (NTM) - dallanadigan mashina. Agar
hisoblashning keyingi bosqichi uchun ko'plab imkoniyatlar mavjud bo'lsa, ushbu
mashina ularning barchasini bir vaqtning o'zida o'chirib qo'yishi mumkin. NTM-lar
O (1) vaqtda ko'p variantlardan to'g'ri variantni taxmin qilishga qodir.
NPga alternativ ta'rif bu mumkin bo'lgan
echim taqdim etilsa
, DTM polinomik vaqt ichida
uning to'g'riligini tekshirishga imkon beradigan qarorlar to'plamidir. Shuni ta'kidlash
kerakki, barcha
P muammolar NP ga ham tegishli
, chunki agar muammo DTM
tomonidan ko'p
martali hal qilinsa
, mumkin bo'lgan echimni tekshirish hal qilishdan
osonroq bo'ladi.
Shunday qilib
, DTM ham ko'plik vaqt ichida ham tekshirishi mumkin
edi. Shunday qilib, arzimas, P
⊆
NP i.e P NP ning pastki qismi.
Bugungi kunda mavjud bo'lgan barcha kompyuterlar DTM va NTM fikrlash tajribalarida
ishlatiladigan sof nazariy kompyuter ekanligini bilish ham muhimdir. Professor Erik
Demain
aytganidek
[1].
"Demak, bu (NTM) ancha kuchli model. Albatta, bunday ishlaydigan kompyuterlar yo'q,
afsuski, men ko'proq qiziqayapman ”.
Do'stlaringiz bilan baham: |