Kirish. Hisoblash modellari, algoritmlar va ularning murakkabligi
―Algoritm - bu belgilaydigan cheklangan qoidalar toʻplami, muayyan vazifalar toʻplamini hal qilish boʻyicha amallar ketma-ketligi . (D. E. Knut)
―Algoritm - bu belgilaydigan cheklangan qoidalar toʻplami, muayyan vazifalar toʻplamini hal qilish boʻyicha amallar ketma-ketligi . (D. E. Knut)
―Algoritm - bu qat‘iy belgilangan qoidalar asosida bajariladigan har qanday hisoblash tizimidir, bu ma‘lum bir qator bosqichlardan soʻng, aniq qoʻyilgan masalani hal qilishga olib keladi" (A. Kolmogorov).
―Algoritm - bu har xil boshlangʻich ma‘lumotlardan kerakli natijaga oʻtadigan hisoblash jarayonini belgilaydigan aniq ketma-ketlik" (A. Markov).
Algoritmning asosiy xossalari haqida quyidagilarni ta‘kidlash mumkin:
Algoritmning asosiy xossalari haqida quyidagilarni ta‘kidlash mumkin:
1 xossa. Diskretlilik, ya‘ni algoritmni chekli sondagi oddiy koʻrsatmalar ketma-ketligi shaklida ifodalash mumkin.
2. xossa. Tushunarlilik, ya‘ni ijrochiga tavsiya etilayotgan koʻrsatmalar uning uchun tushunarli boʻlishi shart, aks holda ijrochi
oddiy amalni ham bajara olmay qolishi mumkin. Har bir ijrochining bajara olishi mumkin boʻlgan koʻrsatmalar tizimi mavjud.
3.xossa. Aniqlik, ya‘ni ijrochiga berilayotgan koʻrsatmalar aniq mazmunda boʻlishi lozim hamda faqat algoritmda koʻrsatilgan tartibda bajarilishi shart.
4.xossa. Ommaviylik, ya‘ni har bir algoritm mazmuniga koʻra bir turdagi masalalarning barchasi uchun yaroqli boʻlishi lozim. Masalan, ikki oddiy kasr umumiy maxrajini topish algoritmi har qanday kasrlar umumiy maxrajini topish uchun ishlatiladi.
5.xossa. Natijaviylik, ya‘ni har bir algoritm chekli sondagi qadamlardan soʻng albatta natija berishi lozim.Bu xossalar mohiyatini oʻrganish va konkret algoritmlar uchun qarab chiqish talabalarning xossalar mazmunini bilib olishlariga yordam beradi.
Algoritmning tasvirlash usullari haqida gapirganda algoritmning berilish usullari xilma-xilligi va ular orasida eng koʻp uchraydiganlari quyidagilar ekanligini koʻrsatib oʻtish joiz:
Algoritmning tasvirlash usullari haqida gapirganda algoritmning berilish usullari xilma-xilligi va ular orasida eng koʻp uchraydiganlari quyidagilar ekanligini koʻrsatib oʻtish joiz:
Algoritmning soʻzlar orqali ifodalanishi.
Algoritmning formulalar yordamida berilishi.
Algoritmning jadval koʻrinishida berilishi, masalan, turli matematik jadvallar, lotereya yutuqlari jadvali, funksiyalar qiymatlari jadvallari bunga misol boʻladi.
Algoritmning dastur shaklida ifodalanishi, ya‘ni algoritm kompyuter ijrochisiga tushunarli boʻlgan dastur shaklida beriladi.
Cheklangan xotira resurslaridan foydalangan holda oqilona vaqt ichida yechilishi kerak. Bu algoritmning vaqt va fazoviy murakkabligi tushunchasiga olib keladi. Qoida tariqasida, algoritm turli vaqtlarni bajarishi mumkin boʻlgan turli xil amallarni oʻz ichiga oladi.
Algoritmlarni baholash uchun koʻpgina mezonlar mavjud. Odatda kirituvchi berilganlarni koʻpayishida masalani yechish uchun kerak boʻladigan vaqt va xotira hajmlarini oʻsish tartibini aniqlash muammosi qoʻyiladi.
O (n) - chiziqli murakkablik. Bunday murakkablik, masalan, saralanmagan massivdagi eng katta elementni topish algoritmiga ega. Qaysi biri maksimal ekanligini aniqlash uchun massivning barcha n elementlaridan oʻtishimiz kerak boʻladi.
O (n) - chiziqli murakkablik. Bunday murakkablik, masalan, saralanmagan massivdagi eng katta elementni topish algoritmiga ega. Qaysi biri maksimal ekanligini aniqlash uchun massivning barcha n elementlaridan oʻtishimiz kerak boʻladi.
O (log n) - logaritmik murakkablik. Eng oddiy misol - ikkilik qidirish. Agar massiv saralangan boʻlsa, uni yarmiga boʻlish orqali ma‘lum bir qiymatga ega ekanligini tekshirishimiz mumkin. Oʻrta elementni tekshirib koʻramiz, agar u kattaroq boʻlsa, unda massivning ikkinchi yarmini tashlab yuboramiz. Agar kichikroq boʻlsa, unda aksincha - biz dastlabki yarmini tashlaymiz va shu tarzda ikkiga boʻlinishni davom ettiramiz, natijada (logn) elementlarini tekshiramiz.
O (n2) - kvadratik murakkablik. Bunday murakkablik, masalan, element qoʻshilishi natijasida yangi saralash algoritmiga ega. Kanonik dasturda bu ikkita ichki sikldan iborat: biri butun massivni bosib oʻtish, ikkinchisi esa allaqachon ajratilgan qismdan keyingi element uchun joy topish. Shunday qilib, amallar soni n*n, ya‘ni n2 kabi massiv oʻlchamiga bogʻliq boʻladi.
