1-Amaliy mashg’ulot Mavzu: Algoritmlarni loyihalash. Algoritm korrekt va samaradorligini baholash. Kvadrat tenglama ildizlarini aniqlash algoritmi. Uchburchak yuzasi uchun Geron formulasi. Ishdan maqsad

1-Amaliy mashg’ulot
Mavzu: Algoritmlarni loyihalash. Algoritm korrekt va samaradorligini baholash. Kvadrat tenglama ildizlarini aniqlash algoritmi. Uchburchak yuzasi uchun Geron formulasi.
Ishdan maqsad: Kvadrat tenglama ildizlarini aniqlash va uchburchak yuzasini hisoblash algoritmlarini tuzish va ularni baholash.
Algoritm so‘zi va tushunchasi IX asrda yashab ijod etgan buyur alloma Muhammad al-Xorazmiy nomi bilan uzviy bog‘liq. Algoritm so‘zi Al-Xorazmiy nomini Yevropa olimlari tomonidan buzib talaffuz qilinishidan yuzaga kelgan. Al-Xorazmiy birinchi bo‘lib o‘nlik sanoq sistemasining tamoyillarini va undagi to‘rtta amallarni bajarish qoidalarini asoslab bergan.
Algoritmlarning turli ta’riflari mavjud. Rasmiy ta’riflardan biri bo’yicha
algoritm bu qo’yilgan masalani yechilishiga olib keluvchi aniq harakatlarning chekli ketma-ketligidir.
Foydalanish uchun mo’ljallangan hisoblash algoritmlariga bir qator talablar qo’yiladi. Ulardan birinchisi – algoritmning to’g’riligi. Agar uchta shart bajarilsa, biz hisoblash algoritmini to’g’ri deb ataymiz:
1) bu kompyuter uchun cheklangan miqdordagi elementar operatsiyalarni bajargandan so’ng, kiruvchi ma’lumotlarni natijaga aylantirishga imkon beradi.
2) kirish natijalarining kichik buzilishlariga nisbatan natija barqaror;
3) Agar ko’rsatilgan shartlardan kamida bittasi bajarilmasa, algoritm noto’g’ri deb nomlanadi.
Birinchi shartni bajarish zarurati aniq. Agar natijaga erishish uchun cheksiz ko’p operatsiyalarni bajarish kerak bo’lsa yoki kompyuterda bajarilmaydigan operatsiyalar talab qilinsa, algoritm noto’g’ri deb tan olinishi kerak.
Misol 1. Raqamlarni “burchak” ga bo’lishning mashhur algoritmi noto’g’ri, chunki hisob-kitoblarni tugatish mezoni aniqlanmagan bo’lsa, u muddatsiz davom etishi mumkin.
Misol 2. Tugatish mezonining yo’qligi algoritmni noto’g’ri qiladi.
S = 1 + 1/2 + 1/3 + 1/4 +.
Misol 3. Kvadrat tenglamaning ildizlarini hisoblash algoritmi
a + bx + c = 0
formulalar bo’yicha
x_1,2 = (- b ± √ (b ^ 2-4ac)) / 2a
Bu formulalar noto’g’ri, agar u kvadrat ildizni ajratish operatsiyasi bajarilmagan kompyuterda ishlatishga mo’ljallangan bo’lsa yoki tuzilgan algoritm b²-4ac ifodasining belgisini hisobga olmasa.
Misol 4. Yon uzunliklari berilgan uchburchakning maydonini hisoblash uchun Geron formulasi. Agar hisoblash algoritmi bunday uchburchakning mavjudligini hisobga olmasa (Ikki tomon uzunliklarining yig’indisi uchinchi tomon uzunligidan katta), bu algoritm noto’g’ri.
Algoritmni amalga oshirishda xotira va vaqt(protsessos) cheklangan resurslarga ega bo’lgan kompyuterdan foydalanamiz. Shuning uchun biz tuzilgan algoritmni vaqt va xotira hajmi bo’yicha baholab bera olishimiz kerak. Algoritmlarni baholashning ikkita modeli RAM va O ”katta” (O()) modellari keng tarqalgan.
RAM modelida dasturda bajariladigan har bir amal bitta qiymatga teng. Misol uchun, 1+2 va 1*2 amallarini bajarilishida operatsiyalar soni bir qiymatga teng. Aslida kompyuterning jisoblash xususiyatiga ko’ra ko’paytirish amali qo’shish amalidan ko’proq vaqt talab qiladi. RAM modelida esa ular bir xil qiymat bilan baholanadi. Bu model algoritmning har bir amalini hisoblab chiqib baholashga asoslangan. Lekin bu model bilan barcha algoritmlarni baholab bo’lmaydi. RAM modeli universal model bo’lmagani uchun undan ko’p foydalanilmaydi.