Teoria da Computação
Programas
Fabrício Dias
[email protected]
Agenda


Composição de instruções
Programa


Programa iterativo
Programa recursivo
Composição de instruções

Duas ou mais operações básicas ou testes
podem ser classificados como:



Composição seqüencial
Composição não-determinista
Composição concorrente
Composição de Instruções

Composição seqüencial


Composição não-determinista


A execução de uma operação ou teste subseqüente
somente pode ser realizada após o encerramento da
execução da operação ou teste anterior
Uma das operações ou testes compostos é escolhido pra
ser executada
Composição concorrente

As operações ou testes compostos podem ser executados
em qualquer ordem, inclusive simultaneamente. Ou seja, a
ordem de execução é irrelevante.
Relembrando...

Programa:

É um conjunto estruturado de instruções que
capacitam uma máquina a aplicar
sucessivamente certas operações básicas e
testes em dados iniciais fornecidos, até que
esses dados se transformem na forma desejada.
Observação

Observação:

Uma operação que não faz coisa alguma, é
denominada: operação vazia, denotada pelo
símbolo √
Tipos de programa



Programa monolítico
Programa iterativo
Programa recursivo
Programa Iterativo

São baseados nos seguintes mecanismos de
composição de programa:




Seqüencial
Condicional
Enquanto
Até
Programa Iterativo

Programa iterativo seqüencial


Composição de dois programas, resultando em
um terceiro, cujo efeito é a execução do primeiro
e depois do segundo programa componente.
Exemplo: P -> V;W
Programa Iterativo Seqüencial

Definição:

Composição seqüencial: se V e W são programas
iterativos, então a composição seqüencial é
denotada por V;W e resulta em um programa
iterativo cujo efeito é a execução de V e depois a
execução de W.
Programa Iterativo



Programa Iterativo Condicional
Composição de dois programas, resultando em
um terceiro, cujo efeito é a execução de somente
um dos dois programas componentes
dependendo do resultado do teste.
Exemplo: (Se T entãoV senão W)
Programa Iterativo Condicional

Definição:

Composição condicional: se V e W são
programas iterativos, e T é um identificador de
teste, então a composição condicional é denotada
por (se T então V senão W) e
resulta em um programa iterativo cujo efeito é a
execução de V se T é verdadeiro ou W se T é
falso;
Programa Iterativo

Programa Iterativo Enquanto


Composição de um programa, resultando em um
segundo, cujo efeito é a execução,
repetidamente, do programa componente
enquanto o resultado de um teste for verdadeiro.
Exemplo: Enquanto T faça V.
Programa Iterativo Enquanto

Definição:

Composição enquanto: se V é um programa iterativo,
e T é um identificador de teste, então a composição
enquanto é denotada por
enquanto T faça (V)
resulta em um programa iterativo que testa T e
executa V, repetidamente, enquanto o resultado do
teste for o valor verdadeiro. Caso contrário, a iteração
termina.
Programa Iterativo

Programa Iterativo Até


Análoga a composição enquanto, diferente
apenas porque a execução do programa
componente ocorre enquanto o resultado de um
teste for falso
Exemplo: Até T faça (V)
Programa Iterativo Até

Definição:


Composição até: se V é um programa iterativo, e T é
um identificador de teste, então a composição até é
denotada por até T faça (V)
resulta em um programa iterativo que testa T e
executa V, repetidamente, enquanto o resultado do
teste for o valor falso. Caso contrário, a iteração
termina.
Programa Iterativo

Exemplo:
•Condicional
(se T1
então enquanto T2
faça (até T3
faça (V;W))
senão √)
•Enquanto
•Até
•Seqüencial
•Vazio
Tradução de programa iterativo
em monolítico

A tradução de Programas Iterativos para
Monolíticos é considerada intuitiva.
Entretanto, a inversa não é verdadeira, ou
seja, fluxogramas nem sempre podem ser
traduzidos para programas iterativos
equivalentes, para qualquer máquina.
Programa Iterativo

Exemplo
enquanto T faça (V)
Transformando para
monolítico...
V
v
T
Programa Recursivo





Recursão é uma forma indutiva de definir programas
Capacidade de um programa de referenciar a si próprio como
sub-rotina
Sub-rotinas permitem a estruturação hierárquica de programas,
possibilitando níveis diferenciados de abstração
Processo de empilhamento é implícito
O conjunto de Identificadores de Sub-rotinas é descrito por
R1, R2, R3 …, Rn
Programa Recursivo

Expressão de sub-rotina

Uma expressão de sub-rotina E, é definida
indutivamente por:



A operação vazia √ constitui uma expressão de subrotinas
Cada identificador de operação constitui uma
expressão de sub-rotinas
Cada identificador de sub-rotina constitui uma
expressão de sub-rotinas.
Programa Recursivo

Expressão de sub-rotina (Continuação)

Composição seqüencial: Se D1 e D2 são
expressões de sub-rotinas, então a
composição seqüencial denotada por: D1 ;
D2 resulta em uma expressão de subrotina
cujo efeito é a execução de D1 e, após, a
execução de D2.
Programa Recursivo
Expressão de sub-rotinas (continuação)
 Composição condicional: Se D1 e D2 são
expressões de sub-rotinas e T é um
identificador de teste, então a composição
condicional denotada por:
(se T então D1 senão D2)
resulta em uma expressão cujo efeito é a
execução de D1 se T é verdadeiro ou D2 se
T é falso.
Programa Recursivo

Definição:

Um programa recursivo P tem a seguinte forma:
P é E0 onde R1 def E1, R2 def E2, ...,
Rn def Em

Onde:
 E0 é a Expressão Inicial a qual é uma expressão
de sub-rotina;
 En é a Expressão que define Rn ou seja, a
expressão que define a sub-rotina identificada por
Rn;
 A operação vazia  constitui um programa
recursivo que não faz coisa alguma
Programa Recursivo

Exemplo:
P é R ; S onde
R def F; (se T então R senão G;S)
S def (se T então √ senão F;R)
Dúvidas???