ASPECTOS TEÓRICOS DA COMPUTAÇÃO QUESTIONÁRIO UNIDADE II

Prévia do material em texto

ASPECTOS TEÓRICOS DA COMPUTAÇÃO QUESTIONÁRIO UNIDADE II 
Pergunta 1 
1. O que caracteriza uma linguagem como "decidível" na teoria da computação? 
 a. A linguagem pode ser escrita em vários idiomas diferentes. 
 b. A linguagem pode ser lida por seres humanos sem esforço. 
 c. 
Existe um algoritmo que, quando aplicado a uma cadeia de entrada, sempre para e decide se a 
cadeia pertence à linguagem ou não. 
 d. A linguagem é usada para comunicação internacional. 
 e. A linguagem é reconhecida, exclusivamente, por uma máquina de Turing não determinística. 
Pergunta 2 
1. Qual das seguintes afirmações é verdadeira sobre o Problema da Parada? 
 a. Existe um algoritmo de parada que pode decidir o resultado para todas as entradas possíveis. 
 b. O Problema da Parada é um problema teórico e não tem relevância prática. 
 c. 
O Problema da Parada é um problema que pode ser resolvido eficientemente por qualquer 
computador. 
 d. 
O Problema da Parada é insolúvel, o que significa que não existe um algoritmo geral para resolvê-
lo. 
 e. 
O Problema da Parada é usado para verificar a velocidade de execução de programas de 
computador. 
Pergunta 3 
1. O que significa dizer que um problema é "indecidível" na teoria da computação? 
 a. Significa que o problema é fácil de resolver por algoritmos. 
 b. Significa que o problema não tem aplicação prática no mundo real. 
 c. 
Significa que não existe um algoritmo geral que possa decidir corretamente se uma instância do 
problema é verdadeira ou falsa. 
 d. Significa que o problema só pode ser resolvido por computadores quânticos. 
 e. Significa que o problema é limitado a computadores superpoderosos. 
Pergunta 4 
1. Na teoria da computação, o que significa quando dizemos que um problema A é "redutível" a um problema 
B? 
 a. Significa que o problema A é mais complexo do que o problema B. 
 b. 
Significa que o problema A pode ser transformado em um problema B, de forma que uma solução 
para B possa ser usada para resolver A. 
 c. Significa que o problema A é equivalente ao problema B. 
 d. Significa que o problema A não tem solução. 
 e. Significa que o problema A é um subconjunto do problema B. 
https://ava.ead.unip.br/webapps/blackboard/execute/courseMain?course_id=_317189_1
Pergunta 5 
1. Qual é o objetivo principal da redutibilidade na teoria da computação? 
 a. Demonstração de que um problema é impossível de ser resolvido. 
 b. Facilitar a resolução de problemas indecidíveis. 
 c. Transformar problemas práticos em problemas teóricos. 
 d. Definir relações de complexidade entre problemas. 
 e. Determinar a complexidade absoluta de um problema. 
Pergunta 6 
1. Quais são os limites assintóticos considerados ao estudar o comportamento de funções? 
 a. O comportamento em um ponto específico da função. 
 b. O comportamento no início da função. 
 c. O comportamento quando a entrada é pequena. 
 d. O comportamento em relação à derivada da função. 
 e. O comportamento à medida que o tamanho da entrada cresce indefinidamente. 
Pergunta 7 
1. O que significa dizer que uma função f(n) = O(g(n)) no contexto do comportamento assintótico de 
funções? 
 a. Significa que f(n) é uma função constante. 
 b. Significa que f(n) é sempre maior do que g(n) para todos os valores de n. 
 c. Significa que f(n) é sempre menor do que g(n) para todos os valores de n. 
 d. Significa que f(n) é igual a g(n) para todos os valores de n. 
 e. Significa que f(n) cresce não tão rápido quanto g(n) para grandes valores de n. 
Pergunta 8 
1. Qual das seguintes afirmações é verdadeira sobre problemas na classe P e na classe NP? 
 a. Problemas na classe P são mais difíceis de resolver do que problemas na classe NP. 
 b. Todos os problemas na classe P também estão na classe NP. 
 c. 
Problemas na classe P têm soluções em tempo exponencial, enquanto problemas na classe NP não 
têm solução. 
 d. Problemas na classe NP são sempre mais simples do que problemas na classe P. 
 e. Problemas na classe P não têm solução. 
Pergunta 9 
1. Considere o seguinte enunciado: 
Sejam A e B dois problemas de decisão. Suponha que seja possível modificar o problema A de tal forma 
que ele se comporte como um caso do problema B. Se A é não solucionável, então, como A é um caso de 
B, conclui-se que B também é não solucionável. Se B é solucionável, então, como A é um caso de B, 
conclui-se que A também é solucionável. 
O enunciado diz respeito à(ao): 
 a. Princípio da Redução. 
 b. Hipótese de Turing-Chuch. 
 c. Problema da Parada. 
 d. Hierarquia de Chomsky. 
 e. Teorema da Aproximação. 
Pergunta 10 
1. O problema do caixeiro viajante (Travelling Salesman Problem – TSP) é de natureza combinatória e é uma 
referência para diversas aplicações, tais como projeto de circuitos integrados, roteamento de veículos, 
programação de produção, robótica etc. Em sua forma mais simples, no TSP, o caixeiro deve visitar cada 
cidade somente uma vez e depois retornar à cidade de origem. Dado o custo da viagem (ou distância) entre 
cada uma das cidades, o problema do caixeiro é determinar qual o itinerário que possui o menor 
custo. Formalmente, o problema pode assim ser enunciado: “Dado um número inteiro n maior igual a 2, 
matriz de distância dij e um inteiro L maior igual a 0, encontrar uma permutação p de {1, 2, ..., n}, tal que 
custo (p) seja menor igual a L. Considere as afirmações seguintes: 
 
I – O algoritmo que resolve o problema consiste em enumerar todas as rotas possíveis, calcular o 
comprimento de cada uma delas e selecionar a menor. 
II – O problema de otimização (a rota ótima) pode ser reduzido a um problema de decisão. 
III – Trata-se de um problema cuja solução polinomial não é conhecida. 
 
É correto o que se afirma em: 
 a. Apenas I e II. 
 b. Apenas I e III. 
 c. I, II e III. 
 d. Apenas II e III. 
 e. Apenas III. 
 
 
 
ATIVIDADE TELEAULA II 
 
Pergunta 1 
1. Qual das seguintes afirmações sobre a decidibilidade está correta? 
 a. Todos os problemas são decidíveis, desde que haja recursos computacionais suficientes. 
 b. 
Um problema é decidível se existir um algoritmo que sempre produzirá uma resposta correta em 
tempo finito. 
 c. Um problema é decidível apenas se for possível resolvê-lo em tempo linear. 
 d. A decidibilidade de um problema depende apenas de sua complexidade. 
 e. A decisão se aplica apenas a problemas estritamente matemáticos. 
 
Pergunta 2 
1. O conceito de redutibilidade na teoria da computação refere-se à: 
 a. Habilidade de reduzir a complexidade de um problema de NP para um problema de P. 
 b. Capacidade de tornar um problema indecidível em um problema decidível. 
 c. 
Transformação de um problema em outro de tal forma que a solução do segundo problema possa 
ser usada para resolver o primeiro. 
 d. Técnica de otimização de algoritmos para torná-los mais eficientes. 
 e. Ideia de transformar um problema em outro problema de maior complexidade. 
 
Pergunta 3 
1. Qual é o objetivo da notação “Big O” (O-grande) no contexto do comportamento assintótico de funções? 
 a. Descrever o comportamento exato de uma função para todos os tamanhos de entrada. 
 b. Provar que uma função é irredutivelmente complexa. 
 c. Determinar a complexidade exata do tempo de execução de um algoritmo. 
 d. 
Fornecer uma estimativa superior do crescimento de uma função à medida que o tamanho da 
entrada cresce. 
 e. Descrever a complexidade espacial de um algoritmo. 
 
Pergunta 4 
1. Qual é a principal diferença entre problemas na classe P e problemas na classe NP? 
 a. 
Problemas em P são solucionáveis em tempo polinomial, enquanto problemas em NP não têm 
solução. 
 b. Problemas em P são mais difíceis de resolver do que problemas em NP. 
 c. 
Problemas em P têm complexidade exponencial, enquanto problemas em NP têm complexidade 
polinomial. 
 d. 
Problemas em P podem ser resolvidos em tempo polinomial, enquanto problemas em NP podem 
ser verificados em tempo polinomial. 
 e. Nãohá diferença significativa entre problemas em P e NP.