Programas Recursivos e conversão de Programas Monolíticos 1
Cláudia Santos Fernandes, Daniela Tereza Ascencio Russi,
Francisco Assis da Silva, Liliane Jacon Jacob
Mestrado Remoto da UFRGS/FACCAR
E-mail: {claudia, daniela, chico, liliane}@apec.unoeste.br
Abstract
The basic concepts of programs, monolithic programs and recursive programs
provide a theory basis needed to introduce other concepts on Computer Science. The
propose of this article is to present the software “Recursive Programs” which permits
conversion of monolithic programs into simple labeled instructions to a recursive
program, and also simplifying it. The proposal to use the software is to be used as a tool
to teach computer theory subject. This article presents the computer environment with
the procedures to install and execute, the help system, as well as examples of how to use
this software.
1 - Introdução
O estudo de Teoria da Computação proporciona um embasamento teórico para um
melhor entendimento da ciência envolvida na computação, necessário para o
desenvolvimento do raciocínio lógico e formal de aluno de Ciência da Computação.
Este estudo compreende noções mais formais de programas, máquinas, algoritmos e
computações, estabelecendo os limites da ciência da computação (onde nem tudo é
computável).
Os conceitos básicos de programas, máquinas e funções computáveis são de vital
importância para a Ciência da Computação, pois são o alicerce para as disciplinas que
tratam de linguagens de programação. É necessário formalizar esses conceitos para que
seja possível estender e aprofundar o estudo em Teoria da Computação, tais como:
computação, Máquinas Universais, funções recursivas, computabilidade, etc.
Em Teoria da Computação são introduzidos os conceitos fundamentais que são
desenvolvidos em outras áreas, e um dos tópicos estudado é sobre a complexidade
estrutural que diz respeito à estrutura de controle adotada e à otimização em termos de
número de instruções e da eliminação de instruções desnecessárias.
O conceito de programa, segundo [DIV99], pode ser visto como um conjunto de
operações e testes compostos de acordo com uma estrutura de controle. Conforme a
estrutura utilizada determina-se a classificação do programa: monolítico, iterativo ou
recursivo.
Este artigo tem como objetivo apresentar os conceitos básicos para o estudo de
programas recursivos e apresentar o software “Construção de Programas Recursivos”,
desenvolvido como aplicação prática dos conceitos teóricos estudados.
O artigo está dividido em seis capítulos. No capítulo 2 é descrito detalhadamente a
classificação de Programas Monolíticos e Recursivos. O capítulo 3 aborda o Ambiente
1
Trabalho desenvolvido como tarefa da disciplina CMP313 Teoria da Computação I no
Mestrado em Ciência da Computação da UFRGS ministrada na FACCAR em Rolândia.
Computacional: equipamento necessário ou recomendado para executar o software,
linguagem de programação e procedimentos de instalação e execução do software. O
objetivo do software, a interface, o sistema de ajuda e as principais características são
detalhados no capítulo 4. Com o intuito de oferecer um melhor entendimento da
interface gráfica que o usuário irá encontrar, no capítulo 5 são demonstrados através de
exemplos o processo de execução do software. O capítulo 6 apresenta as conclusões
deste trabalho.
2 - Programas
Programas podem ser descritos como um conjunto estruturado de instruções que
capacitam uma máquina a executar sucessivamente certas operações básicas e testes
sobre os dados iniciais fornecidos, com o objetivo de transformar estes dados numa
forma desejável. Sendo que existem várias formas de estruturação de controle e essas
formas classificam os programas em:
Monolítico, com apenas desvios condicionais e incondicionais;
Iterativo, possui estruturas de iteração de trechos de programas;
Recursivo, baseado em sub-rotinas recursivas.
Independentemente da estrutura de controle, duas ou mais operações ou testes
podem ser compostos. Sendo que para o estudo de programas, as operações e os testes
serão identificados pelo nome, descritos a seguir:
Identificadores de operações: F, G, H, ...
Identificadores de testes: T.
Uma operação de teste produz somente um valor, podendo ser verdadeiro (v) ou
falso (f). Se a operação não faz nada, ela é denominada como operação vazia ( ).
2.1 – Programa Monolítico
É um programa estruturado, usando desvios condicionais e incondicionais, sem
fazer uso explícito de mecanismos auxiliares de programação que permitam uma melhor
estruturação do controle como iteração, subdivisão ou recursão. O programa monolítico
pode ser especificado na forma de fluxograma (diagramática), mas além dessa forma
pode também ser denotado na forma de texto (melhor descrito), através do uso de
instruções rotuladas. Onde cada instrução rotulada é identificada por um rótulo(cadeia
de caracteres finita (letras e/ou dígitos)), sendo:
Composta por:
Operação: indica a operação a ser executada seguida de um desvio
incondicional para a instrução subsequente.
Teste: determina um desvio condicional, ou seja, que depende da avaliação de
um teste.
Onde:
Não existem duas instruções diferentes com um mesmo rótulo.
E a parada é especificada usando um desvio incondicional para um rótulo sem
instrução associada (instrução vazia).
2.2 – Programas Recursivos
Encontrado com diversas variações, na maioria das linguagens de alto nível que
admitem sub-rotinas recursivas.
Recursão: é uma forma indutiva de definir programas.
Sub-rotinas: permitem a estruturação hierárquica de programas, possibilitando
níveis diferenciados de abstração. Indentificadores de Sub-rotinas são: R1,
R2,...
A computação de um programa recursivo consiste na avaliação da expressão
inicial onde cada identificador de Sub-rotina referenciado é substituído pela
correspondente expressão que o define, e assim sucessivamente, até que seja substituído
pela expressão vazia , determinando o fim da recursão.
Um Programa Recursivo P tem a seguinte forma:
P é E0 onde R1 def E1, R2 def E2, ..., Rn def En
Onde (suponha K ∈ {1, 2, ..., n}):
E0: Expressão inicial a qual é uma expressão de sub-rotinas;
Ek: Expressão que define Rk , a expressão que define a sub-rotina identificada
por Rk.
A operação vazia constitui um programa recursivo que não faz coisa alguma.
3 – Ambiente Computacional
Neste capítulo são abordados alguns aspectos para funcionalidade do software,
conforme descrição a seguir:
3.1 – Equipamento necessário ou recomendado
Microcomputador 486 DX4 – 100 Mhz (ou superior)
16 Mbytes de RAM
monitor SVGA
3 Mbytes de espaço livre em disco rígido
Ambiente: Windows 95 ou versão superior
Configuração de vídeo: 800x600 pixels
3.2 – Linguagem de Programação
O ambiente de programação escolhido para implementação do software foi
Borland Delphi 3, em linguagem Object Pascal. O Delphi é uma ferramenta de fácil
utilização e permite desenvolver aplicativos for Windows.
3.3 - Procedimentos de Instalação do Software
As telas a seguir mostram o processo de instalação do software “Construção de
Programas Recursivos”.
Procedimento 1
Ligue o computador;
Ao iniciar o Sistema Operacional Windows 95 insira no drive 3 ½” do seu
computador o disco de Instalação do software;
Click com o mouse no botão Start (Iniciar) e logo em seguida no item de menu
Run (Executar), figura 1;
Figura 1 – Menu Run (Executar)
Procedimento 2
Ao aparecer a tela abaixo Run (Executar), digite no campo Open (Abrir)
A:\SETUP e click com o mouse no botão OK, figura 2;
Figura 2 – Tela Run (Executar)
Procedimento 3
Aparecerá uma tela dizendo “Bem vindos ao programa de instalação do Programa
Recursivo. Esse programa instalará o Programa Recursivo no seu computador”,
figura 3;
Click com o mouse no botão Next (Próximo);
Figura 3 – Tela Welcome (Bem vindos)
Procedimento 4
Caso você deseje mudar o diretório (local de instalação), click com o mouse no
botão Browse (Procurar) para mudar o diretório de Instalação do Software na Tela
Choose Destination Location (Escolha a Localização de Destino), figura 4;
Figura 4 – Tela Welcome Choose Destination Location
Procedimento 5
Digite no campo Program Folders (Pasta do Programa) na tela Select Program
Folder (Selecione a pasta do Programa), “Programas Recursivos” ou outro nome
para que este seja criado no menu Programas a partir do botão Iniciar, e click no
botão Next (Próximo) , figura 5;
Figura 5 – Select Program Folder
A tela abaixo mostra o Software sendo Instalado do Winchester (Disco Rígido)
do seu computador, onde a barra progressiva indica o percentual da instalação, figura 6.
Figura 6 – Programa sendo instalado no Winchester (Disco Rígido)
Procedimento 6
Click com o mouse no botão Finish (Finalizar) para completar a instalação na tela
Setup Complete (Instalação Completa), figura 7.
Figura 7 – Setup Complete (Instalação Completa)
3.4 - Procedimento de Execução do Software
Click com o mouse no botão Start (Iniciar), em seguida na opção Programs
(Programas) e então escolha o item “Programas Recursivos”, figura 8.
Figura 8 – Procedimentos de Execução do Software
4 – Características do Software “Programas Recursivos”
O objetivo do software desenvolvido é converter programa monolíticos na forma
de Instruções Rotuladas Simples para Programa Recursivo, além de possibilitar a
simplificação do mesmo. O usuário pode criar ou editar um Programa Recursivo, com
opções para adicionar novas instruções, removê-las, desfazer/refazer operações e
imprimir o Programa Recursivo simplificado ou não.
O ambiente gráfico do software permite visualização passo a passo do processo de
simplificação de Programas Recursivos. A interface gráfica do software proporciona um
ambiente amigável com o intuito de diminuir a distância entre homem-máquina. O
software “Construção de Programas Recursivos” tem como público alvo alunos de
graduação e pós-graduação em Ciência da Computação, que se interessem pela
disciplina de Teoria da Computação.
A interface do software por ser no ambiente Windows é muito interativa. Cada
botão apresenta um breve comentário da sua utilização, bastando o usuário posicionar o
mouse sobre o botão desejado. Para um maior esclarecimento sobre a utilização das
funcionalidades do software, existe uma ajuda interativa (help system) incorporada,
ilustrada na figura 9, que é disponibilizada através do botão Ajuda ou da tecla F1.
Figura 9 – Ajuda interativa (help system)
5 - Exemplos
Na tela de abertura, ilustrado na figura 10, a opção a ser escolhida para a entrada
na tela de Construção de Programas Recursivos, deve ser o botão “Programa
Recursivo”.
Figura 10 – Tela de abertura
Após entrar na tela da Construção de Programas Recursivos, o usuário pode
escolher por exemplo converter um programa monolítico (Instruções Rotuladas
Simples) em Programa Recursivo e ou simplificá-lo, bem como poder editá-lo.
5.1 – Exemplo de conversão de um programa monolítico na forma de Instruções
Rotuladas Simples para programa recursivo
O software oferece a opção de abrir, visualizar e converter programas monolíticos
na forma de Instruções Rotuladas Simples em programas recursivos para possível
edição, simplificação ou impressão do programa. A figura 11 ilustra o programa
monolítico (Instruções Rotuladas Simples) e ao fundo o programa recursivo
correspondente.
Figura 11 – Visualização do Programa monolítico (Instruções Rotuladas Simples)
5.2 – Exemplo de Simplificação de um Programa Recursivo
Este software oferece opções de entrar com as instruções para criar um novo
programa recursivo, ou abrir um já existente (botões “Novo” e “Abrir” na figura 2).
Para introduzir uma linha na tela de edição do programa, primeiramente o usuário
escolhe se a instrução é um teste, uma operação, ou então uma instrução vazia (v). Se a
instrução for um teste, devem ser preenchidos os campos de destino: quando a condição
for verdadeira e quando for falsa. No caso das operações, devem ser informados a
operação e o desvio. Em seguida, pressiona-se o botão “Entrar Instrução”. Esse
procedimento é repetido para cada instrução do programa. A figura 12 ilustra um
Programa Recursivo editado pelo software.
Figura 12 – Edição de um Programa Recursivo
O usuário pode editar o programa, através da inclusão de novos comandos, alterar
os já existentes, remover linhas, selecionar e copiar blocos, bem como selecionar todo o
programa. É possível também desfazer ou refazer as ações do usuário.
Após a entrada dos comandos do Programa Recursivo, o usuário pode realizar a
simplificação do mesmo, figura 13. Esta etapa pode ser executada passo a passo, ou
então ser executada de uma única vez. Para o usuário visualizar cada passo no processo
de simplificação, é sugerida a opção “passo a passo”. O botão passo a passo aparecerá
após o usuário pressionar o botão simplificar.
Figura 13 – Programa recursivo simplificado
A opção “imprimir” pode ser executada antes ou após a simplificação do
Programa Recursivo. Caso o usuário deseje imprimir após a simplificação, o software
imprime o Programa Recursivo e sua simplificação correspondente.
6 - Conclusões
A construção do software e a confecção deste artigo exigiu por parte de todos os
elementos do grupo, a fixação de conteúdos, tais como: conceito de programas e a sua
classificação, de acordo com as estruturas de controle utilizadas. Contudo, o enfoque do
software é editar, simplificar e imprimir Programas Recursivos, além de converter
programas monolíticos na forma de Instruções Rotuladas Simples em Programas
Recursivos. Mas o processo de simplificação de Programas Recursivos foi o tema que
proporcionou maior aprofundamento no assunto em questão.
Este software pode ser utilizado como ferramenta de auxílio no ensino da
disciplina de Teoria da Computação, com o objetivo de apresentar aos alunos a
visualização do processo de simplificação de Programas Recursivos, bem como permitir
a introdução de novos exemplos para efeito de estudo.
7 – Referência Bibliográfica
[DIV99] DIVERIO, T. A.; MENEZES, P. B., Teoria da Computação – Máquinas
Universais e Computabilidade. Porto Alegre: Sagra-Luzzato, 1999.
205p. (Série Livros Didáticos do Instituto de Informática da UFRGS, N.5.)