Algoritm va uning intuitiv, formal va kibernetik ta’riflari

Rekursiv hisoblash algoritmlari va rekursiv funksiyalar

Rekursiya deb funksiya tanasida shu funksiyaning o‘zini chaqirishiga aytiladi. Rekursiya ikki xil bo‘ladi:

oddiy – agar funksiya o‘z tanasida o‘zini chaqirsa; vositali – agar birinchi funksiya ikkinchi funksiyani chaqirsa, ikkinchisi esa o‘z navbatida birinchi funksiyani chaqiradi.
Odatda rekursiya matematikada keng qo‘llaniladi. Chunki aksariyat matematik formulalar rekursiv aniqlanadi. Misol tariqasida faktorialni hisoblash formulasini va sonning butun darajasini hisoblashni ko‘rishimiz mumkin:


Algoritm tushunchsini shakllantirish Tyuring
mashinasi
Algoritmlarning ko’p misollari bilan boshlang’ich sinflardan boshlab to’qnashamiz. Avval bu turli sonlar ustida to’rta arifmetik amallarni bajarilishi, natural, butun, kasr, kompleks sonlar ustida shunday amallarni bajarilishi.Mashhur alforitmlad Evklid algoritmi, ikkita natural sonlarning eng kata umumiy bO’luchisini toppish, turli tartibli determinantlarni echish, ratsional lementli matritsalarning ranglarinin hisoblashtenlamalarning taqribiy echimlarinin toppish.v.h.z. Tyuring mahinasi. Tyuring mashinasi bu matematik tasavvur etiladigan mashina bo’lib, fizik mashina eas. U funktsiya, integral v.h.z. kabi bitta tushunchadir.
Markovning normal algoritmlari

1954 yildа ruch mаtеmаtigi А.А. Mаrkоv Tyuring mаshinаsidаgi kаbi so’zlаrni qayta ishlоvchi аlgоritmik sхеmаni tаklif etdi. Bu sхеmа аsоsini butunlаy bоshqа prinsiplаr tаshkil etаdi. Bu yerda lеntа tushunchаsi mаvjud emаs vа qayta ishlаnuvchi so’zning turli qismlаrigа bеvоsit murоjааt etish ko’zda tutilаdi. А.А.Mаrkоv ushbu аlgоritmik sхеmаni nоrmаl аlgоritm dеb аtаdi:

Binar izlash usuli
Aytaylik bizga tartiblangan n ta elementdan iborat arr[] massiv berilgan bo'lsin, va berilgan x ni arr[] ichidan qidirish funksiyasini tuzish sharti qo'yilsin.Bu holatda eng oson yo'l sifatida chiziqli qidiruvni misol keltirish mumkin. Ammo bu usulning vaqt davomiyligi O(n) ni tashkil qiladi. Xuddi shu vazifa uchun biz binar qidir algoritmini ishlatsak bo'ladi.
Binar qidiruvQiyinlik darajasi: 5/10.Eng zo'r ko'rsatkichi(vaqt): O(1)Eng yomon ko'rsatkichi(vaqt): O(log n)O'rtacha ko'rsatkichi(vaqt): O( log n)Binar qidiruvning asosiy g'oyalaridan biri ketma-ket ikkiga bo'lishga asoslanadi, ya'ni berilgan x ni massivning o'rtadagi elementi bilan solishtiradi, agar katta bo'lsa oxiri va o'rtasi orasidagi massivni oladi, agar kichkina bo'lsa boshi va o'rtasi orasidagi massivni oladi, va har safar shu jarayon takrorlanib boradi toki x element solishtirilayotgan massivning elementga teng bo'lgunicha yoki massivning elementlari qolmaguncha.