Axborotlashtirish texnologiyalari

7 MA’RUZA: ALGORITMLARNI ISHLAB CHIQISH METODLARI. MAKSIMUM TOPISH MASALASI.


Reja
1. Masalaning qo’yilishi.
2. So’zli algoritmni ishlab chiqish
3. Algoritmni tahlil qilish


Darsning maqsadi: talabalarga algoritmlarni ishlab chiqish usullari haqida ma’lumot berish. Aniq misolda algoritmni ishlab chiqish va uni optimallashtirish bo’yicha ma’lumot berish
Tayanch iboralar: algoritmlar nazariyasi, minimum, maksimum, murakkablik, vaqtli, hajmiy, mezon, chegara, optimallashtirish, test, ishlab chiqish, hujaatlashtirish.
Mashg’ulot vositalari: sinf doskasi, plakatlar, fundamental fan darsliklari, o’quv va uslubiy qo’llanmalar, informatika bo’yicha atamalar lug’ati, videoproyektor, ekran va kompyuterdan samarali foydalanish.
Mashg’ulot usullari: takrorlash, suhbat va savol-javob, munozara (mavzuni o’zlashtirishni mustahkamlash) tarzida muloqot o’tkazish, (talabalarning mustaqil, erkin fikrlash va so’zlashga o’rgatgan holda fikr mulohazalarini bayon qildirish, buning uchun har bir talabaga, tayanch iboralardan savollar tashlanadi, ular o’z fikrlarini bayon qiladilar, hamma talaba javobni bayon qilib bo’lgandan so’ng talaba bilan birgalikda javoblar yakun qilinadi).
Darsning xronologik xaritasi – 80 minut.
Tashkiliy qismi: Auditoriyaning jixozlanishi va sanitar sharoitlari, talabalar davomati – 2 minut.
Bilimlarni baholash: yangi mavzuni o’rganish uchun zarur bo’lgan material bo’yicha suxbat – 10 minut.
Yangi mavzuni bayon etish – 55 minut.
Mavzu o’zlashtirilgan darajasini aniqlash – 10 minut.
Uyga vazifa – 3 minut.
Yuqorida orttirilgan bilimlar yordamida bir tipik masalani yechamiz:
Masalaning qo’yilishi.
berilgan elementlar bo’yicha m va j larni shunday topingki, bo’lsin. Bu yerda j mumkin bo’lgancha maksimal bo’lsin.


So’zli algoritm

1. 
   Boshlanish.
   
2. 
   j:=n; k:=n-1; m:=xn;
   
3. 
   agar k::=0 unda 7 o’ting.
   
4. 
   agar xk<=m unda 6 o’ting.
   
5. 
   j:=k; m:=xk;
   
6. 
   k:=k-1; 3 o’ting;
   
7. 
   tamom.
   

Algoritm sodda va analizga muhtoj emas deb hisoblanadi. Lekin shu misolda murakkab algoritmn qanday tahlil qilish kerakligini ko’rsatish mumkin. Algoritm tahlili dasturlash uchun juda muhim.
Biz faqatgina bu algoritmni bajarish uchun kerak bo’ladigan vaqtni tahlil qilamiz.Buning uchun har bir qadam necha marta bajarilishini hisoblaymiz:

Qadam raqami	Necha marta bajarilishi
2	1
3	n
4	n-1
5	A
6	n-1

Har bir qadam necha marta bajarilishini bilgan holda, kompyuterga masalani bajarish uchun qancha vaqt kerakligini hisoblab chiqish mumkin.

Jadvalda A dan tashqari hamma qiymatlar ma’lum, A – bu joriy maksimum qiymatini necha marta o’zgartirish kerakligini ko’rsatkichi. Taxlilimiz to’liq bo’lishi uchun A ni ko’rib chiqamiz.
Tahlilning maqsadi A uchun min va max qiymatlarni topish.
1) Min A = 0,
bu holat

bo’lganda kuzatiladi.
2) Max A=n-1;
bu qiymatga

holatida erishiladi.
Shunday qilib A ning tahlili 0 va n-1 larning o’rta arifmetik qiymati va o’rta kvadratini chetlanishini va usullari yordamida topish masalasiga olib keladi.