Algoritm, uning xossalari. Qismiy rekursiv formulalar

Algoritm, uning xossalari. Qismiy rekursiv formulalar Reja : Algoritm tushunchasi. Algoritmning A.N.Kolmogorov tomonidan kirsatilgan xarakterli xususiyatlari. Algoritmga misollar. Bir tipli, bir xil mazmunga ega bilgan masalalarni bir xil usulda yechish algoritm deyiladi. Yagona algoritm yordamida echiladigan bir xil tipli masalalar ommaviy problema deyiladi. Algoritmning ommaviyligi uning asosiy xususiyatlaridan biridir. Щar bir algoritm =andaydir mi=dorlarni boshlanich sistemasi ustida ish boshlaydi shamda diskret rejimda ishlab shar bir navbatdagi va=t momentida (oraliida) mi=dorlarning sistemasini malum bir =onun (programma)ga asosan mi=dorning yangi sistemasiga itkazadi. Shunday =ilib, algoritm mi=dorlarni ketma-ket =urish jarayonidir. Algoritmning uchinchi xususiyati uning bir =iymatli ani=lanuvchanligi, yani algoritmning ishlash jarayonida =andaydir va=t momentida (boshlanich momentidan bosh=a) hosil =ilingan mi=dorlar sitemasi oldingi va=t momentlarida shosil =ilingan mi=dorlar sistemasi or=ali bir =iymatli ani=lanadi. Bazan algoritm biror obyektlar ustida ishlaganda boshlanich mi=dorlarning sistemasidan keyingi sistemalariga itish usuli natija bermaydi. Bunday holda nimani algoritmning natijasi deb hisoblanishi kirsatilishi kerak. Bu esa algoritmning yinalganlik xossasidir. Algoritmik jarayonning bazi bir sholatlari (yoki sholati) oxirgi sholat bilib, bu sholatlar algoritmning natijasini beradi. Algoritmni biror obyektga =illanilganda algoritmik jarayon =uyidagi uchta yildan borishi mumkin: 1. Algoritmning ishlash jarayonida bir sholat ikkinchi sholat bilan almashinadi va bu jarayon shech =achon tugamaydi. 2. Algoritmik jarayonning biror =adamidan sing shunday sholat yuz beradiki, shosil bilgan obyekt (yoki obyektlar sistemasi) ga bevosita =ayta ishlash =onunini =illab bilmaydi va algoritm shech =anday natija bermay tixtaydi. 3. Algoritm chekli =adamda biror natija berib iz ishini tixtatadi. Matematikada ,odatda, shartlarga butun =iymatli chekli sondagi x1, . . . ,xn , argumentlarga boli= bilgan masalalarning algoritmini topish talab etiladi. Bu (x1, . . . , xn) butun =iymatli funksiya =iymatini shisoblaydigan algoritmni topish demakdir. qiymati malum bir algoritm yordamida shisoblanuvchi sonli funksiya shisoblanuvchi funksiya deyiladi. Ammo shisoblanuvchi funksiya tushunchasida algoritm tushunchasi ani=lanmaganligi (ta'riflanmaganligi) uchun shisoblanuvchi funksiya tushunchasini sham ta'riflash mumkin emas. 30 - yillarda algoritm tushunchasini oekursiv funksiyalar yordamida ani=lash mumkin ekanligini (gipoteza sholida) amerikalik matematiklar A.Chyorch, K.Gyodel, S.Klinilar kirsatdilar. Agar X tiplamning bazi elementlariga U tiplamning bir =iymatli ani=langan elementlari mos =iyilgan bilsa, X tiplamda =ismiy rekursiv funksiya berilgan deyiladi. Adabiyotlar : 1. Yo=ubov T.,Kallibekov S. Matematik manti= elementlari.T.,1996. 2. Novikov P.S. Elementi matematicheskoy logiki.M.1973. 3. Chyorch A. Vvedenie v matematicheskuyu logiku.M.,1960. 4. Maltsev A.I. Algoritmi i rekursivnie funktsii.M.,1965. 5. LavrovI.A., Maksimova L.L. Zadachi po teorii mnojestv,matematicheskoy logike i teorii algoritmov.M.,1975. ...