Mavzu: Algoritmlarni murakkablik darajalasining tahlili, murakkablik darajasini baholash usullari Reja

2-Mustaqil ish
Mavzu: Algoritmlarni murakkablik darajalasining tahlili, murakkablik darajasini baholash usullari
Reja:
1.Algoritmlarni tahlil qilishning asosiy maqsadi
2.Algoritmning samaradorligi
3. Algoritmning murakkablik darajasi va ularni baholash
Algoritmlarni tahlil qilishning asosiy vazifasi kirish ma'lumotlari hajmining oshib borishi bilan resurslarga bo'lgan talabni (vaqt va xotira xarajatlari) o'lchash usullarini aniqlashdir. Shundan so'ng, o'sish sur'ati qonuniyatlarini tavsiflash uchun zarur bo'lgan matematik mexanizm ishlab chiqiladi. Kirish ma'lumotlari hajmini oshirish bilan turli xil funktsiyalar; "bitta funktsiya boshqasiga qaraganda tezroq o'sadi" iborasi nimani anglatishini aniqlab olishga yordam beradi. Ba'zi hollarda, yaxshi bajarilish vaqtiga erishish yanada murakkab ma'lumotlar tuzilmalaridan foydalanishga bog'liq va bo'lim oxirida biz bunday ma'lumotlar strukturasining juda foydali misolini ko'rib chiqamiz: ustuvor navbatlar va ularni uyum(kucha, heap) asosida amalga oshirish.
Asosiy maqsad - hisoblash muammolarining samarali algoritmlarini izlash. Ushbu umumiylik darajasida kompyuterni hisoblashning butun sohasi ushbu mavzu bilan bog'liq bo'lib tuyuladi; bizning yondashuvimiz boshqalardan qanday farq qiladi? Algoritmlarni ishlab chiqishda umumiy mavzular va loyihalash tamoyillarini aniqlashga harakat qilamiz. Bizni samarali algoritmlarni loyihalashning asosiy usullarini minimal ma'lumot bilan namoyish etuvchi paradigmatik masalalar va usullar qiziqtiradi.
Algoritmni bajarilish qadami - bu ijrochi tomonidan bitta ko‘rsatmaning bajarilishidir. Bir masalani hal etuvchi ikkita algoritmdan kam qadam talab qilinayotgani samaraliroqdir. Samaradorlik o‘lchovi - bu bor-yo‘g‘i qadamlar sonidir. Lekin chuqurroq e’tibor berib qarasak, bu ta’rifdagi mujmal tomonlarni aniqlaymiz. Ba’zan avval uchragan algoritmlardagidan ko‘ra vaziyat murakkabroq bo’ladi.
Algoritmlar murakkabligi bilan ham farqlanishi mumkin. Algoritmning murakkabligini uning matnidagi satrlar soni bilan o‘lchaymiz. Shu bilan birga quyidagi ikki satrni bir tuzilmaning ikki qismi bo‘lgani uchun bittaga hisoblaymiz
Algoritmlarni tahlil qilishning asosiy vazifasi kirish ma'lumotlari hajmining oshib borishi bilan resurslarga bo'lgan talabni (vaqt va xotira xarajatlari) o'lchash usullarini aniqlashdir. Shundan so'ng, o'sish sur'ati qonuniyatlarini tavsiflash uchun zarur bo'lgan matematik mexanizm ishlab chiqiladi. Kirish ma'lumotlari hajmini oshirish bilan turli xil funktsiyalar; "bitta funktsiya boshqasiga qaraganda tezroq o'sadi" iborasi nimani anglatishini aniqlab olishga yordam beradi. Ba'zi hollarda, yaxshi bajarilish vaqtiga erishish yanada murakkab ma'lumotlar tuzilmalaridan foydalanishga bog'liq va bo'lim oxirida biz bunday ma'lumotlar strukturasining juda foydali misolini ko'rib chiqamiz: ustuvor navbatlar va ularni uyum(kucha, heap) asosida amalga oshirish.
Ko'plab muammolarda uchraydigan yana bir xususiyat - bu ularning asosan diskretligi. Ko'plab muammolarda uchraydigan yana bir xususiyat-bu ularning asosiy ajralib turishi. Boshqacha qilib aytganda, bu shunday masalalarki, ularda yechim kombinatorial variantlarning keng to'plamidan qidirib topiladi; maqsad aniq belgilangan shartlarni qanoatlantiradigan echimni samarali topishdir.
Hisoblash samaradorligi tushunchasini aniqlash uchun, biz birinchi navbatda ish vaqtining samaradorligiga e'tibor qaratamiz: algoritmlar tez ishlashi kerak. Ammo algoritmlar boshqa resursrlardan foydalanish nuqtai nazaridan ham samarali bo'lishi mumkinligini tushunish muhimdir. Xususan, algoritm tomonidan ishlatilinadigan xotira miqdori ham samaradorlikning muhim jixati bo'lishi mumkin.
Algoritm samaradorligi.
(1)T: algoritm samarali deb ataladi agar real kirish ma'lumotlari uchun u tezkor amalga oshirilsa.
(2)T: algoritm samarali deb ataladi agar u sifatli bajarilishni “to’liq qidirish”(полнiy перебор)ga nisbatan tezroq ta'minlasa.
"To'liq qidirish" usuliga qaraganda ancha yaxshi ishlashni ta'minlaydigan algoritmlar, deyarli har doim qimmatli evristik g'oyani o'z ichiga oladi, buning natijasida ushbu yaxshilanishga erishiladi; Bundan tashqari, ular ko'rib chiqilayotgan masalaning ichki tuzilishi va hisoblash qobiliyati haqida foydali ma'lumotlarni taqdim etadilar.
Polinomial vaqt samaradorlik ko'rsatkichi sifatida
Tabiiy kombinatorial masalalarda qidirish vaqti, kirish ma'lumotlari N hajmiga nisbatan eksponensional o'sishga moyildir; agar o'lcham bittaga ko'paysa, unda imkoniyatlar xajmi bir necha marta ko'payadi. Bunday masalalarni yechish uchun yaxshi algoritm yanada samarali miqyoslash modeliga ega bo'lishi kerak; kirish ma'lumotlarining kattalashib borishi bilan o’zgarmas ko’paytuvchiga(aytaylik, ikki baravar) oshishi bilan algoritmning bajarilish vaqti ham qandaydir o’zgarmas S ko’paytuvchiga ko'payishi kerak.
Misollar:
1. Ikkita haqiqiy a va b sonlari berilgan bo´lsin. Ularning o’rta arifmetig va o’rta geometrigini toping
C++ dagi kodi
NATIJA: #include
#include


using namespace std;


int main()
{
float a,b;
cout<<"Birinchi sonni kiriting: ";cin>>a;
cout<<"Ikkinchi sonni kiriting: ";cin>>b;
float ARIFMETIK=(a+b)/2;
float GEOMETRIK=sqrt(a*b);
cout<<"ARIFMETIK: "< cout<<"GEOMETRIK: "< return 0;
}

2. Uchburchak tomonlarining uzunligi bilan berilgan. Uchburchakka ichki r va tashqi R chizilgan aylanalar radiuslarini hisoblang.Ichki chizilgan aylana radiusi r = (a+b+c)/2S, tashqi chizilgan aylana4S radiusi R= formulalar orqali hisoblanadi. Bu yerda S - uchburchakning yuzi, a, abc b, c – uchburchak tomonlarining uzunliklari. Masala echimining blok-sxemasi

#include
#include
using namespace std;
int main()
{ float a,b,c;
cin>>a>>b>>c;
p=(a+b+c)/2;
S=sqrt(p*(p-a)*(p-b)*(p-c));
R=4*S/a*b*c;
r=(a+b+c)/2*S;
cout< cout< return 0;
}

3. Kvadratning tomoni a berilgan. Uning perimetri aniqlansin. P=4*a

#include
int main()
{
float a,P;
cin>> a;
P:=4*a;
cout<<"P=" <