ASPECTOS TEÓRICOS DA COMPUTAÇÃO UNIP 1

Prévia do material em texto

15/10/2018 Revisar envio do teste: QUESTIONÁRIO UNIDADE I – D561_...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_9565340_1&course_id=_23890_1&content_id=_373857_1&return_content=1&step= 1/6
 Revisar envio do teste: QUESTIONÁRIO UNIDADE IASPECTOS TEORICOS DA COMPUTACAO D561_13710_D_20182 CONTEÚDO
Usuário LUCAS DE SOUZA
Curso ASPECTOS TEORICOS DA COMPUTACAO
Teste QUESTIONÁRIO UNIDADE I
Iniciado 15/10/18 14:57
Enviado 15/10/18 15:09
Status Completada
Resultado da tentativa 3,5 em 5 pontos  
Tempo decorrido 12 minutos
Resultados exibidos Respostas enviadas, Perguntas respondidas incorretamente
Pergunta 1
Resposta Selecionada: c. 
É um exemplo de problema não solucionável:
Detector universal de loops.
Pergunta 2
Considere as seguintes afirmações:
UNIP BIBLIOTECAS MURAL DO ALUNOCONTEÚDOS ACADÊMICOS
0,5 em 0,5 pontos
0,5 em 0,5 pontos
LUCAS SOUZA 1
15/10/2018 Revisar envio do teste: QUESTIONÁRIO UNIDADE I – D561_...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_9565340_1&course_id=_23890_1&content_id=_373857_1&return_content=1&step= 2/6
Resposta Selecionada: a. 
I - Uma linguagem L é aceita por uma máquina de Turing com k fitas, m dimensões, n cabeçotes de leitura e gravação por fita se, e somente
se, ela é aceita por uma máquina de Turing determinística com uma fita infinita em apenas um sentido e um cabeçote de leitura e gravação.
II - O conjunto de todos os programas que param para uma dada entrada é um conjunto recursivamente enumerável.
III – A tese de Church Turing iguala uma função computável por algoritmo com uma função computável por Turing.
Está correta a alternativa: 
I, II e III
Pergunta 3
Cada estado distinto da máquina de Turing é nomeado por uma cadeia constituída do símbolo q, que deve ser
sucedido por uma cadeia de símbolos do alfabeto binário.
Analogamente, cada símbolo da cadeia de entrada é nomeado por uma cadeia constituída do símbolo a e
sucedido por uma cadeia de símbolos do alfabeto binário.
Os estados e os símbolos da cadeia de entrada devem ser ordenados. Pode-se por convenção ordená-los em
ordem lexicográ�ca crescente de tal forma que o estado inicial é o primeiro e os estados de aceitação são os
últimos. Os símbolos especiais são os primeiros, na seguinte ordem: (branco, início de �ta (•), movimento à
esquerda (←) e movimento à direita (→)).
Diz-se que “M” é a representação da máquina de Turing “M”.
É possível considerar o formalismo da máquina de Turing como uma linguagem de programação, com a qual se pode se escrever programas.
Programas escritos nessa linguagem podem ser interpretados por uma máquina universal de Turing. Em outras palavras, é possível
especificar uma máquina de Turing através de uma descrição passível de ser a entrada de outra máquina de Turing. Para tanto, faz-se
necessário codificar os estados e os símbolos da cadeia de entrada sobre um determinado alfabeto (conjunto finito de símbolos). A seguinte
convenção pode ser adotada:
0,5 em 0,5 pontos
15/10/2018 Revisar envio do teste: QUESTIONÁRIO UNIDADE I – D561_...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_9565340_1&course_id=_23890_1&content_id=_373857_1&return_content=1&step= 3/6
Resposta Selecionada: b. 
“M” é um conjunto de quádruplas, obtidas a partir da função de transição g de M e deve ser ordenada em ordem lexicográfica crescente,
iniciando-se por g(q0, branco) e o estado de aceitação deverá ser o último estado da ordenação.
 
 A partir do que foi acima produzido, considere a máquina de Turing M = (Q, A, g, q0, F), em que:
 Q = {q0, q1, qf}
 A = {b, •, x}
 F = {qf}
 q0 é o estado inicial;
 b representa “branco”.
A função de transição é dada pela tabela abaixo:
Qual deve ser a representação lexicográfica de q0, q1 e qf, segundo a convenção adotada, respectivamente?
 
q00, q01, q10
Pergunta 4
Resposta
Selecionada:
b.
Assinale a alternativa incorreta:
A classe dos problemas parcialmente solucionáveis é equivalente à classe das linguagens enumeráveis
recursivamente.
0 em 0,5 pontos
15/10/2018 Revisar envio do teste: QUESTIONÁRIO UNIDADE I – D561_...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_9565340_1&course_id=_23890_1&content_id=_373857_1&return_content=1&step= 4/6
Pergunta 5
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.
Pergunta 6
Resposta Selecionada:
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:
0,5 em 0,5 pontos
0,5 em 0,5 pontos
15/10/2018 Revisar envio do teste: QUESTIONÁRIO UNIDADE I – D561_...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_9565340_1&course_id=_23890_1&content_id=_373857_1&return_content=1&step= 5/6
e. 
A fita de trabalho de uma MT é passível de ser lida e escrita.
Pergunta 7
Resposta Selecionada: c. 
Assinale a alternativa incorreta:
Não existem problemas não solucionáveis.
Pergunta 8
Resposta Selecionada: c. 
 Considere uma máquina de Turing X capaz de analisar qualquer máquina de Turing T. As duas únicas possibilidades de X parar são
descritas a seguir:
I - A máquina de Turing X deve parar com a fita contendo apenas um algarismo 1, se e somente se T aceitar uma cadeia.
II - A máquina de Turing X deve parar com a fita contendo apenas um algarismo 0, se e somente se T nunca parar ao processar a cadeia.
Assinale a alternativa correta:
X existe, mas T não existe.
0,5 em 0,5 pontos
0 em 0,5 pontos
15/10/2018 Revisar envio do teste: QUESTIONÁRIO UNIDADE I – D561_...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_9565340_1&course_id=_23890_1&content_id=_373857_1&return_content=1&step= 6/6
Segunda-feira, 15 de Outubro de 2018 15h09min57s BRT
Pergunta 9
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.
Pergunta 10
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.
← OK
0,5 em 0,5 pontos
0 em 0,5 pontos