|
1-Mustaqil ish Fan: Algoritmlarni loyihalash Fakultet: kif guruh: 410-22 Bajardi: Vohobjonov Zavqiddin Mavzu: np to‘liq masalalar. Hisoblashda yechilmaslik hollari np-to'liq muammolarga kirish
|
| bet | 1/8 | | Sana | 18.05.2024 | | Hajmi | 39,79 Kb. | | #243274 |
Bog'liq Zavqiddin AL-M1
O‘zbekiston respublikasi raqamli texnologiyalar vazirligi
Muhammad al-Xorazmiy nomidagi Toshkent axborot texnologiyalari universiteti Nurafshon filliali
1-Mustaqil ish
Fan: Algoritmlarni loyihalash
Fakultet: KIF
Guruh: 410-22
Bajardi: Vohobjonov Zavqiddin
Mavzu: NP - to‘liq masalalar. Hisoblashda yechilmaslik hollari
NP-to'liq muammolarga kirish
NP-to'liqlik tushunchasi hisoblash murakkabligi nazariyasi sohasidagi asosiy mavzudir. NP-to'liq muammolar echilishi eng qiyin bo'lgan hisoblash muammolari sinfini ifodalaydi, chunki ular oqilona vaqt ichida yechim topa oladigan samarali algoritmlarga ega emas deb hisoblashadi. Bu muammolar katta nazariy va amaliy ahamiyatga ega, chunki ular nafaqat hisoblash haqidagi tushunchamiz chegaralarini kengaytiribgina qolmay, balki logistika va rejalashtirishdan tortib kriptografiya va sun'iy intellektgacha bo'lgan turli sohalarda ham keng qamrovli ta'sirga ega.
NP-to'liq muammolarning ta'rifi
NP-to'liq muammolar - bu echilishi eng qiyin bo'lgan hisoblash muammolari sinfidir. Ular NP murakkablik sinfiga tegishli bo'lib, "nodeterministik polinom vaqt" degan ma'noni anglatadi. Bu shuni anglatadiki, NP-to'liq muammoning har qanday yechimi uchun uni to'g'ri deb tezda tekshirish mumkin, ammo bu yechimni topish uchun zarur bo'lgan vaqt muammoning o'lchamiga qarab eksponent ravishda o'sishi mumkin. Boshqacha qilib aytganda, bugungi kunda mavjud bo'lgan eng kuchli kompyuterlar bilan ham NP-to'liq muammolarni oqilona vaqt ichida hal qila oladigan ma'lum samarali algoritm yo'q.
"NP-to'liq" atamasi 1972 yilda matematik Richard Karp tomonidan kiritilgan bo'lib, u bir nechta muhim muammolar, masalan, sayohatchi sotuvchi muammosi va sumka muammosi bu sinf vakillari ekanligini ko'rsatdi. NP-to'liq muammolar shunday xususiyatga egaki, agar ulardan birontasini samarali hal qilish mumkin bo'lsa, NP sinfidagi barcha muammolarni ham samarali hal qilish mumkin. Bu shuni anglatadiki, NP-to'liq muammolar, ma'lum ma'noda, NPdagi "eng qiyin" muammolardir, chunki ular hozirda duch kelayotgan eng qiyin hisoblash muammolarini ifodalaydi.
Muammoning NP-to'liq yoki yo'qligini aniqlash murakkab va qiyin vazifadir, chunki bu muammo NPda ham ekanligini va hech bo'lmaganda NPdagi eng qiyin muammolar kabi qiyin ekanligini isbotlashni talab qiladi. Bu butun dunyo bo'ylab kompyuter olimlari va matematiklarining e'tiborini jalb qilishda davom etayotgan ko'plab ochiq savollar va hal qilinmagan muammolarga ega bo'lgan hisoblash murakkabligi nazariyasi bo'yicha boy tadqiqotlar maydoniga olib keldi.
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
1-Mustaqil ish Fan: Algoritmlarni loyihalash Fakultet: kif guruh: 410-22 Bajardi: Vohobjonov Zavqiddin Mavzu: np to‘liq masalalar. Hisoblashda yechilmaslik hollari np-to'liq muammolarga kirish
|
