4635
правок
Функция Акермана: различия между версиями
Материал из WikiGrapp
нет описания правки
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> используется при | ||
оценке трудоемкости алгоритмов. | оценке трудоемкости [[алгоритм|алгоритмов]]. | ||
==Литература== | ==Литература== | ||
[Словарь] | [Словарь] | ||
