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