Usos da função de Ackermann?

Question

Em nossas matemática discreta do curso em minha universidade, o professor mostra seus alunos a Ackermann função e atribuir ao aluno desenvolver a função em papel.

Além de ser um ponto de referência para a otimização de recursão, faz a função de Ackermann tem quaisquer usos reais?

Answer 1

Sim. O (inverso) função de Ackermann aparece na análise complexidade dos algoritmos. Quando isso acontece, significa que você quase pode ignorar esse termo desde que cresce tão lentamente (muito como log (log ... log (n) ...)) ou seja lg * (n). Por exemplo: Minimum Spanning Trees (também aqui ) e Disjoint Set construção floresta.

também: Davenport-Scinzel sequências

Answer 2

O "uso" original da função de Ackermann foi mostrar que existem funções que não são recursiva primitivo, isto é, que não pode ser calculado utilizando apenas para loops com limites superiores predeterminados.

A função de Ackermann é tal função, ela cresce muito rápido para ser recursiva primitiva.

Eu não acho que há usos muito práticos, ela cresce rápido demais para ser útil. Você não pode mesmo representar explicitamente os números além de um (4,3) em um espaço razoável.

Answer 3

Eu concordo com a outra resposta (por wrang-wrang) "em teoria".

Na prática Ackerman não é muito útil, porque na prática as únicas complexidades algoritmo que tendem a encontro envolvem 1, N, N ^ 2, N ^ 3, e cada um desses multiplicado por logN. (E já que logN é nunca mais do que 64, é efetivamente um termo constante de qualquer maneira.)

O ponto de ser, "na prática", a menos que a sua complexidade algoritmo é "N vezes muito grande", você não se preocupam com a complexidade, porque os fatores do mundo real irá dominar. (Uma função que executa em O (inverso do Ackermann) é teoricamente melhor do que uma função que executa em tempo O (log N), mas na prática, você vai medir as duas implementações reais em relação aos dados do mundo real e selecione Qualquer que seja realmente executa melhor . em contraste, a teoria da complexidade que "importa na prática" para, por exemplo N contra N ^ 2, onde os efeitos da complexidade algorítmica de fato Overpower quaisquer efeitos "mundo real". Acho que "N" é o menor medida que importa na prática .)