Fonction inverse d'Ackermann

Rappel sur la fonction d’Ackermann

Avant toute chose, il est important de revenir sur la fonction d’Ackermann.

La fonction d’Ackermann-Péter est définie récursivement $\forall m,n \in \mathbb{N}$ :

$A(0,n) = n+1$
$A(m,0) = A(m-1,1)$
$A(m,n)=A(m-1,A(m,n-1))$

Cette fonction à pour propriété de croître très rapidement : $A(5,1)$ étant déjà assez grand pour ne pas prendre la peine de l’écrire.

Sans davantage paraphraser Wikipédia, vous pouvez en savoir plus ici.

Fonction d’Ackermann diagonale

Nous dénoterons par la suite la fonction d’Ackermann diagonale par $\mathcal{A}(n)$ tel que $\mathcal{A}(n)=A(n,n)$.

La croissance explosive de cette fonction se voit très rapidement : Pour n allant de 0 à 5, nous avons $\mathcal{A} (n)$ allant de 1, 3, 7, 61, $2^{2^{2^{65536}}}$, la 6ème valeur étant immensément plus grande que la 5ème. [5]

La fonction inverse d’Ackermann

Il existe plusieurs versions de la fonction inverse d’Ackermann. Cependant leurs comportement restent fondamentalement les mêmes. Pour deux fonctions inverses d’Ackermann $\alpha$ et $\alpha’$, nous avons $|\alpha(n)-\alpha’(n)| \in O(1)$. [3]

La fonction inverse d’Ackermann d’arité 1

Une fonction inverse d’Ackermann se retrouvant dans plusieurs sources est la suivante :

Dénoté par $\alpha : \mathbb{N}\rightarrow\mathbb{N}$, $\alpha(n)$ est le plus petit k tel que $n\leq \mathcal{A} (k)$. Autrement dit :

$$\alpha(n)= \min ( \{k \in \mathbb{N} \ | \ n \leq \mathcal{A} (k)\})$$

La fonction inverse d’Ackermann d’arité 2

La fonction inverse d’Ackermann est une fonction à deux paramètres ayant une croissance extrêmement lente.

Elle est définie ainsi [1]:

$$\alpha(m,n) = \min (\{i \in \mathbb{N}^* \ | \ A(i, \lfloor \frac{m}{n}\rfloor) \ > \ log_2(n) \})$$

Remarques :

La fonction inverse d’Ackermann n’est donc pas la fonction réciproque de la fonction d’Ackermann, mais une fonction ayant une croissance aussi lente que celle d’Ackermann est rapide.

On retrouvera cette fonction dans plusieurs preuves (que vous pouvez trouver ci-dessous), notamment dans des calculs de complexités asymptotiques d’algorithmes de Classe-Unions.

En théorie, cette fonction croit infiniment. Cependant, comme nous l’avons vu, en pratique, cette fonction ne dépassant pas 4, il sera communément admit de considérer cette fonction comme appartenenant à $O(1)$ (ie : une constante) -.

mowse