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



Download 134,04 Kb.
Pdf ko'rish
Sana02.07.2022
Hajmi134,04 Kb.
#733234
Bog'liq
LABORATORIYA ISHI 25



LABORATORIYA ISHI - 25 
Mavzu: 
NP-to’liq masalalar.
 
Ishdan maqsad. 
NP-to’liq masalalar haqida o’rganish. 
Qo’yilgan masala.
NP-to’liq masalalar tushunchasi. 
Ish tartibi: 

Tajriba ishi nazariy ma’lumotlarini o‘rganish; 

Berilgan topshiriqning algoritmini ishlab chiqish; 

C++ dasturlash muhitida dasturni yaratish; 

Natijalarni tekshirish; 

Hisobotni tayyorlash va topshirish. 
Nazariy qism 
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.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. 
 
Amliy qism 
NP-qiyin - agar X 

NP X-ga tushadigan bo'lsa, X muammosi kamida NPda hal 
qilinadi, masalan NP-ning har bir muammosini hal qilish qiyin (agar P! = NP bo'lsa, 
unda X P ga tegishli bo'lmaydi). 
Reduksiya - A muammoni kiritishlarni ko'paytma vaqt algoritmidan foydalanib, B 
muammosining ekvivalent kirishiga aylantirish jarayoni. Ekvivalent degani, A va B 
muammolari kirish va o'zgartirilgan kirish uchun bir xil javobni (Ha yoki Yo'q) 
berishi kerak. A dan B gacha qisqartirish algoritmining mavjudligi quyidagilarni 
nazarda tutadi: 
1. Agar B 

P bo'lsa, u holda A 

P (ko'paytmali vaqt ichida A dan B gacha 
qisqartirishingiz mumkin va B polinomik vaqt ichida echishingiz mumkin. Buni 
birlashtirish A uchun ko'p vaqtli algoritmni beradi) 
2. Agar B 

NP bo'lsa, unda A 

NP 
3. Agar A NP-qattiq bo'lsa, B - NP-qattiq. A ko'paytirilgan vaqt ichida B ga 
kamayishi mumkin va agar B NP-qiyin bo'lmasa, u B B NP-NP-qiyin va bu A 

NP-
NP-qattiq, bu farazga zid (A-NP-qiyin) degan ma'noni anglatadi. 

NP-to'liqligi - agar X 

NP va X bo'lsa, NP-qiyin bo'lsa, X muammo NP-
tugallanadi. 
Muammo NP-tugaganligini isbotlash 
Muammoning to'liqligini isbotlash 2 bosqichni o'z ichiga oladi. Avval biz 
muammo NPga tegishli ekanligini ko'rsatishimiz kerak va keyin biz buni NP-
qiyinligini ko'rsatishimiz kerak. Bosqichlarni quyidagicha izohlash mumkin: 


1-qadam - X 

NP ni ko'rsatish. X uchun netereterministik algoritmni toping. 
Ammo amaliy usul, agar potentsial echim taqdim etilsa, X uchun ko'paytmali vaqt 
tekshiruvini o'tkazishdir. 
2-qadam - X-ni ko'rsatish qiyin emas. Ma'lum NP-muammoni X-ga 
qisqartirish. Demak, biz ko'rgan 3-rasm orqali X bu NP-qiyin ekanligini anglatadi. 
 
Topshiriqlar: 
1.
NP-tugaganligini isbotlash algoritmini tuzing. 
Nazorat savollari. 
1.
 
NP-tugaganligini isbotlash algoritmini izohlab bering. 
2.
 
Reduksiya qanday amalga oshiriladi. 

Download 134,04 Kb.

Do'stlaringiz bilan baham:




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