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

2o Semestre de 1997 - Prova I - Duração: 2 horas - Sem consulta

Deveremos complementar logo a Questão 1.

Questão 1 (valor 1,5)

(0,5) a) A que se refere a computabilidade de um problema? E a complexidade de um problema?

A computabilidade de um problema refere-se à existência de um algoritmo que o resolva; já a complexidade refere-se aos recursos computacionais (memória e tempo de processamento) requeridos pelo algoritmo, permitindo classificá-lo como tratável ou intratável.

(0,5) b) Quando se pode dizer que um problema é computacionalmente tratável?

Quando existe um algoritmo para sua solução com complexidade até polinomial.

(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 C é o melhor.

n

2

4

8

16

32

64

A

2

8

24

64

160

384

B

1

4

16

64

256

1024

C

10

20

40

80

160

320

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) O que é uma linguagem de alto nível? Cite uma de suas vantagens.

É uma linguagem de programação mais próxima do usuário. Para executar um programa escrito nesta linguagem é necessário traduzi-lo para linguagem de máquina. Vantagens: não depende do processador, facilita a programação.

(0,3) b) O que são tradutores? Dê dois exemplos.

São programas integrantes do software de sistema que transformam os programas escritos em uma linguagem diferente da linguagem de máquina para a linguagem de máquina. Exemplos: montador (tradução de linguagem simbólica), interpretador e compilador (tradução de linguagens de mais alto nível).

(0,3) c) O que determina a quantidade de bits utilizados para representar um endereço e a quantidade de bits para representar o conteúdo de uma célula, na unidade de memória?

A quantidade de bits utilizados para representar o endereço determina a quantidade de células da unidade de memória que podem ser acessadas. A quantidade de bits utilizados para representar o conteúdo de uma célula da unidade de memória determina o tamanho do dado e a quantidade de dados distintos que podem ser representados.

(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 registrador de estado?

O registrador de estado é um registrador da unidade de controle responsável por armazenar informações relevantes ao funcionamento da unidade central de processamento, entre elas as informações fornecidas pelos "flags".

(0,3) f) Qual é o papel da unidade aritmética e lógica num computador?

A unidade aritmética e lógica é responsável pela execução de todas as operações aritméticas e lógicas sobre os dados, sendo comandada pela unidade 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)

    		  

    SUB A,B,A

    A¬ (A)- (B)

    SUB S1, S2, R

    R ¬ (S1) - (S2)

    		  

    MUL A,C,A

    A¬ (A)*(C)

    DIV S1, S2, R

    R ¬ (S1) / (S2)

    		      

    MUL S1, S2, R

    R ¬ (S1) * (S2)

    		      

     

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

    3.  

    ADD S1, S2

    S2 ¬ (S1) + (S2)

    		  

    MOV B,TMP

    TMP¬ (B)

    SUB S1, S2

    S2 ¬ (S1) - (S2)

    		  

    SUB A,TMP

    TMP¬ (A)- (TMP)

    DIV S1, S2

    S2 ¬ (S1) / (S2)

    		  

    MUL C,TMP

    TMP¬ (C)*(TMP)

    MUL S1, S2

    S2 ¬ (S1) * (S2)

    		  

    MOV TMP,A

    A¬ (TMP)

    MOV S1, S2

    S2 ¬ (S1)

    		      

     

  3. 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)

  

SUB B

Acc¬ (Acc)- (B)

DIV S

Acc ¬ (Acc) / (S)

  

MUL 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 512 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 16:49:56 BRA 1997

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

Voltar para a página do curso.

Ting e Fernando