Mustaqil ishi Bajardi: Avliyoqulov a qabul qildi: Begimov o mavzu

O’zbekiston Respublikasi Raqamli Texnologiyalar vazirligi Muhammad al-Xorazmiy nomidagi Toshkent axborot texnologiyalari universiteti 025-18 guruhi talabasining Algoritmlarni loyihalash fanidan



Mustaqil ishi

Bajardi: Avliyoqulov A

Qabul qildi: Begimov O

Mavzu: Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajmi bo‘yicha qiyinchiliklar.

Reja:

1. 
   Algoritm murakkabligining statik va dinamik o’lchovlari. Vaqt va xotira hajmi bo’yicha qiyinchiliklar.
   
2. 
   Algoritmlarni eng yomon va o’rtacha holatlarda baholash.
   
3. 
   Algoritmlarni vaqt va hajmiy murakkabligini baholashda tekis va logarifmik solishtirma mezonlari.
   

Inson hayoti davomida katta-kichik vazifalar yoki masa- laiarni 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 asos- lanib ma'lum bir tartibga keltiradi. Bunga hayotimizdan xilma- xil misollar keltirish mumkin.

Yuqoridagi misollarda keltirilgan amallar ketma-ketligi, boshqacha aytganda, ko'rsatmalar yoki buyruqlar ketma-ketligi biror kishi tomonidan bajarilgach, ko'zlangan maqsadga erishi- ladi. Bunday amallar ketma-ketligi yoki 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-yilda tug‘ilgan) o‘z ilmiy ishlari xazinasi bilan dunyoga tanilgan vatandoshimiz buyuk astronom, matematik va geograf Abu Abdullo Muhammad ibn Muso al-Xorazmiy nomidan kelib chiqqan. Al-Xorazmiy arifme- tikaga bag‘ishlangan «Hind hisobi haqida kitob» risolasida to‘q- qizta hind raqamining sonlarni ifodalashdagi afzalliklari va ular yordamida har qanday sonni ham qisqa va oson yozish mum- kinligini aytadi va hozirgi kunda hamma o‘quvchilar biladigan sonlar ustida, yuqoridagi 3-misoldagi kabi ustun ko'rinishida amallar bajarish qoidalarini yoritadi. Ayniqsa, nol (0) qo‘llash- ning ahamiyati haqida tushuncha berib, nolni yozmaslik nati- janing xato chiqishiga olib keladi, degan. Bu risola XII asrda Ispaniyada lotin tiliga tarjima qilingan va butun Yevropaga tarqatilgan. Bu tarjimaning XIV asrda ko'chirilgan qo’lyozmasi kutubxonasi ning yagona nusxasi Kembrij universitetining kutubxonasida saqlanmoqda. Risola «Dixit Alxhorithmi», ya’ni oDediki aiXorazmiy» iborasi bilan boshlanadi.
Algoritm- bu aniq hisoblashlarni bajaruvchi protsedura bo‘lib uning kirish qismida kattalik yoki kattaliklar berilib chiqishda natijaviy kattalik yoki kattaliklar olinadi. Demak algoritm hisoblovchi qadamlardan tashkil topgan bo‘lib, dastlabki qiymatlarga ko‘ra natijaviy kattaliklar qiymatini beradi. Bu holatni sxematik tarzda quyidagicha tasvirlash mumkin.
Algoritm deb hisoblash yoki masalani yechish jarayonlarining ketma-ketligi yig’indisi tushuniladi. Algoritmlar biror dasturlash tiliga bog’liq bo’lmaydi, ular istalgan tilda kod yozilgan taqdirda ham bir xil natijaga olib keladigan instruksiyalardir.
Ammo barcha instruksiyalar ham algoritm bo’lavermaydi. Algoritm bo’lishi uchun, instruksiya bir necha xarakteristikalarga ega bo’ladi:

• 
  Barcha qadamlar aniq koʻrsatilgan boʻlishi kerak
  
• 
  Input va Output turi aniq belgilangan bo’lishi kerak
  
• 
  Chegarali. Algoritm doimiy siklga tushib qolmasligi, ohirgi qadamlarigacha yetib borishi zarur
  
• 
  Oson. Algoritm istalgan dasturlash tilida amalga oshirish mumkin bo’ladigan darajada oson tuziladi
  

Algoritmlarning ikki xil turi ajratib ko’rsatiladi, bular: takrorlanuvchi algoritmlar va rekursiv algoritmlar. Takrorlanuvchi algoritmlar asosida sikl va shart operatorlari yotadi. Bu sinf algoritmlarining analizi barcha sikllar va ular ichidagi amallar hisobini taqazo etadi. Rekursiv algoritmlar (rekursiv funksiya – o’z-o’zini chqiruvchi funksiya) esa asosiy masalani qismlarga ajratadi va ularning har birini alohida yechadi. Rekursiv algorutmlarning analizi anchayin murakkab. U masalani qismlarga bo’lish amallarini sonini, asosiy masalaning har bir qismida algoritmning bajarilishini, shu bilan birga ularning birlashmasini hisoblashni talab etadi.
Qaysi instruksiyalarni hisoblash kerak? Bu savolga aniq javob mavjud emas, lekin aniq faktki – hisoblashda mavjud operatsiyalar(amallar)ni inobatga olish lozim.
Ularga quyidagilarni kiritish mumkin:
Oddiy o’zlashtirish: а ← b ;
Massiv elementlarini indekslash (uning qiymatini aniqlash);
Arifmetik amallar: -, +, *, / ;
Solishtirish amallari: <, >, =, <=, >=, <> ;
Mantiqiy amallar: or, and, not.
Algoritmning vaqt bo’yicha murakkabligiga kirish ma’lumotlarining hajmi sezilarli ta’sir ko’rsatadi. Unchalik kata bo’lmagan hajmdagi ma’lumotlarni qayta ishlashda ikkita turli algoritmning ishlash vaqti ahamiyatsizdek tuyulishi mumkin, ammo ma’lumotlar hajmining ortishi ularning bajarilish vaqtiga sezilarli darajada ta’sir ko’rsatishi mumkin.
Lekin vaqt bo’yicha murakkablik faqatgina hajmga emas, balki ma’lumotlarning qiymatiga, shuningdek ularning tushish(uchrash) tartibiga ham bog’liq. Masalan, ko’pchilik saralash algoritmlari agar massivning o’zi saralangan bo’lsa, massivni tartiblashga anchayin kam vaqt sarflaydi. Shu kabi holatlar sabab vaqt bo’yicha murakkablikni uch xil holatda ko’rib chiqiladi: yomon, yaxshi va o’rta.
Yomon holat kirish ma’lumotlarining omadsiz kiritilishida ya’ni algoritm masalani yechish uchun maksimal sondagi elementar amallarni bajarishi to’g’ri kelish holatiga mos keladi. Yaxshi holatda aksincha kirish ma’lumotlari imkon qadar minimal sondagi amallarni bajarilishi ta’minlaydi.
O’rta holat anchayin murakkab aniqlanadi. Kirish ma’lumotlari imkon darajasida guruhlarga ajratiladi. Keyin har bir guruhning qatnashish ehtimolligi aniqlanadi. Shundan so’ng, har bir guruhning ma’lumotlar bilan ishlashi bo’yicha algoritmning ishlash vaqti hisoblanadi. Bizni ko’pincha eng kam va eng ko’p holatlari ko’proq qiziqtiradi.
Kiritiluvchi ma’lumotlarning hajmi katta bo’lganda biror masalaning ekzemplyar(nusxa) asosida bajariluvchi yechimi, algoritmlarning ishlash vaqti analizini solishtirish asimptotik tahlil deb yuritiladi. Asimptotik murakkabligi kamroq bo'lgan algoritm ko'proq samarador (effektiv) hisoblanadi.
Asimptotik tahlilda algoritmning murakkabligi – bu algoritmning ma’lumotlari hajmi ortishi bilan algoritmning ishlash vaqtining tezkor ravishta ortishini belgilovchi funksiyadir. Asimptotik tahlilda asosiy uchraydigan o'sishni baholash funksiyalari bular:
(O-katta) – vaqtni o'sishini yuqori asimptotik baholash funksiyasi;
Ω (Omega) – vaqtni o'sishini quyi asimptotik baholash funksiyasi;
Θ (Teta) - vaqtni o'sishini quyi vayuqori asimptotik baholash funksiyasi.
Bunda n – ma'lumotlarning hajmiy kattaligi bo'lsin. U holda f(n) algoritmning o’sish funksiyasini asimptotik jihatdan g(n) funksiya bilan chegaralash mumkin:

Misol uchun, muassasaning tozalash vaqti uning maydoni kattaligiga chiziqli ravishta bog’liq (Θ(S)), ya’ni maydon kattaligining n marta ortishi bilan uni tozalash vaqti ham n marta ortadi. Telefon daftarchasidan ismni qidirishda agar chiziqli qidirish algoritmidan foydalanilsa, O(n) chiziqli vaqtni talab etadi. Agar ikkilik qidiruvdan foydalanilsa, u holda (Ο(log₂(n))) yozuvlar soniga logarifmik bog’liq bo’ladi.
Biz O – funksiya bilan ko’proq kuzatuvlar olib boramiz. Keyingi kuzatishlarda algoritmlarning murakkabligi yuqori asimptotik chegara bilan beriladi.
Asimptotik tahlilning muhim qoidalari:

O(k*f) = O(f) – doimiy ko’payuvchi k (konstanta) tashlab yuboriladi, chunki doimiy kirish ma’lumotlarining ortishi bilan uning ahamiyati yo’qoladi, masalan: