Fan nomi algoritmlarni loyihalash hafta

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI


Dasturiy injiniring kafedrasi

LABORATORIYA MASHG’ULOTI

FAN NOMI		Algoritmlarni loyihalash
HAFTA		13
MAVZU:		NP- To’liq masalalar
ISHDAN MAQSAD:		NP TO’LIQ MASALASI NP to’liq masalalari haqida tushuncha; NP to’liq masalalariga kiruvchi saper o’yini masalasi va yechimi;

NP- to`liq masalalarini yechish usullarini keltiring?

NP – to’liq masalalarni yechish usullarining tasnifi
Ko'p qiziqarli va amaliy masalalarni polynomial vaqtda hal qilish mumkin emas yoki ular uchun hozirgi vaqtda polinomial algoritmlar topilmagan. NP(Nondeterminictic Polinomial) murakkablik sinfidagi masala - bu shunday masalalar sinfidirki, ularni yechish uchun polinomial algoritm mavjud bo'lmasligi mumkin, lekin agar biz uning yechimini bilsak (masalan, biz buni taxminan topgan bo’lsak), unda polinominal vaqt ichida uning to'g'riligini tekshirish mumkin.
NP-to'liq masalalarning namunalari:\

• 
  Bool formulalarining bajarilish masalasi
  
• 
  “O’n beshlik” o'yinining eng qisqa yechimi
  
• 
  Kommivoyajer masalasi
  
• 
  Shteyner muammosi
  
• 
  Grafni bo'yash muammosi
  
• 
  Graf cho’qqisini qoplash masalasi
  
• 
  To’plamni qoplash masalasi
  
• 
  Graf cho’qqilarining mustaqil to’plamlari masalasi
  
• 
  Saper o’yini
  
• 
  Tetris o’yini
  

NP-murakkab masalalarni hal qilish usullari quyidagilarga bo'linadi:

• 
  aniq,
  
• 
  evristik
  
• 
  metaevristik usullari