sexta-feira, 21 de agosto de 2009

Função Ackermann

Uma das mais importantes funções na ciência da computação. Sua maior propriedade é que ela cresce surpreendentemente rápido pois esta função eleva seu retorno rapidamente para números muito grandes, denominados números Ackermann e que normalmente são representados em uma notação inventada por Donald Knuth, a notação "up-arrow" ou notação de Knuth.

A função Ackermann foi descoberta e estudada por Wilhelm Ackermann em 1928. A função que ele descobriu, que então recebeu seu nome, é um simples exemplo de uma função total e bem definida que pode ser computável mas não é uma recursão primitiva. "Total e bem definida" significa que a função é internamente consistente e não quebra as regras das instruções que a define. "Computável" significa que ela pode, em princípio, ser avaliada por todos os valores possíveis em suas variáveis. "Recursão primitiva" significa que pode ser computada usando somente laços for, repetindo a operação em um número de vezes predeterminado. A função Ackermann somente pode ser calculada usando o laço de repetição while, que repete a ação até que o teste da condição retorne falso.

A função Ackermann é definida recursivamente para números inteiros não negativos, m e n, como:

          n + 1                  se m = 0
A(m, n) = A(m - 1, 1) se m > 0 e n = 0
A(m - 1, A(m, n - 1)) se m > 0 e n > 0


Dois inteiros positivos, m e n, são a entrada e A(m ,n) é a saída sendo outro inteiro positivo. A função pode ser programada facilmente em apenas poucas linhas de código. O problema não é a complexidade da função mas sua terrível taxa de crescimento. Por exemplo uma inocente entrada A(4,2) retorna um número de 19.729 dígitos:

A(0, n) = n + 1
A(1, n) = 2 + (n + 3) - 3
A(2, n) = 2 × (n + 3) - 3
A(3, n) = 2^(n + 3) - 3
A(4, n) = 2^(2^(...^2)) - 3 (n + 3 números dois)
A(5, n) = 2^(2^(...^2))^(2^(2^(...^2)))^(...^(2^(2^(...^2)))) - 3

Por isso o uso de uma grafia especial para números grandes como a notação de Knuth é indispensável, como mostra o exemplo abaixo:

A(4, n) = 2^^(n + 3) - 3
A(5, n) = 2^^^(n + 3) - 3

Como podem perceber, a função Ackermann estabelece adições iterativas e multiplicações iterativas, efetuando potências dentro de potências, recursivamente (potências iterativas). Alguns resultados da função Ackermann para as entradas m e n são mostrados abaixo:

                             n
0 1 2 3 4 5
0 1 2 3 4 5 6
m 1 2 3 4 5 6 7
2 3 5 7 9 11 13
3 5 13 29 61 125 253
4 13 65533 2^65536 -3 2^2^65536 -3 ...
5 65533 ...


O código para a função Ackermann é bastante simples, abaixo dois exemplos em java que aplicam a função:

public static long acker(long m, long n) {
if(m == 0) {
return n + 1;
} else if(n == 0) {
return acker(m-1, 1);
} else {
return acker(m-1, acker(m, n-1));
}
}


Ou:

public static long acker(long m, long n) {
return (m == 0) ? (n + 1) : ((n == 0) ? acker(m-1, 1) : acker(m-1, acker(m, n-1)));
}


A função Ackermann devido a sua característica de recursão extremamente profunda pode ser usada como teste de medida da capacidade de um compilador otimizar a recursão.

Veja mais em:

http://mathworld.wolfram.com/AckermannFunction.html
http://rosettacode.org/wiki/Ackermann_Function
http://planetmath.org/encyclopedia/AckermannFunction.html
http://kosara.net/thoughts/ackermann.html

Um comentário:

  1. Fico doida com essa função!
    "Antes de aprender recursividade, é preciso aprender recursividade."

    ResponderExcluir