En nuestro discreto curso de matemáticas en mi universidad, el maestro muestra a sus alumnos el Ackermann function y asigna al alumno para desarrollar la función en papel.¿Usos de la función de Ackermann?
Además de ser un punto de referencia para la optimización de la recursividad, ¿la función de Ackermann tiene algún uso real?
Sí. La función (inversa) de Ackermann aparece en el análisis de complejidad de los algoritmos. Cuando lo hace, significa que casi puede ignorar ese término, ya que crece muy lentamente (muy parecido a logaritmo (log ... log (n) ...)), es decir, lg * (n). Por ejemplo: Minimum Spanning Trees (también here) y Disjoint Set construcción forestal.
también: Davenport-Scinzel sequences
Específicamente el algoritmo de búsqueda de unión si desea un ejemplo. http://www.yucs.org/~gnivasch/alpha/index.html – Joshua
Pero es el inverso de la función, ¿qué pasa con la función real? –
Estoy de acuerdo con la otra respuesta (por wrang-wrang) "en teoría".
En la práctica, Ackerman no es demasiado útil, porque en la práctica las únicas complejidades de algoritmo que suele encontrar involucran 1, N, N^2, N^3, y cada uno de ellos multiplicado por logN. (Y como logN nunca es más de 64, de hecho es un término constante.)
El punto es que "en la práctica", a menos que la complejidad de su algoritmo sea "N veces demasiado grande", no le importa la complejidad , porque los factores del mundo real dominarán. (Una función que se ejecuta en O (inversa-Ackermann) es teóricamente mejor que una función que se ejecuta en tiempo O (logN), pero en la práctica, medirá las dos implementaciones reales con datos del mundo real y seleccionará la que tenga un mejor rendimiento Por el contrario, la teoría de la complejidad "importa en la práctica", por ejemplo, N frente a N^2, donde los efectos de complejidad algorítmica dominan los efectos del "mundo real." Encuentro que "N" es la medida más pequeña que importa en la práctica .)
De hecho, el análisis teórico solo le proporciona la base para el análisis del rendimiento. –
¿Puede explicar cómo logN nunca es más de 64? –
Por lo general, el "registro" es la base 2. Si el registro (n) es 64, significa que tiene 2^64 elementos de datos. Eso es mucho más de lo que tendrías en la práctica; de hecho, en una computadora de 64 bits tiene punteros de 64 bits, por lo que no puede representar fácilmente más de 2^64 bytes. – Andrey
El "uso" original de la función de Ackermann era mostrar que hay funciones que no son primitivas recursivas, es decir, que no se pueden calcular utilizando solo bucles con límites superiores predeterminados.
La función de Ackermann es una función tal, crece demasiado rápido para ser recursivo primitivo.
No creo que haya usos realmente prácticos, crece demasiado rápido para ser útil. Ni siquiera puede representar explícitamente los números más allá de (4,3) en un espacio razonable.
https://en.wikipedia.org/wiki/Hyperoperation – starblue