Algoritmlarni loyihalash” fanidan laboratoriya ishlari

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
Topshiriqlar:

1. 
   NP-tugaganligini isbotlash algoritmini tuzing.
   

Javob
#include
#include
void matrix_print(int a[10][10], int m, int n)
{
// matritsani jadval shaklida chiqarish
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
cout << a[i][j] << "\t";
}
cout << "\n";
}
}
int satr_max(int a[], int n)
{
// massivning eng katta elementini aniqlash
int max = a[0];
for (int i = 1; i < n; i++)
if (max < a[i]) max = a[i];
return max;
}
int main()
{
int m, n, a[10][10];
cout << "Satrlar sonini kiriting \nm="; cin >> m;
cout << "Ustunlar sonini kiriting \nn="; cin >> n;
cout <<"Massiv elementlarini kiriting \n";
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
cin >> a[i][j];
cout << "Kiritilgan matritsa\n";
//funksiyaga matritsa, satrlar va ustunlar soni jo'natiladi
matrix_print(a, m, n);
for (int i = 0; i < m; i++)
{
// funksiyaga i-satrning 0-elementi adresini
// va elementlar sonini jo'natamiz
cout << i << "-satrning eng kattasi=" <<
satr_max(&a[i][0], n);
cout << endl;
}
return 0;
}
Nazorat savollari.

1. 
   NP-tugaganligini isbotlash algoritmini izohlab bering.
   
2. 
   NP-to‘liqlik masala qanday ishlaydi.