Hisoblash modellari, algoritmlar va ularning murakkabligi Algoritm tushunchasi. Avvalo algoritm

1) Algoritmlarning klassik nazariyasi (rasmiy tillar nuqtai nazaridan masalalarni shakllantirish, yechuvchanlik muammosi tushunchasi, murakkablik sinflarini kiritish, P = NP (?) masalasini shakllantirish, NP-ning toʻliq masalalarini sinfi va uni oʻrganish);
2) Algoritmlarni asimptotik tahlil qilish nazariyasi (algoritmning murakkabligi tushunchasi, algoritmlarni baholash kriteriyalari, asimptotik baholarni olish usullari, xususan, rekursiv algoritmlar uchun, murakkablikni yoki bajarilish vaqtini asimptotik tahlil qilish);
3) Hisoblash algoritmlarini amaliy tahlil qilish nazariyasi (funksiyalarning intervalli tahlili, algoritmlar sifatining amaliy mezonlari, ratsional algoritmlarni tanlash metodikasi).
Algoritmlar nazariyasida hal qilingan maqsad va vazifalar:
- "algoritm" tushunchasini formallashtirish (rasmiylashtirish) va formal (rasmiy) algoritmik tizimlarni oʻrganish;
- muammolarning algoritmik yechimini rasmiy tasdiqlash;
- vazifalarni tasniflash, murakkablik sinflarini aniqlash va tadqiq qilish;
- algoritmlarning murakkabligini asimptotik tahlil qilish;
10
- rekursiv algoritmlarni oʻrganish va tahlil qilish;
- algoritmlar sifatini qiyosiy baholash mezonlarini ishlab chiqish.
1.1. Algoritm tushunchasini formallashtirish
1-ta‟rif. Algoritm - bu ma‘lum bir tilda berilgan, mumkin boʻlgan dastlabki ma‘lumotlar sinfi uchun masalani hal qilish uchun mumkin boʻlgan elementar amallarning cheklangan ketma-ketligi.
Masalaning dastlabki ma‘lumotlarining toʻplami D boʻlsin va R - mumkin boʻlgan natijalar toʻplami, shunda algoritm 𝐃 → 𝐑 koʻrinishida tasvirlanadi. Bu tasvirlanish toʻliq boʻlmasligi mumkin.
Agar natija faqat ba‘zi 𝑑 ∈ 𝐷 uchun olingan boʻlsa, algoritm qismiy algoritm va agar barcha 𝑑 ∈ 𝐷 uchun toʻgʻri natija olsa toʻliq algoritm deyiladi.
2-ta‟rif. Algoritm - bu cheklangan vaqt ichida masalani yechish natijasiga erishish uchun ijrochining harakatlari tartibini tavsiflovchi aniq koʻrsatmalar toʻplami.
Algoritmning aniq yoki bilvosita turli xil ta‘riflari bir qator talablarni keltirib chiqaradi:
- algoritmda cheklangan miqdordagi elementar bajarilishi mumkin boʻlgan ketma-ketlik boʻlishi kerak, ya‘ni yozuvning aniqligi talabi bajarilishi kerak;
- algoritm masalani yechishda cheklangan sonli bosqichlarni bajarishi kerak, ya‘ni harakatlarning aniqligi talabi bajarilishi kerak;
- barcha qabul qilingan kirish ma‘lumotlari uchun algoritm bir xil boʻlishi kerak, ya‘ni universallik talabiga javob berish;
- algoritm qoʻyilgan vazifaga nisbatan toʻgʻri yechimga olib kelishi kerak, ya‘ni toʻgʻrilik talabi bajarilishi kerak.