Comprendre l'algorithme de Grossman & Zeitman

Question

J'ai lu le journal Un calcul intrinsèquement itératif de la fonction d'Ackermann publié par Grossman & Zeitman, dans lequel ils présentent un algorithme qui optimise la fonction d'Ackermann.

Nous savons que la fonction d'Ackermann produit le résultat dans les sous-séquences A(m,n)

m=0 : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,...
m=1 : 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,...
m=2 : 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33,...
m=3 : 5, 13, 29, 61, 125, 253, 509, 1021, 2045, 4093, 8189, 16381, 32765, 65533,...
m=4 : 13, 65533,...

Il est indiqué que le Next Le tableau est pour garder la trace de l'endroit où nous sommes dans chaque sous-séquence et le Goal tableau est de garder la trace de ce que nous devons atteindre avant de transférer la valeur qui vient d'être calculée à la sous-séquence suivante. . Et tout ce qu'il fait est d'incrémenter de 1 à la valeur :

Ackermann(m, n)
    {next and goal are arrays indexed from 0 to m, initialized so that next[0] 
     through next[m] are 0, goal[0] through goal[m - l] are 1, and goal[m] is -1} 
    repeat
        value  next[0] + 1 
        transferring  true 
        current  0 
        while transferring do begin
           if next[current] = goal[current] then goal[current]  value
                                            else transferring  false
           next[current]  next[current] + 1
           current  current + 1 
           end while
    until next[m] = n + 1 
    return value {the value of A(m, n)}
    end Ackermann

J'ai du mal à comprendre comment les deux tableaux indiquent où nous sommes/où nous devons nous déplacer ? J'ai du mal à comprendre ce que cela signifie exactement lorsque nous nous arrêtons à next[m] = n + 1 pourquoi spécifiquement cette valeur ? J'ai essayé de retracer l'algorithme et je ne comprends toujours pas comment il fonctionne. Cet algorithme est-il considéré comme une mise en œuvre ascendante ?

Voici un code Java qui imprime la valeur, le courant et les deux tableaux.

import java.util.Arrays;

public class Ack {
    static int arrayAck(int m, int n) {
        //Next array to keep track of where we are in each subsequence, 
        //and Goal array to keep track of where we need to reach before transferring the value just calculated to the next subsequence.
        int[] next = new int[m+1];
        int[] goal = new int [m+1];
        Arrays.fill(next, 0);
        Arrays.fill(goal, 1);
        goal[m] = -1;

        int value = next[0] + 1;
        while(true) {
            value = next[0] + 1;
            boolean transferring = true;
            int current = 0;

            System.out.println("--");
            System.out.println("Next = " + Arrays.toString(next));
            System.out.println("Goal = " + Arrays.toString(goal));
            System.out.println("Current= " + current);
            System.out.println("Value = " + value);
            while(transferring) {
                if(next[current] == goal[current])
                    goal[current] = value;
                else
                    transferring = false;
                next[current]=next[current]+1;
                current += 1;
                System.out.println("Current= " + current);
                System.out.println("Next = " + Arrays.toString(next));
                System.out.println("Goal = " + Arrays.toString(goal));
            }

            if(next[m]==n+1)
                break;

        }

        return value;
    }

    public static void main(String[] args) {
        int m=2,n=2;
        System.out.println("Ackermann value for ("+m+","+n+") = " + arrayAck(m, n));
    }

}

Answer 1

J'ai lu l'article pour me faire une idée de l'algorithme qu'ils proposent, et ce n'est pas si mal quand on s'y retrouve.

L'idée de base est la suivante. Nous avons une version à deux arguments de la fonction d'Ackermann définie comme suit :

• A(0, n) = n + 1
• A(i, 0) = A(i - 1, 1)
• A(i, n) = A(i - 1, A(i, n - 1))

L'approche proposée par les auteurs est essentiellement un calcul ascendant de la fonction d'Ackermann, optimisé pour l'espace. Plutôt que de donner la version finale de leur algorithme, voyons si nous pouvons plutôt le dériver à partir des règles ci-dessus. Nous allons imaginer de remplir un tableau 2D où chaque ligne correspond à une valeur différente de i et chaque colonne correspond à une valeur de n. En suivant la convention de l'article, nous placerons la ligne pour i = 0 en haut, comme ceci :

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0 
i=1
i=2
i=3

Notre objectif sera de remplir ce tableau. Pour l'instant, ne vous préoccupez pas de la taille du tableau ; nous pourrons la déterminer plus tard.

Le premier des trois cas de la fonction d'Ackermann dit que

Règle 1 : A(0, n) = n + 1.

Nous pouvons interpréter cela comme signifiant

La ligne supérieure du tableau est la séquence de valeurs 1, 2, 3, 4, 5, ...

Nous pourrions compléter cette information maintenant, mais pour des raisons qui deviendront plus claires plus tard, nous nous abstiendrons de le faire pour le moment.

La règle suivante est que

Règle 2 : A(i, 0) = A(i - 1, 1).

Nous pouvons interpréter cela comme signifiant

La première entrée de chaque ligne successive du tableau est la deuxième entrée (indice 1) de la ligne qui la précède.

Avec ces deux règles en tête, commençons à remplir les entrées de la table. Nous pouvons remplir l'emplacement pour A(0, 0) en utilisant la première règle : A(0, 0) = 0 + 1 = 1.

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0  1
i=1
i=2
i=3

Maintenant, remplissons A(0, 1) = 1 + 1 = 2 :

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0  1    2
i=1
i=2
i=3

Comme nous venons de remplir cette entrée du tableau, nous pouvons utiliser la règle suivante pour remplir l'emplacement de A(1, 0), qui sera donné par A(0, 1) = 2 :

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0  1    2
i=1  2
i=2
i=3

Pour progresser dans le remplissage de la ligne pour i = 1, nous devrons extraire le troisième cas de la fonction d'Ackermann :

Règle 3 : A(i, n) = A(i - 1, A(i, n - 1)).

Cette règle est dense, mais son intuition est très agréable. Pour remplir l'emplacement de la table A(i, n), faites ce qui suit :

1. Déterminez ce qui se trouve dans l'emplacement de table A(i, n - 1). Interprétez ce nombre comme un indice k.
2. Recopiez le kème élément de la ligne située au-dessus de vous (c'est-à-dire, positionnez A(i - 1, k) = A(i - 1, A(i, n - 1))).

Dans notre cas, supposons que nous voulons remplir A(1, 1). En utilisant la procédure ci-dessus, nous faisons ce qui suit :

1. Regardez l'emplacement du tableau A(1, 0) = 2.
2. Copiez l'index 2 de la ligne 0 (c'est-à-dire A(0, 2)).

Cependant, en regardant notre tableau, nous pouvons voir que nous n'avons pas encore calculé A(0, 2). Faisons-le donc. Nous calculons A(0, 2) = 3 via la règle 1 :

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0  1    2    3
i=1  2
i=2
i=3

Cela signifie à son tour, par la règle 3, que A(1, 1) = 3 :

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0  1    2    3
i=1  2    3
i=2
i=3

Et maintenant, quelque chose d'intéressant se produit. Nous venons de remplir A(1, 1), ce qui, selon la règle 2, nous permet de remplir A(2, 0) en copiant A(1, 1) à cet endroit :

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0  1    2    3
i=1  2    3
i=2  3
i=3

Faisons le point sur ce qui vient de se passer.

• Nous avons calculé A(0, 2) via la règle 1.
• En calculant une autre entrée de la rangée 0, on obtient une nouvelle entrée de la rangée 1 via la règle 3.
• En calculant une autre entrée de la rangée 1, on obtient une nouvelle entrée de la rangée 2 via la règle 2.

En d'autres termes, en calculant une autre valeur dans la rangée 0, nous avons eu un effet d'entraînement qui s'est propagé vers le bas, nous permettant de calculer d'autres entrées dans la rangée 1, la rangée 2, etc. Cela suggère donc une approche à adopter : générer une autre valeur dans la rangée 0, ce qui est facile à faire en utilisant la règle 1, et à partir de là, voir si nous pouvons "répercuter" cette valeur plus haut dans le tableau en utilisant la règle 2 et la règle 3.

Pour voir cela en action, remplissons A(0, 3) = 3+1 = 4 en utilisant la règle 1 :

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0  1    2    3    4
i=1  2    3
i=2  3
i=3

Maintenant, regardez la ligne 1. La règle 3 dit que pour remplir A(1, 3), nous devons d'abord calculer A(1, 2) (c'est fait - c'est 3) et ensuite prendre la colonne 3 de la ligne 0. Nous venons de calculer la colonne 3 de la ligne 0, ce qui signifie que nous devons copier A(0, 3) dans A(1, 2) :

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0  1    2    3    4
i=1  2    3    4
i=2  3
i=3

Maintenant, regardez la rangée 2. Nous avons rempli A(2, 0), donc le prochain à calculer ici est A(2, 1). Pour calculer A(2, 1), nous devons d'abord calculer A(2, 0) (c'est fait - c'est 3), donc nous devons prendre l'entrée de la colonne 3 de la ligne 1. Nous ne l'avons pas encore calculé, donc rien de plus ne se passe. L'ondulation s'arrête ici.

Calculons l'entrée suivante de la rangée 0 : A(0, 4) = 4+1 = 5. Ça va ici :

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0  1    2    3    4    5
i=1  2    3    4
i=2  3
i=3

En regardant la rangée 1, pour remplir A(1, 3), nous regardons A(1, 2) (qui est 4) et copions A(0, 4) par-dessus :

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0  1    2    3    4    5
i=1  2    3    4    5
i=2  3
i=3

En regardant la rangée 2, pour remplir A(2, 2), nous regardons A(2, 1) (qui est 3) et copions A(1, 3) par-dessus :

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0  1    2    3    4    5
i=1  2    3    4    5
i=2  3    5
i=3

Maintenant, regardez la rangée 3. La règle 2 dit que A(3, 0) = A(2, 1), donc nous copions A(2, 1) :

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0  1    2    3    4    5
i=1  2    3    4    5
i=2  3    5
i=3  5

Et l'ondulation est faite comment parce que c'est toutes les lignes de notre table.

Pour voir comment ce système évolue, exécutons quelques autres ondulations, l'une après l'autre :

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0  1    2    3    4    5    6
i=1  2    3    4    5    6
i=2  3    5
i=3  5

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0  1    2    3    4    5    6    7
i=1  2    3    4    5    6    7
i=2  3    5    7
i=3  5

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0  1    2    3    4    5    6    7    8
i=1  2    3    4    5    6    7    8
i=2  3    5    7
i=3  5

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0  1    2    3    4    5    6    7    8    9
i=1  2    3    4    5    6    7    8    9
i=2  3    5    7    9
i=3  5

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0  1    2    3    4    5    6    7    8    9    10
i=1  2    3    4    5    6    7    8    9    10
i=2  3    5    7    9
i=3  5

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0  1    2    3    4    5    6    7    8    9    10   11
i=1  2    3    4    5    6    7    8    9    10   11
i=2  3    5    7    9   11
i=3  5

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0  1    2    3    4    5    6    7    8    9    10   11   12
i=1  2    3    4    5    6    7    8    9    10   11   12
i=2  3    5    7    9   11
i=3  5

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0  1    2    3    4    5    6    7    8    9    10   11   12   13
i=1  2    3    4    5    6    7    8    9    10   11   12   13
i=2  3    5    7    9   11   13
i=3  5   13

Vous pouvez comparer ces valeurs à la figure 1 du tableau de l'article et vous verrez que cela correspond (partiellement) à ce qui se passe.

Un détail important dans l'exécution de cet algorithme est qu'à chaque instant, nous ne nous intéressons qu'au tout dernier élément de chacune des lignes. Cet élément nous indique quel index doit être rempli dans la ligne inférieure avant que nous ne copions la valeur suivante. En gardant cela à l'esprit, nous pourrions imaginer d'exécuter à nouveau cet algorithme, mais en ne stockant que le dernier élément de chaque ligne. Cela pourrait ressembler à ceci :

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0  1
i=1
i=2
i=3

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0       2
i=1  2
i=2
i=3

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0            3
i=1       3
i=2  3
i=3

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0                 4
i=1            4
i=2  3
i=3

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0                      5
i=1                 5
i=2       5
i=3  5

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0                           6
i=1                      6
i=2       5
i=3  5

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0                                7
i=1                           7
i=2            7
i=3  5

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0                                     8
i=1                                8
i=2            7
i=3  5

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0                                          9
i=1                                     9
i=2                 9
i=3  5

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0                                               10
i=1                                          10
i=2                 9
i=3  5

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0                                                    11
i=1                                               11
i=2                      11
i=3  5

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0                                                         12
i=1                                                    12
i=2                      11
i=3  5

    n=0  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10 n=11 n=12
i=0                                                              13
i=1                                                         13
i=2                           13
i=3       13

Il s'agit d'un gain de place important, et cela permet d'exposer quelque chose d'intéressant sur chaque ligne. Pour chaque ligne, nous avons juste besoin de stocker deux valeurs :

1. Le numéro qui est stocké dans cette ligne.
2. L'indice de la colonne correspondant à l'endroit où se trouve le numéro le plus à droite.

Quelles sont les significations de ces deux valeurs ? Ce premier nombre peut être interprété de deux façons. Premièrement, c'est une valeur réelle de la séquence d'Ackermann. Ensuite, pour les rangs supérieurs au premier, c'est un indicateur qui dit "quelle position devons-nous avoir dans le rang inférieur pour que je puisse passer à la colonne suivante dans mon rang ?". Il s'agit de la valeur que le journal stocke dans le goal le tableau.

Le second de ces nombres peut à son tour être considéré comme indiquant "à quelle position je me trouve", ce que les rangs de niveau supérieur peuvent ensuite utiliser pour déterminer le moment où il convient d'avancer leur goal valeurs. C'est la valeur que le papier stocke dans le next le tableau.

Plutôt que de reprendre le pseudo-code de l'article, je vais réécrire l'algorithme à partir de zéro, pour aboutir à quelque chose de similaire mais pas exactement identique à ce que l'article propose. L'idée de base est de simuler le processus ci-dessus. Nous gardons la trace de la colonne dans laquelle nous nous trouvons dans chacune des lignes de la table (j'ai appelé ceci positions pour rendre sa signification plus claire) et quelle valeur est stockée dans chaque ligne du tableau (j'ai appelé ceci values ).

Pour simplifier la logique de la gestion du cas où certaines lignes ont des valeurs et d'autres non (voir les premières étapes de la trace ci-dessus, par exemple), et pour unifier la règle 2 et la règle 3, j'ai adopté la stratégie suivante. Nous allons étendre la fonction d'Ackermann pour que la valeur de A(i, -1) soit définie de la manière suivante :

• A(0, -1) = 0
• A(i, -1) = 1

Nous prétendrons ensuite que chaque rangée commence en position -1, c'est-à-dire "juste avant la première colonne". L'intuition est que la rangée 1, la rangée 2, la rangée 3, etc. attendent toutes qu'un élément apparaisse en position 1 dans la rangée qui les précède, alors que dans la rangée 0, la valeur juste avant la première devrait être 0, de sorte que la séquence de valeurs produite dans la rangée 0 est la série 0, 1, 2, 3, ... .

Avec cela en tête, voici ma mise en œuvre :

/**
 * File: Ackermann.java
 * Author: Keith Schwarz (htiek@cs.stanford.edu)
 *
 * An implementation of a variation of Grossman and Zeitman's fast algorithm
 * for computing the Ackermann function. This implementation uses O(i) space
 * to compute A(i, n), and takes O(A(i, n)) time. The only operation required
 * on integers is "increment an integer" and "copy an integer." While this is
 * implemented using vanilla ints, it could easily be extended to use BigInteger
 * types or the like.
 */
public class Ackermann {
    public static int ackermann(int i, int n) {
        /* Bounds-check. */
        if (i < 0 || n < 0) throw new RuntimeException("Invalid arguments.");

        /* Positions array stores what column we're in in each row of
         * the table. Initially this is all -1 to signify that we're just
         * before the first column.
         */
        int[] positions = new int[i + 1];
        for (int j = 0; j < positions.length; j++) {
            positions[j] = -1;
        }

        /* Values array stores the value currently in the filled column
         * in each row. The value in the zeroth row is set to zero because
         * our algorithm works by repeatedly incrementing its value and
         * we need it to be the case that A(0, 0) = 1. Since we start off
         * with "A(0, -1)" computed, we place a zero there.
         *
         * All the other values are set to 1. This corresponds to the rule
         * that A(i, 0) = A(i - 1, 1), meaning we're waiting for column 1
         * to come up in the level below us.
         */
        int[] values = new int[i + 1];
        for (int j = 1; j < values.length; j++) {
            values[j] = 1;
        }

        /* Run the algorithm until we compute A(i, n), which happens when
         * positions[i] == n.
         */
        while (positions[i] != n) {        
            /* Push the value in the bottom row forward and increment it to simulate
             * computing the next value of A(0, *).
             */
            values[0]++;
            positions[0]++;

            /* Now, do the ripple. We continue rippling upward while
             *
             * 1. There's a layer above us to ripple to, and
             * 2. The value above us equals our current position.
             */
            for (int j = 1; j <= i && positions[j - 1] == values[j]; j++) {
                values[j] = values[j - 1]; // Copy the value
                positions[j]++;            // Shift forward a column
            }
        }

        return values[i];
    }

    public static void main(String[] args) {
        if (args.length != 2) {
            System.err.println("Usage: java Ackermann i n");
            return;
        }

        int i = Integer.parseInt(args[0]);
        int n = Integer.parseInt(args[1]);

        System.out.println("A(" + i + ", " + n + ") = " + ackermann(i, n));
    }
}

Un dernier détail - je pense que l'analyse originale du temps d'exécution de Zeitman et Grossman de O(iA(i, n)) est correcte mais pas stricte. Plus précisément, cela suppose qu'à chaque étape de l'algorithme, nous copions une valeur d'une couche à la suivante. Or, ce n'est pas le cas. Les valeurs de chaque ligne croissent si rapidement que, dans la plupart des étapes, nous ne copierons rien sur une ligne élevée du tableau. Plus précisément, notez que la rangée 2 du tableau est constituée d'un nombre impair sur deux, de sorte que seule la moitié des étapes d'incrémentation y copieront quelque chose, et les rangées supérieures ne copient sûrement pas plus de la moitié des valeurs de la couche inférieure. Cela signifie qu'en moyenne, chaque ondulation aura 100 % de chances de copier sur la rangée 1, au plus 50 % de chances de copier sur la rangée 2, au plus 25 % de chances de copier sur la rangée 3, etc. En additionnant le nombre de copies effectuées et en utilisant le fait qu'il y a (au moins) une décroissance géométrique ici, cela signifie que l'opération "moyenne" ne copie que sur O(1) rangées au total. Cela signifie que nous effectuons O(A(i, n)) étapes d'incrémentation, dont chacune (en moyenne) ne copie que O(1) rangées au total, de sorte que le travail total effectué est de O(A(i, n)) . Ce n'est pas une énorme amélioration par rapport à la limite d'exécution (le terme A(i, n) est gigantesque !), mais c'est un résultat légèrement meilleur.