Usos de la función de Ackermann?

Question

En nuestro curso de matemáticas discretas en mi universidad, el maestro muestra a sus alumnos la función Ackermann y asigne al alumno para desarrollar la función en papel.

Además de ser un punto de referencia para la optimización de la recursividad, ¿la función Ackermann tiene algún uso real?

Answer 1

Sí La función (inversa) de Ackermann aparece en el análisis de complejidad de algoritmos. Cuando lo hace, significa que casi puede ignorar ese término ya que crece muy lentamente (muy parecido a log (log ... log (n) ...)), es decir, lg * (n). Por ejemplo: Árboles de expansión mínima (también aquí ) y Conjunto disjunto construcción forestal.

También: secuencias Davenport-Scinzel

Answer 2

El original "uso" de la función de Ackermann fue mostrar que hay funciones que no son primitivas recursivas, es decir, que no pueden calcularse utilizando solo bucles con límites superiores predeterminados.

La función de Ackermann es tal función, crece demasiado rápido para ser primitiva recursiva.

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 un (4,3) en un espacio razonable.

Answer 3

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 sueles encontrar son 1, N, N ^ 2, N ^ 3 y cada una de ellas multiplicada por logN. (Y dado que logN nunca es más de 64, de todos modos es efectivamente un término constante).

El punto es, "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 (inverso-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 contra datos del mundo real y seleccionará el que realmente funcione mejor Por el contrario, la teoría de la complejidad sí importa en la práctica, por ejemplo, N contra N ^ 2, donde los efectos de la complejidad algorítmica dominan de hecho cualquier efecto del mundo real. Me parece que "N" es la medida más pequeña que asuntos en la práctica.)