ASPECTOS TEORICOS DA COMPUTAC1

Prévia do material em texto

13/04/2018 Revisar envio do teste: QUESTIONÁRIO UNIDADE I – D561_...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_2847545_1&course_id=_8900_1&content_id=_148026_1&return_content=1&step=
 
Revisar envio do teste: QUESTIONÁRIO UNIDADE I
ASPECTOS TEORICOS DA COMPUTAC D561_13701_A_R_20181 CONTEÚDO
Usuário IVANNA SOARES PEREIRA
Curso ASPECTOS TEORICOS DA COMPUTAC
Teste QUESTIONÁRIO UNIDADE I
Iniciado 13/04/18 15:40
Enviado 13/04/18 16:38
Status Completada
Resultado da tentativa 4,5 em 5 pontos  
Tempo decorrido 57 minutos
Resultados exibidos Respostas enviadas, Perguntas respondidas incorretamente
Pergunta 1
Resposta Selecionada:
e. 
Considere as seguintes afirmações:
I – É provado ser insolúvel o seguinte o problema: “Dadas duas gramáticas gerais arbitrárias
G1 e G2, determinar se as linguagens geradas por G1 e G2 são iguais”.
II – É provado ser insolúvel o seguinte problema: “Dadas duas máquinas de Turing M1 e M2
arbitrárias, elas param com as mesmas entradas”.
III – Não existe algoritmo genérico que sempre pare capaz de comparar dois arbitrários
compiladores de linguagens livres do contexto e verificar se são equivalentes, ou seja, se de
fato, reconhecem a mesma linguagem.
Está correta a alternativa:
 
I, II e III
Pergunta 2
Resposta Selecionada: d. 
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:
Problema da parada.
CONTEÚDOS ACADÊMICOS BIBLIOTECAS MURAL DO ALUNOASSOCIADA / COLIGADA
0,5 em 0,5 pontos
0,5 em 0,5 pontos
IVANNA PEREIRA 1
13/04/2018 Revisar envio do teste: QUESTIONÁRIO UNIDADE I – D561_...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_2847545_1&course_id=_8900_1&content_id=_148026_1&return_content=1&step=
Pergunta 3
Resposta Selecionada: c. 
É um exemplo de problema não solucionável:
Detector universal de loops.
Pergunta 4
Resposta Selecionada: c. 
A máquina de Turing permite a computação de números naturais. Seja I um símbolo fixo não
branco. Um número natural n pode ser representado em notação unária, pela cadeia de
símbolos I, de comprimento n+1.
Considerando essa definição, selecione a representação unária para os números 0, 1 e 2,
respectivamente, com I =1|.
1, 11, 111
Pergunta 5
Resposta Selecionada: d. 
Considere as seguintes afirmações:
I – Como algoritmos podem representar máquinas de Turing e vice-versa, isso implica que
questões gerais sobre algoritmos não podem ser sempre respondidas com o auxílio de
algoritmos.
II – Nenhuma linguagem (máquina de Turing universal) permite sistematizar a forma de
descobrir se um programa (máquina de Turing) faz realmente o que se deseja para qualquer
entrada possível.
III – O problema da verificação formal de programas é insolúvel no seu caso geral.
Está correta a alternativa:
I, II e III
Pergunta 6
0,5 em 0,5 pontos
0,5 em 0,5 pontos
0,5 em 0,5 pontos
0,5 em 0,5 pontos
13/04/2018 Revisar envio do teste: QUESTIONÁRIO UNIDADE I – D561_...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_2847545_1&course_id=_8900_1&content_id=_148026_1&return_content=1&step=
Resposta Selecionada:
e. 
Q é o conjunto �nito não vazio de estados.
A é o alfabeto de entrada, formado por um conjunto não vazio
de símbolos.
Γé o conjunto �nito e não vazio de símbolos que podem ser lidos
e/ou escritos na �ta de trabalho Γ⊇ A.
q0∈Q é o estado inicial.
F ⊆ Q é o conjunto de estados �nais.
 
Sabe-se que a máquina de Turing é definida formalmente como uma quíntupla MT = (Q, A,
Γ, g, q0, >, b, F), em que:
 Assinale a alternativa correta sobre a Máquina de Turing MT:
 
A fita de trabalho de uma MT é passível de ser lida e escrita.
Pergunta 7
Resposta Selecionada:
e. 
A máquina de Turing permite a computação de números naturais. Seja I um símbolo fixo não
branco. Um número natural n pode ser representado em notação unária, pela cadeia de
símbolos I, de comprimento n+1. Considerando essa definição, selecione a representação
unária para os números 0, 1 e 2, respectivamente, com I =*
 
Não existe representação unária.
Pergunta 8
Resposta
Selecionada:
e.
A hipótese de Turing-Church sugere:
Qualquer outra forma de expressar algoritmos terá no máximo a mesma
capacidade computacional da máquina de Turing.
0 em 0,5 pontos
0,5 em 0,5 pontos
13/04/2018 Revisar envio do teste: QUESTIONÁRIO UNIDADE I – D561_...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_2847545_1&course_id=_8900_1&content_id=_148026_1&return_content=1&step=
Sexta-feira, 13 de Abril de 2018 16h38min33s BRT
Pergunta 9
Resposta
Selecionada:
e.
 Assinale a alternativa incorreta:
Sempre existe uma máquina de Turing que detecta um loop infinito.
Pergunta 10
Resposta
Selecionada:
b.
Para a classe das linguagens recursivas:
Existe, pelo menos, uma máquina de Turing reconhecedora que sempre
para qualquer que seja a entrada.
← OK
0,5 em 0,5 pontos
0,5 em 0,5 pontos