6.Recursivitate_2012

1RECURENTA VERSUS ITERATIE

Facultatea de Matematica si Informatica,

Universitatea din Bucuresti

7 aprilie 2012

2Noiunea de algoritm = notiune primar.Exist descrieri i proprieti:

Un algoritm const dintr-o mulime finit de pai, fiecare necesitnduna sau mai multe operaii.

Pentru a fi implementate pe un calculator, ntr-un anumit limbaj deprogramare, aceste operaii trebuie s fie:

definite;

efective.

Caracteristicile algoritmilor

corectitudinea;

finititudinea:;

generalitatea;

completitudinea;

claritatea.

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recuren i iteraie in programare






Studiul algoritmilor cuprinde mai multe aspecte (1):Elaborarea algoritmilor.

Tehnici de elaborare (reguli) + creativitate (intuiie) = soluie

Exprimarea algoritmilor

- scheme logice, limbaje de tip pseudocod, programe in diferite

limbaje de programare.

- se impune utilizarea unui anumit stil de programare (legat nu de un

anumit limbaj de programare, ci de tipul limbajului i de modul deabordare)






Studiul algoritmilor cuprinde mai multe

aspecte (2):

Validarea algoritmilor (demonstrarea

matematica a corectitudinii, independent de

implementare).

Analiza algoritmilor. (in general: timpul de

calcul i/sau la memoria necesar)

Testarea programelor :

(i) depanarea (debugging) Cf. E.W.

Djikstra, prin depanare putem evidentia

prezenta erorilor dar nu si absenta lor!

(ii) verificare (profiling)






Incercarea de definire (decada 1930-1940):

Sunt propuse diverse formalisme pentru

notiunea de algoritm:

Functiile -calculabile (Alonzo CHURCH iStephen Cole KLEENE);

Masinile Turing (Alan TURING);

Functiile general recursive (Kurt GDEL);

Sistemele Post, inclusiv masina Post-Turing

(Emil Leon POST);

Algoritmii normali Markov (N.N. MARKOV)

Toate teoriile: echivalente

Teza Church-Turing (cele 2 variante)

6Lambda calculul

O -functie este definit de o lambda-expresie careexprim aciunea funciei n argumentele ei.

Exemple: funcia f(x)=x+2: x. x + 2 .

numrul f(3): ( x. x+ 2) 3






7Masina Turing

a b a b

unitate de

control






9Maina Turing

Un sistem ( , , Q, q0, F, ) unde:

este o mulime finit, nevida numit alfabet de intrare;

este o mulime finit, nevida numit alfabetul benzii;

, i ;

Q este o mulime finit, nevida numit mulimea strilormasinii;

q0 Q este starea iniial;

F Q este mulimea strilor finale (de acceptare sau derespingere);

: Q x Q x x { L , R } este funcia de tranziie, unde Ldenota deplasarea la stnga iar R denota deplasarea ladreapta a cursorului masinii.






10






Stephan Cole KLEENE: "The Theory of Recursive

Functions, Approaching its Centennial", Bulletin (New

Series) of the American Mathematical Society, Vol. 5,

No. 1, July 1981:

"prini" teoriei funciilor recursive (inafara lui Kurt Gdel iKleene nsui) sunt considerai a fi:

Leopold Kronecker, prin conferina inut pe 21 sept. 1886 n faa Der Deutschen Naturforscherversammlung zu Berlin (Asociaia pentru Cercetarea Naturii), cf. H. Weber, Leopold

Kronecker, Math. Ann. 43 (1893), 1-25

Julius Wilhelm Richard Dedekind (18311916), prin Teorema 126 ("Satz der Definition durch

Induktion") din articolul "Was sind und was sollen

die Zahlen? (Ce sunt i ce ar trebui sa fie numerele)" publicat n 1888 si prin Definitia 71

(care contine defiinitia axiomatica a N i.e.

axiomele Dedekind-Peano)

11

Exemple de functii primitiv recursive:

a+0 = a

a+succ(x) = succ(a+x)

a 0 = 0

a succ(x) = a x+a

a 0 = 1

a succ(x) = a x a

unde succ(x)=x+1 .






12

Recurenta primitiva

Fie funciile : g : N n N , h : N n+2 N ;

se cere s se construiasc funcia

f : N n+1 N

care s satisfac urmtoarele dou ecuaii :

(1) f(a1 ,a2 ,, an ,0) = g(a1 ,a2 ,, an) ,

(2) f(a1 ,a2 ,, an , x+1) = h(a1 ,a2 ,, an , x , f(a1 ,a2 ,, an , x)) .

Spunem c f este definit prin recuren primitiv asupra lui x dinfunciile g i h , prin intermediul a n>=0 parametri a1 ,a2 ,, an .

Convenim ca n cazul n=0 s notm prin g o constant numrnatural.






13






Compunerea functionala

Fie n , m dou numere naturale.

Se dau m+1 funcii de n argumente:

h : N m N , g i : Nn N , 1 i m

Funcia

f : N n N

este definit prin compunere funcional din funciile h , g1 , g2 ,, gmdac i numai dac:

f(x1 ,x2 ,, xn ) = h (g1(x1 ,x2 ,, xn ), g2(x1 ,x2 ,,xn ),,gm(x1 ,x2 ,, xn))

Un caz particular de compunere functionala:

subtitutia (m=1)

14

f(a1 ,a2 ,, an ,0) = g(a1 ,a2 ,, an) ,f(a1 ,a2 ,, an , x+1) = h(a1 ,a2 ,, an , x , f(a1 ,a2 ,, an , x)) .

f(x1 ,x2 ,, xn ) = h(g1(x1 ,x2 ,, xn ), g2(x1 ,x2 ,,xn ),,gm(x1 ,x2 ,, xn ))

Exemplul 1:sum(a,x) = a+x,

=> n=1, a1=a

=> sum (a,0) = a+0 = a => g(a) = a = p1(1)(a) ,

sum(a,x+1)=a+(x+1)=(a+x)+1

=>h(a,x,y)=succ(sum(a,x))=succ(p3(3)(a,x,sum(a,x))).

=> sum(a,0)=p1(1)(a) ,

sum(a,x+1)=h(a,x,sum(a,x)) , unde h:N3 N , h(a,x,y)=(succ0p3(3))(a,x,y).

Exemplul 2:|x-y| = max(0,x-y)+max(0,y-x),

=> |x-y|= max(0, P(2)1 (x,y)-P(2) 2(x,y)) + max(0, P (2) 2(x,y)-P(2)1(x,y)).

15






Exemplul 3:

O funcie general recursiv: funcia Ackermann-Peter:

int ack(int m, int n)

{

if (0==m) return n+1;

if (0==n) return ack(m-1,1);

return ack(m-1,ack(m,n-1));

}

altfelnmackmack

nmack

mn

nmack

)),1,(,1(

0),1,1(

0,1

),(

16






Exemplul 4 (Conjectura lui Collatz, 1937)

Se d irul de numere a0 ,a1 ,,an , definit priniteraia pur:

Pentru orice numr natural a exist un index n astfelnct

an=1

Verificata pe calculator pana la 20 258 5.764 1018

.,13

,,2/1

0

altfela

paresteadacaaa

aa

n

nnn

17






Functia lui COLLATZ :

este definita prin:

f(n)= n/2, daca n este par,

f(n)= 3*n+1, daca n este impar

i are urmatoarele propretati:

lungimea secventei de numere generata in vederea atingerii valorii 1 unse poate calcula pintr-o formula bazata pe datele de intrare

tinde catre 1.

Se cere sa se scrie un program care sa citeasca o pereche de valori naturale nenule,reprezentand primul si ultimul numar intr-o secventa inchisa de numere naturale.

Pentru fiecare astfel de secventa inchisa, se cere sa se deteremine valoarea caregenereaza cea mai lunga serie cu functia de mai sus, inainte de a ajunge la 1.

Cea mai mare valoare din secventa si din sirul transformarilor nu va depasi tipul long.

http://gfredericks.com/math/Arith/collatzPage.html

18






#include

long int length (long int n)

{

long int aux=1;

if (n%2) n=n*3+1; else n/=2;

while(n-1){

if (n%2) n=n*3+1; else n/=2;

aux++;

}

return aux;

}

void main ()

{

long int n,m,max,l,i;

cin>>n>>m; max=0; l=-1;

for (i=n; il) {

max=i; l=length(i);

}

cout

19






Mulimea funciilor de baz

este format din:

funcia succesor succ : N N , succ(x)=x+1

funciile constante ca(n): N n N , ca

(n) (x1 ,x2 ,, xn )=a

funciile proiecie pi(n): N n N , pi

(n) (x1 ,x2 ,, xi ,, xn )= xi ,

unde a , n , m N , 1 i n, 1jn.

20






Clasa funciilor primitiv recursive

este cea mai mic familie de funcii f : N n N , n>=1,care

conine mulimea funciilor de baz i

este nchis fa de operaiile de

compunere funcional i

recuren primitiv.

Dedekind (1888) i Peano (1889),

Skolem: (1923),

Gdel (1931),

Peter (1934).

21






Urmtoarele funcii si predicate sunt primitiv recursive:

a) f:N 2N , f(x,y)=x+y

b) f:N 2N , f(x,y)=x*y

c) f:N 2N , f(x,y)=xy , (x0=1)

d) pd:NN , pd(x)=max(0,x-1)

e) f:N 2N , f(x,y)=max(0,x-y) , (diferena aritmetic)

f) sg:NN , sg(0)=0 , sg(x)=1, x>0 ,

g) f:N2N , f(x,y)=|x-y| , (modulul)

h) sqrt:NN ,

i) ls,gr,eq:N 2{0,1}, ls(x,y)=1, daca xy, gr(x,y)=0, altfel

eq(x,y)=1, daca x=y, eq(x,y)=0, altfel

xxsqrt )(

22






Scheme de recuren speciale:

recurena ereditar

recurena simultan

23






Schema de recuren ereditar

Exemplu:

Considerm irul lui Fibonacci:

u0=u1=1 ,

un+2=un+1+un.

24






Limbajul Borland Pascal

{fib1.pas : implementarea rec. }

function Fib (n: integer): integer;

{returneaza al n-lea termen din

sirul lui Fibonacci, n0}

begin

if (n

25






Limbajul Borland Pascal

{fib2.pas: implementarea iterativa}

function Fib (n: integer): integer;

var crt, old, older : integer;

begin

old : = 1; older : = 0;

while (n > 1) do

begin

crt : = old +older;

older : = old;

dec(n)

end;

end;

Limbajul C/C++

// fib2.cpp : implementarea iterativa

long Fib (long n)

{

if (n1)

{

crt = old +older;

older = old;

}

return crt;

}

26






Definitie

Fie x0, x1,, xk N. Numarul natural

se numeste numrul Gdel asociat irului (x0, x1,,x k) ise noteaz cu .

Exemple: = 233152 = 600,

= 21325075 = 2898918

Definiie:

Funcia f:Nn+1 N se obine prin recuren ereditar din funciileg : Nn N i h : Nn+2 N dac:

f(x ,0) = g(x) ,

f(x ,y+1) = h(x ,y ,) ,

unde xNn iar desemneaza numarul Gdel asociatsirului f(x,0), ,f(x,y).

kx

kpx

px

pn ...110

0

27






Teorem:

Clasa funciilor primitiv recursive este nchis fa derecurena ereditar.

Corolar:

Funcia f: N N, f(n) = un este primitiv recursiv.

28






Schema de recuren simultanExemplu:

Considerm ecuaia lui Pell:

x2-dy2=1, unde x,y N , a>1, d=a2-1.

Propoziie:

Perechea (x,y) N 2 este o soluie pentru ecuaia lui Pelldac exist un numr n0 astfel nct

x = xn , y = yn , unde :

x0 = 1, y0 = 0 ,

xn+1 = a.xn + d

.yn ,

yn+1 = xn + a.yn , x 0 .

29






program rec_indirecta;

var a,d,n: integer;

function y (n: integer): integer; forward;

function x (n: integer): integer;

begin

if n=0 then x:=1

else x:=a*x(n-1)+d*y(n-1)

end; {x}

function y (n: integer): integer;

begin

if n=0 then y:=0

else y:=x(n-1)+a*y(n-1)

end; {y}

begin {programul principal}

writeln ('dati constanta a > 1 si ordinul solutie n = '); readln (a,n);

d := a *a - 1;

writeln ('perechea de solutii de ordinul ',n,' este: (',x(n):4,' , ',y(n):4,').');

readln;

end.

30






Definiie:

Funciile fi : Nn+1 N, (i=1,2) sunt definite prin recuren simultan

din funciile gi : Nn N i hi : N

n+3 N (i=1,2) dac

fi(x,0)=gi(x),

fi(x,y+1)=hi(x, f1(x,y), f2(x,y)) , (i=1,2).

Teorem:

Clasa funciilor primitiv recursive este nchis fa de recurenasimultan.

Corolar:

Funciile f1,f2: N N, f1(n) = xn, f2(n)=yn sunt primitiv recursive.

31

Conceptul de subprogram de tip funcie cu apel recursiv.

Forma general a unui subprogram de tip funcie recursiv:

function f()

{

calcul initial;

conditie de oprire;

apel recursiv f();

calcul final;

return rezultat;

}






32






Tipuri de subprograme recursive

(1) bazate pe funcii (primitiv) recursive unare, (funcia se apeleaz pe ea nsi n moddirect, ca n cazul calculrii factorialului);

(2) bazate pe funcii (primitiv) recursive de mai multe argumente (ca n cazul calculriicmmdc pentru dou numere naturale);

acestea sunt cunoscute sub numele de recursivitate liniar direct:

int cmmdc1 (int x, int y)

{ if (x==y) return x;

else

if (x>y) return cmmdc1(x-y, y);

else return cmmdc1(x, y-x);

}

int cmmdc2 (int x, int y)

{if (0==y) return x;

else

return cmmdc2(y, x%y);

}

33






(3) bazate pe funcii care se apeleaz una pe alta (recursivitateasimultana, numita si recursivitate indirect), ca in cazul calculariisolutiilor ecuatiei lui Pell: x2-dy2=1, unde x,y N , a>1, d=a2-1),

int x(int n)

{

if (n==0) return 1;

return a*x(n-1)+d*y(n-1);

}

int y(int n)

{

if (n==0) r eturn 0;

return x(n-1)+a*y(n-1);

}

34






(4) bazate pe funcii care au nevoie de mai multe valori anterioare pentrua calcula valoarea curent (recursivitatea ereditara, numita sirecursivitatea neliniar sau n cascad), ca n cazul determinrii unuielement al irului lui Fibonacci dup formula:

int fibonacci (int n)

{

if (n

35

Un subprogram recursiv trebuie s respecte urmtoarelereguli:

1. subprogramul trebuie s poat fi executat, cel puin ntr-osituaie, fr a se autoapela;

2. subprogramul recursiv se va autoapela ntr-un mod n care se

tinde spre ajungerea n situaia de execuie fr autoapel.

Pentru a permite apelarea recursiv a subprogramelorlimbajele de programare dispun de mecanisme speciale

de suspendare a execuiei programului apelant,

de salvare a informaiilor necesare i

de reactivare a programului suspendat.











36

Pentru implementarea recursivitii se folosete o stiv.

La fiecare apel recursiv al unuisubprogram se salveaz n stiv stareacurent a execuiei sale (adresa derevenire i contextul programului).

Stiva implicita = zona de memorie

n care se poate face salvarea

temporar a unor valori, organizat dup principiul LIFO

Adresa de revenire = adresa

instruciunii cu care va continua programul ntrerupt la reluarea

execuiei sale

Context = valorile variabilelor locale

subprogramului, valorile parametrilor

de tip valoare i adresele parametrilor de tip referin

37

Dei variabilele locale ale subprogramului apelat au aceiaiidentificatori cu cei ai subprogramului apelant, orice referire la

aceti identificatori se asociaz ultimului set de variabile alocaten stiv.

Zona din stiv rmne alocat pe tot parcursul execuieisubprogramului apelat i se dealoc n momentul revenirii nprogramul apelant.

Stiva nu este gestionat explicit de programator ci de ctrelimbaj.

La terminarea execuiei subprogramului apelat recursiv sereface contextul programului din care s-a fcut apelul.






38

Datorit faptului c la fiecare autoapel se ocup o zon destiv, recursivitatea este eficient numai dac numrul deautoapeluri nu este mare, astfel nct s nu se ajung n situaiaumplerii stivei.

Recursivitatea ofer avantajul unor soluii mai clare pentruprobleme i unei lungimi mai mici a programelor.

Ea prezint ns dezavantajul unui timp mai mare de execuiei a unui spaiu de memorie ocupat mai mare.






39

Ce se ntmpl la autoapelul funciei/procedurii?

Prin autoapelul funciei/ procedurii instruciunilermn neschimbate.

Procedura/funcia va prelucra datele transmise n stiv.

In cazul unui nou autoapel, se creeaz un nou nivelpentru stiv, n care se depun noile valori.

Procedura/funcia care s-a autoapelat se reia de lainstruciunea care urmeaz autoapelului i va lucra cuvariabilele (valorile) reinute n stiv n momentulautoapelului, la care se adaug valorile returnate.

La atingerea unuia dintre cazurile de baz (condiia deoprire), urmeaz s se revin din autoapelri.






40






Demonstrarea corectitudinii algoritmilor recursivi:

se face intr-un mod similar demonstrarii corectitudinii

algoritmilor nerecursivi;

este mult simplificat de forma algoritmului (care permite utilizarea comod a metodei induciei matematice complete):

se verific mai nti dac toate cazurile particulare (de terminare a apelului recursiv) funcioneaz corect;

se trece apoi la o verificare formal, prin inducie, a funciei recursive corespunztoare, pentru restul cazurilor.

41






Exemplificare: calculul factorialului unui numr

int factorial (int n)

{

if (0==n) return 1;

return n*factorial(n-1);

}

Demonstrarea corectitudinii: doi pasi:

pentru n = 0, valoarea 1 returnat de program este corect;

dac n>1 atunci, presupunnd corect valoarea returnatpentru (n-1), prin nmulirea acesteia cu n se obine valoareacorect a factorialului numrului natural n, valoare returnat desubprogram.

n ambele situaii este satisfcut condiia de oprire.

42

Algoritmul cutrii binare: un exemplu algoritm proiectat prinaplicarea tehnicii recursivitatii si a metodei divide-et-impera:

Fie a1, a2, , an un ir ordonat de n numere naturale (nN,n2) si fie x un numar natural, dat . Se cere sa severifice daca numarul x se afla printre elementele sirului.

Metoda:

se injumatateste intervalul [[a1, an]] si se caut x n jumtateacea mai apropiat de valoarea acestuia;

urmeaza divizarea recursiv a acestei jumtii n alte dou jumtimai mici i reluarea procedeului pana la gasirea elementului saupana cand domeniul cautarii devine vid.






43

LIMBAJUL C++

// bs.cpp: algoritmul recursiv de cautarebinara

int BinarySearch (float *arr, int n, float x,

int btm, int top)

{

if ( top>=btm )

{ int mid=(top+btm)/2;

if (arr[mid]==x)

return mid; //cautare cu succes

if (arr[mid]

44

LIMBAJUL BORLAND PASCAL

{ bs.pas: algoritmul recursiv de cautare binara }

function BinarySearch (arr:real; n: integer; x:real;

btm, top:integer) : integer;

var mid : integer;

begin

if (( top>=btm ) then

begin

mid : = (top+btm) div 2;

if (arr[mid] = x) then BinarySearch : = mid;

if (arr[mid]

45

Ridicarea unui numr real x la o putere n natural, xn binare: unalt exemplu algoritm proiectat prin aplicarea tehnicii

recursivitatii si a metodei divide-et-impera:

Metoda clasic de ridicare la putere este multiplicarea sa cu el nsuIde n-1 ori, iar algoritmul este de complexitate O(n).






46

Tehnica divide-et-impera: se poate obine un algoritm cu complexitate:

O(log(n)).

Strategia se bazeaz pe urmtoarele proprieti ale puterilor ntregi:

Se observ cum valorile lui n scad, pn cnd atinge unul dintrecazurile de baz.






impar esten daca , x x4)par esten daca , x x3) x x2) 1 x1) 1-nn22n1 0 xn

Cazurile care reprezint

cazurile de baz ale recursivitii.

Cnd n este par se

calculeaz mai nti xn-1

i apoi se multiplic rezultatul cu x.

Cnd n este impar se

multiplic x cu el nsui (x2) i apoi rezultatul se ridic recursiv la puterea n/2.

47

LIMBAJUL BORLAND PASCAL

{pow1.pas functia putere recursiva }

function Power(x:real; n :integer): real;

begin

if (n=0) then power:=1;

if (n=1) then power:=x;

if odd ( n) then

Power:=Power(x,n-1)*x; {n impar}

Else Power:=Power(x*x, n/2); {n par}

end;

LIMBAJUL C++

//pow1.cpp functia putere recursiva

float Power(float x, int x)

{

if (n==0) return 1;

if (n==1) return x;

if (n&1)

return Power(x,n-1)*x; //n impar

else return Power(x*x, n/2); //n par

}

impar esten daca , x x4)par esten daca , x x3) x x2) 1 x1) 1-nn22n1 0 xn

48

1. se definete o stiv i se initializeaz cumulimea vid;

2. ct timp este ndeplinit condiia decontinuare a recursivitii:3. se execut instruciunile dinainte de

apel;

4. se salveaza pe stiv valorile actuale cereprezint argumentele funcieirecursive;

5. se execut instruciunile funcieirecursive;

6. se modific argumentele funcieirecursive;

7. cnd condiia nu mai este indeplinit idac stiva este nevid atunci8. se aduce de pe stiva un set de variabile,

9. se executa o serie de calcule (cele dedup apelul recursiv) i

10. se trece la pasul 3.

11. dac stiva este vid algoritmul se oprete.

void print_rec()

{

int c = getch ();

if (c!=\n) { print_rec(); printf(%c,c);}

}

void print_it ()

{

Stack S;

empty (S);

int c = getch ();

while (c!=\n) { push(c); c = getch();}

while (nevida(S)) {c=pop (S);

printf (%c,c);}}






Pentru a tranforma o funcie recursiv ntr-o funcie iterativ:

49

Exista o legatura stransa intrerecursivitate si structurile de date de tip stiva, arbore, etc folosite in limbajele Borland Pascal si C++ pentru reprezentarea functiilor / procedurilor recursive (insasidefinitia stivelor, arborilor, listelorrealizandu-se recursiv).

Deseori, variantele iterative necesita folosirea explicita a structurii de tip stiva, generandastfel un cod extrem de laborios. In aceste situatii se considerasolutia recursiva mai eleganta, datorita simplitatii sale.

Recursivitatea trebuie inlocuitaprin iteratie atunci candrecursivitatea este prea adancasau cand limbajul de programarenu permite implementarea de apeluri recursive.

Din punctul de vedere al memorieisolicitate, o varianta recursivanecesita un spatiu de stivasuplimentar pentru fiecare apelfata de varianta iterativa.

Dimensiunea stivei trebuie aleasaastfel incat sa poata permitememorarea elementelor pentrutoate iteratiile.






Avantajele si dezavantajele utilizarii subprogramelor recursive

50

Greseli tipice in realizarea subprogramelor recursive (1):

1. Declararea ca variabile globale a unor variabile care

controleaza adresa de revenire (cazul cand apelurile se

fac din interiorul unei structuri repetitive).

2. Declararea ca parametri transmisi prin valoare sau ca

variabile locale a unor date structurate (de exemplu de tip

tablou) micsoreaza semnificativ adancimea acceptata a

recursivitatii, deoarece memorarea lor necesita un spatiu

mare de memorie.






51

Greseli tipice in realizarea subprogramelor recursive (2):

4. Absenta unei conditii de oprire.

5. Exprimarea unei conditii de oprire in care nu intervin nici

variabile locale si nici parametrii transmisi prin valoare sau

prin referinta ai subprogramului.

6. Marirea dimensiunii problemei prin transmiterea in cadrul

autoapelurilor a unor parametri actuali care nu tind sa se

aproprie de valorile impuse prin conditia de oprire.

7. Neutilizarea directivei forward (limbajul Borland Pascal) in

cazul declararii unor subprograme indirect recursive






52






BIBLIOGRAFIE1. Rzvan ANDONIE, Ilie GARBACEA: Algoritmi

fundamentali. O perspectiv C++, Editura Libris, Cluj-Napoca, 1995.

2. Cristian Sorin CALUDE: Theories of Computational Complexity, Elsevier Science Publ., Amsterdam, 1988.

3. Richard JOHNSONBAUGH, Marcus SCHAEFER: Algorithms, Pearson Prentice Hall, Upper Saddle River, NJ., 2004.

4. D. JOYCE: The Dedekind/Peano Axioms, Clark University, posted on January 2005, http://aleph0.clarku.edu/~djoyce/numbers/peano.pdf

5. Dexter C. KOZEN: Theory of Computation, Springer-Verlag, Berlin Heidelberg, 2006.

6.Recursivitate_2012

Documents

Transcript of 6.Recursivitate_2012