Arquitetura de Computadores do século XXITeoria da Computação

Prévia do material em texto

Arquitetura de Computadores do século XXI
Teoria da Computação
1 - A teoria da computação fornece base científica e matemática para muitos processos computacionais. Um deles é o que se refere à análise de algoritmos, o que permite a comparação entre desempenho de algoritmos que resolvem um mesmo problema. Em geral, quanto mais rápido cresce a função que representa um algoritmo em função do tamanho de entrada e o número de comparações, pior é o algoritmo
Dados quatro algoritmos (A), (B), © e (D) que resolvem um mesmo problema, sendo que: (A) algoritmo de desempenho logarítmico, (B) algoritmo de desempenho linear, © algoritmo de desempenho polinomial e (D) algoritmo de desempenho exponencial, podemos afirma
RESPOSTA: Algoritmo A é preferível, depois na ordem, B, C e D, sendo este último o menos interessante deles
2-A Máquina de Turing tem grande importância na Computação porque:
RESPOSTA: Ajuda a esclarecer os limites das máquinas e o significado de algoritmos
3- Quanto ao algoritmo de busca sequencial, podemos afirmar:
RESPOSTA: Método de busca de um elemento em uma lista em que os elementos são visitados sequencialmente até que o elemento procurado seja encontrado ou termine a lista
4-Quanto ao algoritmo de busca binária tem por característica:
RESPOSTA:Método de busca eficiente de um elemento em uma lista mas só roda em listas ordenadaS
5-O Problema do Caixeiro Viajante é clássico na Computação e ajuda a compreender que alguns problemas não tem solução fácil embora sejam relativamente comuns
O Problema do Caixeiro Viajante tem solução ou complexidade:
RESPOSTA:Exponencial
6-(ENADE/Adaptado) Dado o autômato representado pelo diagrama de estados abaixo, qual a única cadeia de entrada que este autômato aceita? Dica: comece por onde entra a seta (estado A), o autômato “aceita” a cadeia de 0´s e 1´s se parar no estado B
RESPOSTA:111011000