1. Ma’ruza Mavzu: Algoritmlarni loyihalashga kirish. Algoritmlarni vaqt va hajm bo ‘yicha baholash. Ko‘phadlar qiymatlarini hisoblashda Gorner sxemasi

Download 71,41 Kb.
bet	2/2
Sana	21.05.2024
Hajmi	71,41 Kb.
	#249018

1 2

Bog'liq
1. Ma\'ruza

Yo`q
ha

p=(a+b+c)/2

Chiqarish S

A7

tamom

Sxema va blok sxema strukturasi о`quvchilarga informatika kursidan ma’lum. Biz keyinchalik ham algoritmlarni aynan shunday shaklidan foydalanamiz. Bunday yondoshuvda algoritm g`oyasi va negizini mantiqan tassavur qilish, hamda bu shakldan algoritmlash tillaridan birortasiga о`tish osonlashadi.

Mustaqil vazifa sifatida kvadrat tenglama diskriminantni mumkin bо`lgan qiymatlarini hisobga olib, uni yechishning blok-sxemasini tuzing va shunga mos ravishda keltiriladigan javobni shakillantiring.

Hisoblash mashinalarining yaratilishi texnik taraqqiyotning zarur qadami bо`lib, katta hajmdagi hisob-kitobni talab qiladigan masalalar sinfi paydo bо`lishi bilan bog`liqdir. Hisoblash mashinalarining paydo bо`lishi о`z navbatida hisoblash mashinalarini boshqarish uchun ma’lum kо`rsatmalarni tuzish muammosini keltirib chikardi. Shunday qilib, HM uchun algoritmlarni loyixalash va bu algoritmlarga mos ravishda dasturlar tuzish zaruriyati vujudga keldi. Zamonaviy kompyuterlarni tezkorligiga qaramasdan, kundan kunga katta hajmdagi hisob-kitob talab qiluvchi shunday yangidan-yangi masalalar vujudga kelayaptiki, ularni yechish uchun zamonaviy kompyuterlar xotiralari ham yetmayapti. Kurs davomida biz bir necha bor bunday masalalarga e’tibor qaratamiz.
Mutaxasislarga yaxshi ma’lum bо`lgan, shaxmatga bogliq yana bir misolni keltiramiz: ot bilan surish qoidasi bо`yicha amalga oshiriladigan A₁katakdan boshlanuvchi va barcha kataklar bо`ylab bir marotabadan о`tib A₁katakka qaytib keluvchi marshrutni aniqlang.
Agar bu masalani graflar nazariyasi terminlaridan foydalanib ifodalasak, uchlari shaxmat taxtasi kataklarida joylashgan, qirralari esa ot surish qoidasi bо`yicha xarakatlanuvchi shaxmat figurasi bosib о`tgan kataklarni tutashtiruvchi chiziqlar bо`lgan, Gamilton grafi xosil bо`ladi.
_Bu yerda marshrutlarni mavjud variantlari soni _formula_yordamida_hisoblanadi.
_{Kо`rinishidan oddiy bо`lgan}_misolda_ham_biz_juda_kо`p_{variantlarga duch}kelayapmiz. Agar bunday grafda har bir qirra ma’lum о`tish narhiga ega bо`lsa va biz mavjud marshrutlardan narhi bо`yicha eng arzon marshrut tanlashimiz kerak bо`lsa, bunday masalani xatto zamonaviy tezkor kompyuterlar ham yecha olmaydi. Shu bilan birga marshrutlarni о`zaro solishtirish uchun kompyuter xotirasida har bir marshrut haqida axborot saqlashimiz kerak, bunday ma’lumotni saqlash uchun shunday katta xotira hajmi kerak bо`ladiki, bu hajmdagi ma’lumot uchun zamonaviy kompyuter xotirasi yetarli emas. Shuning uchun algoritmlarni loyixalashda biz ularni hisoblash hajmi buyicha hamda tuzilgan algoritmni realizatsiya qilish uchun hotira hajmi bо`yicha ham baholashimiz kerak. Keyinchalik har bir taklif qilingan algoritmni aynan shu kо`rsatkich bо`yicha baholaymiz.
Keltirilgan yondoshuvni tasavvur etish uchun biror nuqtada kо`pxad qiymatini hisoblash jarayonini kо`raylik. Buning uchun zarur bо`lgan amallar sonini aniqlaymiz.
Birinchi yondoshuv – tо`g`ridan tо`g`ri yondoshuv bо`lib, unda arifmetik amallar ketma-ket hisoblanadi. Har bir qо`shiluvchi uchun kо`paytirishlar soni mos ravishda: Qо`shishlar soni esa Hammasi bо`lib ta amal bajariladi.
Ikkinchi yondoshuv – Gorner sxemasi bо`yicha hisoblash bо`lib, unda kо`phad kо`rinishda bо`ladi. Bu yerda zarur amallar soni: ta kо`paytiruv va ta qо`shishdan iborat. Ikkichi yondoshuv samaradorligi kо`rinib turibti.
Ma’lum bir masala algoritmini loyihalashga о`tishdan oldin, masala korrekt qо`yilganiga ishonch xosil qilishimiz kerak. Ya’ni, birinchidan masala yechimi mavjudligi, ikkinchidan esa, agar biror qо`shimchalar bо`lmasa, yechim yagonaligi. Buning uchun mavjudlik va yagonalikni ta’minlovchi barcha shartlar bо`lishi zarur. Tasavvur qilish uchun quyidagi misolni kо`raylik: 133 000 sо`m pulga narxlari 5 000, 11 000 va 18 000 sо`mdan bо`lgan 10 ta daftar sotib olish kerak. Har bir tur daftarni sonini aniqlang.
Yechim. Narxlari 5 000,11 000 va 18 000 sо`m bо`lgan daftarlar sonini mos ravishda x, y va z deb belgilasak, masala shartiga kо`ra tenglamalar sistemasi hosil bо`ladi:

Ma’lumki, bunday sistema cheksiz kо`p yechimga ega bо`lib Diofant sistemasi deb ataladi. Bizga zarur bо`lgan yechimni ajratib olish uchun, ushbu cheklovni kiritamiz: daftarlar soni butun musbat son bо`lishi kerakligidan, biz faqat butun musbat yechimlarni olamiz. Shuni hisobga olib, sistemadan yechimning umumiy formulasini topamiz:

a+b>c ʌ a+c>b ʌ b+c>a
ва shunday qilib shartga kо`ra ligidan bо`lganda butun musbat sonlar va olamiz.

Download 71,41 Kb.

1 2

Download 71,41 Kb.