EA869 - Introdução a Sistemas de Computação Digital

2o Semestre de 1997 – 1a Prova - Duração: 2 horas - Sem consulta


Deveremos complementar logo a Questão 1.


Questão 1 (valor 2,5)

(0,5) a) Todos os problemas computáveis são tratáveis? Justifique.

Não. Um problemas é computável se existe um algoritmo que o resolva. No entanto, caso a complexidade do melhor algoritmo de solução existente seja maior que polinomial, o problema é intratável.

(0,5) b) O que distingue um algoritmo de um procedimento?

Tanto um algoritmo quanto um procedimento representam uma descrição finita da solução de um dado problema. O que distingue ambos é o fato do algoritmo ser um procedimento que termina após um número finito de passos, fato que não ocorre com todos os procedimentos.

(1,5) c) Considere um problema para o qual foram elaborados 3 algoritmos de solução: A, B e C. A complexidade temporal dos algoritmos é dada por:

A: B: C:

onde n é o tamanho do problema.

  • Quais são as complexidades temporais assintóticas (big-Oh) dos três algoritmos? Qual é o melhor algoritmo neste caso?

A: B: C:

O melhor algoritmo vai ser aquele que apresenta a menor complexidade para n ® ¥ . Neste caso, o algoritmo A é o melhor.

n

2

4

8

16

32

64

A

40

80

160

320

640

1280

B

4

16

64

256

1024

4096

C

8

32

96

256

640

1536


Questão 2 (valor 1,5)

Dentre as 6 questões apresentadas a seguir, escolha 5 para serem respondidas. Indique a questão que não será respondida (na ausência desta indicação, todas as questões serão avaliadas, sendo que a questão em que o aluno obtiver melhor avaliação será desconsiderada).

(0,3) a) Conceitue processador, computador e sistema computacional.

Processador: é a unidade central de processamento.

Computador: engloba o procressador, memória, interfaces de E/S e barramentos.

Sistema computacional: engloba o computador, os periféricos e o software, provendo máquinas virtuais para os usuários.

(0,3) b) O que é uma linguagem de máquina?

É uma linguagem específica de cada processador, em representação binária, que o hardware do computador "entende".

(0,3) c) O que é uma máquina de 2 endereços?

É uma máquina cujas instruções possuem no máximo dois campos de endereço, sendo que o resultado das operações é armazenado no endereço de um dos operandos.

(0,3) d) O que são os "flags" de uma UAL? Qual é a sua utilidade?

Os "flags" são bits que indicam o estado do processador após a última operação. A utilidade dos "flags" é auxiliar na implementação de desvios na execução de programas.

(0,3) e) Qual é a finalidade do contador de programa?

O contador de programa é um registrador que contém o endereço da posição de memória onde se encontra a próxima instrução a ser executada. Portanto seu conteúdo é utilizado para seqüenciar a execução das instruções de um programa.

(0,3) f) Qual é o papel da unidade de controle num computador?

A unidade de controle ter a função de comandar todos os módulos do computador pelo seqüenciamento dos sinais de controle.

 


Questão 3 (valor 1,5)

 

Seja a seguinte expressão aritmética:

A = (A+B) / C

Escreva programas em linguagem simbólica que calcule o valor de A sem destruir o conteúdo de B e C para:

  1. uma máquina de 3 endereços, com o seguinte repertório de instruções (observe que R não precisa ser necessariamente diferente de S1 e S2):
  2.  

    ADD S1, S2, R

    R ¬ (S1) + (S2)

     

    ADD A,B,A

    A¬ (A)+(B)

    SUB S1, S2, R

    R ¬ (S1) - (S2)

     

    DIV A,C,A

    A¬ (A)/(C)

    DIV S1, S2, R

    R ¬ (S1) / (S2)

         

    MUL S1, S2, R

    R ¬ (S1) * (S2)

         

     

  3. uma máquina de 2 endereços, com um registrador de uso geral TMP e o seguinte repertório de instruções:
  4.  

    ADD S1, S2

    S2 ¬ (S1) + (S2)

     

    ADD B,A

    A¬ (B)+(A)

    SUB S1, S2

    S2 ¬ (S1) - (S2)

     

    MOV C,TMP

    TMP¬ (C)

    DIV S1, S2

    S2 ¬ (S1) / (S2)

     

    DIV A,TMP

    TMP¬ (A)/(TMP)

    MUL S1, S2

    S2 ¬ (S1) * (S2)

     

    MOV TMP,A

    A¬ (TMP)

    MOV S1, S2

    S2 ¬ (S1)

         

     

  5. uma máquina de 1 endereço, com o seguinte repertório de instruções:

 

ADD S

Acc ¬ (Acc) + (S)

 

LDA A

Acc¬ (A)

SUB S

Acc ¬ (Acc) - (S)

 

ADD B

Acc¬ (Acc)+(B)

DIV S

Acc ¬ (Acc) / (S)

 

DIV C

Acc¬ (Acc)/(C)

MUL S

Acc ¬ (Acc) * (S)

 

STA A

A¬ (Acc)

STA S

S ¬ (Acc)

     

LDA S

Acc ¬ (S)

     

 


Questão 4 (valor 2,5)

Utilizando os diagramas fornecidos (inclua, caso necessário, novos diagramas):

 


Questão 5 (valor 2,5)

No computador hipotético da figura Q5, apenas a memória está especificada como tendo 256 palavras de 12 bits. Sabe-se também que todas as instruçõs são de 1 palavra, contendo o código de operação e o endereço de um operando conforme o seguinte formato:

(1.0 pt) a. Complete a descrição técnica desse computador inidcando:

(1.0 pt) b. Para o mesmo computador da figura, assuma a priori de agora, que podem existir instruções com dois operandos, formadas por duas palavras como segue:

Contando apenas com os registradores existentes, mostre todos os passos para busca e execução da instrução
ADD end1,end2          end2 <- (end1)+(end2)

Valor Ciclos Pulso Micooperações Microcomandos
0.2 pt Ciclo de Busca 1 REM <- (PC) TPC
2 RDM <- ((REM)) E, R/-W
PC <- (PC) + 1 IPC
3 RI <- (RDM) TB, TRB
0.2 pt Ciclo de Leitura do (end1) 4 REM <- (RI.end) TRI
5 RDM <- ((REM)) E, R/-W
6 Acc <- (RDM) TRB, WA
0.2 pt Ciclo de Leitura do end2 7 REM <- (PC) TPC
8 RDM <- ((REM)) E, R/-W
PC <- (PC) + 1 IPC
9 RI <- (RDM) TRB, TB
0.2 pt Ciclo de Leitura do (end2) 10 REM <- (RI.end) TRI
11 RDM <- ((REM)) E, R/-W
12 TMP <- (RDM) TRB, W
0.2 pt Ciclo de Execução 13 SOMA <- (Acc) + (TMP) R, RE
14 Acc <- SOMA WE
15 RDM <- (Acc) TBR, RA
16 (REM) <- (RDM) E, R/-W
Observe que no ciclo de execução não foi executada a microoperação
REM <- (RI.end)
pois considerou-se que não houve alteração do conteúdo do REM a partir do pulso 10.

(0.5 pt) c. Mostre esquematicamente o circuito do controlador para a instrução do item (b).

Foi considerada correta a solução que apresenta pelo menos três flip-flops devidamente identificados e sequenciados.

 


Last modified: Thu Sep 18 15:19:37 BRA 1997

Sugestões para ting@dca.fee.unicamp.br

Voltar para a página do curso.

Ting e Fernando