Функция Акермана: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Функция Акермана''' (''Ackermann's function'') - Функция <math>A</math>, индуктивно заданная ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Функция Акермана''' (''Ackermann's function'') - | '''Функция Акермана''' (''[[Ackermann's function]]'') - | ||
Функция <math>A</math>, индуктивно заданная на парах неотрицательнх целых чисел | Функция <math>A</math>, индуктивно заданная на парах неотрицательнх целых чисел | ||
<math> | <math> | ||
\begin{array}{c} | \begin{array}{c} | ||
| Строка 8: | Строка 10: | ||
\end{array} | \end{array} | ||
</math> | </math> | ||
где <math>m, n \geq 0</math>. Следовательно, | где <math>m, n \geq 0</math>. Следовательно, | ||
<math> | <math> | ||
\begin{array}{c} | \begin{array}{c} | ||
| Строка 16: | Строка 22: | ||
\end{array} | \end{array} | ||
</math> | </math> | ||
Высокая рекурсивность этой функции используется для проверки | Высокая рекурсивность этой функции используется для проверки | ||
способности компиляторов выполнять рекурсию. Эта функция, названная в | способности компиляторов выполнять рекурсию. Эта функция, названная в | ||
| Строка 25: | Строка 33: | ||
где <math>A</math> определено, как показано выше. Для нее имеем | где <math>A</math> определено, как показано выше. Для нее имеем | ||
<math> | <math> | ||
\begin{array}{c} | |||
\mbox{Ack}(0) = 1, \\ | \mbox{Ack}(0) = 1, \\ | ||
\mbox{Ack}(i) = 2^{\mbox{Ack}(i-1)}\mbox{ для }i > 0. | \mbox{Ack}(i) = 2^{\mbox{Ack}(i-1)}\mbox{ для }i > 0. | ||
\end{array} | \end{array} | ||
</math> | </math> | ||
Определим теперь функцию <math>G(n)</math> как наименьшее целое число <math>k</math>, для | Определим теперь функцию <math>G(n)</math> как наименьшее целое число <math>k</math>, для | ||
которого <math>\mbox{Ack}(k) \geq n</math>. Функция <math>G</math> растет очень медленно. | которого <math>\mbox{Ack}(k) \geq n</math>. Функция <math>G</math> растет очень медленно. | ||
Действительно, <math>G(n) \leq 5</math> для всех "практических" значений <math>n</math>, а | Действительно, <math>G(n) \leq 5</math> для всех "практических" значений <math>n</math>, а | ||
именно для всех <math>n \leq 2^{65536}</math>. Функция <math>G(n)</math> используется при | именно для всех <math>n \leq 2^{65536}</math>. Функция <math>G(n)</math> используется при | ||
оценке трудоемкости алгоритмов. | оценке трудоемкости [[алгоритм|алгоритмов]]. | ||
==Литература== | ==Литература== | ||
[Словарь] | [Словарь] | ||
Версия от 12:33, 23 марта 2010
Функция Акермана (Ackermann's function) - Функция [math]\displaystyle{ A }[/math], индуктивно заданная на парах неотрицательнх целых чисел
[math]\displaystyle{
\begin{array}{c}
A(0,n) = n + 1; \\
A(m+1,0) = A(m,1); \\
A(m+1, n+1) = A(m, A(m+1,n)),
\end{array}
}[/math]
где [math]\displaystyle{ m, n \geq 0 }[/math]. Следовательно,
[math]\displaystyle{
\begin{array}{c}
A(1,n) = n+2; \\
A(2,n) = 2n+3; \\
A(3,n) = 2^{n+3} - 3.
\end{array}
}[/math]
Высокая рекурсивность этой функции используется для проверки
способности компиляторов выполнять рекурсию. Эта функция, названная в
честь У.Акермана, является примером функции, которая вообще
рекурсивна, а не примитивно рекурсивна вследствие очень быстрого
возрастания ее значения по мере увеличения [math]\displaystyle{ m }[/math]. Функцию Акермана можно
также рассматривать как функцию Ack одной переменной:
[math]\displaystyle{ \mbox{Ack}(n) = A(n,n), }[/math]
где [math]\displaystyle{ A }[/math] определено, как показано выше. Для нее имеем
[math]\displaystyle{
\begin{array}{c}
\mbox{Ack}(0) = 1, \\
\mbox{Ack}(i) = 2^{\mbox{Ack}(i-1)}\mbox{ для }i \gt 0.
\end{array}
}[/math]
Определим теперь функцию [math]\displaystyle{ G(n) }[/math] как наименьшее целое число [math]\displaystyle{ k }[/math], для
которого [math]\displaystyle{ \mbox{Ack}(k) \geq n }[/math]. Функция [math]\displaystyle{ G }[/math] растет очень медленно.
Действительно, [math]\displaystyle{ G(n) \leq 5 }[/math] для всех "практических" значений [math]\displaystyle{ n }[/math], а
именно для всех [math]\displaystyle{ n \leq 2^{65536} }[/math]. Функция [math]\displaystyle{ G(n) }[/math] используется при
оценке трудоемкости алгоритмов.
Литература
[Словарь]