Get best of the week

Computação recursiva automatizada

1. Introdução


O impacto das sub-rotinas (sub-rotina em inglês) na programação sem exagero é enorme. Introduzidos no início da programação, eles não perdem sua relevância até hoje. Sem eles, a programação prática é simplesmente impossível de imaginar. Embora do ponto de vista formal, eles não são tão necessários, porque A teoria pura está mais interessada nas propriedades do algoritmo do que em seu tamanho.

Na teoria dos autômatos, o conceito de autômato aninhado, com base no qual a prática de subprogramas de autômatos (AMP) seria baseada, raramente é discutido. Uma organização hierárquica semelhante (aninhada) de autômatos, se considerada, é muito superficial. Uma das razões para esse relacionamento pode ser a complexidade de implementar uma hierarquia aninhada no nível do hardware [1, 2].

A programação é mais flexível e oferece mais recursos do que a prática de projetar circuitos digitais. Temos que garantir isso, considerando ainda mais a implementação de software de autômatos aninhados e, em seguida, o conceito de algoritmos recursivos de autômatos.

Para todos os problemas específicos da formação de um modelo de autômato aninhado, sua definição formal não causa problemas. Mas, por outro lado, a escolha de construir uma hierarquia de modelos certamente terá um impacto significativo na sua implementação de software.

2. Algoritmos recursivos automatizados


No artigo anterior [3], apenas uma definição formal do modelo de controle de programas automáticos (PA) foi dada sem considerar sua implementação e exemplos específicos de uso. A possibilidade de implementar algoritmos recursivos também foi mencionada. Em seguida, usando o exemplo de cálculo fatorial, em primeiro lugar, consideraremos a implementação de software dos mecanismos para criar rotinas automáticas dentro da estrutura do paradigma C ++ do autômato de objetos e, em segundo lugar, como consideraremos um algoritmo recursivo, definiremos essencialmente um princípio geral para implementar qualquer um desses métodos. algoritmos no âmbito da programação automática.

O uso de funções recursivas em uma API pode ser bastante simples. Isso demonstra o código para listar 1 do programa de máquina de objeto. Aqui, a classe de autômatos FSimpleFactorial não é um processo, mas uma rotina de autômatos, porque contém o estado final "00" (para mais detalhes sobre subprogramas, consulte [3]). No nível do comportamento, o objeto de autômato criado corresponde a um autômato com uma transição incondicional do estado inicial “f0” para o estado final “00” e uma chamada para essa transição no quadro da ação y1 da função fatorial fatorial usual (fatorial (...)).

Listagem 1. Chamando a função fatorial do 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);
}


Como o objeto FSimpleFactorial é um autômato aninhado (sub-rotina), deve haver um "invólucro" para ele - o processo que o chama. Seu exemplo é um processo gerado a partir de um objeto chamado FTskSimple, cujo código é mostrado na Listagem 2.

Listagem 2. O processo para criar um autômato aninhado
#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);
}


Esse processo na transição do estado inicial “st” para o estado “t1” cria um objeto do tipo FSimpleFactorial, que será a base para a criação de um autômato aninhado (no sentido usual, chamando uma sub-rotina). Além disso, com base no estado atual da variável local do tipo booleano bStart (consulte também o código de predicado x1), causa uma transição do estado "t1" para "t2". Nesta transição, a ação de y1, em primeiro lugar, redefine o valor dessa variável local (para evitar reinicialização falsa) e, em segundo lugar, chama o procedimento FCall, que cria um autômato aninhado.

O intérprete dos autômatos do ambiente VKPA organiza a transição para o estado inicial “f0” do autômato incorporado e os estados deste último se tornam os estados atuais do processo. A transição do autômato aninhado para o estado final "00" retorna o cálculo para o nível anterior de aninhamento e, no nosso caso, para a conclusão da transição do autômato de nível superior para o estado t2. Em seguida, o processo, em uma transição incondicional do estado "t2" para o estado "t1", executa a ação y2, que define o resultado do cálculo do fatorial da variável local do processo dF.

Observe e é muito importante que o resultado de um autômato aninhado esteja disponível somente após a conclusão de seu trabalho e a transição para o próximo estado de um autômato de nível superior. Será possível obtê-lo (resultado) através de um ponteiro para um objeto de um autômato aninhado.

E tudo ficaria bem se não fosse o tempo de execução da função recursiva. Em comparação com a sub-rotina usual, devido ao aninhamento, em geral, é muito maior e, portanto, pode violar a atomicidade condicional das ações de processos automáticos, cujo tempo total de execução deve se encaixar no valor de um ciclo de relógio discreto.

No nosso caso, o cálculo do fatorial é bastante pequeno e até o valor máximo de um resultado duplo para n = 170 se encaixa em 1 microssegundo. Para calcular valores grandes, é preciso mudar para a aritmética longa (veja, por exemplo, [4, 5]). Ao mesmo tempo, o tempo de computação fatorial aumentará ainda mais e quase garantirá ir além do ciclo de relógio discreto, afetando a velocidade das máquinas de rede restantes que operam no modo multitarefa não-preventiva e a reatividade da resposta do aplicativo como um todo, que se manifestará em seus "freios".

Você pode manter-se dentro de um ciclo de relógio discreto e se livrar do defeito dos “freios” expandindo o cálculo em etapas. Para esses propósitos, é conveniente converter o algoritmo fatorial usual em forma automática. É verdade que, devido ao modo de interpretação dos autômatos, o tempo de cálculo aumentará, mas as propriedades temporais do aplicativo retornarão ao normal.

A Listagem 3 mostra o cálculo do fatorial em sua forma usual e na forma preparada para conversão subsequente em uma forma de autômato. O último representa explicitamente etapas atômicas que estão ocultas no código fonte do programa. Nesse caso, estamos falando de operadores da forma y = f (...), onde f é uma função de programa comum ou recursiva. Esse registro mascara o tempo de operação da função e cria uma falsa impressão da atribuição "instantânea" do valor da variável y. Na realidade, não existe um nem o outro.

Listagem 3. Funções de software para calcular fatorial
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;
    }
}


Na estrutura do conceito de programação automática, ações atômicas (métodos) de objetos automáticos de software são consideradas condicionalmente instantâneas. E se apenas o tempo total de operação das ações se encaixar em um único ciclo de tempo discreto de espaço de autômato, a implementação do software corresponde ao seu modelo formal.

Observação 1. O tempo total total de operação das ações em um ou outro ciclo de relógio discreto pode variar bastante. No caso de exceder o tempo de ciclo, o ambiente VKPA tenta compensá-lo nos ciclos subsequentes da operação espacial do autômato, reduzindo, se possível, o tempo discreto dos ciclos subsequentes.

Na fig. A Figura 1 mostra um diagrama de blocos que inclui a marcação que reflete os estados de uma máquina de estados finitos equivalente e os nomes de seus predicados e ações. O próprio modelo de autômato na forma de um gráfico do autômato é mostrado na Fig. 2.

imagem
Fig. 1. Diagrama de blocos do fatorial do algoritmo recursivo

imagem
Fig. 2. Um modelo de autômato de um algoritmo fatorial recursivo

O código para a rotina automática de cálculo do fatorial é mostrado na Listagem 4. Os comentários na tabela de transição (TP) refletem o tempo de cálculo do fatorial em ms e o número de etapas distintas gastas no procedimento de cálculo para n = 170. E se o tempo de cálculo depende da velocidade da plataforma de computação e / ou do tipo de projeto (depuração / liberação), o número de etapas discretas (ciclos de clock) é determinado apenas pelas propriedades do algoritmo e pode servir como uma avaliação objetiva da velocidade do algoritmo, independentemente da forma de sua apresentação e implementação.

No caso de um modelo de autômato, o número de ticks discretos pode ser calculado de maneira bastante simples e, após coletar determinadas estatísticas, derivar uma fórmula analítica para a velocidade do algoritmo. Entretanto, essas estimativas são muito aproximadas e baseiam-se em conclusões, muitas vezes obtidas como resultado de um raciocínio bastante complexo.

Listagem 4. Rotina fatorial 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. Conclusões


Admito que, devido às especificidades das tarefas a serem resolvidas, na verdade não precisei usar e desenvolver algoritmos recursivos em projetos reais, exceto para fins de treinamento e para testar o kernel para a implementação de aninhamento. Rotinas automatizadas - quase constantemente e em grandes números. Entre elas, as sub-rotinas chamadas inerciais são especialmente interessantes (para mais detalhes, consulte [3]). Mas eles deveriam dedicar um artigo separado à sua consideração.

Algoritmos recursivos são uma parte importante da teoria do programa [6]. Sem a implementação de rotinas e recursão, é difícil imaginar um modelo computacional eficiente e conveniente sob todos os pontos de vista. E para implementar a recursão, dadas as possibilidades de programação de objetos (veja exemplos do artigo), depois de criar um modelo de subprogramas, não é tão difícil. Obviamente, você pode usar certos métodos de conversão da recursão em uma forma regular, ignorando-a usando os mesmos ciclos. Mas é preferível não se livrar dele estupidamente, mas ter mecanismos diretos para sua implementação. Obviamente, será mais lento, é claro, mais caro em termos de recursos (despesas da mesma memória de pilha), mas com os recursos de hardware existentes, isso não será tão crítico.

Mas algoritmos recursivos também são interessantes como testes para avaliar as capacidades, universalidade e eficácia dos modelos algorítmicos. Nesse sentido, o modelo de autômato não apenas implementa a recursão de maneira bastante eficaz, mas também adiciona "chips de autômato" como bônus - a capacidade de controlar o estado interno do algoritmo recursivo, contar etapas para avaliar o desempenho, controlar o tempo de execução do algoritmo etc. etc.

Combater a recursão é inútil o suficiente. Deve ser capaz de usar. Vou citar com a qual concordo completamente: "À primeira vista, a recursão pode parecer complicada. Mas, em alguns casos, o método recursivo é incrivelmente eficaz se tudo for feito corretamente. No entanto, às vezes é melhor usar loops. A compreensão de ambos os métodos e a capacidade de usá-los efetivamente o ajudarão no seu trabalho e serão uma vantagem na entrevista ”[7]. Só posso acrescentar que modelos automáticos de algoritmos recursivos tornam possível, usando as "propriedades automáticas" de um modelo computacional, entender a recursão, depurar e refinar esse algoritmo muito mais rapidamente.

E o último. No entanto, gostaria de obter uma resposta para a pergunta - como estão as coisas com a recursão da corotina? Eu já perguntei, mas não recebi uma resposta ... Afinal, uma coisa é criar um milhão de rotinas (veja [8] para exemplos) e outra implementar um algoritmo recursivo que tem um nível de aninhamento que não é o mesmo, mas alto o suficiente. E, ao que parece, a resposta a esta pergunta interessa não apenas a mim ... [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