Algoritmlarni loyihalash” fanidan laboratoriya ishlari

Amliy qism
NP-qiyin - agar X ∈ NP X-ga tushadigan bo'lsa, X muammosi kamida NPda hal qilinadi, masalan NP-ning har bir muammosini hal qilish qiyin (agar P! = NP bo'lsa, unda X P ga tegishli bo'lmaydi).
Reduksiya - A muammoni kiritishlarni ko'paytma vaqt algoritmidan foydalanib, B muammosining ekvivalent kirishiga aylantirish jarayoni. Ekvivalent degani, A va B muammolari kirish va o'zgartirilgan kirish uchun bir xil javobni (Ha yoki Yo'q) berishi kerak. A dan B gacha qisqartirish algoritmining mavjudligi quyidagilarni nazarda tutadi:
1. Agar B ∈ P bo'lsa, u holda A ∈ P (ko'paytmali vaqt ichida A dan B gacha qisqartirishingiz mumkin va B polinomik vaqt ichida echishingiz mumkin. Buni birlashtirish A uchun ko'p vaqtli algoritmni beradi)
2. Agar B ∈ NP bo'lsa, unda A ∈ NP
3. Agar A NP-qattiq bo'lsa, B - NP-qattiq. A ko'paytirilgan vaqt ichida B ga kamayishi mumkin va agar B NP-qiyin bo'lmasa, u B B NP-NP-qiyin va bu A ∈ NP-NP-qattiq, bu farazga zid (A-NP-qiyin) degan ma'noni anglatadi.

• 
  NP-to'liqligi - agar X ∈ NP va X bo'lsa, NP-qiyin bo'lsa, X muammo NP-tugallanadi.
  

Muammo NP-tugaganligini isbotlash

Muammoning to'liqligini isbotlash 2 bosqichni o'z ichiga oladi. Avval biz muammo NPga tegishli ekanligini ko'rsatishimiz kerak va keyin biz buni NP-qiyinligini ko'rsatishimiz kerak. Bosqichlarni quyidagicha izohlash mumkin:
1-qadam - X ∈ NP ni ko'rsatish. X uchun netereterministik algoritmni toping. Ammo amaliy usul, agar potentsial echim taqdim etilsa, X uchun ko'paytmali vaqt tekshiruvini o'tkazishdir.
2-qadam - X-ni ko'rsatish qiyin emas. Ma'lum NP-muammoni X-ga qisqartirish. Demak, biz ko'rgan 3-rasm orqali X bu NP-qiyin ekanligini anglatadi.


Topshiriqlar:

1. 
   NP-tugaganligini isbotlash algoritmini tuzing.
   

Javob
#include
#include
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 satr = 0; satr < m ; satr++)
for(int ustun = 0; ustun < n; ustun++)
{
cout << "a[" << satr << "][" << ustun << "]="; cin >> a[satr][ustun];
}
for(int satr = 0; satr < m; satr++)
{
for(int ustun = 0; ustun < n; ustun++)
cout << a[satr][ustun] << "\t"; cout<<"\n";
}
return 0;
}