tradukoj: en ru

rekursi/o KompLeks

rekursio  

MATKOMP Tia maniero difini funkcion aŭ komputan proceduron, ke la difinato eventuale povas referenci sin mem: senfina rekursio (ekz-e kaŭzita de cirkla difino).
SUB:rikuro1
Rim.: Kaj „rekursio“, kaj „rikuro“ etimologie signifas „retroiro“, t.e. reveno al la antaŭe komputitaj valoroj de iu vico por komputi la sekvan. Pri la termino „rekursio“ tiu koncepto ne plu validas: rekursia komputo povas anticipe ekzameni ankaŭ siajn „postajn“ valorojn, eĉ plenumi elĉerpan serĉon tra ili. Tion oni neniam faras en la klasika matematiko, por kies bezonoj plene sufiĉas rikuro, koncepto logike pli sekura. [Sergio Pokrovskij]

rekursia  

MATKOMP Uzanta rekursion, karakterizata de rekursio: rekursia proceduro (programlingva proceduro2 kiu eventuale vokas sin mem dum la rultempo); SUB:rikura1

rekursia funkcio  

MAT Unu el la matematikaj precizigoj de la intuicia koncepto pri komputeblo. Oni reduktas ĉiujn komputajn problemojn al naturnombraj funkcioj3 Nⁿ→N, kaj konstruas hierarkion el 3 subklasoj: primitive rekursiaj funkcioj, ĉieaj rekursiaj funkcioj, μ-rekursiaj funkcioj. La lasta klaso estas la plej ĝenerala, ĝi entenas la du aliajn kaj reprezentas ĉiujn komputeblajn funkciojn. Se oni diras simple „rekursia funkcio“, tiam oni celas ĝuste tiun ĉi klason: simbole la hierarkion de la rekursiaj funkcioj eblas prezenti per la formulo PRF⊂ĈRF⊂MRF; estas pruvite, ke la klaso da rekursiaj funkcioj, la klaso da funkcioj difineblaj per Turinga aŭtomato, per λ-kalkulo, per la Markovaj ĉenoj estas ĉiuj egalaj.

primitive rekursia funkcio, PRF  

MAT La difino estas rikura1.b: oni difinas la bazan klason kaj du operatorojn. La bazaj funkcioj estas: la konstanta funkcio O(x)=0; la alkremento S(x)=x+1; la projekcioj Pr[m,n](x1,…xn)=xm, 1≤m≤n. La operatoroj estas la kunligo2 kaj la primitiva rekursiilo. Primitive rekursia funkcio estas baza primitive rekursia funkcio aŭ rezulto de finifoja apliko de la operatoro(j): S(S(x)) estas primitive rekursia funkcio ĉar ĝi estas kunligo de du alkrenentoj (ĝi ĵetas x→x+2); ĉiuj primitive rekursiaj funkcioj estas ĉieaj funkcioj; pliopo da nombroteoriaj funkcioj estas primitive rekursiaj funkcioj.

primitiva rekursiilo  

MAT Operatoro uzata en la difino de primitive rekursia funkcio, simila al nombrila iteracio; la formala difino estas rikura1.b. Estu f funkcio n-loka, kaj g funkcio n+2-loka; tiam apliko de primitiva rekursiilo al la paro da funkcioj (f,g) estas tia n+2-loka funkcio h, ke baze: h(x1,…,xn,0)=f(x1,…,xn); kaj rikure: h(x1,…,xn,y+1) = g(x1,…,xn,y,h(x1,…,xn,y)). Estu f(x)=Pr[1,1](x)=x kaj g(x,y,z)= S(Pr[2,3](x,y,z))=S(y). Tiam h(0,x) = x kaj h(S(y),x) = g(y,h(y,x),x) = S(h(y,x)). Sekve h(0,1)=1, h(1,1)=S(h(0,1))=2, h(2,1)=S(h(1,1))=3. Do, h estas 2-loka primitive rekursia funkcio, nome „adicio“.

μ-rekursia funkcio, MRF, parta rekursia funkcio  

MAT Funkcio difinta per la samaj rimedoj, kiel la primitive rekursiaj funkcioj, plus la μ-operatoro de senbara serĉo: ĉar la minimumigo povas diverĝi, tial ne ĉiuj μ-rekursiaj funkcioj estas ĉieaj; ankaŭ nenie difinitaj (ĉie diverĝaj) funkcioj estas partaj rekursiaj funkcioj.

ĉiea rekursia funkcio, ĈRF  

MAT μ-rekursia funkcio kiu estas ĉiea funkcio: ĉiu PRF estas ĉiea rekursia funkcio; ekzistas ĉieaj rekursiaj funkcioj kiuj ne estas primitive rekursiaj.

tradukoj

anglaj

~o: recursion; ~a: recursive; ~a funkcio: recursive function; primitive ~a funkcio, PRF: primitive recursive function; primitiva ~ilo: primitive recursion; μ-~a funkcio, MRF, parta ~a funkcio: partial recursive function, >(μ-)recursive function; ĉiea ~a funkcio, ĈRF: total recursive function. senfina ~o: infinite recursion; ~a proceduro: recursive procedure.

rusaj

~o: рекурсия; ~a: рекурсивный; ~a funkcio: рекурсивная функция; primitive ~a funkcio, PRF: примитивно-рекурсивная функция; primitiva ~ilo: оператор примитивной рекурсии; μ-~a funkcio, MRF, parta ~a funkcio: частично рекурсивная функция; ĉiea ~a funkcio, ĈRF: общерекурсивная функция. senfina ~o: бесконечная рекурсия; ~a proceduro: рекурсивная процедура.

fontoj

~o: Mankas dua fontindiko.
~o: Mankas fonto, kiu estas nek vortaro nek terminaro.
~a: Mankas dua fontindiko.
~a: Mankas fonto, kiu estas nek vortaro nek terminaro.
~a funkcio: Mankas dua fontindiko.
~a funkcio: Mankas fonto, kiu estas nek vortaro nek terminaro.
primitive ~a funkcio, PRF: Mankas dua fontindiko.
primitive ~a funkcio, PRF: Mankas fonto, kiu estas nek vortaro nek terminaro.
primitiva ~ilo: Mankas dua fontindiko.
primitiva ~ilo: Mankas fonto, kiu estas nek vortaro nek terminaro.
μ-~a funkcio, MRF, parta ~a funkcio: Mankas dua fontindiko.
μ-~a funkcio, MRF, parta ~a funkcio: Mankas fonto, kiu estas nek vortaro nek terminaro.
ĉiea ~a funkcio, ĈRF: Mankas dua fontindiko.
ĉiea ~a funkcio, ĈRF: Mankas fonto, kiu estas nek vortaro nek terminaro.


ℛevo | datumprotekto | rekursi.xml | redakti... | traduki... | artikolversio: 1.4 2018/11/24 15:10:14