Baixe o app para aproveitar ainda mais
Prévia do material em texto
Bacharelado em Ciência da Computação Aspectos Teóricos da Computação Trabalho P1 Nome.: Juliana Carolina Alves de Oliveira RA: D747FH7 As questões que se seguem constituem o trabalho a nota P1 da disciplina. O valor de cada questão é 0.5 ponto. Assim sendo a nota máxima para o trabalho é 5.0 DATA DE ENTREGA: 10 DE MAIO. APÓS ESTA DATA NÃO SERAO ACEITOS TRABALHOS PARA A Composição DA Média FINAL. Questão 1 (0.5 ponto) - Sabe-se que a máquina de Turing, é definida formalmente como uma quíntupla MT = (Q, A, , g, q0, >, b, F), onde: · Q é o conjunto finito não vazio de estados. · A é o alfabeto de entrada, formado por um conjunto não vazio de símbolos. · é o conjunto finito e não vazio de símbolos que podem ser lidos e/ou escritos na fita de trabalho. A. · q0Q é o estado inicial. · F Q é o conjunto de estados finais. Assinale a alternativa correta sobre a Máquina de Turing MT: a) O cursor de acesso à fita de trabalho de uma máquina de Turing pode se deslocar apenas à direita. b) Apresenta a fita de trabalho limitada à direita. c) Sempre, para qualquer que seja o conteúdo da fita de entrada e qualquer que seja a função de transição. d) Apresenta um conjunto ilimitado de estados. e) A Fita de trabalho de uma MT é passível de ser lida e escrita. Questão 2(0.5 ponto) Considere a seguinte tabela, que representa a operação de uma máquina de Turing: estado Símbolo lido na fita Símbolo gravado na fita Direção Próximo estado q0 direita q0 q0 x x direita q1 q0 y x direita q0 q0 b b direita q0 q1 x y direita q0 q1 y y esquerda q0 Considere ainda, a seguinte configuração inicial de reconhecimento: b y x b q0 A última fita de entrada é: a) b x x b q0 b) b y y b qf c) b y x b q1 d) b x x b q1 e) O processamento não para. Questão 3 (0.5 ponto)- Considere a seguinte tabela, que representa a operação de uma máquina de Turing: estado Símbolo lido na fita Símbolo gravado na fita Direção Próximo estado q0 direita q0 q0 x x direita q1 q0 y x direita q0 q0 b b direita q0 q1 x y direita q0 q1 y y esquerda q0 Considere ainda, a seguinte configuração inicial de reconhecimento: b x y b q0 A última fita de entrada é: a) b x x b q0 b) b y y b qf c) b x y b q1 d) b x y b q1 e) O processamento não para, efetuando ciclos. Questão 4: (0.5 ponto) A Hipótese de Turing-Church sugere: a) Que à Máquina de Turing devem ser adicionadas duas ou mais pilhas de forma que o seu poder computacional de expressar algoritmos seja menos restritivo; b) Que se a máquina de Turing fosse multidimensional seu poder computacional de expressar algoritmos seria menos restritivo; c) Que à Máquina de Turing devem ser adicionados múltiplos cabeçotes de leitura e gravação sobre a mesma fita, de forma que o seu poder computacional de expressar algoritmos seja menos restritivo; d) Que se a máquina de Turing fosse multidimensional seu poder computacional de expressar algoritmos seria muito restritivo; e) Qualquer outra forma de expressar algoritmos terá no máximo a mesma capacidade computacional da Máquina de Turing; Questão 5 (0.5 ponto) Considere a seguinte definição: “Dada uma Máquina Universal M qualquer e uma palavra w qualquer sobre o alfabeto de entrada, existe um algoritmo que verifique se M para, aceitando ou rejeitando, ao processar a entrada w?”. Trata-se da definição do problema conhecido como: a) Problema da Análise Lexicográfica; b) Problema das Máquinas Universais; c) Problema das Entradas; d) Problema da Parada; e) Problema da Auto-Aplicação; Questão 6 (0.5 ponto) Assinale a alternativa que diz respeito a um problema que apresenta desempenho polinomial: a) problema do Caixeiro Viajante. b) Problema do Clique. c) Problema dos Conjuntos Independentes d) Detecção de um ciclo Hamiltoniano em um Grafo e) Detecção de um caminho Euleriano em um Grafo; Questão 7 (0.5 ponto) Considere o g rafo G=(V, A, g), onde: V = {1, 2, 3, 4, 5, 6, 7, 8} são os vértices A = {a, b, c, d, e} g(a) = 2-6 g(b) = 4-3 g(c) = 2 – 3 g(d) = 1-4 g(e) = 1-2 g(f) = 5-6 g(g) = 5- 8 g(h)=8-7 g(i)= 6-7 g(j) = 7-3 g(k) = 8-4 Sejam ainda, as seguintes afirmações: I - O grafo apresenta um caminho de Euler, pois apresenta um número par de nós ímpares; II – O grafo apresenta um ciclo Hamiltoniano, pois apresenta um número par de nós ímpares III – Este grafo apresenta 8 vértices e desta forma um programa que verifique se existe um caminho Hamiltoniano deverá efetuar em uma situação de pior caso 8! cálculos. IV – Este grafo apresenta 6 nós ímpares e portanto não apresenta um Caminho de Euler. a) I, II, III e IV; b) Apenas III e IV; c) Apenas I e II; d) Apenas I e III; e) Apenas II e IV; Questão 8 (0.5 ponto) Assinale a alternativa correta: a) Verificar se uma dada fórmula booleana cujas cláusulas apresentam apenas 2 literais é “satisfazível, é um problema NP. b) É possível demonstrar que P NP e NP P. c) Não se sabe se P = NP; d) Se P é diferente de NP, então existem problemas na classe P que são NP-completos. e) O algoritmo para a busca em uma árvore binária é NP-completo; Questão 9 (0.5 ponto) Assinale a alternativa que representa um problema NP-Completo: a) Satisfabilidade booleana-2; b) Problema da parada; c) Detecção universal do loop completo; d) Problema do Ciclo de Euler; e) Problema do Ciclo Hamiltoniano Questão 10(0.5 ponto) Em uma determinada edificação, onde o esquema de segurança é crucial, deseja-se cobrir todas as áreas de circulação e ao mesmo tempo minimizar o número de pontos de monitoração. Sabe-se que o número de salas deste lugar é 30 e o número de corredores é 15. A fim de se obter exatamente o menor número de pontos de monitoração de forma a cobrir todos os corredores, deveriam ser realizados cálculos de complexidade: a) fatorial; b) quadrática; c) linear d) logarítmica; e) cúbica;
Compartilhar