|
modul. Algoritmlar nazariyasi. – Mavzu: algoritm va algoritmlar samaradorligini baholash. Reja
|
| bet | 7/8 | | Sana | 13.05.2024 | | Hajmi | 31,65 Kb. | | #229681 |
Bog'liq 1-ma\'ruzaAlgoritm korrektligni baholash.
Algoritmni har qanday shaklda taqdim etgandan so‘ng, uning to‘g‘riligini baholash kerak. Bu shuni anglatadiki, tanlangan algoritm cheklangan vaqt uchun har qanday to‘g‘ri kirish qiymatlari uchun kerakli natijani beradi. Misol uchun, Euclid algoritmining ikki raqamning tugunlarini hisoblash uchun to‘g‘riligi, turi GCD (t, n) = GCD (n, m mod n) tengligining to‘g‘riligidan kelib chiqadi, bu esa o‘z navbatida isbotlanishi kerak, shuningdek, har bir iteratsiya bo‘yicha ikkinchi raqam har doim kamayadi va ular nolga etib borgach, algoritmni bajarish to‘xtatiladi.Ba’zi algoritmlarning to‘g‘riligini isbotlash juda oson, boshqalari esa juda qiyin. Algoritmning to‘g‘riligini isbotlashning universal usuli matematik indüksiyon usuli hisoblanadi. Aslida, algoritmlar tabiatan iterativ bo‘lib, indüksiyon usuli bilan isbotlashda ishlatiladigan asta-sekin ko‘rsatmalar ketma-ketligi sifatida tavsiflanadi. Bu diqqat bilan tanlangan kiritish ma’lumotlar bir necha Odatda, algoritmlar yaratuvchilari bir necha talablarga javob berishga harakat qilishadi. Algoritmning to‘g‘riligini tekshirgandan so‘ng, eng muhim xususiyatlardan biri uning samaradorligini baholashdir. Amalda, algoritmning samaradorligini baholashning ikki turi mavjud: vaqtinchalik va mekansal. Vaqtinchalik samaradorlik (vaqt samaradorligi) algoritmning ishlash tezligi ko‘rsatkichidir. Mekansal samaradorlikka (space efficiency) kelsak, bu taxmin algoritmni ishlatish uchun zarur bo‘lgan qo‘shimcha RAM miqdorini ko‘rsatadi.
Agar siz algoritmning samaradorligi, soddaligi yoki umumiyligi bilan qoniqmasangiz, yana qalamni olib, algoritmni qayta ishlashingiz kerak bo‘ladi. Va algoritm tahlil ijobiy natijalarga olib keldi bo‘lsa ham, u boshqa algoritmik muammoni hal qilish uchun qarash mantiqiy. Avvalgi bobda ko‘rib chiqilgan tugunni aniqlash uchun uchta algoritmni esga olish kifoya. Umuman olganda, siz birinchi urinishda muammoning eng yaxshi echimini topishga umid qilishingiz kerak emas. Eng kam narsa, yaratilgan algoritmni optimallashtirishga harakat qilishdir. Har doim mashhur frantsuz yozuvchisi, uchuvchi va samolyot dizaynerlari Antoine De Saint-Exupery (Antoine de Saint-Exupery) ning bayonotini eslang: "dizayner o‘zining aql-idrokiga qo‘shilmaydigan hech narsa bo‘lmasa, mukammallikka erishadi va boshqa hech narsa yo‘q bo‘lganda".
Algoritmning yana bir muhim xususiyati uning soddaligi (simplicity). Qattiq matematik ifodalar yordamida aniq belgilanishi va baholanishi mumkin bo‘lgan samaradorlikdan farqli o‘laroq, algoritmning keyingi muhim xususiyatlarining soddaligi uning umumiyligi yoki ko‘p qirrali (generality) hisoblanadi. Aslida, bu erda ikkita nuqta bor: muammoni hal qilish uchun algoritm ishlab chiqilgan muammoning umumiyligi va uning kirish ma’lumoti.
Bizning algoritmimiz haqiqatan ham to‘g‘ri ekanligini qanday baholay olamiz? To‘g‘ri algoritm har qanday kirish uchun to‘g‘ri chiqish shaklida natija beradigan algoritmdir. Misol uchun, agar biz qidiruv algoritmini ko‘rib chiqsak, uning ishining natijasi topilgan elementning indeksi yoki -1 raqami bo‘lishi kerak. Algoritmning to‘g‘riligini tekshirish uchun bir necha usullar mavjud.
|
| |
