Page 52 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

= 3+2(3+2(3+2(3+...2,A(3,0)))…) //A(3,0)=A(2,1)=2(1)+3=5

= 3+2(3+2(3+2(3+...2(5)))))…)

Se observa que se tiene un anidamiento con una profundidad x (desde x-1 hasta 0).

Abriendo un paréntesis, primero entenderemos la siguiente operación algebraica equivalente a A(3,x)
para comprender el comportamiento de la anidación:

x(y+x(y+x(y+xz))) = x(y+x(y+xy+x z)) = x(y+xy+ x y+ x z) = xy+ x y+ x y+ x z
2
3
2
3
4
2
Por lo tanto,
A(3,x) = 3+3*2+3*2 +3*2 +3*2 +...+ 5*2 x
2
3
4
= 3(2 +2 +2 +2 +...+2 ) +5*2
3
x-1
2
0
1
x
= 3(2 -1) + 5*2 x
x
= 3*2 -3+5*2 x
x
= 8*2 -3
x
= 2 *2 -3
x
3
= 2 x+3 - 3
El valor de A(3,x) se utilizará para obtener

A(4,x) =A(3, A(4,X-1))

obteniéndose como resultado x potencias sucesivas de 2.

Algunos valores interesantes de la función de Ackermann son:
A(0,0) = 1 A(0,n) = n+1;

A(1,0) = 2

A(1,n) = n+1

A(2,0) = 3

A(2,n) = 2n+3

A(3,0) = 5

A(3,1) = 13

46