Аноним

Функция Акермана: различия между версиями

Материал из WEGA
нет описания правки
(Создана новая страница размером '''Функция Акермана''' (''Ackermann's function'') - Функция <math>A</math>, индуктивно заданная ...)
 
Нет описания правки
Строка 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> используется при
оценке трудоемкости алгоритмов.
оценке трудоемкости [[алгоритм|алгоритмов]].
==Литература==
==Литература==
[Словарь]
[Словарь]