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

Algoritmo para solução da Torre de Hanói

A Torre de Hanói é um quebra-cabeça matemático que consiste em três hastes e um número de três ou mais discos de diferentes tamanhos para serem dispostos nas hastes. O problema está em passar todos os discos de uma haste para outra, usando uma terceira haste como auxiliar, de maneira que um disco maior nunca fique em cima de outro menor e movendo um disco por vez. O nível de dificuldade mais fácil é com três discos apenas.

O número mínimo de movimentos para conseguir transferir todos os discos da primeira haste para a haste final é 2^n -1, sendo n o número de discos. Por exemplo para solucionar uma Torre de Hanói com 7 discos são necessários 127 movimentos.

Existem soluções para este problema com o uso de algoritmos iterativos, mas geram um código muito extenso visto que algoritmos recursivos são bem mais fáceis de serem compreendidos pois são compactos. Entretanto por usarem intensivamente a pilha, os algoritmos recursivos tendem a ser mais lentos que os iterativos.

Vejamos então um exemplo de algoritmo recursivo:

Função resolveHanoi(Inteiro discos, String origem, String destino, String auxiliar) {
 Se (discos > 0) {
 resolveHanoi(discos-1,origem,auxiliar,destino);
 Imprime("Mover disco " + discos + " de " + origem + " para " + destino);
 resolveHanoi(discos-1,auxiliar,destino,origem);
 }
}

A função é chamada com:

resolveHanoi(3,"haste inicial","haste final","haste auxiliar");

Este algoritmo imprime na tela toda a seqüência de movimentos para a solução do problema. A função é chamada pela primeira vez com parâmetros determinando o número total de discos e quais são as hastes inicial, final e auxiliar.

Para a solução, os movimentos realizados pelo algoritmo estão separados em três estágios. O primeiro estágio move os n-1 discos superiores para a haste auxiliar, o segundo move o último e maior disco para a haste final e finalmente o terceiro estágio move os n-1 discos superiores para a haste final.

Com o uso da recursão, dentro do primeiro e do terceiro estágio, são realizados novamente os três estágios com a pilha de n-1 discos, avançando recursivamente sempre no primeiro e terceiro estágios até que se chegue no menor disco.

A seqüência dos discos movidos para uma torre com três discos é 1-2-1-3-1-2-1. A representação gráfica desta solução é semelhante ao Triângulo de Sierpinski, que é uma figura geométrica obtida através de um processo recursivo.

Sugestão de website: Hanoimania!