Mavzu: p va np sinflari. Np to’liq masala tushunchasi



Download 147,84 Kb.
Pdf ko'rish
bet1/3
Sana01.07.2022
Hajmi147,84 Kb.
#727850
  1   2   3
Bog'liq
1-deadline.(Mustaqil ish)Al.loyihalash.Maruzadan



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

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 ”.

Download 147,84 Kb.

Do'stlaringiz bilan baham:
  1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish