TEORIA DA COMPUTAÇÃO · TEORIA DA COMPUTAÇÃO UNIVERSIDADE FEDERAL RURAL DO SEMI-ÁRIDO CURSO:CIÊNCIA DA COMPUTAÇÃO Aula 03 Aula 03 ––Programas Programas (Monolítico e

TEORIA DA COMPUTAÇÃOTEORIA DA COMPUTAÇÃO

UNIVERSIDADE FEDERAL RURAL DO SEMI-ÁRIDOCURSO: CIÊNCIA DA COMPUTAÇÃO

Aula 03 Aula 03 –– Programas Programas (Monolítico e Iterativo)(Monolítico e Iterativo)

Prof.ª Danielle Casillo

Programas, Máquinas e Programas, Máquinas e ComputaçõesComputações

� Diferentes computadores podem ter diferentesarquiteturas e os diversos tipos de linguagem deprogramação.◦ Suas características essenciais são descritas em◦ Suas características essenciais são descritas emmodelos matemáticos simples;

◦ Isso permite um rápido entendimento de suassemânticas;

◦ Facilitando a demonstração de resultados.

Teoria da Computação - Aula 03 2

ProgramaPrograma

� Definição: Conjunto de operações e testescompostos de acordo com uma estrutura decontrole.

� O tipo de estrutura de controle associadadetermina uma classificação de programascomo:como:◦ Monolítico: baseada em desvios condicionais eincondicionais;

◦ Iterativo: possui estruturas de iteração detrechos de programas;

◦ Recursivo: baseado em sub-rotinas recursivas.


ProgramaPrograma

� É descrito como um conjunto estruturado deinstruções que capacitam uma máquinaaplicar sucessivamente certas operaçõesbásicas e testes em uma parte determinadados dados iniciais fornecidos, até que essesdos dados iniciais fornecidos, até que essesdados tenham se transformado numa formadesejável.

� Um programa deve possuir uma estrutura decontrole de operações e testes.


ProgramaPrograma

� Estruturação Monolítica: É baseada emdesvios condicionais e incondicionais, nãopossuindo mecanismos explícitos de iteração,subdivisão ou recursão.

� Estruturação Iterativa: Possui mecanismos� Estruturação Iterativa: Possui mecanismosde controle de iterações de trechos deprogramas.

� Estruturação Recursiva: Possui mecanismosde estruturação em subrotinas recursivas.Recursão é uma forma indutiva de definirprogramas.


Composição de instruçõesComposição de instruções

� Composição Sequencial: A execução daoperação ou teste subsequente somente podeser realizada após o encerramento da execuçãoda operação ou teste anterior.

� Composição Não Determinista: Uma das� Composição Não Determinista: Uma dasoperações (ou testes) compostas é escolhidapara ser executada.

� Composição Concorrente: As operações outestes compostos podem ser executados emqualquer ordem, inclusive simultaneamente, ouseja, a ordem de execução é irrelevante.


Instruções: operações e testesInstruções: operações e testes

� Não é necessário saber qual a natureza precisa dasoperações e dos testes que constituem asinstruções. Serão conhecidas pelos seus nomes.◦ Identificadores de Operações: F, G, H, ...◦ Identificadores de Testes: T1, T2, T3, ...Um teste é uma operação de um tipo especial a� Um teste é uma operação de um tipo especial aqual produz somente um dos dois possíveis valoresverdade, ou seja, verdadeiro ou falso, denotadospor: v e f, respectivamente.

� Uma operação que não faz coisa alguma,denominada: operação vazia, denotada pelosímbolo .


Resumindo...Resumindo...

� Definições:◦ Programas Monolíticos, Iterativos, Recursivos;◦ Estruturas de programa;◦ Composições de instruções:

� Sequencial;� Sequencial;� Não determinista;� Concorrente;

◦ Instruções:� Identificadores de operações;� Identificadores de testes.


Programa MonolíticoPrograma Monolítico

� É estruturado, usando desvios condicionais eincondicionais, não fazendo uso explícito demecanismos auxiliares de programação. A lógicaé distribuída por todo o bloco (monólito) queconstitui o programa.


Programa MonolíticoPrograma Monolítico� Fluxogramas:

◦ É uma das formas mais comuns de especificarprogramas monolíticos;

◦ É um diagrama geométrico construído a partir decomponentes elementares denominados:

◦ No caso da operação vazia , o retângulocorrespondente que à operação pode ser omitido,resultando simplesmente em uma seta.


testev f

operaçãopartida parada


� Exemplo de um fluxograma

T1v

partida

F


1

f

G

T2

v

f

parada


� Instruções rotuladas:◦ Fluxogramas podem ser reescritos na forma detexto, usando instruções rotuladas. São utilizadosrótulos.


1: faça F vá_para 22: se T1 então vá_para 1 senão vá_para 33: faça G vá_para 44: se T2 então vá_para 5 senão vá_para 1


◦ Uma instrução rotulada pode ser:� Operação: Indica a operação a ser executadaseguida de um desvio incondicional para ainstrução subsequente.

� Teste: Determina um desvio condicional, ou seja,


� Teste: Determina um desvio condicional, ou seja,que depende da avaliação de um teste.

� Uma parada é especificada usando um desvioincondicional para um rótulo sem instruçãocorrespondente.

� Assume-se que a computação sempre inicia norótulo 1:


� Definição:◦ Rótulo: ou Etiqueta é uma cadeia de caracteresfinita constituída de letras ou dígitos.

◦ Instrução rotulada: é uma sequência desímbolos de uma das duas formas a seguirsímbolos de uma das duas formas a seguir(suponha que F e T são identificadores deoperação e teste, respectivamente e que r1, r2 er3 são rótulos):� Operação r1: faça F vá_para r2 ou r1: faça vá_para r2

� Teste r1: se T então vá_para r2 senão vá_para r3



� Um programa monolítico P é um par ordenadoP = (I, r)

onde:I Conjunto de instruções rotuladas o qual éfinito;finito;r Rótulo inicial o qual distingue a instrução

rotulada inicial em I.



� Resumindo:◦ Não existem duas instruções diferentes com ummesmo rótulo;

◦ Um rótulo referenciado por alguma instrução oqual não é associado a qualquer instruçãoqual não é associado a qualquer instruçãorotulada é dito um Rótulo Final.

◦ A definição de programa monolítico requer aexistência de pelo menos uma instrução,identificada pelo rótulo inicial.


ExemploExemplo

� São exemplos de programas monolíticos:a) P1 = (I1, 1)

Em que I1 é o conjunto constituído pelasinstruções rotuladas 1, 2, 3 e 4. Neste caso qual éo rótulo final?o rótulo final?


1: faça F vá_para 22: se T1 então vá_para 1 senão vá_para 33: faça G vá_para 44: se T2 então vá_para 5 senão vá_para 1

ExemploExemplo

� São exemplos de programas monolíticos:b) P2 = (r1: faça vá para r2) em que r2 é um

rótulo final. Qual o correspondente fluxograma?


Programa monolítico X Programa monolítico X FluxogramaFluxograma

� O mecanismo de composição sequencialdado pelas instruções rotuladas é do tipo maisfundamental de controle de estrutura.

� É a estrutura básica utilizada pela maioria daslinguagens de montagem (Assembly) e éincorporada de certa maneira a outraslinguagens de alto nível.


Programa IterativoPrograma Iterativo

� São baseados em quatro mecanismos decomposição (sequenciais) de programas, osquais podem ser encontrados em um grandenúmero de linguagens de alto nível.



� Esses mecanismos de composição são:◦ Sequencial◦ Condicional◦ Enquanto◦ Até◦ Até

� Sequencial: composição de dois programas,resultando em um terceiro, cujo efeito é aexecução do primeiro e, após, a execução dosegundo programa componente;



� Condicional: composição de dois programas,resultando em um terceiro, cujo efeito é aexecução de somente um dos dois programascomponentes, dependendo do resultado de umteste;

� Enquanto: composição de um programa,resultando em um segundo, cujo efeito é aexecução, repetidamente, do programacomponente enquanto o resultado de um testefor verdadeiro.



� Até: análoga à composição enquanto,excetuando que a execução do programacomponente ocorre enquanto o resultado de umteste for falso.



� Um Programa Iterativo P é indutivamentedefinido por:◦ A operação vazia constitui um programaiterativo;iterativo;

◦ Cada identificador de operação constitui umprograma iterativo;

◦ Composição Seqüencial: V; W

◦ Composição Condicional: (se T então Vsenão W)



� Um Programa Iterativo P é indutivamentedefinido por:◦ Composição Enquanto: enquanto T faça (V).Resulta no programa que testa T e executa V,repetidamente, enquanto o resultado do teste forrepetidamente, enquanto o resultado do teste foro valor verdadeiro.

◦ Composição Até: até T faça (V). Resulta noprograma que testa T e executa V,repetidamente, enquanto o resultado do teste foro valor falso.



� Os parênteses são usados para possibilitar ainterpretação, de forma unívoca, por partesconsistentes.

enquanto T faça V; Wenquanto T faça V; W

admite duas interpretações distintas,

(enquanto T faça V);Wenquanto T faça (V;W)



� Fluxograma que simula a composição enquanto

Tv f

V

� Qual seria o correspondente fluxograma para a composição até?

� Em que condição na execução de umenquanto, V pode não ser executado?



� Exemplo: o programa abaixo é do tipo iterativo.

(se T1 entãoenquanto T2 faça

(até T faça (V;W))(até T3 faça (V;W))senão )

Traduza este programa para monolitico nas formas de fluxograma e instrução rotulada.


EExercíciosxercícios

1. Desenhe um fluxograma que corresponde acada um dos seguintes programas:

a) Programa sem instrução alguma Partida

NÃO EXISTE

a) Programa sem instrução de parada


Prada

ExercíciosExercícios

2. Relativamente a programas iterativo:

a) Porque a operação vazia constitui um programaiterativo?

Resp: Por definição de Programa iterativo, temos que


Resp: Por definição de Programa iterativo, temos quecada identificador de operação e a operação � constituium programa iterativo. Pois a operação � é a base daindução para a definição de programa iterativo.

ExercíciosExercícios

b) Por que pode-se afirmar que:A tradução de um programa iterativo para ummonolítico é trivial?

Resp: Porque para cada instrução iterativa existe umfluxograma correspondente. Cada instrução iterativa é


fluxograma correspondente. Cada instrução iterativa édefinida por um fluxograma.

ExercíciosExercícios3. Faça o fluxograma do seguinte programa

monolítico:

1: Se T1 vá para 2 senão vá para 32: Faça G vá para 43: Faça F1 vá para 44: Se T2 vá para 6 senão vá para 5

4. Faça o programa iterativo para o exemploacima


4: Se T2 vá para 6 senão vá para 55: Faça F2 vá para 1

Se T1 então G senão F1Até T2 faça F2

ExercíciosExercícios5. A partir do fluxograma, escreva o programa

monolítico através das instruções rotuladas.


1: Faça F vá para 22: Se T1 vá para 1 senão vá para 33: Faça G vá para 44: Se T2 vá para 5 senão vá para 1

Documents

TEORIA DA COMPUTAÇÃO · TEORIA DA COMPUTAÇÃO UNIVERSIDADE FEDERAL RURAL DO SEMI-ÁRIDO CURSO:CIÊNCIA DA COMPUTAÇÃO Aula 03 Aula 03 ––Programas Programas (Monolítico e