Dasturiy injiniring” kafedrasi 108-guruh talabasi Yusupov Umarjonning

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI

TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI

“Dasturiy injiniring” kafedrasi

108-guruh talabasi

Yusupov Umarjonning

“Algoritmlarni loyihalash” fanidan

Mustaqil ish № 11

SAMARQAND-2021

Mustaqil ish topshiriqlari

1. 
   Quyidagi nazariy savollarga javob bering
   

1. 
   NP-to’liq masalalar haqida tushuncha bering
   
2. 
   Xasislik algoritmini tushuntirib bering
   

2. 
   Quyidagi masalalarni xasislik algoritmi boyicha yeching va dastur kodini yozib natija oling.
   

Nazariy qism:

Katta o’lchamdagi zalga kichik gilamlar bilan qoplash kerak. Bizga turli xil o’lchamdagi gilamlar bor. Zalni to’liq qoplash uchun kamida nechta gilam kerak.Zalning o’lchamlari (MxN) va har bir gilamning o’lchamlari (a[i] va b[i]) berilgan. Masalaning algoritmi va dasturini tuzing.

NP-to’liq masalalarda bunday algoritmlar optimal yechimga yaqin bo’lgan natijani olish uchun ishlatilishi mumkin. Аlgоritmlаr nаzаriyasi usullаri quyidаgi vаzifаlаrni bаjаrishgа imkоn bеrаdi:

- Bеrilgаn mаsаlаni еchish аlgоritmlаri to’plаmidаn eng rаsiоnаl аlgоritmni tаnlаsh;
- Murаkkаb mаsаlаlаrni еchish аlgоritmlаrini vаqt jihаtidаn bаhоlаsh;

- Kriptоgrаfik mеtоdlаr uchun muhim bo’lgаn mаsаlа еchimini mа’lum vаqt оrаlig’idа оlib bo’lmаsligini ishоnchli bаhоlаsh;

- Prаktik аnаliz аsоsidа ахbоrоtlаrni qаytа ishlаsh sоhаsidаgi mаsаlаlаrni еchish effеktiv аlgоritmlаrini ishlаb chiqish vа rivоjlаntirish;

Xasislik algoritmi masalalarning aniq yechimini olishda qullaniladi. Bu algoritim optimal yechim bulmasada natija optimal darajada yaqin yechim hisoblanadi. Xasislik algoritmni bir qarashda murakkabdik tuyiladi. Algaritimning ishlash vaqti sekin bulishi mumkin. Dastur aniq yechimni olish uchun bizga birilgan chigaraviy qiymat bilan solishtiradi. Shuning uchun ham bu algoritim ishlashi jihatdan sekin.