UNIVERSIDADE FEDERAL RURAL DO SEMI-ÁRIDO … · NORMA (NumberTheOreticRegisterMA chine) Possui como memória um conjunto infinito de registradores naturais e três instruções sobre

UNIVERSIDADE FEDERAL RURAL DO SEMI-ÁRIDO

CURSO: CIÊNCIA DA COMPUTAÇÃO

Prof.ª Danielle Casillo

� NORMA (Number TheOretic Register MAchine)

� Possui como memória um conjunto infinito deregistradores naturais e três instruções sobre cadaregistrador:registrador:

� Adição do valor um;� Subtração do valor um;� Teste se o valor armazenado é zero.

TC - Máquina NORMA 2

� NNNN∞∞∞∞ denota o conjunto de todas as uplas com infinitos(mas contáveis) componentes sobre o conjunto dosnúmeros naturais .� Ex: (0, 1, 2, 3, ...) e (5, 5, 5, 5, ...)

� Para evitar subscritos, as componentes das uplas sãodenotadas por letras maiúsculas como A, B, X, Y, ...,as quais denotam os registradores na MáquinaNORMA.


Definição: Máquina NORMA

� A Máquina NORMA é uma 7-upla (suponha que Kseja um registrador, K∈∈∈∈ { A, B, X, Y,... }):seja um registrador, K∈∈∈∈ { A, B, X, Y,... }):

NORMA = (NNNN∞∞∞∞, NNNN, NNNN, ent, sai, { adK, subK }, { zeroK })



a) Cada elemento do conjunto de valores de memória NNNN∞∞∞∞

denota uma configuração de seus infinitos registradores, osdenota uma configuração de seus infinitos registradores, osquais são denotados por: A, B, X, Y, ...

b) A função de entrada: ent: NNNN →→→→ NNNN∞∞∞∞ é tal que carrega noregistrador denotado por X o valor de entrada,inicializando todos os demais registradores com zero;

c) A função de saída: sai: NNNN∞∞∞∞ →→→→ NNNN é tal que retorna o valorcorrente do registrador denotado por Y;



d) O conjunto de interpretações de operações é uma famíliade operações indexada pelos registradores, na qual, paracada registrador K ∈∈∈∈ { A, B, X, Y,... }, tem-se que:


cada registrador K ∈∈∈∈ { A, B, X, Y,... }, tem-se que:

adK: NNNN∞∞∞∞ →→→→ NNNN∞∞∞∞ adiciona um à componente correspondente aoregistrador K, deixando as demais com seus valores inalterados.

subK: NNNN∞∞∞∞→→→→ NNNN∞∞∞∞ subtrai um da componente correspondente aoregistrador K, se o seu valor for maior que zero (caso contrário,mantém o valor zero), deixando as demais com seus valoresinalterados.

Norma = (NNNN∞∞∞∞, NNNN, NNNN, ent, sai, { adK, subK }, { zeroK })

e) O conjunto de interpretações de testes é uma família detestes indexada pelos registradores na qual, para cadaregistrador , tem-se que:testes indexada pelos registradores na qual, para cadaregistrador K, tem-se que:

zeroK: NNNN∞∞∞∞→→→→ { verdadeiro, falso } resulta em verdadeiro, se acomponente correspondente ao registrador K for zero e em falso,caso contrário.

� Para um registrador K, as correspondentes operaçõesou teste adk, subk e zerok são denotadas:

K := K + 1 K := K – 1 K = 0TC - Máquina NORMA 7

� É uma máquina extremamente simples, de tal formaque parece difícil acreditar que o seu podercomputacional é, no mínimo, o de qualquercomputador moderno.

� Características de máquinas reais são simuladasusando a Máquina NORMA, reforçando as evidênciasde que se trata de uma máquina universal.


� As características são as seguintes:

a) Operações e Testes. Definição de operações e testes maiscomplexos como adição, subtração, multiplicação e divisãocomplexos como adição, subtração, multiplicação e divisãode dois valores e tratamento de valores diversos como osnúmeros primos;

b) Valores Numéricos. Armazenamento e tratamento devalores numéricos de diversos tipos como inteiros(negativos e não-negativos) e racionais;


� EXEMPLO: Atribuição do Valor Zero a umRegistrador A. A := 0

� Programa Iterativo:até A = 0 até A = 0 faça (A := A – 1)

� Pode-se tratar a operação A := 0 como uma macro, ouseja, um trecho de programa que é substituído pela suadefinição sempre que referenciado.

� Usando a macro A := 0, é fácil construir macros paradefinir operações de atribuição de um valor qualquer.


� EXEMPLO: Atribuição de um Valor Natural a umRegistrador.

� A macro de atribuição de um valor natural n a umregistrador A, A := n, é a generalização do programaregistrador A, A := n, é a generalização do programaabaixo.

� Programa Iterativo n = 3A := 0; ou A := 0; A := A+1; Até A = 3A := A+1; faça (A := A + 1)A := A+1


� EXEMPLO: Adição de Dois Registradores.� A macro correspondente à operação de adição do valor

do registrador B ao do registrador A, é denotada por:A : = A + B

� Programa Iterativoaté B = 0faça (A := A + 1; B := B - 1)

� Observe que, ao somar o valor de B em A, oregistrador B é zerado!


� EXEMPLO: Adição de Dois Registradores,Preservando B� A macro correspondente à operação de adição do valor

do registrador B ao do registrador A, preservando ovalor em B, necessita usar um registrador auxiliar Cvalor em , necessita usar um registrador auxiliar

� Programa Iterativo A := A + B usando CC := 0;até B = 0faça (A := A + 1; C := C + 1; B := B - 1);até C = 0faça (B := B + 1; C := C - 1)


� Ainda com relação ao programa anterior:� Como este programa não preserva o conteúdo original

do registrador de trabalho C, faz-se necessárioexplicitar o uso deste registrador.

� É necessário escolher um registrador de trabalho C que� É necessário escolher um registrador de trabalho C quenão seja usado!


� EXEMPLO: Multiplicação de Dois Registradores.� Programa Iterativo A := A ×××× B usando C, D:

C := 0;até A = 0faça (C := C + 1; A := A - 1);faça (C := C + 1; A := A - 1);até C = 0faça (até B = 0

faça (A = A + 1; D = D + 1; B = B - 1)até D = 0faça (B = B + 1; D = D – 1);C := C - 1)


� EXEMPLO: Teste se o Valor do Registrador é umnúmero Primo.� Programa Iterativo teste_primo(A) usando C

(se A = 0 então falso senão C := A;

C := C - 1; C := C - 1; (se C = 0 então falsosenão até teste_mod(A, C)

faça (C := C – 1)C := C – 1; (se C = 0 então verdadeirosenão falso) ) )

16

� É uma macro de teste que verifica se o valor de umregistrador A é um número primo, usando umregistrador de trabalho C, retornando o valorverdadeiro, se o valor de A é primo, e o valor falso,caso contrário:caso contrário:

� teste_mod(A, C) é um teste que retorna o valorverdadeiro, se o resto da divisão inteira do conteúdode A por C é zero, e o valor falso, caso contrário.


� Como representar pares ordenados em NORMA?

� Usando dois registradores, o primeiro referente ao sinal,e o segundo, à magnitude (valor absoluto).

� Inteiros (negativos e não-negativos) e Racionais


� Inteiros: Um valor inteiro m pode ser representadocomo um par ordenado:

(s, m) onde:� s denota o sinal de m: se m < 0,

� então s = 1 (negativo)� então s = 1 (negativo)� senão s = 0 (positivo)

� m denota magnitude dada pelo valor absoluto dem;


� Representação de Inteiros utilizando doisregistradores� Supor que o registrador inteiro A é representado pelo

par (A1, A2) na representação conhecida como sinal-magnitude, ou seja, A1 (sinal) e A2 (magnitude )., ou seja, 1 e 2

� Programa Iterativo A := A + 1:(se A1 = 0então A2 := A2 + 1 senão A2 := A2 - 1;

(se A2 = 0então A1 := A1 – 1senão √) )


� Sugere-se como exercício a operação de subtraçãocom números inteiros (utilizando a representaçãosinal-magnitude).

(A := A -1)


� Números Racionais:� Um valor racional r pode ser denotado como um par

ordenado: (a, b) tal que b > 0 e r = a/b.

� A representação não é única pois, por exemplo, o valor� A representação não é única pois, por exemplo, o valorracional 0.75 pode ser representado pelos pares (3, 4) e(6, 8), entre outros (na realidade, os pares (3, 4) e (6, 8)pertencem à mesma classe de equivalência).


� Racionais:

� Neste contexto, as operações de adição, subtração,multiplicação e divisão, bem como o teste de igualdade,podem ser definidos como segue:

� (a, b) + (c, d) = (a*d + b*c, b*d)

� (a, b) - (c, d) = (a*d – b*c, b*d)

� (a, b) × (c, d) = (a*c, b*d)

� (a, b) / (c, d) = (a*d, b*c) (com c ≠ 0)

� (a, b) = (c, d) se, e somente se, a*d = b*c


� Exemplo:� Adição 0,25 + 0,75 = 1(1, 4) + (3, 4) = (4 + 12, 16) = (16, 16)

� Multiplicação 0,25 * 0,75 = 0,1875� Multiplicação 0,25 * 0,75 = 0,1875(1, 4) * (3, 4) = (3, 16)

� Teste de igualdade(1, 4) = (3, 12) é verdadeiro pois, 1*12 = 4*3


3.14 – Mostre como as instruções abaixo podem serconstruídas como macros em NORMA:

a) r1: se A < 2 então vá para r2 senão vá para r3


se A = 0então r2senão (A := A – 1;

se A = 0então r2senão r3)

3.15 – Desenvolva o programa em NORMA querealiza a operação abaixo:

a) A := B – C (B deve ser maior que C)

A := 0;


A := 0;até C = 0 faça ( B := B – 1;

C := C – 1 );até B = 0 faça ( B := B – 1;

A := A + 1 );

Documents

UNIVERSIDADE FEDERAL RURAL DO SEMI-ÁRIDO … · NORMA (NumberTheOreticRegisterMA chine) Possui como memória um conjunto infinito de registradores naturais e três instruções sobre