Toshkent 2023 Mavzu: p va np sinflar, np- to‘liq masalalar tushunchasi Reja: p va np sinflarining tengligi muammosi
Download 77.93 Kb.
|
TbtvQebW9FC7EKvLUEbZ1X1jXdOoaSJ4
- Bu sahifa navigatsiya:
- Toshkent 2023 Mavzu
- P va NP sinflarining tengligi muammosi.
- NPC klassi (NP - toliq topshiriqlar)
|
O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
Fan: Algoritmlarni loyihalash Bajardi: 0111-21 guruh talabasi Karimov M Toshkent 2023 Mavzu: P va NP sinflar, NP- to‘liq masalalar tushunchasi Reja: 1. P va NP sinflarining tengligi muammosi. 2. NP – to’liq masalalarni yechish usullarining tasnifi 3. NP to'liq masalalarni hal qilish uchun evrestik algoritmlar P va NP sinflarining tengligi muammosi. Determetik Turing mashinasi aniqlanmagan bosqich Turing mashinasining alohida holati sifatida ko'rib chiqilishi mumkin va unda taxmin qilish bosqichi mavjud emas va tekshirish bosqichi DMT ga to'g'ri kelganligi sababli, NP klassi P sinfini o'z ichiga oladi, shuningdek ularni hal qilish uchun faqat o'lchovga eksperimental ravishda bog'liq bo'lgan algoritmlar ma'lum. kiritish (ya'ni katta kirish uchun samarasiz). Ushbu ikki sinfning tengligi masalasi nazariy informatika sohasidagi eng qiyin ochiq muammolardan biri hisoblanadi. Bugungi kunga kelib, ushbu sinflarning (P = NP) mos kelishi va ularning mos kelmasligi to'g'risida nazariy dalillar mavjud emas. Gap shundaki, P klassi NP sinfining tegishli to'plami, ya'ni. NP \ P bo'sh emas. NPC klassi (NP - to'liq topshiriqlar) NPC (NP-complete) yoki NP-tugallangan vazifalar sinfining ta'rifi quyidagi ikkita shartni talab qiladi: birinchidan, vazifa NP sinfiga tegishli bo'lishi kerak, ikkinchidan, NP sinfidan barcha vazifalar unga ko'paytirilishi kerak. NRS sinfi uchun quyidagi teorema isbotlandi: agar [URS polinomial echim algoritmi mavjud bo'lgan URS] sinfiga tegishli muammo bo'lsa, u holda P klassi NP klassiga to'g'ri keladi, ya'ni. P = NP Hozirgi vaqtda yuzlab NP bilan bog'liq to'liq muammolar mavjudligi isbotlangan, ammo hozirgacha ularning hech biriga polinomial echim algoritmi topilmadi. Hozirgi vaqtda tadqiqotchilar quyidagi sinf nisbatlarini taklif qilmoqdalar: Download 77.93 Kb. Do'stlaringiz bilan baham: 
|