Bajaruvchi: Bekmatov e tekshiruvchi: Axmedov f samarqand-2022 5-mavzu. P, Np, np-to’liq masalalar

1-masala: Saper o’yini. O’yin sharti: n x n o’lchamdagi elementlari 0 va 1 lardan tashkil topgan yopiq matritsa beriladi. Matritsa indekslarini kiritganingizda “0” chiqsa yana urinish bor, agar bir chiqsa yutqazasiz.
Masalaning dasturi:
#include
#include
using namespace std;
int main() {
int n,l;
cout<<"saper o`yini o'lchamini kiriting";
cin>>n; l=n/2.;
bool m[n+2][n+2];
for(int i=0; i<=n+1; i++){
for(int j=0; j<=n+1; j++){
m[i][j] = false;
}
}
srand(time(0));
int x, y;
for(int i=1; i<=l; i++){
do{
x = rand() % n + 1;
y = rand() % n + 1;
}while(m[x][y]);
m[x][y] = true;
}
int xCount = n*n;
while(xCount != 0){
cin >> x >> y;
if(m[y][x]){
cout << "fail" << endl;
goto L1;
}xCount--;cout<<"0"<
if (xCount == 0){cout << "win" << endl;}
L1: cout<<" ";for(int i=1; i<=n; i++)cout<
for(int i=1; i<=n; i++){cout<<" "<
for(int j=1; j<=n; j++){
cout << m[i][j]<<" ";
}
cout << endl;
}
return 0;
}



Mavzu: NP- To’liq masalalarga keltirish usullari.
Ishning maqsadi:NP sinfdagi masalalarni P sinfdagi masalalarga keltirish algoritmlarini ko’rib chiqish
Kerakli jihozlar: Kompyuter, proyektor, doska, C++ dasturlash tili
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 bajarilishmasalasi
  
• 
  “O’n beshlik” o'yinining eng qisqa yechimi
  
• 
  Kommivoyajer masalasi
  
• 
  Shteyner masalasi
  
• 
  Grafni bo'yash masalasi
  
• 
  Graf cho’qqisini qoplash masalasi
  
• 
  To’plamni qoplash masalasi
  
• 
  Graf cho’qqilarining mustaqil to’plamlari masalasi
  
• 
  Sapper o’yini
  
• 
  Tetris o’yini
  

Синфларга ажратиш
1. P-масалалар
2. NP-масалалар
3. NP-тулик масалалар
4. EXPTIME синфи
5. EXPTIME-тулик масалалар синфи

NP to'liq masalalarni hal qilish uchun evrestik algoritmlar
Evristika yoki evristik algoritm – algoritm deb ta’riflanishi uchun quyidagi xususiyatlarga ega bo’lishi kerak:
1. U odatda shartli ravishda optimal bo’lmasa ham, yaxshi yechimlarni topish kerak.
2. Uni ixtiyoriy ma’lum aniq algoritmdan ko’ra, amalga oshirish tezroq va soddaroq bo’lishi kerak.
Odatda yahshi algoritmlar evristik bo’lib chiqadi. Faraz qilaylik, biz tez ishlaydigan va barcha test topshiriqlariga javob beradigan algoritmni tuzdik, lekin uning to’g’riligini isbotlab bilmaymiz. Shundayisbotberilmaguncha, algoritm evristik deb tushuniladi.
NP-тулик масалаларни ечишга ёндошув

• 
  NP-тулик масалалар синфини ечишга ёндошувни иккита категорияга булиш мумкин.
  
• 
  Birinchi toifaga sanab o'tish miqdorini iloji boricha kamaytirishga harakat qilingan yondashuvlar kiradi, ammo bu eksponent ish vaqti muqarrarligini ham tan oladi.
  
• 
  Qo'pol kuchni kamaytirishning eng ko'p qo'llaniladigan usullari bu shoxlangan va bog'langan usulga yoki yashirin qo'pol kuch usuliga asoslangan.Ushbu texnikalar qidiruv daraxti ko'rinishidagi "qisman echimlar" ni qurish va istiqbolsiz qisman echimlarni aniqlash uchun kuchli baholash usullaridan foydalanishdan iborat bo'lib, natijada qidiruv daraxtidan bir qadamda butun filial kesiladi.
  
• 
  NP-тулик масалаларга мисол
  
• 
  Коммивояжёр масаласи
  
• 
  Графни буяш масаласи ва х.к.