Laboratoriya mashg’ulotlari mavzulari

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI FARG’ONA FILIALI 642-20 GURUH TALABASI
ABDURAXMONOV SHOHRUXNING
“ALGORITMLARNI LOYIHALASH” FANIDAN

25-30 LABARATORIYA ISHI.

Qabul qildi: Abdulxamidov A.

LABORATORIYA MASHG’ULOTLARI MAVZULARI

1. 
   NP-to’liq masalalar.
   
2. 
   NP-to’liq masalalarga keltirish usullari.
   
3. 
   Graf erkin uchlarini ajratish masalasi.
   
4. 
   Kommivoyajer haqidagi masala
   
5. 
   Qatorlar yig’indisini hisoblash.
   
6. 
   To’plam ostilari yig’indisini hisoblash
   

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.