O’ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI QARSHI FILIALI
KI FAKULITETI DI_12-22 GURUH TALABASINING
Algortimlarni Loyihalash FANIDAN
1-Mustaqil ishi
BAJARDI: Davronov Behruz
QABUL QILDI: Begulov O
QARSHI-2024
Mavzu : Algoritm murakkabligining statik va dinamik o‘lchovlari. Vaqt va xotira hajmi bo‘yicha qiyinchiliklar Algoritmlarni eng yomon va o‘rtacha holatlarda baholash. Algoritmlarni vaqt va hajmiy murakkabligini baholashda tekis va logorifmik solishtirma mezonlari. Ketma – ketliklar, to’plamlar, daraxtlar, graflarni ifodalash usullari. Taqribiy integrallash usullarini aniqligi va hisoblash hajmi bo‘yicha taqqoslash. Algebraik va transtsendent tenglamalarni taqribiy yechish usullarini yaqinlashish tezligi bo‘yicha baholash.
Reja :
Algoritm murakkabligining statik va dinamik o‘lchovlari.
Vaqt va xotira hajmi bo‘yicha qiyinchiliklar Algoritmlarni eng yomon va o‘rtacha holatlarda baholash.
Algoritmlarni vaqt va hajmiy murakkabligini baholashda tekis va logorifmik solishtirma mezonlari.
Algoritm murakkabligi haqida statik va dinamik o'lchovlar asosan algoritmlar yoki dasturlar bajarilgan vaqtdagi muammolar miqdori, jarayonlarning tezligi va dasturlar yoki algoritmlarning ishlaydigan ma'lumotlarni muhafaza qilish va ulardan foydalanish xususiyatlariga bog'liqdir.
Statik O'lchovlar:
Statik o'lchovlar algoritmning dastur yoki algoritmlar bajarilishi vaqtida muammolarni yechish vaqti, xotirani ishlatish va boshqa resurslar asosida o'lchaydi.
Dastur ishga tushgandan keyin muammolar o'zgartirilmasligi kriteriyasi asosida o'lchovlar amalga oshiriladi.
Statik o'lchovlar algoritmlar va dasturlar bajarilishi dasturiy tuzilish va optimallashtirish jarayonlarida foydalaniladi. Misol uchun, algoritmlar bajarilish vaqti, ishlatiladigan xotira hajmi, operatsiyalar soni va boshqalar.
Dinamik O'lchovlar:
Dinamik o'lchovlar esa algoritm ishga tushgandan so'ng dastur yoki algoritmlar bajarilishi jarayonida yuzaga kelishi mumkin bo'lgan muammolarni o'lchaydi.
Dastur ishga tushgandan keyin muammolar o'zgartirilishi mumkinligi shart kiritilgan xususiyatlardan biri hisoblanadi.
Dinamik o'lchovlar amaliy muammolar sonini o'lchashda, algoritm yoki dastur ishga tushgandan keyin muammolarning nechta bo'lganligini va ularning har biri uchun sarflangan resurslarni hisoblashda foydalaniladi.
Statik va dinamik o'lchovlar algoritmlar va dasturlarni yaxshi tuzish, optimallashtirish, va ta'minlash jarayonlarida foydalaniladi. Bu o'lchovlar algoritmlarning amalga oshirish va muammo yechish davridagi kompleksliklarini o'rganishga va ularga echim topishga yordam beradi.
Algoritmlarni vaqt va xotira hajmi bo'yicha baholash, ularning amaliy ishlash vaqtini va ishlatiladigan xotira miqdorini o'rganishda yordam beradi. Bu baholash, algoritmni tuzish va optimallashtirish jarayonida juda muhimdir. Quyidagi yomon va o'rtacha holatlar, algoritmlarni baholashda muhimdir:
Vaqt bo'yicha qiyinchiliklar:
Algoritmlarni vaqt bo'yicha baholashda birinchi qiyinlik algoritmlarning amalga oshirish vaqti miqdorini aniqlashdir. Agar algoritmning amaliyati uchun zarur bo'lgan vaqt juda katta bo'lsa, bu algoritm yomon hisoblanadi.
Agar algoritmning amaliyati bajarilish uchun kerak bo'lgan vaqt ortiqcha katta bo'lsa, ushbu algoritm yomon deb baholanadi. Buning sababi, amalga oshirish vaqtining ko'p bo'lishi dasturning umuman qabul qilingan muddatdan o'tishi yoki dastur ishchi holatga kirishi uchun kelgusi operatsiyalarga ta'sir qilishi mumkin.
Xotira hajmi bo'yicha qiyinchiliklar:
Algoritmlarni xotira hajmi bo'yicha baholashda algoritmlar tomonidan ishlatiladigan xotira miqdorini aniqlash mumkin. Xotira miqdori, algoritmlar ishga tushgandan so'ng qo'llaniladigan hajmni ifodalaydi.
Agar algoritm ishlatiladigan xotira juda katta bo'lsa, bu algoritm yomon hisoblanadi. Chunki katta xotira miqdori dasturni bajarish vaqti oshishiga olib kelishi mumkin.
Xotira miqdori algoritmlarning dastur tizimini qo'llab-quvvatlash uchun e'tibor qaratilishi kerak. Agar dastur odatda ko'p xotira egallayotgan bo'lsa, boshqa dasturlardan ko'ra afzaldir.
Eng yomon va o'rtacha holatlarda algoritmlarni baholashda, vaqt va xotira hajmi ko'plik qo'shimchasini olishi mumkin, shuningdek, algoritmning samaradorligi va effektivligi past darajada bo'ladi. Bu yomon holatlarni identifikatsiya qilish va algoritmni yangilash yoki optimallashtirish uchun yo'l ko'rsatadi.
Algoritmik murakkablikni baholashda tekis va logorifmik solishtirma mezonlari foydalaniladi. Bu mezonlar algoritmik jarayonlarni tahlil qilishda va ularning murakkabligini aniqlashda foydalaniladi.
Tekis Solishtirma:
Tekis solishtirma, algoritmlar va dasturlar murakkabliklarini o'lchashda amalga oshiriladigan oddiy jarayonlardan biridir.
Ushbu solishtirma odatda dastur bajarilish vaqti, ishlatiladigan xotira miqdori, va boshqa resurslar kabi direkt qiyinchiliklarni o'lchaydi.
Boshqa bir solishtirma usullariga nisbatan, tekis solishtirma murakkab algoritmlarni tahlil qilishda ko'proq katta o'lchovda vaqt sarflaydi, ammo oddiylik va tushunarli bo'lib, aniq natijalarga olib keladi.
Logorifmik Solishtirma:
Logorifmik solishtirma algoritmik murakkablikni o'lchashda yuqori darajada qo'llaniladi. U bu murakkablikni algoritmlar va dasturlarning o'lchovlari va murakkablik darajasini ta'riflashda yordam beradi.
Bu solishtirma logarifmik funksiyalardan foydalanib, muammolarni hal qilish uchun kerak bo'lgan har bir operatsiya yoki muammoni hal qilish uchun zarur bo'lgan amalni hisoblashda foydalaniladi.
Logorifmik solishtirma algoritmlar va dasturlar murakkabliklarini o'lchashda atrofida xotira sarflanishini minimallashtirishga yordam beradi, chunki uning ishchi vaqtning o'lchamida, ma'lumotlar tashxisida minimal miqdorda o'lchov amalga oshiriladi.
Bu solishtirma mezonlari, algoritmik murakkablikni o'lchashda foydalaniladigan ma'lumotli vositalardir. Ularning qo'llanish tartibi jarayonning murakkabligi va qo'llaniladigan ma'lumotlarning miqdori bilan bog'liq bo'ladi.
Ketma-ketliklar, to'plamlar, daraxtlar, va grafiklarni ifodalash usullari, ma'lumotlar va obyektlar o'rtasidagi bog'liqni aniqlashda va dasturiy modellar yaratishda juda muhimdir. Quyidagi usullar boshqarish, ma'lumotlar olish va ta'riflashda qo'llaniladi:
Ketma-ketliklar (Arrays):
Ketma-ketliklar o'zlarida bir nechta o'zaro bog'langan elementlarni saqlaydigan o'zgaruvchilar turi.
Masalan, bir yoki bir nechta to'plamlar, matritsalar va boshqa ma'lumotlar turlari ketma-ketliklar yordamida ifodalash mumkin.
To'plamlar (Sets):
To'plamlar, unikal elementlarni saqlaydigan ma'lumot turi. Bu elementlar qator tartibida joylashishi zarur emas.
To'plamlar, ma'lumotlar tahlili, matematika, va boshqa sohalar uchun juda qulay bo'lishi mumkin.
Daraxtlar (Trees):
Daraxtlar, ma'lumotlar strukturasi bo'lib, o'z ichiga bir nechta elementlarni saqlaydi. Ular o'zaro munosabatlar orqali bog'langan bo'lishi mumkin.
Masalan, binar daraxtlar, AVL daraxtlar, 2-3 daraxtlar kabi turli xil daraxtlar mavjud.
Graflar (Graphs):
Graflar, almashtirilgan elementlarni yoki obyektlarni ifodalovchi ma'lumot strukturasi. Ular uchun turli xil algoritmlar va amaliyotlar mavjud.
Graflar tarmoq, kommunikatsiya tarmoqlari, tizimlar tarmoqlari va boshqa bog'liqlik modellarini ifodalash uchun qo'llaniladi.
Har bir usulning o'zining xususiyatlari va foydalanish sohalariga ega. Masalan, ketma-ketliklar odatda o'zgaruvchilarni bir joyda saqlash uchun qo'llaniladi, to'plamlar esa qat'iy unikal elementlarni saqlash uchun. Daraxtlar, elementlarni tarkibiy qurilishda yordam beradi, graflar esa bog'liqlik va munosabatlarni ifodalashda qo'llaniladi. Raqamli ma'lumotlar uchun ketma-ketliklar va to'plamlar, va o'rganish uchun daraxtlar, bog'liqlik va tarmoqlarni tahlil qilish uchun graflar juda qulay bo'ladi.
Foydalanilgan adabiyotlar :
Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ. Москва-Санкт-Петербург-Киев. Изд. дом «Вильямс», 2003. 1293 стр.
Levetan Anany. Introduction to the design & analisis of algorithms. 3rd ed. Villanova university. New Jersey. 2012. 693 page.
Род Стивенс. Готовые алгоритмы. М.: ДМК Пресс. Питер 2004. 384 стр.
Стивен Скиены. Алгоритмы. Руководство по разработке. Питер 2011. 715 стр.
|
