Algoritm so`zi va tushunchasi IX asrda yashab ijod etgan buyuk

1.3.2. Tarmog`lanuvchi algoritmlar. 
Biror shartning bajarilishi bilan bog`liq ravishda tuziladigan algoritmlarga 
tarmog`lanuvchi algoritmlar deyiladi. Tarmog`lanuvchi algoritmlar hisoblashlar 

ketma-ketligini aniqlaydigan shartlarni o`z ichiga oladi. Blok-sxema ko`rinishida 

bu shuni bildiradiki, blok-sxemada hech bo`lmaganda bitta romb ishtirok etadi. 
Masalan: ko`chaga qanday kiyimda chiqishimiz ob-havoga, avtomatdan sharbatli 
yoki mineral suv ichishimiz esa unga qancha so`mlik “jeton” tashlashimizga 
bog`liqdir. Yuqorida keltirilgan “Svetofor” algoritmi ham tarmog`lanuvchi 
algoritmga misoldir. 
1.3.3. Takrorlanuvchi (siklik) algoritmlar. 
Ma'lum bir shart asosida algoritmda bir necha marta takrorlanish yuz beradigan 
jarayonlar ham ko`plab uchraydi. Masalan, yil fasllarining har yili bir xilda 
takrorlanib kelishi, har haftada bo`ladigan darslarning kunlar bo`yicha takrorlanishi 
va hokazo. Demak, takrorlanuvchi algoritmlar deb shunday algoritmlarga 
aytiladiki, unda bir yoki bir necha amallar ketma-ketligi bir necha marta 
takrorlanadi, bu ketma-ketlik tarmog`lardan iborat bo`lishi ham mumkin. Bundan 
chiziqli va tarmog`lanuvchi algoritmlar takrorlanuvchi algoritmlarning xususiy holi 
ekanligi kelib chiqadi. 
Masalan:Natural sonlarning yig`indisini topish algoritmi-takrorlanuvchi algoritmga misol bo`la oladi. Haqiqatan ham, yig`indi quyidagicha hisoblanishi mumkin
3. 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.
A
Matematik nuqtai nazardan ushbu masshtablash modelini quyidagicha shakllantirish mumkin. Aytaylik, algoritm quyidagi xususiyatga ega: c> 0 va d> 0 absolyut konstantalar mavjudki, har qanday N xajmli kirish ma'lumotlari to'plami uchun, bajarilish vaqti cN^d sondagi eng sodda operatsiyalar soni bilan chegaralanadi. Boshqacha qilib aytganda, bajarilish vaqti N^d ga proportsionallikdan ko’p emas. Qanday bo'lmasin, ba'zi bir c va d lar uchun bajarilish vaqti ushbu chegaradan oshmaganda, algoritm polinomial bajarilish vaqtini ta'minlaydi deymiz yoki u polinomial vaqtga ega bo'lgan algoritmlar toifasiga kiradi. polinomial vaqtga ega har qanday chegara yuqoridagi masshtablashga ega bo’ladi.
(3)T: Agar algoritm polinomial bajarilish vaqtiga ega bo'lsa, u samarali deb ataladi.
Lekin, polinomial vaqt d ning katta qiymatlarida yaxshi natija bermasligi mumkin, masalan d>=100 holatda bu son juda katta bo’ladi, natijada polinomial bajarilish vaqti kattalashib ketadi. Algoritm ishlayveradi. Bu xolda N^d faqat chegara vazifasini o’taydi.

4.Ko‘phadlar qiymatlarini hisoblashda Gorner sxemasi

Xorner Uilyam Jorj (1786 - 1837), ingliz matematikasi. Asosiy tadqiqot algebraik tenglamalar nazariyasi bilan bog'liq. Har qanday darajadagi tenglamalarni taxminiy yechish metodikasi ishlab chiqilgan. 1819 yilda u polinomni (Horner sxemasi) binomiallariga bo'lishning algebra uchun muhim usulini kiritdi.