ASPECTOS TEÓRICOS DA COMPUTAÇÃO Questionario 2

Prévia do material em texto

• Pergunta 1 
0,5 em 0,5 pontos 
 
O que caracteriza uma linguagem como "decidível" na teoria da computação? 
Resposta 
Selecionada: 
c. 
Existe um algoritmo que, quando aplicado a uma cadeia de 
entrada, sempre para e decide se a cadeia pertence à linguagem 
ou não. 
Respostas: 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. 
Comentário 
da resposta: 
Resposta: C 
Comentário: Uma linguagem é considerada "decidível" na teoria da 
computação quando existe um algoritmo que pode determinar, de 
forma eficaz, se uma cadeia de entrada pertence à linguagem ou 
não. Isso implica que o algoritmo sempre para e fornece uma 
resposta definitiva. 
 
 
• Pergunta 2 
0,5 em 0,5 pontos 
 
Qual das seguintes afirmações é verdadeira sobre o Problema da Parada? 
Resposta 
Selecionada: 
d. 
O Problema da Parada é insolúvel, o que significa que não existe 
um algoritmo geral para resolvê-lo. 
 
Respostas: 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. 
Comentário 
da resposta: 
Resposta: D 
Comentário: O Problema da Parada é um exemplo clássico de um 
problema indecidível na teoria da computação. Isso significa que 
não existe um algoritmo geral que possa decidir corretamente se 
qualquer programa de computador terminará ou não quando 
aplicado a uma entrada específica. Portanto, o Problema da Parada 
é insolúvel e não tem uma solução geral. 
 
• Pergunta 3 
0,5 em 0,5 pontos 
 
O que significa dizer que um problema é "indecidível" na teoria da computação? 
Resposta 
Selecionada: 
c. 
Significa que não existe um algoritmo geral que possa decidir 
corretamente se uma instância do problema é verdadeira ou 
falsa. 
Respostas: 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. 
Comentário 
da resposta: 
Resposta: C 
Comentário: Quando um problema é chamado de "indecidível" na 
teoria da computação, isso significa que não existe um algoritmo 
geral que possa tomar qualquer instância do problema como 
entrada e decidir corretamente se essa instância é verdadeira ou 
falsa. É um conceito fundamental que demonstra a existência de 
limitações intrínsecas na capacidade de resolução de problemas por 
algoritmos. 
 
• Pergunta 4 
0,5 em 0,5 pontos 
 
Na teoria da computação, o que significa quando dizemos que um problema A é 
"redutível" a um problema B? 
 
Resposta 
Selecionada: 
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. 
Respostas: 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. 
Comentário 
da resposta: 
Resposta: B 
Comentário: Quando dizemos que um problema A é "redutível" a 
um problema B, significa que podemos transformar instâncias do 
problema A em instâncias do problema B de tal forma que uma 
solução para B também seja uma solução para A. Em outras 
palavras, podemos usar um algoritmo para resolver B e aplicá-lo às 
instâncias de A. Isso implica que A é, de alguma forma, "mais 
simples" ou "não mais difícil" do que B. 
 
• Pergunta 5 
0,5 em 0,5 pontos 
 
Qual é o objetivo principal da redutibilidade na teoria da computação? 
Resposta 
Selecionada: 
d. 
Definir relações de complexidade entre problemas. 
Respostas: 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. 
Comentário 
da resposta: 
Resposta: D 
Comentário: O objetivo principal da redutibilidade na teoria da 
computação é estabelecer relações de complexidade entre 
problemas. Isso ajuda a classificar problemas em termos de sua 
dificuldade relativa e a compreender como os problemas se 
relacionam uns com os outros em termos de solubilidade. 
Redutibilidade é uma ferramenta fundamental para a teoria da 
computação e ajuda a definir classes de complexidade, como P, NP, 
NP-completo, entre outras. 
 
• Pergunta 6 
0,5 em 0,5 pontos 
 
Quais são os limites assintóticos considerados ao estudar o comportamento de 
funções? 
 
Resposta 
Selecionada: 
e. 
O comportamento à medida que o tamanho da entrada cresce 
indefinidamente. 
Respostas: 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. 
Comentário 
da resposta: 
Resposta: E 
Comentário: Os limites assintóticos na análise do comportamento 
de funções concentram-se no comportamento à medida que o 
tamanho da entrada cresce indefinidamente. Isso ajuda a entender 
 
como as funções se comportam "no infinito" e como seu 
crescimento se compara a outras funções. Essa análise é importante 
para compreender a eficiência de algoritmos e a complexidade de 
problemas à medida que lidamos com entradas cada vez maiores. 
 
• Pergunta 7 
0,5 em 0,5 pontos 
 
O que significa dizer que uma função f(n) = O(g(n)) no contexto do comportamento 
assintótico de funções? 
 
Resposta 
Selecionada: 
e. 
Significa que f(n) cresce não tão rápido quanto g(n) para 
grandes valores de n. 
Respostas: 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. 
Comentário 
da resposta: 
Resposta: E 
Comentário: Dizer que uma função f(n) = O(g(n)) significa que f(n) 
não cresce tão rápido quanto g(n) para grandes valores de n. Em 
outras palavras, g(n) é uma função que fornece um limite superior 
para o crescimento de f(n) à medida que n aumenta. Essa notação é 
usada para analisar e comparar o desempenho de algoritmos em 
termos de complexidade. 
 
 
• Pergunta 8 
0,5 em 0,5 pontos 
 
Qual das seguintes afirmações é verdadeira sobre problemas na classe P e na classe 
NP? 
 
Resposta 
Selecionada: 
b. 
Todosos problemas na classe P também estão na classe NP. 
Respostas: 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. 
Comentário 
da resposta: 
Resposta: B 
Comentário: A afirmação correta é que todos os problemas na 
classe P também estão na classe NP. Isso ocorre porque a classe P 
consiste em problemas que têm soluções em tempo polinomial, o 
que significa que, se podemos resolver um problema em tempo 
polinomial, também podemos verificar a solução em tempo 
polinomial. Portanto, todos os problemas em P também estão em 
NP. 
 
 
• Pergunta 9 
0,5 em 0,5 pontos 
 
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): 
 
Resposta Selecionada: a. 
Princípio da Redução. 
Respostas: 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. 
Comentário da 
resposta: 
Resposta: A 
Comentário: Seja A um problema de decisão e B outro problema 
de decisão. A redução de A para B é uma função computável f que 
mapeia instâncias de A para instâncias de B de forma que: 
1 - Se x é uma instância de A para a qual a resposta é "sim", ou 
seja, x ∈ A, então f(x) é uma instância de B para a qual a resposta 
também é "sim", ou seja, f(x) ∈ B. 
2 - Se x é uma instância de A para a qual a resposta é "não", ou 
seja, x ∉ A, então f(x) é uma instância de B para a qual a resposta 
também é "não", ou seja, f(x) ∉ B. 
 
 
• Pergunta 10 
0,5 em 0,5 pontos 
 
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: 
Resposta Selecionada: c. 
I, II e III. 
Respostas: a. 
Apenas I e II. 
 
b. 
Apenas I e III. 
 
c. 
I, II e III. 
 
d. 
Apenas II e III. 
 
e. 
Apenas III. 
Comentário 
da resposta: 
Resposta: C 
Comentário: Todas as afirmações são corretas. Entretanto, em I, 
para algumas poucas dezenas de cidades, já se torna inviável. Em II, 
podemos estabelecer uma distância e verificar facilmente a melhor 
rota. Em III, o problema do caixeiro é NP, logo, não existe solução 
em tempo polinomial.