Mavzu: p va np sinflar,np-toʻliq masalalar tushunchasi

Muhammad Al-Xorazmiy nomidagi TATU Qarshi filiali TT-11-20 guruh talabasi Normamatov Annamurodning “Algoritmlarni loyihalash” fanidan tayyorlagan 15-Mustaqil ishi.

Mavzu: P va NP sinflar,NP-toʻliq masalalar tushunchasi.

Reja:

1. P va NP sinflar muammosi. 2. NP to’liq masala tushunchasi

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

• 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: -

Tegishli atamalar va ta'riflar: -

Yuqoridagii noaniq bayonotda ishlatiladigan kompyuter so'zi Deterministik Turing Machine (DTM) ga tegishli. Oddiy so'z bilan aytganda, bu faqat bitta keyingi bosqichga o'tishni tanlashi mumkin bo'lgan mashina. 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.