Get best of the week

Computación recursiva automatizada

1. Introducción


El impacto de las subrutinas (subrutina en inglés) en la programación sin exageración es enorme. Introducidos en los albores de la programación, no pierden su relevancia hasta el día de hoy. Sin ellos, la programación práctica es simplemente imposible de imaginar. Aunque desde un punto de vista formal, no son tan necesarios, porque La teoría pura está más interesada en las propiedades del algoritmo que en su tamaño.

En la teoría de los autómatas, el concepto de autómatas anidados, en base al cual se basaría la práctica de los subprogramas de autómatas (AMP), rara vez se discute. Una organización jerárquica similar (anidada) de autómatas, si se considera, es muy superficial. Una de las razones de esta relación puede ser la complejidad de implementar una jerarquía anidada a nivel de hardware [1, 2].

La programación es más flexible y proporciona más funciones que la práctica de diseñar circuitos digitales. Tenemos que asegurarnos de esto, considerando más la implementación de software de autómatas anidados, y luego el concepto de algoritmos recursivos de autómatas.

Para todos los problemas particulares de formar un modelo de autómata anidado, su definición formal no causa ningún problema. Pero, por otro lado, la elección de construir una jerarquía modelo ciertamente tendrá un impacto significativo en su implementación de software.

2. Algoritmos recursivos automatizados


En el artículo anterior [3], solo se dio una definición formal del modelo de control de los programas automáticos (AP) sin considerar su implementación y ejemplos específicos de uso. También se mencionó la posibilidad de implementar algoritmos recursivos. Luego, usando el ejemplo de cálculo factorial, en primer lugar, consideraremos la implementación de software de los mecanismos para crear rutinas automáticas dentro del marco del paradigma C ++ del autómata de objetos, y en segundo lugar, dado que consideraremos un algoritmo recursivo, definiremos esencialmente un principio general para implementar cualquiera de estos algoritmos en el marco de la programación automática.

Usar funciones recursivas en una API puede ser bastante simple. Esto demuestra el código para enumerar 1 del programa de máquina de objetos. Aquí la clase de autómata FSimpleFactorial no es un proceso, sino una rutina de autómata, porque contiene el estado final "00" (para más detalles sobre subprogramas ver [3]). A nivel de comportamiento, el objeto de autómata creado corresponde a un autómata con una transición incondicional desde el estado inicial "f0" al estado final "00" e invoca esta transición dentro del marco de acción y1 del factor de función de cálculo factorial factorial habitual (...).

Listado 1. Llamando a la función factorial desde el AMS
#include "lfsaappl.h"

class FSimpleFactorial : public LFsaAppl
{
public:
    double dF{1};		//	 
    FSimpleFactorial(int n);
    virtual ~FSimpleFactorial() {};
private:
    int nN{0};
    void y1();
    double factorial(int n);
};

#include "stdafx.h"
#include "FSimpleFactorial.h"

LArc TT_SimpleFactorial[] = {
    LArc("f0", "00", "--",	"y1"),		//
    LArc()
};
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
FSimpleFactorial::FSimpleFactorial(int n)
    :LFsaAppl(TT_SimpleFactorial, "FSimpleFactorial")
{
    nN = n;
}
//
void FSimpleFactorial::y1() { dF = factorial(nN); }

double FSimpleFactorial::factorial(int n)
{
    if (n == 0) return 1;
    else return n*factorial(n-1);
}


Dado que el objeto FSimpleFactorial es un autómata anidado (subrutina), debe haber un "contenedor" para él, el proceso que lo llama. Su ejemplo es un proceso generado a partir de un objeto llamado FTskSimple, cuyo código se muestra en el Listado 2.

Listado 2. El proceso para crear un autómata anidado
#include "lfsaappl.h"

class FTskSimple : public LFsaAppl
{
public:
    LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTskSimple(nameFsa); }
    bool FCreationOfLinksForVariables();
    FTskSimple(string strNam);
    virtual ~FTskSimple();

    CVar    *pVarF;
    CVar    *pVarN;
    CVar    *pVarStart;

    LFsaAppl *pFCall{nullptr};
protected:
    int x1();
    void y1(); void y2(); void y3();
};

#include "stdafx.h"
#include "FTskSimple.h"
#include "FSimpleFactorial.h"
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
LArc TT_Task[] = {
    LArc("st", "t1", "--",	"y1"),	//
    LArc("t1", "t2", "x1",	"y3"),	//
    LArc("t2", "t1", "--",	"y2"),	//
    };

FTskSimple::FTskSimple(string strNam)
    :LFsaAppl(TT_Task, strNam)
{
}

FTskSimple::~FTskSimple() { if (pFCall) delete pFCall; }

bool FTskSimple::FCreationOfLinksForVariables() {
    pVarF = CreateLocVar("dF", CLocVar::vtDouble, "factorial value");
    pVarN = CreateLocVar("nN", CLocVar::vtInteger, "input value");
    pVarStart = CreateLocVar("bStart", CLocVar::vtBool, "start?");
    return true;
}

int FTskSimple::x1() { return pVarStart->GetDataSrc(); }

void FTskSimple::y1()
{
    // reset flag start
    pVarStart->SetDataSrc(this, 0.0);
    // creating and calling a subroutine
    pFCall = new FSimpleFactorial(pVarN->GetDataSrc());
}
void FTskSimple::y2()
{
    // display factorial value
    pVarF->SetDataSrc(this, static_cast<FSimpleFactorial*>(pFCall)->dF);
}

void FTskSimple::y3()
{
    // reset flag start
    pVarStart->SetDataSrc(this, 0.0);
    static_cast<FSimpleFactorial*>(pFCall)->nN = pVarN->GetDataSrc();
    // creating and calling a subroutine
    pFCall->FCall(this);
}


Este proceso en la transición del estado inicial "st" al estado "t1" crea un objeto de tipo FSimpleFactorial, que será la base para crear un autómata anidado (en el sentido habitual, llamar a una subrutina). Además, según el estado actual de la variable local del tipo booleano bStart (véase también el código de predicado x1), provoca una transición del estado "t1" a "t2". En esta transición, la acción y1, en primer lugar, restablece el valor de esta variable local (para evitar un reinicio falso) y, en segundo lugar, llama al procedimiento FCall, que crea un autómata anidado.

El intérprete de los autómatas del entorno VKPA organiza la transición al estado inicial "f0" del autómata incorporado y los estados de este último se convierten en los estados actuales del proceso. La transición del autómata anidado al estado final "00" devuelve el cálculo al nivel anterior de anidamiento y, en nuestro caso, a la finalización de la transición del autómata de nivel superior al estado t2. Luego, el proceso, en una transición incondicional del estado "t2" al estado "t1", realiza la acción y2, que establece el resultado del cálculo del factorial de la variable local del proceso dF.

Tenga en cuenta que es muy importante que el resultado de un autómata anidado esté disponible solo después de completar su trabajo y la transición al siguiente estado de un autómata de nivel superior. Será posible obtenerlo (resultado) a través de un puntero a un objeto de un autómata anidado.

Y todo estaría bien si no fuera por el tiempo de ejecución de la función recursiva. En comparación con la subrutina habitual, debido a la anidación, por regla general, es mucho más grande y, por lo tanto, puede violar la atomicidad condicional de las acciones de los procesos automáticos, cuyo tiempo de ejecución total debe ajustarse al valor de un ciclo de reloj discreto.

En nuestro caso, el cálculo del factorial es bastante pequeño y hasta el valor máximo de un resultado doble para n = 170 se ajusta a 1 microsegundo. Para calcular valores grandes, uno necesita cambiar a aritmética larga (ver, por ejemplo, [4, 5]). Al mismo tiempo, el tiempo de cálculo factorial aumentará aún más y casi garantizará ir más allá del ciclo de reloj discreto, afectando la velocidad de las máquinas de red restantes que operan en el modo multitarea no preventivo y la reactividad de la respuesta de la aplicación en su conjunto, que se manifestará en sus "frenos".

Puede mantenerse dentro de un ciclo de reloj discreto y deshacerse del defecto de "frenos" expandiendo el cálculo en pasos. Para estos fines, es conveniente traducir el algoritmo factorial habitual en forma automática. Es cierto que, debido al modo de interpretación de los autómatas, el tiempo de cálculo aumentará, pero las propiedades temporales de la aplicación volverán a la normalidad.

El Listado 3 muestra el cálculo del factorial en su forma habitual y en la forma preparada para la conversión posterior a una forma de autómata. Este último representa explícitamente los pasos atómicos que están ocultos en el código fuente del programa. En este caso, estamos hablando de operadores de la forma y = f (...), donde f es una función de programa ordinaria o recursiva. Tal registro enmascara el tiempo de funcionamiento de la función y crea una falsa impresión de la asignación "instantánea" del valor de la variable y. En realidad, no hay uno ni el otro.

Listado 3. Funciones de software para calcular factorial
int factorial(int n)
{
    if (n == 0) return 1;
    else return n*factorial(n-1);
}

double Factorial(int n)
{
    double dF = 1;
    if (n == 0)
        return dF;
    else {
        double dPrev = Factorial(n-1);
        double dF = n*dPrev;
        return dF;
    }
}


En el marco del concepto de programación automática, las acciones atómicas (métodos) de los objetos automáticos de software se consideran condicionalmente instantáneas. Y si solo el tiempo operativo total de las acciones se ajusta a un solo ciclo de tiempo discreto del espacio del autómata, entonces la implementación del software corresponde a su modelo formal.

Observación 1. El tiempo real total de operación de las acciones en uno u otro ciclo de reloj discreto puede variar bastante. En caso de exceder el tiempo del ciclo, el entorno VKPA intenta compensarlo en los ciclos posteriores de la operación de espacio del autómata, reduciendo, si es posible, el tiempo discreto de los ciclos posteriores.

En la Fig. La Figura 1 muestra un diagrama de bloques que incluye marcado que refleja los estados de una máquina de estados finitos equivalente y los nombres de sus predicados y acciones. El modelo del autómata en forma de gráfico del autómata se muestra en la Fig. 2.

imagen
Fig. 1. Diagrama de bloques del algoritmo recursivo factorial

imagen
Fig. 2. Un modelo de autómata de un algoritmo factorial recursivo

El código para la rutina automática para calcular el factorial se muestra en el Listado 4. Los comentarios en la tabla de transición (TP) reflejan el tiempo de cálculo del factorial en ms y el número de pasos discretos gastados en el procedimiento de cálculo para n = 170. Y si el tiempo de cálculo depende de la velocidad de la plataforma informática y / o del tipo de proyecto (depuración / liberación), el número de pasos discretos (ciclos de reloj) está determinado solo por las propiedades del algoritmo y puede servir como una evaluación objetiva de la velocidad del algoritmo, independientemente de la forma de su presentación e implementación.

En el caso de un modelo de autómata, el número de tics discretos se puede calcular de manera bastante simple y, después de recopilar ciertas estadísticas, derivar una fórmula analítica para la velocidad del algoritmo. Mientras tanto, tales estimaciones son muy aproximadas y se basan en conclusiones, a menudo obtenidas como resultado de un razonamiento bastante complejo.

Listado 4. Rutina factorial automatizada
#include "lfsaappl.h"

class FFactRec : public LFsaAppl
{
public:
    FFactRec(int n);
    virtual ~FFactRec() { if (pFFactRec) delete pFFactRec; };
    int nN;		//	n
    double dF;	//	n!
private:
	int x1();
    void y1(); void y2(); void y3();
protected:
    void CallFactorial();
    double  PrevFactorial();
    FFactRec *pFFactRec{nullptr};
};

#include "stdafx.h"
#include "FFactRec.h"

#define QT_NO_DEBUG_OUTPUT

extern LArc TT_FactRec[];
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
//	   
FFactRec::FFactRec(int n)
    :LFsaAppl(TT_FactRec, "FFactRec")
{
    nN=n; dF=1;
}

LArc TT_FactRec[] = {
//        Debug    Release     Steps
//msec: 120-129   98-101        340
    LArc("f1", "00", "x1",	"y3"),	//
    LArc("f1", "f2", "^x1",	"y1"),	//
    LArc("f2", "00", "--",	"y2"),	//
    LArc()
};

int FFactRec::x1() { return nN==0; }
//   
void FFactRec::y1() { CallFactorial(); }
//	1.      
//	2.    
void FFactRec::y2() { dF = PrevFactorial()*nN; }
// 0!
void FFactRec::y3() { dF = 1; }
//   (  )
void FFactRec::CallFactorial()	{
    //	     
    pFFactRec = new FFactRec(nN-1);
    pFFactRec->FCall(this);
};
//    
double  FFactRec::PrevFactorial()	{ return pFFactRec->dF; };


3 Conclusiones


Admito que, debido a los detalles de las tareas a resolver, en realidad no tuve que usar y desarrollar algoritmos recursivos en proyectos reales, excepto para fines de capacitación y para probar el núcleo para la implementación de anidamiento. Rutinas automatizadas, casi constantemente y en grandes cantidades. Entre ellas, las subrutinas llamadas inerciales son especialmente interesantes (para más detalles, ver [3]). Pero se supone que deben dedicar un artículo separado a su consideración.

Los algoritmos recursivos son una parte importante de la teoría del programa [6]. Sin la implementación de rutinas y recursividad, es difícil imaginar un modelo computacional eficiente y conveniente desde todos los puntos de vista. Y para implementar la recursión, teniendo en cuenta las posibilidades de la programación de objetos (ver ejemplos del artículo), después de crear un modelo de subprogramas, no es tan difícil. Puede, por supuesto, usar ciertos métodos para convertir la recursión en una forma regular, evitándola usando los mismos ciclos. Pero es preferible no deshacerse de él estúpidamente, sino tener mecanismos directos para su implementación. Por supuesto, será más lento, por supuesto, más costoso en términos de recursos (gastos de la misma memoria de pila), pero con las capacidades de hardware existentes esto no será tan crítico.

Pero los algoritmos recursivos también son interesantes como pruebas para evaluar las capacidades, la universalidad y la efectividad de los modelos algorítmicos. En este sentido, el modelo de autómata no solo implementa la recursión de manera bastante efectiva, sino que también agrega "chips de autómata" como una ventaja adicional: la capacidad de controlar el estado interno del algoritmo recursivo, contar los pasos para evaluar el rendimiento, controlar el tiempo de ejecución del algoritmo, etc. etc.

La lucha contra la recursión no tiene sentido. Debe poder usar. Citaré con lo que estoy completamente de acuerdo: "A primera vista, la recursión puede parecer complicada. Pero en algunos casos, el método recursivo es increíblemente efectivo si todo se hace correctamente. Sin embargo, a veces es mejor usar bucles. Comprender ambos métodos y la capacidad de usarlos de manera efectiva lo ayudará en su trabajo y será una ventaja en la entrevista ”[7]. Solo puedo agregar por mi cuenta que los modelos automáticos de algoritmos recursivos hacen posible, usando las "propiedades automáticas" de un modelo computacional, comprender la recursividad, depurar y modificar dicho algoritmo mucho más rápido.

Y el último. Sin embargo, me gustaría obtener una respuesta a la pregunta: ¿cómo van las cosas con la recurrencia de rutina? Ya lo pregunté, pero no he recibido una respuesta ... Después de todo, una cosa es crear un millón de corutina (ver [8] para ver ejemplos) y otra para implementar un algoritmo recursivo que tiene un nivel de anidamiento que no es el mismo pero lo suficientemente alto. Y, al parecer, la respuesta a esta pregunta no solo me interesa a mí solo ... [9]

Literatura
1. .., .. . I, . ., 1981, 2, 135-144. [ ], : mi.mathnet.ru/at5725 . . . ( 10.03.2020).
2. .., .. . II, . ., 1981, 3, 112-121. [ ], : mi.mathnet.ru/at5743 . . . ( 10.03.2020).
3. . [ ], : habr.com/ru/post/484588 . . . ( 10.03.2020).
4. . [ ], : habr.com/ru/post/255761 . . . ( 10.03.2020).
5. C++. [ ], : habr.com/ru/post/172285 . . . ( 10.03.2020).
6. . . : . . – .: , 1983. – 256 .
7. , ? Python. Ethan Jarrell. Recursion vs. Looping in Python [ ], : nuancesprog.ru/p/3325 . . . ( 15.03.2020).
8. Your first coroutine with Kotlin. [ ], : kotlinlang.org/docs/tutorials/coroutines/coroutines-basic-jvm.html . . . ( 18.03.2020).
9. . CyberForum.ru. [ ], : www.cyberforum.ru/unity/thread2479923.html . . . ( 18.03.2020).

More articles:


All Articles