Guru Mamatxalilov Subxonjon 2-Amaliy mashg’uloti. Mavzu: Hisoblash murakkabligi. Ishdan maqsad

615-17-23 guru

Mamatxalilov Subxonjon

2-Amaliy mashg’uloti.

Mavzu: Hisoblash murakkabligi.

Ishdan maqsad: Masalalarni yechishning hisoblash murakkabligini о‘rganish. Ushbu jarayonni о‘yinlar yaratishda qо‘llashni kо‘rib chiqish.

Uslubiy kо‘rsatmalar: Hisoblash murakkabligi – bir qancha algoritmlarni bajaruvchi ish hajmiga bog‘liq funksiylarni belgilydigan informatika va algoritm nazariyasidagi tushuncha. Hisoblash murakkabligini о‘rganish bо‘limi hisoblash nazariyasi deb nomlanadi. Uning ish hajmi odatda hisoblash resursi deb nomlanuvchi fazo va vaqt abstract tushunchasi bilan о‘lchanadi. Unga sarflanuvchi vaqt masalani yechish uchun zarur bо‘lgan elementar qadamlar soni bilan aniqlanadi. Bunday holda, “kirish hajmiga bog‘liq xotira bandligining hajmini va bajarish vaqtini qanday о‘zgartirish kerak” degan algoritmlarni ishlab chiqish savoliga javob beramiz. Kirish hajmi ostida bitlarda berilgan vazifalarning tavsifi uzunligi, chiqish hajmi ostida esa – masalani yechishning tavsifi uzunligi tushuniladi.

Murakkablik sinflari. Murakkablik sinflari – bu mavjud hisoblash murakkabligi bо‘yicha о‘xshash algoritmlar yechimini tanishning kо‘p sonli vazifasidir. Bunda ikkita muhim sinf mavjud: P sinfi. P sinfi “tez” hisoblanuvchi barcha yechimlar, muammolarni aralashtirib yuboradi. Bu graf kabilar bilan bо‘gliqlikni aniqlovchi massivdan elementlarni qidirish va saralashga olib boradi.

NP sinfi. NP sinfi kiruvchi ma’lumotlar hajmiga bog‘liq polynomial qadamlar sonini yechuvchi determinirlanmagan Tyuring mashinasi vazifalarini о‘z ichiga oladi. Ularning yechimi polynomial qadamlar soni uchun determinirlangan Tyuring mashinasi yordamida tekshirilishi mumkin. Shuni aytish kerakki, determinirlanmagan Tyuring mashinasi faqat о‘sh vaqtdagi chegaralangan xotirali determinirlangan Tyuring mashinasiga mos keluvchi zamonaviy kompyuterlarga о‘xshash bо‘lgan abstract modeldir. NP sinfi о‘z ichiga P sinfini hamda kirish hajmiga eksponensial bog‘liq faqat ma’lum bо‘lgan algoritmlarni yechishning bir qancha muammolarini о‘z ichiga oladi. NP sinfiga komivoyajer masalasi, bul formulalarini bajarish masalasi, faktorizatsiya masalasi va boshqa shu kabi masalalari kiradi.

NP va P sinflari tengligi muammosi. Bu ikki sinf tengligi haqidagi savol nazariy informatikadagi eng ochiq muammolardan biri hisoblanadi. Kley matematika instituti bu muammoni ming yillik muammolar rо‘yxatiga kiritgan va bu muammo yechimi uchun 1 million AQSH dollari miqdorida mukofot e’lon qilgan.