TEORIA DA COMPUTAÇÃO-SIMULADO-01

Prévia do material em texto

10/11/21, 2:36 PM Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=186165540&user_cod=2828661&matr_integracao=202004135813 1/5
 
Simulado AV
Teste seu conhecimento acumulado
 
Disc.: TEORIA DA COMPUTAÇÃO   
Aluno(a): ALESSANDRO VIANA DE ARAUJO 202004135813
Acertos: 7,0 de 10,0 11/10/2021
 
 
Acerto: 0,0  / 1,0
Quando operamos dois conjuntos e retornamos  os elementos existentens no primeiro que não existem no segundo temos  a
operação
PRODUTO CARTESIANO
 
 DIFERENÇA
 UNIÃO
COMPLEMENTO
INTERSECÇÃO
Respondido em 11/10/2021 14:08:42
 
 
Explicação:
a diferença corresponde a operação
A - B = {x | x ∈ A e x ∉ B} 
Ex: Seja A = {0, 1, 2} e B = {2, 3}, então A - B = {0, 1}
 
 
Acerto: 0,0  / 1,0
É uma noção simples, abstrata e intuitiva, usada para representar a ideia de alguma espécie de relação entre os objetos.
Graficamente, aparece representado por uma figura com nós ou vértices. Trata-se dos
dados.
 grafos.
 objetos geométricos.
triângulos.
registros.
 
Respondido em 11/10/2021 14:09:13
 
 
Explicação:
Grafo (graph) é um conjunto de vértices (ou nodos), interconectados dois a dois por arestas (ou arcos). 
 
 Questão1
a
 Questão2
a
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
10/11/21, 2:36 PM Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=186165540&user_cod=2828661&matr_integracao=202004135813 2/5
 
Acerto: 1,0  / 1,0
Considere que uma arvore binária foi criada a partir da inserção de dados na seguinte ordem  5, 7, 8, 3, 2, 4, 1, 9
A raiz da subarvore esquerda arvore é o numero 
5
3
1
9
 
 7
Respondido em 11/10/2021 14:09:57
 
 
Explicação:
A raiz será o primeiro valor na subarvore direita, ou seja maior que a raiz que é o 7
 
 
Acerto: 1,0  / 1,0
Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F)  onde Ʃ representa 
o estado inicial
 
as transições
o conjunto de estados finais
 os simbolos de entrada
O número de estados
Respondido em 11/10/2021 14:12:33
 
 
Explicação:
Seguindo a propriedade de um autômato finito que é representado por uma quíntupla (Q, Ʃ, δ, q0, F):
    Q = número de estados = {q0, q1, q2, q3}
    Ʃ = símbolos de entrada = {0,1}
    δ = transições = 
                δ (q0, 0) = q2
                δ (q0, 1) = q1
                δ (q1, 0) = q3
                δ (q1, 1) = q0
                δ (q2, 0) = q0
                δ (q2, 1) = q3
                δ (q3, 0) = não possui = Ø (vazio)
                δ (q3, 1) = q2
    q0 = estado inicial = {q0}
    F = conjunto de estados finais = {q0}
 
 
Acerto: 0,0  / 1,0
Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde q0 representa 
 
as transições
os simbolos de entrada
o conjunto de estados finais
 o estado inicial
 
 O número de estados
Respondido em 11/10/2021 14:15:56
 Questão3
a
 Questão4
a
 Questão5
a
10/11/21, 2:36 PM Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=186165540&user_cod=2828661&matr_integracao=202004135813 3/5
 
 
Explicação:
Seguindo a propriedade de um autômato finito que é representado por uma quíntupla (Q, Ʃ, δ, q0, F):
    Q = número de estados = {q0, q1, q2, q3}
    Ʃ = símbolos de entrada = {0,1}
    δ = transições = 
                δ (q0, 0) = q2
                δ (q0, 1) = q1
                δ (q1, 0) = q3
                δ (q1, 1) = q0
                δ (q2, 0) = q0
                δ (q2, 1) = q3
                δ (q3, 0) = não possui = Ø (vazio)
                δ (q3, 1) = q2
    q0 = estado inicial = {q0}
    F = conjunto de estados finais = {q0}
 
 
Acerto: 1,0  / 1,0
Considere as seguintes expressões regulares cujo alfabeto é {a,b}.
 R1 = a(a ∪ b)*
 R2 = b(a ∪ b)*
Se L(R) é uma linguagem associada a uma expressão regular R, é correto afirmar que
 
 
L(R2) = {w | w termina com b}
L(R1) = L(r2) 
 Existe um autômato finito determinístico cuja linguagem é igual a L(R1) ∪ L(R2).
Se R3 é uma expressão regular tal que L(R3) = L(R1) ∩ L(R2), então L(R3) é uma linguagem infinita.2). 
Um autômato finito não determinístico que reconheça L(R1) ∪ L(R2) tem, pelo menos, quatro estados.
 
 
Respondido em 11/10/2021 14:23:11
 
 
Explicação:
linguagem L(R1) é composta das palavras ou sequências que iniciam com ¿a¿ e a linguagem L(R2) é composta das palavras
ou sequências que iniciam com ¿b¿. Note que a expressão regular (a ∪ b)* gera qualquer sequência de a´s e b´s. 
Logo, L(R2) não termina com b necessariamente. Sabemos ainda que a união de L(R1) e L(R2) são todas as palavras que
comecem com ¿a¿ ou com ¿b¿, ou seja qualquer palavra sobre o alfabeto, exceto a palavra vazia. Este AFD pode
ser representado com dois estados apenas. Portanto, resta apenas a alternativa C, e como afirmado anteriormente, um AFD de
dois estados reconhece L(R1) ∪ L(R
 
 
Acerto: 1,0  / 1,0
Seja a seguinte linguagem, onde ϵ representa a sentença vazia
SABCD→AB|CD→a|ϵ→b|f→c|g→h|i
Qual o conjunto de terminais que podem começar sentenças derivadas de S?
{a,c,g,h,i}
 
 {a,b,f,c,g}
 
{a,c,g}
{a,b,f}
{a,b,f,c,g,h,i}
 
Respondido em 11/10/2021 14:25:02
 Questão6
a
 Questão7
a
10/11/21, 2:36 PM Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=186165540&user_cod=2828661&matr_integracao=202004135813 4/5
 
 
Explicação:
(A) {a,c,g}
(B) {a,b,f,c,g}
(C) {a,b,f,c,g,h,i}
(D) {a,c,g,h,i}
(E) {a,b,f}
Resolução
Na prática, o enunciado solicita o conjunto FIRST de S.
Todos os terminais que iniciam sentenças produzidas pelos não terminais A e C fazem parte do conjunto: {a,c,g}. Como A
produz a cadeia vazia, então devemos também incluir os não terminais que iniciam sentenças produzidas pelo não terminal B:
{b,f}.
Unindo os conjuntos, temos: {a,b,c,f,g}. Portanto, a alternativa correta é a B.
 
 
Acerto: 1,0  / 1,0
No que concerne a utilização e o processamento de máquina de Turing, assinale a opção correta.
 
As saídas podem ser apenas binárias, pois as referidas máquinas trabalham com representações lógicas. 
O conjunto de símbolos usados pela máquina de Turing é infinito. 
 Na máquina de Turing, o processamento inclui a sucessiva aplicação da função programada até ocorrer uma
condição de parada. 
A máquina em questão registra o valor da palavra de entrada e depois pára, quando a função indicar um movimento
da cabeça para a esquerda e ela já se encontrar no início da fita. 
Uma máquina de Turing pode alterar várias entradas em cada vez, pois ela é capaz de transferir sua atenção para
mais de uma posição da fita em cada argumento da função de transição.
 
 
Respondido em 11/10/2021 14:26:07
 
 
Explicação:
.
 
 
Acerto: 1,0  / 1,0
Considere a gramática G definida pelas regras de produção abaixo, em que os símbolos não-terminais são S, A e B, e os
símbolos terminais são a e b. 
S -> AB
AB -> AAB
A -> a
B -> b
Com relação a essa gramática, é correto afirmar que
a gramática G é ambígua.
a gramática G gera a cadeia nula.. 
a cadeia aabbb é gerada por essa gramática.
a gramática G é uma gramática livre de contexto.
 é possível encontrar uma gramática regular equivalente a G.
Respondido em 11/10/2021 14:34:31
 
 
Explicação:
Quanto ao tipo da gramática, ela não é livre de contexto (alternativa B), pois uma das regras, a segunda, tem dois símbolos do
lado esquerdo. 
As alternativas C e E estão incorretas porque nem a sentença nula, nem a sentença aabbb têm o formato aa*b (note que as
sentenças da linguagem têm exatamente um b)
 Questão8
a
 Questão9
a
10/11/21, 2:36 PM Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=186165540&user_cod=2828661&matr_integracao=202004135813 5/5
 
 
Acerto: 1,0  / 1,0
Um cientista afirma ter encontrado uma redução polinomial de um problema NP-Completo para um problema pertencente à
classe P. Considerando que esta afirmação tem implicações  importantes no que diz respeito à complexidade computacional,
avalie as seguintes asserções e a relação proposta entre elas.
I. A descoberta do cientista implica que P = NP
PORQUE
II. A descoberta do cientistaimplica na existência de algoritmos polinomiais para todos os problemas NP-Completos.
A respeito dessas asserções, assinale a opção correta.
 
 
As asserções I e II são proposições falsas.
 
 
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
 
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
 
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
 
  As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
 
 
Respondido em 11/10/2021 14:28:27
 
 
Explicação:
Uma redução polinomial de um problema NP-completo para um problema pertencente à classe P implica que P=NP, pois se
qualquer problema NPcompleto pode ser resolvido em tempo polinomial, então P=NP, um problema aberto e fundamental na
teoria da computação. Logo, a asserção I está correta.
Por outro lado, quando um problema pertence à classe NP-Completo, o mesmo pode ser reduzido, em tempo polinomial, a um
outro problema da classe NP-Completo. Por isso, ao solucionar um problema em tempo polinomial, todos podem ser
solucionados da mesma forma. 
 
 
 
 
 
 
 
 
 
 
 
 Questão10
a
javascript:abre_colabore('38403','268993763','4877776398');