Axborotlashtirish texnologiyalari

8 MA’RUZA: EVKLID ALGORITMINING TAHLILI
Reja
1. Masala qo’yilishi.
2. Algoritmni tuzish
3. Algoritm tahlili
4. Algoritm optimallashtirish
5. Algoritmni amalga oshirish
Darsning maqsadi: talabalarga algoritmlarni ishlab chiqishni Evklid algoritmi misolida ko’rsatish Aniq misolda algoritmni baholash va 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.


Masala qo’yilishi

Ikkita butun musbat m va n sonlar berilgan. Ularning umumiy bo’luvchisini topish talab qilinadi. Ya’ni, eng katta butun musbat son topish kerakki, unga m va n ni bo’lganda butun son chiqsin.

Algoritmni tuzish

1. 
   Boshlash;
   
2. 
   m ni n ga bo’lamiz, qoldiq r ga teng bo’lsin;
   
3. 
   Agar r=0 unda n-natija; 5 o’ting;
   
4. 
   m:=n; n:=r; 2 o’ting;
   
5. 
   tamom.
   

Algoritm tahlili
Shu algoritmni tadqiq qilib ko’raylik. m=119, n=544 deb qabul qilaylik. Ikkinchi qadamdan boshlaymiz. Algoritmga binoan bo’lish natijasini nolga teng deb hisoblaymiz va r ga 119 ni ta’minlaymiz, keyin 3-qadamga o’tamiz. R nolga teng bo’lmaganligi uchun, hech nima qilmaymiz va 4-qadamga o’tamiz. Bu yerda m ga 544 ni, n ga 119 ni ta’minlaymiz. Umuman, ravshan bo’ldiki, m

Algoritm optimallashtirish
Algoritmni optimallashtirish uchun unga quyidagi qadamni qo’shamiz:

1. 
   agar m

Endi 2-qadamga kelsak, 544:119=4,68/119. r ga 68 ni ta’minlaymiz. 3-qadam ishlamaydi. 4-qadamda n=68, m=544, r=68. Keyingi sikllarda (r=51, m=68, n=51), keyin (r=17, m=51, n=17) va 51/17, ya’ni r=0.
Shunday qilib, algoritm sikli 3- qadamda tugadi va 544 va 119 larning umumiy bo’luvchisi 17 ga teng bo’ldi.
Bu algoritm umumiy bo’luvchini topish uchun yagona emas. Bunday algoritmni topish uchun Dj. Steynning binar algoritmi, yoki V, xorrisning algoritmidan foydalaniladi.


Algoritmni amalga oshirish
Shu algoritmni kompyuterda amalga oshirish uchun quyidagi Paskal dasturini keltirish mumkin:
Program evklid;
Var a, b, nod, r, x, y: integer;
Begin read (a, b);
if a>b then begin x:=a; y:=b; end;
else begin x:=b; b:=a; end;
if (x>0) and (y>=0) then begin while y<>0 do
begin r:=x mod y; x:=y; y:=r; end;
Nod:=x; write (nod);
end; else write (‘berilganlarda xato’);
end.