|
modul. Algoritmlar nazariyasi. – Mavzu: algoritm va algoritmlar samaradorligini baholash. Reja
|
| bet | 8/8 | | Sana | 13.05.2024 | | Hajmi | 31,65 Kb. | | #229681 |
Bog'liq 1-ma\'ruzaMatematik induksiyon usuli. Barcha tabiiy sonlar uchun uning haqiqatini isbotlash uchun n bir necha qadamni bajarishi kerak: P eng oddiy holatda - n = 1 uchun haqiqiy ekanligini isbotlang. Bunga induksiyon bazasi deyiladi. Keyinchalik, bu bayonot ba’zi k uchun to‘g‘ri ekanligini va k uchun to‘g‘ri bo‘lsa, k + 1 uchun ham to‘g‘ri ekanligini isbotlaymiz. Bunga indüksiyon bosqichi yoki indüksiyon o‘tish deyiladi. Agar biz buni isbotlasak, p ning bayonoti barcha n uchun amal qiladi degan xulosaga kelish mumkin. Faqat matematik misollar o‘zingiz uchun qarash mumkin, va men algoritmlar to‘g‘ridan-to‘g‘ri harakat qiladi. Misol uchun, ikkilik qidiruv algoritmining to‘g‘riligini isbotlaylik. Faqat uning kodini beraman:
int binary_search(int arr[], int start, int end, int target)
{
if (start == end)
{
return arr[start] == target ? start : -1;
}
int mid = floor(start + (end - start) / 2);
f (target <= arr[mid])
{
//
Левая часть
return binary_search(arr, start, mid, target);
}
else
{
//
Правая часть
return binary_search(arr, mid + 1, end, target);
}
}
Ishning to‘g‘riligini isbotlash uchun biz algoritmning oxirgi qadam soni bo‘yicha ishni yakunlashini ko‘rsatishimiz kerak. Nima uchun shunday? Algoritm yakunlandi bo‘lsa, bu funktsiya, degan ma’noni anglatadi, ikki qismga qator sindirib va to‘g‘ri massaj bilan o‘zini sabab, ertami-kechmi recursion eng past darajada bo‘ladi, bir qator bilan muomala qilinadi, bitta element o‘z ichiga olgan. Agar shunday bo‘lsa, algoritm faqat taqqoslash jarayonini bajarishi va qiymatni qaytarishi mumkin. Taqqoslash operatsiyasining isboti ahamiyatsiz, shuning uchun biz faqat taqdim etilgan har qanday kirish ma’lumotlari bilan algoritm to‘g‘ri bajarilishi va qiymat qaytarilishi kerakligiga ishonch hosil qilishimiz kerak.
Birinchidan, takroriy qo‘ng‘iroqlar sonini hisoblaylik. Men buni allaqachon qildim, shuning uchun faqat ⌈log2n⌉deb ayting. Har bir funktsiya chaqiruvi bilan, qator ikki qismga bo‘linadi, n ning 2 marta o‘sishi faqat bitta qadamni qo‘shadi. Mid har doim (bu holda kichik yo‘nalishda) yumaloq, chunki, biz, katta yo‘nalishda qiymatini yumaloq, va shuning uchun n, qaysi emas, balki bir necha 2, biz bir ikki vaziyatni hosil, qachon, holda, element o‘ng tomonida joylashgan bo‘lsa, algoritm amalga oshiradi 1 qadam ko‘proq. Ta’riflash uchun biz ushbu "eng yomon" holatdan foydalanamiz. Natijada, dalil, eng past darajadagi recoursiyaning (bir element bilan funktsiya chaqirilganda) to‘g‘ri bajarilganligini aniqlash kerak, keyin esa eng past darajaga erishish mumkinligini isbotlash kerak.
⌈log2n⌉=0. Agar bir element bir qator bilan vazifasini chaqirganda, qo‘ng‘iroq zanjiri to‘xtaydi, algoritm operator return qoqiladi, deb, qaysi topilgan element o‘rnini qaytaradi, yoki -1. Keyinchalik, bizning bayonotimiz k = n uchun to‘g‘ri deb hisoblaymiz. Natijada log log2k+1⌉ tabiiy son bo‘ladi - k tabiiy sondir va har qanday tabiiy sonning logaritmasi salbiy son bo‘lishi mumkin emas. Olingan javob katta tomonga yumaladi, bu esa uni tabiiy songa aylantiradi.
Dastur tuzish jarayonida uning ko‘p taraflariga e’tibor berish kerak: modullilik, qulay interfeyslilik, xavfsizlilik, tushunarlilik va b.q. Dasturningning ishlash davomida o‘zini tutishi (performance) esa dasturning barcha muhim jihatlaridanda muhimroqdir. Chunki,dasturni qotib qolmasdan ishlashi va doim to‘g‘ri natijalar berishi uning asosiy vazifasidir. Dastur uchun eng yaxshi unumdorlikni tanlash uchun esa unda foydalaniladigan algoritmni dastlab Tahlil qilib ko‘rish kerak.
Ikkita algoritm berilgan, qaysi biri yaxshiroq ekanligini qanday aniqlash mumkin?
Eng oddiy yo‘li, dasturni ikkita kompyuterda ishga tushirib dasturga turli sonlar kiritish bilan tekshirib ko‘rish va qaysi birini kam vaqt olayotganini aniqlash. Ammo, bu usulning juda ko‘p kamchiliklari mavjud:
1) Ba’zi sonlar uchun birinchi algoritm, ba’zi sonlar uchun esa ikkinchi algoritm tezroq ishlashi mumkin.
2) Ba’zi sonlar uchun birinchi kompyuterdagi birinchi algoritm, ba’zi sonlar uchun esa ikkinchi algoritm boshqa kompyuterda tezroq ishlashi mumkin.
Algoritmni asimptotik tahlil qilish yuqoridagi muammolarni bartaraf etishga yordam beradi. Algoritmni asimptotik tahlil qilishda biz algoritmga turli sonlar kiritilganda u qanday unumdorlik ko‘rsatishini baholaymiz. Biz algoritmga kiritilayotgan sonlar ortishi bilan uning ishlash vaqti (yoki xotiradan joy egallashi) qanday ortishini o‘lchaymiz (algoritmni ishlash vaqt davomiyligi qanchaligini emas).
Asimptotik Tahlil algoritmni baholash uchun eng yaxshi variantmi?
Asimptotik Tahlil 100% to‘g‘ri tahlil qilish imkonini bermaydi, ammo algoritmini asimptotik Tahlil qilish mavjud boshqa barcha Tahlil yo‘llari ichida eng yaxshisi. Misol uchun, ikkita saralash algoritm bor deb tassavur qilaylik, birinchisiga n son kiritilganda uning ishlash vaqti 100nLog(n) funksiya asosida, ikkinchisiga n son kiritilganda uning ishlash vaqti 2nLog(n) funksiya asosida ortsin. Bu algoritmlarning unumdorligi asimptotik Tahlilda teng deb hisoblanadi (o‘sish tartibi nLog(n)), chunki asimptotik Tahlilda konstanta koeffisiyentlar hisobga olinmaydi.
Algoritmalar samaradorligini baholash uchun bir nechta metoddan foydalanish mumkin. Birinchi qadamda, algoritmlarni samaradorligini hisoblash uchun o‘zgaruvchilarini (mikro va makro samaradorliklar, ishchi va xotiradagi resurslar, vaqt va kenglik) qaror qilish kerak. Bu parametrlar ustida tafsilotli hisobot tuzish va ularga bog‘liq qiymatlar bilan to‘ldirish muhimdir.Algoritmni baholash uchun usullardan biri, uning bajarish vaqti va kengligini hisoblashdir. Bu maqsadda, algoritmniki bajarishlar soni, algoritmniki amalga oshirishlar, hisoblash operatsiyalari va yadrolar va uning bajarilishini to‘xtatish vaqti ko‘rsatiladi. Agar bajarish vaqti katta bo‘lsa, shuningdek xotiradagi resurslarni ko‘rsatish ham muhimdir.Boshqa bir metoddan foydalanish uchun, algoritmning samaradorligini hisoblash uchun eksperimentlarni amalga oshirishingiz mumkin. Buning uchun algoritmdan keyingi har bir qadami, yozilish vaqti, xotiradagi resurslar va o‘zgaruvchilarning qiymatlari bilan birlikda bajariladi. Natijalar to‘plami to‘g‘ri natija olish uchun bir nechta marta takrorlanishi mumkin. Ushbu usul, algoritmdagi samaradorlik muammosini aniqlash va uning qaysi qismiga e’tibor qaratishga yordam berishi mumkin.
Iteratsion sikllar, algoritmlarni samaradorlik va samarali ko‘rinishini oshirishga yordam beradigan boshqa bir vosita hisoblanadi. Sikl birlikda qayta-qayta ishlaydi va uning natijalari ustida natijalar olishga imkon beradi. Iteratsion sikllarning samaradorligi, siklning qancha marta takrorlanishi va bajarilish vaqti asosida baholanishi mumkin. Biroq, siklning hammasi bog‘liq algoritmdan va unda ishlatilgan ma’lumotlardan qat’iy nazar, uning samaradorligini aniq hisoblash mumkin emas.Sizning o‘ziga xos loyihangizda algoritmlarning samaradorligini baholash uchun muhim bo‘lgan parametrlarni aniqlash va ularga qiymatlar topish lozim. Ushbu parametrlar ustida amaliyotlarni sinab ko‘rish va eksperimentlardan kelgan natijalarni hisoblash orqali o‘zgaruvchilarni hisoblash mumkin. Iteratsion sikllarni ham foydalanish va unAniqlangan algoritmlar samaradorligini baholash uchun bir nechta metoddan foydalanish mumkin:
1. Bajarish vaqti: Algoritmda ishlatilgan barcha operatsiyalarning vaqti o‘lchab ko‘riladi. Agar bajarish vaqti uzluksiz oshib ketayotgan bo‘lsa, samaradorlik pasayishi mumkin. Bajarish vaqti, algoritmda ishlatilgan har bir qadami, sikllarni va resurslar sonini hisobga olgan holda yig‘indisi hisoblanadi.
2. Xotiradagi resurslar: Algoritmda ishlatilgan xotiradagi resurslar, yani operativ xotira va disk maydoni kabi resurslar, samaradorlikni ta’sir qilishi mumkin. Xotiradagi resurslar orqali ish faolligini o‘lchab ko‘rish uchun monitoring qilish, algoritmda foydalaniladigan xotiradagi resurslarni belgilash, xotiradagi resurslar bo‘yicha monitoring vositalaridan foydalanish muhimdir.
3. Mikro va makro samaradorlik: Mikro samaradorlik, bitta amalning samaradorligini tahlil qiladi, masalan, algoritmning bir qadami yoki operatsiyasi. Makro samaradorlik esa algoritmdagi barcha qadamlar yoki operatsiyalarni yig‘indisini hisobga oladi. Mikro va makro samaradorliklarni ta’qib qilish, algoritmda ko‘proq vaqt va resurs sarflanadigan qadamlarni aniqlashga yordam beradi.
4. Natijalar va aniqlashlar: Algoritmning to‘g‘ri natijalar olishi, xatolar sonini kamaytirish va aniqlashlarni aniqlashning samaradorligini aks ettiradi. Algoritmdan kelgan natijalar va aniqlashlar ustida tahlil va taqqoslash, natijalarning aniqlash darajasini, xatolar sonini va ularning ta’sirini baholash imkonini beradi.
Bu metoddan foydalanish orqali algoritmlar samaradorligini baholashga imkon beriladi. Har bir metodning o‘ziga xos xususiyatlari va cheklari mavjudligini unutmang. Algoritmlarni samaradorlik asosida tahlil qilish va optimallashtirish, samaradorlik darajasini oshirish va ish faolligini yaxshilashga yordam beradi.Algoritmlarning samaradorligini baholash uchun boshqa bir usul ham iteratsion sikllarning efektivligini o‘rganishdir. Iteratsion sikllar, biror vazifani to‘g‘ri bajarish uchun bir qator qadamni takrorlash orqali ishni bajargan ko‘rinishdir.
TALABA BILIMINI MUSTAHKAMLASH UCHUN NAZORAT SAVOLLAR
1. CorelDraw 2018 dasturining umumiy tuzilishi.
2. Dastur ishga tushirilgandan keyingi ishlar.
3. Xotirada bir nechta usullarda saqlash yo‘llari.
4. Menyuning Файл (File) va Импортировать (Import) buyrug`i.
5. CorelDRAW dasturida import qilingan tasvirlarni o‘zgartirish.
6. Импортировать (Import) ro‘yxatidan foydalanish.
7. CorelDrawning ishlash prinsiplari.
|
| |
