Mavzu: Algoritm tushunchasi

Informatika-9. 4 – dars.

Mavzu: Algoritm tushunchasi

Maqsad:

1) ta’limiy: O`quvchilrga algoritm, algoritm ijrochisi, ijrochini ko`rsatmari tizimi haqida tushuncha berish;

2) tarbiyaviy: O`quvchilr buyukallomalarimizga hurmat ruhida tarbiyalash;

3) Rivojlantiruvchi: Masalalar yechish orqali o`quvchilarning algoritmlash ko`nikmalarini rivojlantirish.

DTS: algoritm, algoritm ijrochisi, ijrochini ko`rsatmari tizimi haqida tushunchaga ega bo`lish.

Darsning borishi.

I. Tashkiliy davr.

II. Takrorlash.

1. Obyekt, uning tavsifi va tavsif qiymati haqida misollar asosida so‘zlab bering.

2. Model deb nimaga aytiladi?

3. Matematik model deb nimaga aytiladi? Matematik modellar qanday sohalarda qo‘llaniladi?

4. Matematik modelning boshqa modellardan farqini tushuntiring.

5. Modellar necha turga bo‘linadi?

III. Yangi mavzuni o`rganish

Inson hayoti davomida katta-yu-kichik vazifalar yoki masalalarni hal etishni o‘z oldiga maqsad qilib qo‘yadi. Odatda, u o‘z maqsadiga erishishi uchun bajarishi lozim bo‘lgan amal yoki ishlarini hayotiy tajribasi yoki o‘zlashtirgan bilimiga asoslanib ma’lum bir tartibga keltiradi. Bunga hilma-xil misollar keltirish mumkin.

1–misol. Choy damlash maqsad qilib qo‘yilgan bo‘lsin. U holda choy damlayotgan kishi biz uchun odatiy hol bo‘lib qolgan quyidagi ishlarni bajarishi lozim bo‘ladi:

1. choynak qopqog‘i ochilsin;

2. choynak qaynoq suv bilan chayilsin;

3. choynakka bir choy qoshiq miqdorida quruq choy solinsin;

4. choynak to‘lguncha qaynagan suv quyilsin;

5. choynak qopqog‘i yopilsin;

6. choynak sochiq bilan yopilib besh daqiqa dam yedirilsin.

2 – misol. Eni N metr va bo‘yi M metr bo‘lgan joyni to‘ldirishga 12 25 santimetrli (eni 12 santimetr va bo‘yi 25 santimetr) g‘ishtdan necha dona sotib olinishini topish kerak bo‘lsin. Hisoblayotgan kishi geometriya fanidan olgan bilimiga asoslanib quyidagi ketma-ketlikdagi amallarni bajaradi:

1. joyning yuzasi S_joy santimetr o‘lchov birligida topilsin;

2. bir dona g‘ishtning yuzasi S_g‘isht santimetr o‘lchov birligida topilsin;

3. g‘ishtlar soni S_son joyning yuzasini g‘ishtning yuzasiga nisbati deb olinsin.

Bu amallar ketma-ketligini quyidagi matematik formula bilan ifodalash mumkin:

.

3–misol. Amal bajarilsin: 19632107 + 19702202. Bu amalni qanday bajargan bo’lar edingiz? Ha, to’gri, bu sonlarni ustun ko’rinishida deyarli quyidagicha qo’shasiz:

1) sonlar xonalari mos keladigan tartibda tagma tag yozib olinsin;

2) sonlarni birlik xonasidagi raqamlarini qo’shib, natijani birlik raqami birliklar tagiga yozilib, o’nlik raqami dilda saqlansin;

3) sonlarni o’nlikdagi raqamlarini va dildagi raqam qo’shilib, natijani birlik raqami o’nliklar tagiga yozilib, o’nlik raqami dilda saqlansin;

va 3-banddagi qoida yuzliklar, mingliklar va hokazo uchun takrorlanadi. Bu amallar quyidagi ko’rinishda sizga juda tanish:

Yuqoridagi misollarda keltirilgan amallar ketma-ketligi, boshqacha aytganda, ko’rsatmalar yoki buyruqlar ketma-ketligi biror kishi tomonidan bajarilgach, ko’zlangan maqsadga erishiladi. Hayotimizda har kuni va har soatda uchrab turadigan turli qoidalar ichida biror zaruriy natijaga erishishga olib keladigan amallarni ketma-ket bajarishni talab etadigan qoidalar informatikaning asosiy tushunchalaridan biri algoritm so’zi bilan ifodalanadi.

Algoritm so‘zi IX asrda yashab (783 - 850) o‘z ilmiy ishlari xazinasi bilan dunyoga tanilgan vatandoshimiz buyuk astronom, matematik va geograf Abu Abdulloh Muhammad ibn Muso al-Xorazmiy nomidan kelib chiqqan. Al-Xorazmiyning arifmetikaga bag‘ishlangan risolasi XII asrda Ispaniyada lotin tiliga tarjima qilingan. Bu tarjimaning XIV asrda ko‘chirilgan yagona qo‘lyozma nusxasi Kembrij universitetining kutubxonasida saqlanmoqda. Risola lotin tilida “Dixit Algorithmi”, ya’ni “Dediki Alxorazmiy” iborasi bilan boshlanadi.

Algoritmdagi har bir ko’rsatma yoki buyruq biror amalni bajarishni ko’zda tutadi. Algoritmdagi amallarni bajaradigan obyektni ijrochi tushunchasi bilan bog’laymiz. Har qanday algoritm – bu amallarni belgilovchi qoida bo’lib, ularning zanjiri natijasida berilgan qiymatlardan izlangan natijaga kelinadi. Bunday amallar zanjiri algoritmik jarayon, har bir amal algoritmning qadami deb ataladi.

Algoritm deganda biror maqsadga erishishga qaratilgan, ijrochi bajarishi uchun mo‘ljallangan buyruqlarning ketma-ketligi tushuniladi.

Demak, yuqorida keltirilgan misollardagi buyruqlar (yoki ko‘rsatmalar) ketma-ketligi algoritm va bu algoritmlarni bajarayotgan inson – ijrochi bo‘lar ekan. Birinchi misoldagi ko‘rsatmalar “Choy damlash algoritmi” deb ataladi. Bundan shunday hulosaga kelamiz: inson hayotida ko‘zlagan maqsadiga erishishi uchun ijrochi sifatida ko‘plab algoritmlarni bajaradi. Ko‘pgina algoritmlar inson uchun odat bo‘lib qoladi. Masalan, taom tayyorlash, ovqatlanish, tartibli kiyinish, honadan chiqish, yozish, bir joydan ikkinchi joyga borish va hokazo.

Ko‘rsatmalarning tartibi buzilishi qanday oqibatga olib kelishi mumkinligini o‘zingiz tasavvur qilishingiz qiyin emas. Misol sifatida “Choy damlash algoritmi”da birinchi va uchinchi ko‘rsatmalarni o‘rnini almashtirib bajarish kifoya.

Odatda algoritmlardagi ko‘rsatmalar ijrochiga tushunarli bo‘lishi uchun sodda amallardan iborat bo‘ladi. Ikkinchi misoldagi algoritmning birinchi ko‘rsatmasini quyidagi uch ko‘rsatmaga ajratish mumkin:

1a) joy eni N metr santimetr o‘lchov birligiga o‘tkazilsin;

1b) joy bo‘yi M metr santimetr o‘lchov birligiga o‘tkazilsin;

1d) joyning yuzasi S_joy topilsin.

Algoritm ijrochisi faqat insonmi, degan savol berishingiz tabiiy. Bu savolga javob quyidagicha:

Algoritm ijrochisi – algoritmda ko‘rsatilgan buyruq yoki ko‘rsatmalarni bajara oladigan abstrakt yoki real (texnik yoki biologik) sistema.

Ijrochi bajara olishi mumkin bo‘lgan ko‘rsatma yoki buyruqlar to‘plami ijrochinining ko‘rsatmalar sistemasi (qisqacha, IKS) deyiladi. Masalan, “16 sonidan kvadrat ildiz chiqarilsin” ko‘rsatmasi 2-sinf o‘quvchisining ko‘rsatmalar sistemasiga tegishli bo‘lmaydi, lekin 8-sinf o‘quvchisining ko‘rsatmalar sistemasiga tegishli bo‘ladi. Shuni ta’kidlash joizki, informatikada algoritmning asosiy ijrochisi bo‘lib kompyuter xizmat qiladi.

Ijrochining ko’rsatmalar sistemasini tushunib olish uchun quyidagi masalani qaraymiz.

4 –misol. Bo’g’irsoq uchun “oldindagi” katak qalpoqchasi ko’rsatayotgan katakdir, masalan u o’ngga burilganda ko’rinishda bo’ladi. Bo’g’irsoq 1 ta oldindagi katakka yura oladi yoki turgan katagida o’ngga yoki chapga burila oladi. Bo’g’irsoq bir katakdan bir necha marta o’tishi ham mumkin. Bo’g’irsoq o’zi turgan katakdan bilan belgilangan katakka biror yo’l bilan bora oladigan bo’lsa, zaruriy ko’rsatmalar ketma-ketligini yozing.

Masala shartidan ijrochi Bo’g’irsoqning ko’rsatmalar sistemasini yoza olamiz, ya’ni BKS={oldinga; o’ngga; chapga}. Endi masala yechimi sifatida quyidagi algoritmlardan birini olish mumkin:

Demak, masala yechimiga olib boruvchi algoritm yagona bo’lmasligi ham mumkin ekan.

Yuqorida ko‘rib chiqilgan misollarda yoki aytib o‘tilgan masalalardan shunday xulosaga kelamiz: ijrochi algoritmni bajarish jarayonida ko‘zlangan maqsadni bilmasligi ham mumkin. Masalan, quyidagi algoritmni bajarishdan qanday maqsad ko‘zlangani oldindan bilinmaydi:

1) N va M natural sonlar olinsin;

2) S soni nolga teng deb olinsin;

3) N va M sonlarning kattasi aniqlansin;

4) N va M sonlarning kattasidan kichigi ayirilsin va S ga bir qo‘shilsin;

4) agar N va M sonlarning ikkalasi ham noldan katta bo‘lsa 3)-bandga o‘tilsin;

5) javob sifatida S yozilsin.

Bu algoritm quyidagi masalaning yechimini topish imkonini beradi:

5–misol. Tomonlari N va M natural sonlarga teng bo‘lgan to‘g‘ri to‘rtburchak berilgan. Agar har qadamda eng katta yuzali kvadrat kesib olinaversa, nechta kvadrat kesib olinadi?

Bu dars orqali masalalarni kompyuterda yechishning asosiy bosqichlaridan biri bilan bog’liq bo’lgan informatikaning algoritm, algoritm ijrochisi, ijrochinining ko‘rsatmalar sistemasi kabi asosiy tushunchalari bilan tanishib shunday xulosaga kelamiz: algoritm orqali ijrochi boshqariladi.

IV. Mustahkamlsh

1. Algoritm deganda nimani tushunasiz?

2. Algoritm so‘zini kelib chiqish tarixini so‘zlab bering.

3. Algoritmga maktab hayotidan misollar keltiring.

4. Darslikdan berilgan mavzuni topish algoritmini tuzing.

5. “Oshpalov” pishirish algoritmini tuzing.

6. Kompyuterni ishga tushirish algoritmini tuzing.

7. Algoritm ijrochisi haqida nimalarni bilasiz?

8. Qanday ko‘rsatmalarni ijrochi bajara olmaydi?

9. Ijrochining ko‘rsatmalar sistemasiga misollar keltiring.

10. Sinfdoshingiz bajara olmaydigan ko’rsatmalar yozing.

11. Quyidagi ko‘rsatmalar algoritm bo‘ladimi va ularni bajarishdan qanday maqsad ko‘zlangan?

1) daryodan bir chelak suv olinsin;

2) chelakdagi suv daryoga solinsin;

3) 1-bandga o‘tilsin.

V. Uyga vazifa.

10-topshiriq.