Exercícios com Resolução - Introdução a Sistemas de Computação Digital

Prévia do material em texto

EA869 – Prof. Von Zuben 
DCA/FEEC/Unicamp 
Lista de Exercícios 1 (com gabarito) 1
EA869 - Introdução a Sistemas de Computação Digital 
Lista de Exercícios Preparatórios para a Prova 1 (com Gabarito) 
Questão 1 
a) Explique por que existem problemas claramente definidos que não podem ser resolvidos por 
qualquer computador, independente de tempo e quantidade de memória disponíveis. 
Mesmo restrito ao conjunto dos problemas claramente definidos, está demonstrado teoricamente 
que existem problemas para os quais não é possível obter um algoritmo (número finito de 
procedimentos finitos) que leve à solução, sendo portanto problemas não-computáveis. 
 
b) Defina problemas computacionalmente tratáveis. 
São problemas computáveis para os quais existe um algoritmo de solução cuja complexidade 
(temporal e espacial) é polinomial ou menor. 
 
c) Dado um problema e dois algoritmos (A e B) propostos para sua solução, explique por que as 
complexidades dos algoritmos A e B podem ser diferentes e relacione estas duas complexidades à 
complexidade intrínseca do problema. 
Podem existir diferentes algoritmos que levam à mesma solução de um dado problema, de modo 
que suas complexidades podem diferir. Ex: algoritmos para multiplicação apresentados em aula. 
A complexidade dos algoritmos A e B vai ser sempre maior ou igual à complexidade intrínseca 
do problema. 
 
d) Numere de 1 a 8 os termos a seguir, de acordo com a seqüência de passos que levam à resolução de 
um problema usando computador. 
( 6 ) programa em linguagem de máquina ( 2 ) elaboração do algoritmo 
( 1 ) definição do problema ( 4 ) programa em linguagem de alto nível 
( 3 ) definição da linguagem de alto nível ( 8 ) execução 
( 5 ) compilação + montagem ( 7 ) carregamento na memória 
 
e) Use o conceito de máquina virtual para explicar por que os computadores são considerados 
máquinas de propósito geral. 
Dependendo dos recursos alocados pelo software que se encontra em execução, o mesmo 
hardware pode realizar diferentes tarefas de processamento de informação, se comportando, sob 
a perspectiva do usuário, como uma máquina de escrever virtual, uma televisão virtual, uma 
calculadora virtual, etc. Se o mesmo hardware é capaz de executar diferentes tarefas via 
software, então se justifica a denominação de máquina de propósito geral. 
 
f) Descreva a função da memória cache e explique por que o princípio da localidade de referência é 
usado para justificar o uso da memória cache. 
EA869 – Prof. Von Zuben 
DCA/FEEC/Unicamp 
Lista de Exercícios 1 (com gabarito) 2
A memória cache se posiciona entre a memória principal e o processador, é mais rápida que a 
memória principal e com menos capacidade, por ser mais cara. A transferência entre ela e o 
processador é feita palavra-a-palavra, e entre ela e a memória principal é feita bloco-a-bloco. 
Sua função é acelerar a velocidade média de acesso à memória, e isso é garantido pelo princípio da 
localidade de referência, que afirma que é alta a probabilidade de que a próxima palavra de 
memória a ser lida ou escrita está no mesmo bloco da palavra que está sendo processada. Sendo 
assim, ocorrem em média muitas transferências palavra-a-palavra a cada transferência bloco-a-
bloco. 
Obs: Existe memória cache também para a memória secundária, denominada cache de disco. 
 
Questão 2 
Seja a seguinte expressão aritmética: 
A = (A*B) − C 
Para cada item a seguir, escreva um programa em linguagem simbólica que calcule o valor de A sem 
alterar os conteúdos de B e C. 
a) 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, e não há registradores auxiliares): 
ADD S1, S2, R R ← (S1) + (S2) 
SUB S1, S2, R R ← (S1) − (S2) MUL A, B, A 
DIV S1, S2, R R ← (S1) / (S2) SUB A, C, A 
MUL S1, S2, R R ← (S1) * (S2) 
 
b) uma máquina de 2 endereços, com um único registrador auxiliar TMP e o seguinte repertório de 
instruções: 
 
ADD S1, S2 S2 ← (S1) + (S2) MOV B, TMP 
SUB S1, S2 S2 ← (S1) − (S2) MUL A, TMP 
DIV S1, S2 S2 ← (S1) / (S2) MOV C, A 
MUL S1, S2 S2 ← (S1) * (S2) SUB TMP, A 
MOV S1, S2 S2 ← (S1) 
 
c) uma máquina de 1 endereço, com o seguinte repertório de instruções (não há registradores 
auxiliares): 
ADD S Acc ← (Acc) + (S) 
SUB S Acc ← (Acc) − (S) LDA A 
DIV S Acc ← (Acc) / (S) MUL B 
MUL S Acc ← (Acc) * (S) SUB C 
STA S S ← (Acc) STA A 
LDA S Acc ← (S) 
 
 
EA869 – Prof. Von Zuben 
DCA/FEEC/Unicamp 
Lista de Exercícios 1 (com gabarito) 3
Questão 3 
Utilizando os diagramas fornecidos (inclua, caso necessário, novos diagramas), mostre a execução da 
instrução a seguir, indicando ao lado de cada diagrama as microoperações em cada pulso de relógio. 
Suponha que a UAL contém um circuito combinacional para adição, mas não para subtração. O 
conteúdo do registrador TMP pode ser incrementado e pode também ser complementado. 
SUB,I end Acc ← (Acc) − ((end)) 
formato da instrução SUB,I 
 end 
 
UCP
UCUAL
Memória
Acc
RDM
TMP
PC
RI
Rg
REM
1
23
 
 
 
1. REM ← (PC) 
2. RDM ← ((REM)) 
 PC ← (PC) + 1 
3. RI ← (RDM) 
UCP
UCUAL
Memória
Acc
RDM
TMP
PC
RI
Rg
REM
4
5
6
 
 
 
4. REM ← (PC) 
5. RDM ← ((REM)) 
 PC ← (PC) + 1 
6. Rg ← (RDM) 
UCP
UCUAL
Memória
Acc
RDM
TMP
PC
RI
Rg
REM
7
8
9
 
 
 
 
7. REM ← (Rg) 
8. RDM ← ((REM)) 
9. Rg ← (RDM) 
UCP
UCUAL
Memória
Acc
RDM
TMP
PC
RI
Rg
REM
10
11
12
 
10. REM ← (Rg) 
11. RDM ← ((REM)) 
12. TMP ← (RDM) 
13. TMP ← (TMP) 
14. TMP ← (TMP) + 1 
15. Σ ← (Acc) + (TMP) 
16. Acc ← (Σ) 
EA869 – Prof. Von Zuben 
DCA/FEEC/Unicamp 
Lista de Exercícios 1 (com gabarito) 4
Questão 4 
No computador hipotético da figura Q4, apenas a memória está especificada como tendo 256 palavras 
de 12 bits. Sabe-se também que todas as instruções são de 1 palavra, contendo o código de operação e 
o endereço de um operando, conforme o seguinte formato: 
C.O. end 
a) Complete a descrição técnica desse computador indicando: 
• largura dos barramentos e conexões na figura (no de bits); 
• tamanho dos registradores na figura (no de bits); 
• número máximo de instruções que a máquina suportaria: 24 = 16 . Justifique. 
A palavra de instrução vai ter 12 bits. Como existem 256 palavras na memória principal, 
são necessários 8 bits para o campo de endereço, sobrando 4 bits para o código de 
operação. Veja barramentos associados ao registrador RI na figura Q4. 
 
b) Para o mesmo computador da figura, assuma, a partir de agora, que podem existir instruções com 
dois operandos, formadas por duas palavras como segue 
C.O. end1 
 end2 
Contando apenas com os registradores existentes, mostre todos os passos para busca e execução da 
instrução 
ADD end1,end2 end2 ← (end1) + (end2) 
indicando, para cada pulso de relógio, as microoperações e microcomandos correspondentes. 
Pulso Microoperações Microcomandos 
1 REM ← (PC) TPC 
2 RDM ← ((REM)) E, R/ W 
 PC ← (PC) + 1 IPC 
3 RI ← (RDM) TB, TRB 
 
4 REM ← (RI.end) TRI 
5 RDM ← ((REM)) E, R/ W 
6 Acc ← (RDM) TRB, WA 
 
7 REM ← (PC) TPC 
8 RDM ← ((REM)) E, R/ W 
 PC ← (PC) + 1 IPC 
9 RI ← (RDM) TB, TRB 
 
10 REM ← (RI.end) TRI 
11 RDM ← ((REM)) E, R/ W 
12 TMP ← (RDM) TRB, W 
 
EA869 – Prof. Von Zuben 
DCA/FEEC/Unicamp 
Lista de Exercícios 1 (com gabarito) 5
13 Σ ← (Acc) + (TMP) R, Rε 
14 Acc ← (Σ) Wε 
(opcional) REM ← (RI.end) TRI 
15 RDM ← (Acc) TBR, RA 
16 (REM) ← (RDM) E 
 
 
Especificação dos sinais de controle:Z: zera o registrador TMP C: complementa o conteúdo do registrador TMP 
I: incrementa o conteúdo do registrador TMP R: lê do registrador TMP 
W: escreve no registrador TMP WA: escreve do barramento no registrador Acc 
RA: lê do registrador Acc para o barramento Wε: escreve da saída do somador no registrador Acc 
Rε: lê do registrador Acc para a entrada do somador TB: transferência do barramento 
TRI: transferência do RI TPC: transferência do PC 
IPC: incrementa PC TBR: transferência do barramento para o registrador 
TRB: transferência do registrador para o barramento R/ W : leitura da memória / escrita na memória 
E: habilita 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura Q4 – Computador hipotético 
PC 
REM 
MEMÓRIA 
RAM 
256 × 12 
RDM
RI 
E 
R/W 
TRB 
TBR 
IPC 
TPC
TRI 
TB 
Rε
Wε 
RA 
WA 
W
R
I
C
Z
E 
R/W 
TRB 
TBR 
IPC 
TPC 
TRI 
TB 
TMP 
I 
C 
Z 
W
R
Acc 
Wε 
Rε 
WA 
RA 
Σ
CONTROLADOR 
8 
8 
8 
8 
8 
4 
12
12
12
12
12 
12 
12
12
12 
12
12 
12 
EA869 – Prof. Von Zuben 
DCA/FEEC/Unicamp 
Lista de Exercícios 1 (com gabarito) 6
Questão 5 
Embora os processos físicos envolvidos sejam distintos, tanto um scanner quanto uma máquina 
fotográfica digital têm a função básica de digitalizar uma imagem. Utilizando os conceitos de pixel, 
resolução e número de cores por pixel, explique como gerar um arquivo apenas com valores binários 
que corresponda a uma dada imagem processada pelo scanner ou pela máquina fotográfica. Apresente 
o procedimento para se calcular o tamanho em bytes do arquivo binário resultante. Calcule o tamanho 
do arquivo sabendo-se que: 
• a resolução é 1280 × 1024 pixels; 
• o número de cores distintas é 512. 
Para digitalizar uma imagem é necessário realizar dois processos de quantização. 
Primeiramente, divide-se a imagem em um número finito de pixels, arranjados uniformemente 
em linhas e colunas. Em seguida, é necessário supor que cada pixel pode indicar uma dentre um 
conjunto finito de cores. A resolução da imagem está associada com a quantidade de linhas e 
colunas utilizadas, formando uma matriz de pixels. Esta matriz de pixels pode ser convertida em 
um vetor de pixels, empilhando uma a uma suas linhas (ou suas colunas). Como cada cor deve 
possuir um código binário associado, então o número de bits por pixel deve ser suficiente para 
que haja um único código binário por cor. 
Com os dados numéricos da questão, o número de pixels será de 1.310.720 e o número de bits por 
pixels deve ser no mínimo 9. Sendo assim, o vetor de bits correspondente à imagem digitalizada e 
a ser armazenado na memória do computador terá dimensão de 11.796.480 bits, ou seja, 
1.474.560 bytes. 
A interpretação da seqüência de bits precisa levar em conta o número de bits por pixel e a 
política de empilhamento das linhas (ou colunas) da matriz de pixels. Normalmente, arquivos 
correspondentes a imagens vão conter um cabeçalho descrevendo as dimensões envolvidas e 
serão armazenados após a aplicação de algum processo de compactação de informação. 
Dependendo do processo de compactação, resultam arquivos JPG, GIF, BMP, TIF, etc. 
 
Questão 6 
Sabendo que um sistema operacional multi-usuário é basicamente um sistema que aceita 
multiprogramação (uma única UCP executando vários programas) e que compartilha recursos 
computacionais entre vários usuários (além de compartilhar a UCP, todos os arquivos dos usuários 
podem estar armazenados em um mesmo disco rígido), explique como a existência de um sistema 
operacional multi-usuário pode reduzir o custo de uma empresa com computadores, mesmo sabendo 
que a multiprogramação requer máquinas com grande quantidade de recursos computacionais, portanto 
mais caras. 
Compartilhar recursos entre vários usuários implica amortizar o custo de aquisição dos 
recursos, além de reduzir drasticamente os custos de manutenção e gerenciamento. Se a máquina 
é 10 vezes mais cara que uma outra que atenda cada usuário individualmente, então se ela tiver 
capacidade de suprir recursos para mais de 10 usuários simultaneamente haverá uma redução 
EA869 – Prof. Von Zuben 
DCA/FEEC/Unicamp 
Lista de Exercícios 1 (com gabarito) 7
do custo de uma empresa com computadores. É lógico que muitos outros fatores devem ser 
levados em conta na hora de especificar o parque computacional de uma empresa, como por 
exemplo a diversidade de usos a que se destinam as máquinas, mas o tipo de raciocínio acima 
representa um dos fatores a serem considerados. 
 
Questão 7 
Em 2003, jornais e revistas dedicaram muita atenção ao 50o aniversário da descoberta da estrutura 
química do DNA. Embora James D. Watson e Francis Crick mereçam todo o reconhecimento, não 
houve menção do feito de um outro experimento científico que também completou 50 anos e que 
também causou grande impacto na ciência. Em 1953, Enrico Fermi e dois de seus colegas do 
Laboratório Científico Los Alamos (onde foi descoberta a bomba atômica), John Pasta e Stanislaw 
Ulam, inventaram o conceito de um ‘experimento de computador’. De repente, o computador se 
transformou em uma nova forma de exercer ciência, por realizar uma função semelhante àquela do 
microscópio e outros equipamentos que ampliam a capacidade sensorial humana, ao revelar 
peculiaridades de fenômenos que jamais seriam perceptíveis por meio de procedimentos tradicionais de 
experimentação em laboratório. Fermi e seus colegas introduziram a simulação computacional como 
uma forma eficaz de se buscar uma maior compreensão do conceito de entropia, e desde então 
inúmeros experimentos científicos e tecnológicos têm sido realizados usando simulação 
computacional. Pergunta: O que está por trás do poder da simulação computacional? 
A simulação computacional é possível devido a dois fatores: 
• o computador é uma máquina de propósito geral, podendo virtualmente sintetizar inúmeros 
fenômenos, com maior ou menor grau de precisão; 
• os princípios da computação analógica permitem utilizar um sistema para fornecer 
informações sobre um outro sistema, por analogias que podem ser estabelecidas entre 
ambos. 
Sendo assim, caso se queira prever o comportamento de algum dispositivo físico sujeito a 
algumas leis da natureza, basta tomar, em um computador, variáveis numéricas que expressem 
os atributos deste dispositivo físico e submetê-las a equacionamentos matemáticos que descrevam 
as leis da natureza que devem governar a evolução do fenômeno físico. Com isso, o mundo 
abstrato criado em computador vai reproduzir, por analogia, o fenômeno físico que estaria 
ocorrendo em um experimento de laboratório. Também aqui há muitas outras questões 
envolvidas, mas a essência dos processos envolvidos está evidenciada acima. 
 
Questão 8 
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: nnf 20)(1 = B: 
2
2 )( nnf = C: nnnf 23 log4)( = 
onde n é o tamanho do problema. 
EA869 – Prof. Von Zuben 
DCA/FEEC/Unicamp 
Lista de Exercícios 1 (com gabarito) 8
• Quais são as complexidades temporais assintóticas (big-Oh) dos três algoritmos? Qual é o melhor 
algoritmo neste caso? 
A: )(nO B: )( 2nO C: )(log)log( 22
nnOounnO 
O melhor algoritmo vai ser aquele que apresenta a menor complexidade para n → ∞. Neste caso, 
o algoritmo A é o melhor. 
• Determine os intervalos de valores de n em que cada um deles é melhor que os outros dois 
(Sugestão: use valores de n que sejam potências de 2). 
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 6401536 
 
B AC
2 16 32 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
0 0.5 1 1.5 2 2.5 3
-10
0
10
20
30
40
50
60
0 5 10 15 20 25 30 35 40
0
200
400
600
800
1000
1200
1400
1600
EA869 – Prof. Von Zuben 
DCA/FEEC/Unicamp 
Lista de Exercícios 1 (com gabarito) 9
Questão 9 
O que é um problema NP e o que significa dizer que frente ao aumento do tamanho de um problema 
NP é necessário direcionar esforços no sentido de objetivos mais factíveis? 
Um problema NP é um problema computável mas não-deterministicamente polinomial. A 
melhor solução até então conhecida está associada a algoritmos de complexidade exponencial ou 
até superior. No entanto, não se sabe se existem algoritmos de solução menos complexos, capazes 
de resolver o problema em tempo polinomial ou até inferior. Embora se esteja mencionando 
apenas tempo de processamento, deve ser considerado também o uso de memória nesta análise. 
Repare que, quando se fala em algoritmos de solução está se referindo a algoritmos exatos, ou 
seja, algoritmos que garantem a obtenção da solução ótima. 
Frente ao aumento do tamanho de um problema NP, obter a sua solução usando computador 
passa a ser impossível caso se recorra aos algoritmos exatos existentes. No entanto, para muitos 
problemas NP, dentre eles parte significativa dos problemas de grande interesse prático nos dias 
de hoje, já existem algoritmos de aproximação, ou seja, algoritmos de solução que não garantem 
a obtenção da solução ótima. Logo, na ausência de factibilidade dos algoritmos exatos, se 
justifica o investimento nos algoritmos de aproximação, os quais podem até fornecer a solução 
ótima ou ao menos uma boa solução aproximada (com desempenho próximo do ótimo). Os 
algoritmos de aproximação geralmente estão baseados em heurísticas e meta-heurísticas, as 
quais podem ser concebidas de acordo com as peculiaridades de cada problema. Exemplos: 
algoritmos evolutivos, busca tabu, simulated annealing, etc. 
 
Questão 10 
Descreva como surgiu o sistema operacional UNIX, o qual foi o primeiro sistema operacional 
desenvolvido quase que totalmente em linguagem de alto nível (linguagem C) e cuja versão para PCs é 
denominada Linux. 
Todos os pontos fortes e fracos do UNIX podem ser diretamente relacionados com a história do 
seu desenvolvimento, que teve início em meados dos anos 60 com a criação de um projeto 
conjunto entre Massachusetts Institute of Technology (MIT), General Electric e Bell Labs (mais 
especificamente Bell Telephone Laboratories, companhia controlada pela AT&T) para o 
desenvolvimento de um sistema operacional com compartilhamento de tempo. Este sistema 
operacional foi denominado MULTICS (MULTiplexed Information and Computing Service), 
não tendo o sucesso esperado, principalmente porque o projeto era muito ambicioso para a 
época e, além disso, o sistema operacional foi escrito em uma linguagem muito “pesada”, com 
compilador ineficiente. A equipe da Bell Labs abandonou o projeto em 1969. Mas Ken 
Thompson, um dos membros desta equipe e conhecedor do potencial do MULTICS, sentiu a 
necessidade de desenvolver por conta própria um sistema operacional com os mesmos 
propósitos, mas de uma forma bem mais simples e utilizando linguagem assembly (linguagem de 
montagem). Como o sistema desenvolvido por Thompson funcionou muito bem, ele começou a 
atrair a atenção de seus colegas da Bell Labs, sendo que um deles, Brian Kernighan, chamou-o 
EA869 – Prof. Von Zuben 
DCA/FEEC/Unicamp 
Lista de Exercícios 1 (com gabarito) 10
de UNICS (UNiplexed Information and Computing Service), parodiando MULTICS. Esta 
denominação pegou, sendo, mais tarde, reduzida definitivamente para UNIX. Conforme o 
sistema UNIX ia sendo transportado para arquiteturas de computador cada vez mais poderosas, 
ficou evidente que era preciso eliminar a necessidade de se reescrever todo o sistema operacional 
em linguagem assembly para cada nova máquina. Esta foi uma visão inovadora, pois até então a 
linguagem assembly era considerada indispensável para garantir funcionalidade efetiva e acesso 
irrestrito ao hardware. Depois de uma tentativa sem muito sucesso de reescrever o UNIX em 
uma linguagem de alto nível desenvolvida pelo próprio Ken Thompson (denominada linguagem 
B), foi seu colega Dennis Ritchie quem projetou uma linguagem especificamente voltada para a 
implementação de um sistema operacional, a qual ele denominou linguagem C. A linguagem C é 
uma linguagem de alto nível, mas apenas o suficiente para manter a portabilidade junto a várias 
arquiteturas de computador. Uma vez implementado o compilador C, Ritchie e Thompson 
reescreveram a maior parte do UNIX em C (RITCHIE & THOMPSON, 1974). Uma vez controlada 
pela AT&T, monopólio da área de telecomunicações, a Bell Labs não tinha permissão para 
operar comercialmente na área de computação. Sendo assim, a Bell Labs não impunha muitos 
obstáculos para licenciar o UNIX, o que motivou muitas universidades a solicitarem cópias deste 
sistema operacional. Com isso, grandes conhecedores de computação puderam fazer uso do 
UNIX e também contribuir para o seu desenvolvimento. 
Bibliografia citada: RITCHIE, D.M. & THOMPSON, K. The UNIX Timesharing System. Commun. 
of the ACM, vol. 17, pp. 365-375, 1974. 
 
Questão 11 
Descreva em poucas palavras o sistema operacional Linux. 
O LINUX é um sistema operacional gerado a partir de um “clone” do UNIX. Ele foi 
originalmente concebido para rodar em computadores pessoais médios dotados de processadores 
Intel, como 386, 486 e Pentium. O LINUX é uma implementação da especificação POSIX, com 
extensões SYSV e BSD (estas são versões do UNIX), o que garante a semelhança entre os dois 
sistemas, embora o código tenha origens distintas. O autor original do núcleo (kernel) do LINUX 
foi Linus Torvalds, sendo que este sistema foi mantido e estendido por muitos voluntários ao 
redor do mundo. Ele é protegido por uma licença GPL (GNU Public License), de modo que 
qualquer pessoa pode copiar, alterar e distribuir o LINUX, sem no entanto poder impor 
qualquer restrição em relação à sua distribuição futura, devendo manter sempre o código 
disponível gratuitamente. Embora este cenário permita uma rápida evolução do sistema 
operacional, com uma tendência de suportar cada vez mais tipos de arquiteturas de computador, 
a diversidade de versões e potencialidades pode ser um forte empecilho para a sua disseminação. 
Além disso, é evidente que o mercado já ‘profissionalizou’ o Linux e hoje existe um custo para 
aquisição destas versões ‘profissionais’ do Linux, embora boa parte do custo esteja associada a 
garantias de manutenção por parte do fornecedor. 
 
EA869 – Prof. Von Zuben 
DCA/FEEC/Unicamp 
Lista de Exercícios 1 (com gabarito) 11
Questão 12 
A seguir, estão apresentadas as várias fases de duas propostas distintas de solução (ainda existem 
outras) via algoritmos de aproximação para o problema do caixeiro viajante, um dos mais importantes 
e mais conhecidos problemas NP-completos dentro da computação. O objetivo é partir de uma cidade, 
passar uma única vez por todas as demais cidades e retornar à cidade de partida com um percurso de 
extensão mínima. As duas propostas de solução são semelhantes no aspecto de não garantirem a 
obtenção da solução ótima. O que existe notadamente de diferente entre as duas propostas de solução, 
sabendo que uma delas emprega um algoritmo evolutivo e a outra uma rede neural auto-organizável? 
A primeira proposta de solução interpreta o problema como a busca da melhor permutação de 
índice das cidades. Foi aplicado um algoritmo evolutivo, o qual vai gradualmente melhorando a 
qualidade da solução aolongo do tempo. A segunda proposta interpreta o problema como um 
problema de atração entre os pontos do anel (que variam de quantidade ao longo do tempo, 
igualando o número de cidades ao final) e as cidades, resultando num problema de auto-
organização. Repare que, embora pudessem ser os mesmos, o número de cidades e as posições 
das cidades são diferentes em cada caso, o que não prejudica a comparação qualitativa. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
0 20 40 60 80 1000 
10 
20 
30 
40 
50 
60 
70 
80 
90 
100 
Melhor indivíduo na população inicial
0 20 40 60 80 100 0
10
20
30
40
50
60
70
80
90
100
Melhor indivíduo após 500 gerações 
0 20 40 60 80 1000 
10 
20 
30 
40 
50 
60 
70 
80 
90 
100 
Melhor indivíduo após 2000 gerações
0 20 40 60 80 100 0
10
20
30
40
50
60
70
80
90
100
Melhor indivíduo após 4000 gerações 
EA869 – Prof. Von Zuben 
DCA/FEEC/Unicamp 
Lista de Exercícios 1 (com gabarito) 12
Complementação da Tabela 3.5 
Livro-texto, pg. 99, cap. 3 
(Obs: As operações de multiplicação e divisão foram feitas com soma e subtração, 
respectivamente. Um código diferente seria produzido com o uso de shift. Esta é a 
razão de terem sobrado palavras da micromemória.) 
 
 
 Endereço na 
Micromemória 
Microoperações da 
Microinstrução 
Sinais de 
Controle 
 
0 
REM ← (PC) + 0 
RDM ← ((REM)) 
MPC ← (MPC) + 1 
1, 15 
16 
19, 23 
 
 
 
Busca 
1 
PC ← (PC) + 1 
RI ← (RDM) 
MPC ← (MPC) + (RI.co) 
1, 5, 10 
18 
22, 23 
2 MPC ← 0 + 11 7, 9, 10, 24 
3 MPC ← 0 + 13 7, 8, 10, 24 
4 MPC ← 0 + 15 7, 8, 9, 10, 24 
5 MPC ← 0 + 17 6, 10, 24 
6 MPC ← 0 + 19 6, 9, 10, 24 
7 MPC ← 0 + 36 5, 8, 24 
8 MPC ← 0 + 53 5, 6, 8, 10, 24 
9 MPC ← 0 + 54 5, 6, 8, 9, 24 
 
 
 
Mapea– 
 
 
mento 
10 MPC ← 0 + 57 5, 6, 7, 10, 24 
 
11 
REM ← 0 + (RI.end) 
RDM ← ((REM)) 
MPC ← (MPC) + 1 
6, 15 
16 
19, 23 
 
 
LOAD 
12 Acc ← 0 + (RDM) 
MPC ← 0 + 0 
7, 11 
 
EA869 – Prof. Von Zuben 
DCA/FEEC/Unicamp 
Lista de Exercícios 1 (com gabarito) 13
13 REM ← 0 + (RI.end) 
MPC ← (MPC) + 1 
6, 15 
19, 23 
 
 
STORE 14 RDM ← (Acc) + 0 
(REM) ← (RDM) 
MPC ← 0 + 0 
2, 14 
17 
 
15 REM ← 0 + (RI.end) 
RDM ← ((REM)) 
MPC ← (MPC) + 1 
6, 15 
16 
19, 23 
 
 
ADD 
16 Acc ← (Acc) + (RDM) 
MPC ← 0 + 0 
2, 7, 11 
 
17 REM ← 0 + (RI.end) 
RDM ← ((REM)) 
MPC ← (MPC) + 1 
6, 15 
16 
19, 23 
 
 
SUB 
18 Acc ← (Acc) – (RDM) 
MPC ← 0 + 0 
2, 7, 8, 11 
 
 
19 
REM ← 0 + (RI.end) 
RDM ← ((REM)) 
MPC ← (MPC) + 1 
6, 15 
16 
19, 23 
20 R2 ← (RDM) 
MPC ← (MPC) + 1 
7, 13 
19, 23 
21 R1 ← 0 + 0 
MPC ← (MPC) + 1 
12 
19, 23 
22 MPC ← (MPC) + TESTZERO 20, 23 
23 MPC ← 0 + 26 6, 7, 9, 24 
24 R1 ← (R1) + (R2) 
MPC ← (MPC) + 1 
3, 4, 12 
19, 23 
25 Acc ← (Acc) – 1 
MPC ← 0 + 22 
2, 5, 8, 11 
6, 8, 9, 24 
 
 
 
 
 
 
 
 
MUL 
 
26 Acc ← (R1) 
MPC ← 0 + 0 
3, 11 
 
 
EA869 – Prof. Von Zuben 
DCA/FEEC/Unicamp 
Lista de Exercícios 1 (com gabarito) 14
. 
. 
. 
. 
. 
. 
. 
. 
. 
36 REM ← 0 + (RI.end) 
RDM ← ((REM)) 
MPC ← (MPC) + 1 
6, 15 
16 
19, 23 
37 R2 ← (RDM) 
MPC ← (MPC) + 1 
7, 13 
19, 23 
38 R1 ← 0 – 1 
MPC ← (MPC) + 1 
5, 8, 12 
19, 23 
39 MPC ← (MPC) + TESTNEG 21, 23 
40 MPC ← 0 + 43 5, 7, 9, 10, 24 
41 R1 ← (R1) + 1 
MPC ← (MPC) + 1 
3, 5, 12 
19, 23 
42 Acc ← (Acc) – (R2) 
MPC ← 0 + 39 
2, 4, 11 
5, 8, 9, 10, 24 
 
 
 
 
 
 
 
 
DIV 
43 Acc ← (R1) 
MPC ← 0 + 0 
3, 11 
 
 . 
. 
. 
. 
. 
. 
. 
. 
. 
JUMP 53 PC ← 0 + (RI.end) 
MPC ← 0 + 0 
6, 10 
 
54 MPC ← (MPC) + TESTZERO 20, 23 
55 PC ← 0 + (RI.end) 
MPC ← 0 + 0 
6, 10 
 
 
 
JZ 
56 MPC ← 0 + 0 
57 MPC ← (MPC) + TESTNEG 21, 23 
58 PC ← 0 + (RI.end) 
MPC ← 0 + 0 
6, 10 
 
 
 
JN 
59 MPC ← 0 + 0 
EA869 – Prof. Von Zuben 
DCA/FEEC/Unicamp 
Lista de Exercícios 1 (com gabarito) 15
Exercícios – Capítulo 4: Modos de 
Endereçamento 
• a máquina possui os seguintes modos de endereçamento: 
‰ REGISTRADOR DIRETO 
‰ REGISTRADOR INDIRETO 
‰ ABSOLUTO DIRETO 
‰ IMEDIATO 
e também 8 registradores (R0 a R7). 
• instruções disponíveis para manipulação de registradores e posições de memória: 
‰ MOV R1, R2 R2 ← (R1) 
‰ MOV end, R1 R1 ← (end) 
‰ MOV R1, end end ← (R1) 
‰ MOV #opr, R1 R1 ← opr (pode ser dado ou endereço) 
‰ INCR R1 R1 ← (R1) + 1 
‰ DCR R1 R1 ← (R1) − 1 
 
 
Questão 2 
(a) auto-incremento 
MOV A, (R3)+ (R3) ← (A) 
R3 ← (R3) + 1 
MOV A, (R3) 
INCR R3 
 
(b) autodecremento 
MOV B, −(R5) R5 ← (R5) − 1 
(R5) ← (B) 
DCR R5 
MOV B, (R5) 
 
 
 
EA869 – Prof. Von Zuben 
DCA/FEEC/Unicamp 
Lista de Exercícios 1 (com gabarito) 16
Questão 3 
(a) POP R1 SP ← (SP) − 1 
R1 ← ((SP)) 
R2 ≡ SP 
DCR R2 
MOV (R2), R1 
 
 
(b) PUSH R1 (SP) ← (R1) 
SP ← (SP) + 1 
R2 ≡ SP 
MOV R1, (R2) 
INCR R2 
 
 
Questão 4 
MOV R1, P(R2) 
n = no. de bits em R2 
(P) ⊕ (R2) ← (R1) R3 ≡ P 
MOV R3, R4 
MUL 321L
n
0001# , R4 
ADD R2, R4 
MOV R1, (R4) 
 
 
Questão 5 
MOV R1, RX(R2) (R2) + (RX) ← (R1) R3 ≡ RX 
MOV R2, R4 
ADD R3, R4 
MOV R1, (R4) 
 
 
 
 
 
 
EA869 – Prof. Von Zuben 
DCA/FEEC/Unicamp 
Lista de Exercícios 1 (com gabarito) 17
Questão 6 
• indexado indireto pré-indexado 
MOV R1, ( RX(R2) ) ( (R2) + (RX) ) ← (R1) R3 ≡ RX 
MOV R2, R4 
ADD R3, R4 
MOV (R4), R5 
MOV R1, (R5) 
 
• indexado indireto pós-indexado 
MOV R1, RX((R2)) ((R2)) + (RX) ← (R1) R3 ≡ RX 
MOV (R2), R4 
ADD R3, R4 
MOV R1, (R4) 
 
 
Questão 7 
MOV R1, R2(RB) (RB) + (R2) ← (R1) R3 ≡ RB 
MOV R2, R4 
ADD R3, R4 
MOV R1, (R4) 
 
Questão 8 
MOV R1, RX(RB) (RB) + (RX) ← (R1) R2 ≡ RB 
R3 ≡ RX 
MOV R2, R4 
ADD R3, R4 
MOV R1, (R4) 
 
 
 
EA869 – Prof. Von Zuben 
DCA/FEEC/Unicamp 
Lista de Exercícios 1 (com gabarito) 18
Questão 9 
• registrador direto: armazenagem temporária de dados. 
• registrador indireto: implementação de ponteiros (armazena endereço, só 
conhecido em fase de execução, de uma área de dados da memória − acesso 
aleatório e indireto); viabiliza aritmética de ponteiros. 
• absoluto direto: acesso aleatório e direto à memória. 
• absoluto indireto: implementação de ponteiros (armazena endereço, só conhecido 
em fase de execução, de uma área de dados da memória − acesso aleatório e 
indireto); viabiliza aritmética de ponteiros, embora de forma menos eficiente que 
no modo registrador indireto. 
• imediato: operações envolvendo constantes e não variáveis. 
• relativo: acesso à memória relativo ao valor atual do PC. O deslocamento pode ser 
positivo ou negativo. Seu uso permite a produção de código relocável. 
• auto-incremento / autodecremento: acesso seqüencial e indireto aos elementos da 
memória (forma variante do modo por registrador indireto). 
• por pilha: armazenamento temporário, para posterior recuperação, do conteúdo de 
registradores e posições de memória. Possui um registrador auxiliar denominado 
Apontador de Pilha (stack pointer - SP), que sempre aponta para o topo da pilha 
(primeira posição livre). Usa sempre o modo de endereçamento por registradorindireto, sendo que o incremento e decremento de SP é implícito. 
• paginado: viabiliza a divisão do espaço de endereçamento em páginas (blocos de 
memória de tamanho fixo). O endereço efetivo é formado pela concatenação do 
número da página (que se encontra no Registrador de Página) e do deslocamento 
dentro da página (valor obtido do campo de endereço), que certamente terá um 
número reduzido de bits. Com a paginação da memória e o uso de tabela de 
páginas, um programa não precisa ocupar páginas contíguas da memória principal, 
e também não é necessário que todas as páginas do programa estejam ao mesmo 
tempo na memória durante sua execução. 
• indexado: muito útil para acesso aleatório a elementos de vetores e matrizes, 
utilizando os conceitos de endereço-base e deslocamento (positivo ou negativo), 
sendo que o endereço-base está no campo de endereço da instrução (requer muitos 
bits para referenciar toda a memória) e o deslocamento encontra-se em um 
EA869 – Prof. Von Zuben 
DCA/FEEC/Unicamp 
Lista de Exercícios 1 (com gabarito) 19
registrador indexador. Ambos são somados para a produção do endereço efetivo. 
Possui os modos direto, indireto pré-indexado e indireto pós-indexado. 
• baseado: mesmo princípio de operação do indexado, com a diferença de que agora 
o endereço-base está em um registrador de base e o deslocamento encontra-se no 
campo de endereço da instrução (não requer muitos bits), o que leva a usos 
distintos de acordo com o que já se conhece em tempo de programação e em 
tempo de execução. Muito utilizado pelo sistema operacional para gerenciamento 
de memória 
• baseado e indexado: é o mais versátil dos modos de endereçamento. 
Exemplo: Somando nelem elementos de um vetor carregado na memória (a partir da 
posição endvetor) e armazenamento do resultado no endereço endresult: 
 MOV #nelem, R0 
 MOV #endvetor, R1 
 MOV #0, endresult 
loop: ADD (R1)+, endresult 
 DCR R0 
 JNZ loop 
 STOP 
 
Modos de endereçamento (Exercício sem gabarito) 
Considere a seguinte instrução em uma máquina fictícia de dois endereços (EE = endereço efetivo): 
MOV EE1, EE2 EE2 ← (EE1) 
Supondo que o formato da instrução nesta máquina é dado por: 
 
C.O. modo1 
campo de endereçamento 1 
///////////////////////// modo2 
campo de endereçamento 2 
e sabendo-se que esta máquina admite os seguintes modos de endereçamento (n é um número inteiro 
com sinal): 
modo de endereçamento código binário notação endereço efetivo 
por registrador direto 0001 R R 
por registrador indireto 0010 (R) (R) 
absoluto direto 0011 end end 
absoluto indireto 0100 (end) (end) 
baseado 0101 n(RB) (RB)+n 
relativo 0110 n(PC) (PC)+n * 
autoincremento (pós-incremento) 0111 (R)+ (R) 
autodecremento (pré-decremento) 1000 
−(R) (R)−1 
indexado direto 1001 RIX(n) (RIX)+n 
(*) neste caso, o conteúdo de PC corresponde ao endereço de memória do início da próxima instrução 
faça: 
EA869 – Prof. Von Zuben 
DCA/FEEC/Unicamp 
Lista de Exercícios 1 (com gabarito) 20
• apresente a seguir a notação, em linguagem de montagem, das instruções presentes nas posições de 
memória de 100 a 111 e os endereços efetivos (em código decimal) correspondentes aos 
respectivos campos de endereçamento. 
 
 Notação em linguagem de montagem EE1 EE2 
1a instrução 
2a instrução 
3a instrução 
 
• indique na Tabela 1 todas as alterações, em seqüência, nos conteúdos dos registradores e posições 
de memória após a execução das três instruções. 
 
Obs: Toda notação não-binária presente na configuração de memória apresentada a seguir está sendo 
utilizada para representar os respectivos códigos binários que efetivamente estão presentes. 
 
Tabela 1 
PC R1 R2 RIX RB 381 382 383 384 385 715 716 
100 384 715 333 666 384 715 716 385 381 383 382 
− − 
 
 
 
 
 
 100 mov 0110 
 101 281 
 102 /////////// 0100 
PC 100 103 716 
 104 mov 0011 
 105 381 
R1 384 106 /////////// 0111 
 107 r2 
 108 mov 0010 
R2 715 109 r1 
 110 /////////// 0101 
 111 50 
RIX 333 ≈ ≈ 
 381 384 
 382 715 
RB 666 383 716 
 384 385 
 385 381 
 ≈ ≈ 
 715 383 
 716 382 
 ≈ ≈