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

LABORATORIYA ISHI - 26
Mavzu: NP-to’liq masalalarga keltirish usullari.
Ishdan maqsad. NP-to’liq masalalarga keltirish usullarini o’rganish.
Qo’yilgan masala. NP-to’liq masalalarga keltirish usullari.
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
Agar masalaning qisim masalalari mavjud bo‘lsa u kuchli NP-to‘liq masala deyiladi, bunda: Masalaning raqamli parametrlari mavjud bo‘lmasa (ya'ni, bu masalada uchraydigan kattaliklarning maksimal' qiymati polinom uzunligi bilan yuqoridan chegaralangan).
Masalaning raqamli parametrlari mavjud bo‘lmasa (ya'ni, bu masalada uchraydigan kattaliklarning maksimal' qiymati polinom uzunligi bilan yuqoridan chegaralangan).
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.


Amaliy qism

NP-to‘liqlik masala.

Bunday vazifalar sinfi NPCS deb nomlanadi. Agar P ≠ NP gipotezasi to‘g‘ri bo‘lsa, unda NPCS masalasi uchun soxtaopolinomial algoritm mavjud emas.

NP-to‘liqlik masalaga misollar

Bul' formulalari bajarilishi masalasi
"Dog‘lar" n × n o‘lchamining eng qisqa yechimi
Kommivoyajyora masalasi
Shteyner muammosi
Grafani bo‘yash masalasi
Soxa (yuza) qoplamasi masalasi
To‘plamni qoplash masalasi
Tanlash masalasi
To‘plamning mustaqilligi masalasi
Saper (o‘yin)
Tetris