Ackermann 기능의 사용?

Question

우리 대학의 개별 수학 과정에서 교사는 그의 학생들에게 Ackermann 기능 그리고 학생에게 종이에 기능을 개발하도록 할당하십시오.

재귀 최적화의 벤치 마크 외에도 Ackermann 기능은 실제 사용이 있습니까?

Answer 1

예. (역) Ackermann 함수는 알고리즘의 복잡성 분석에서 나타납니다. 그렇다면, 그것은 너무 느리게 자라기 때문에 그 용어를 거의 무시할 수 있음을 의미합니다 (log (log ... log (n) ...)), 즉 lg*(n). 예를 들어: 최소 스패닝 나무 (또한 여기) 그리고 분리 세트 산림 건축.

또한: Davenport-Scinzel 서열

Answer 2

Ackermann 함수의 원래 "사용"은 원시적 재귀가 아닌 함수가 있음을 보여주는 것이 었습니다. 즉, 미리 정해진 상한이있는 루프에만 사용하여 계산할 수없는 기능이 있습니다.

Ackermann 함수는 이러한 기능이며 원시 재귀가 되기에는 너무 빠르게 자랍니다.

나는 실제로 실용적인 용도가 있다고 생각하지 않고 너무 빨리 자라서 유용합니다. 합리적인 공간에서 A (4,3)를 넘어 숫자를 명시 적으로 표현조차 할 수 없습니다.

Answer 3

나는 "이론에서"다른 대답 (Wrang-Wrang)에 동의합니다.

실제로 Ackerman은 너무 유용하지 않습니다. 실제로 만난 유일한 알고리즘 복잡성에는 1, n, n^2, n^3이 포함되며 각각은 logn으로 곱해지기 때문입니다. (그리고 Logn은 64 세를 넘지 않기 때문에 어쨌든 효과적으로 일정한 용어입니다.)

알고리즘 복잡성이 "N 배 너무 큰"경우, 실제 요소가 지배적이기 때문에 복잡성에 신경 쓰지 않는 요점은 "실제로"입니다. (O (verse-ackermann)에서 실행되는 함수는 이론적으로 O (LOGN) 시간에 실행되는 기능보다 이론적으로 우수하지만 실제로는 실제 데이터에 대한 실제 구현을 측정하고 실제로 더 나은 성능을 선택하는 것을 선택할 수 있습니다. 대조적으로, 복잡성 이론은 예를 들어 N^2에 대해 "실제로"문제가되는데, 여기서 알고리즘 복잡성 효과는 실제로 "실제"효과를 압도한다. 나는 "n"은 실제로 중요한 측정치라는 것을 알게된다. .))