CCT0832 - Simulado AV

Prévia do material em texto

1a
          Questão
	Acerto: 1,0  / 1,0
	
	Considerando A um conjunto e R uma relação em A, há algumas propriedades a serem respeitadas. No que tange a propriedade Reflexiva é correto afirmar:
		
	 
	Para todo a ∈ A, aRa
	
	aRb e bRa, então a≠b
	
	aRb, então bRa 
	
	aRb e bRc, então aRc
	
	aRb e bRa, então a=b
	Respondido em 23/03/2021 13:59:14
	
	Explicação:
Em um conjunto qualquer, podemos dizer que existe relação reflexiva se os subconjuntos deste conjunto possuírem os mesmos elementos.
	
		2a
          Questão
	Acerto: 1,0  / 1,0
	
	Com relação ao tema Estrutura de Dados ¿ Grafos, entendese por ¿grau de um nó":
		
	
	 um conjunto de nós e um conjunto de arestas.
	 
	 o número de arestas a ele ligadas.
	
	 uma relação que liga dois nós.
	
	uma entidade, tal como "uma fruta", "uma pessoa".
	
	 sequência de nós interligados que liga um nó (origem) a um outro nó (destino).
 
	Respondido em 23/03/2021 13:59:28
	
	Explicação:
O grau de um grafo indica o número de arestas que conectam um vértice do grafo a outros vértices, ou seja, número de vizinhos que aquele vértice possui no grafo (que chegam ou partem dele). Para grafos direcionados são indicados dois tipos de grau, grau de entrada (número de arestas que chegam ao vértice) e grau de saída (número de arestas que partem do vértice
	
		3a
          Questão
	Acerto: 1,0  / 1,0
	
	Ao percorrermos uma arvore se visitamos primeiro a subarvore esquerda  estamos no percurso em:
		
	
	Ordem Natural
	
	Pré Ordem
	
	Ordem Central
 
	
	Pós Ordem
	 
	Ordem
	Respondido em 23/03/2021 14:00:46
	
	Explicação:
Ordem: Esquerda, Centro, Direita
	
		4a
          Questão
	Acerto: 1,0  / 1,0
	
	Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde Q representa 
		
	 
	O número de estados
	
	os simbolos de entrada
	
	o conjunto de estados finais
	
	o estado inicial
 
	
	as transições
	Respondido em 23/03/2021 14:01:41
	
	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}
	
		5a
          Questão
	Acerto: 1,0  / 1,0
	
	A definição formal diz que um autômato finito é uma lista de cinco objetos: conjunto de estados, alfabeto de entrada, regras para movimentação, estado inicial, e estados de aceitação. Essa lista de cinco elementos é frequentemente chamada:
		
	
	Array
	
	Mapeamento
	
	Autômato quinto
	 
	quíntupla
	
	Five elements
	Respondido em 23/03/2021 14:01:54
	
	Explicação:
Dizemos que um autômato finito é representado por uma quíntupla (Q, Ʃ, δ, q0, F), onde Q é o conjunto finito de estados, Ʃ é o conjunto finito de símbolos de entrada, δ é a função de transição, q0 é o estado inicial (q0 ∈ Q  o estado inicial é apontado por uma seta) e F o conjunto de estados finais ou de aceitação (os estados de aceitação são apontados por um círculo dentro de outro ou asterisco e um estado inicial também pode ser final).
	
		6a
          Questão
	Acerto: 1,0  / 1,0
	
	Seja Σ={a,b}. Uma expressão regular denotando a linguagem L = {w∈Σ∗ tal que toda ocorrência de "a" em w é imediatamente seguida de "b"} é:
		
	
	 a∗b
	
	(ab)∗
 
	
	(a∗b)∗
	 
	(b+ab)∗
	
	 b+(ab)∗
	Respondido em 23/03/2021 14:03:29
	
	Explicação:
(A) (a∗b)∗
(B) (b+ab)∗
(C) a∗b
(D) b+(ab)∗
(E) (ab)∗
As alternativas A e C estão incorretas, pois as expressões regulares reconhecem, por exemplo, a cadeia aab, que não faz parte da linguagem do enunciado.
A alternativa E também está errada. O problema é que ela não reconhece todas as cadeias da linguagem do enunciado. Por exemplo, a cadeia bab faz parte de L, mas não é reconhecida pela ER.
A alternativa D está errada. Entretanto, a ER dessa alternativa é confusa, pois não temos como saber se o operador "+" é o fecho positivo ou o operador de união, que é normalmente representado por "|". Felizmente, em ambos os casos a alternativa estaria errada.
Portanto, a única alternativa correta é a B.
	
		7a
          Questão
	Acerto: 1,0  / 1,0
	
	Seja a linguagem formal L={anb2nc,n≥0}. Analise as seguintes assertivas.
I. L é uma linguagem livre de contexto.
II. A gramática G=({S,X},{a,b,c},{S→Xc,X→aXbb|ϵ},S) gera a linguagem L.
III. L não pode ser reconhecida por um autômato com pilha.
A análise permite concluir que estão CORRETAS
 
		
	
	apenas as assertivas I e III.
	
	apenas as assertivas II e III.
 
	
	nenhuma das assertivas.
	
	todas as assertivas.
 
	 
	apenas as assertivas I e II.
 
	Respondido em 23/03/2021 14:04:42
	
	Explicação:
(A) apenas as assertivas I e II.
(B) apenas as assertivas I e III.
(C) apenas as assertivas II e III.
(D) todas as assertivas.
(E) nenhuma das assertivas.
Resolução
As afirmativas I e II estão corretas. A gramática G é livre de contexto e produz corretamente a linguagem L.
A produção X→aXbb|ϵ produz anb2n, isto é, para cada a à esquerda, teremos dois b's à direita. Essa "simetria" não pode ser expressa por uma gramática regular.
Uma vez que a gramática G é livre de contexto, então a linguagem L, produzida por G, é livre de contexto.
A afirmativa III está incorreta, pois como a linguagem L é livre de contexto, então ela é reconhecida por um autômato com pilha.
Portanto, a alternativa correta é a A.
	
		8a
          Questão
	Acerto: 1,0  / 1,0
	
	Qual das seguintes afirmações é falsa?
 
		
	 
	 Não existe autômato finito determinístico que reconheça alguma linguagem livre de contexto.
 
	
	
 Não existe algoritmo que determina quando uma gramática livre de contexto arbitrária é ambígua.
 
	
	Um autômato com duas pilhas pode ser simulado por uma máquina de Turing.
 
	
	 Dada uma máquina de Turing M com alfabeto de entrada Σ e uma string w∈Σ, não se sabe se a computação de M com entrada w vai ou não parar.
 
	
	 O problema da parada é indecidível.
 
	Respondido em 23/03/2021 14:05:32
	
	Explicação:
(A) Dada uma máquina de Turing M com alfabeto de entrada Σ e uma string w∈Σ, não se sabe se a computação de M com entrada w vai ou não parar.
(B) O problema da parada é indecidível.
(C) Não existe algoritmo que determina quando uma gramática livre de contexto arbitrária é ambígua.
(D) Não existe autômato finito determinístico que reconheça alguma linguagem livre de contexto.
(E) Um autômato com duas pilhas pode ser simulado por uma máquina de Turing.
A única alternativa falsa é a D. Linguagens regulares são reconhecidas por autômatos finitos determinístico e, pela hierarquia de Chomsky, toda linguagem regular também é livre de contexto.
	
		9a
          Questão
	Acerto: 1,0  / 1,0
	
	Em uma gramática sensível ao contexto definida por  G = {V, T, P, S} o que  T significa?
		
	 
	Conjunto finito de símbolos terminais DISJUNTOS
	
	Uma palavra ¿final¿, composta dos símbolos terminais
 
	
	Regras de produção da forma
	
	Conjunto finito de símbolos ou variáveis Não-Terminais
	
	Um símbolo especial escolhido aparte de V denominado inicial
	Respondido em 23/03/2021 14:06:10
	
	Explicação:
V - Conjunto finito de símbolos ou variáveis Não-Terminais, ou seja, são variáveis a serem substituídas por outras variáveis ou símbolos terminais nos passos de produção das palavras da gramática e nenhum deles deverá aparecer nas palavras finais da linguagem gerada por ela. 
T -Conjunto finito de símbolos terminais DISJUNTOS , ou seja, que não façam parte de V.  Eles são ditos ¿terminais¿ pois são os que farão parte das palavras geradas por essa gramática.
P - Regras de produção da forma:  
S - Um símbolo especial escolhido aparte de V denominado inicial. Esteé o símbolo por onde começamos a substituição das regras de produção.
	
		10a
          Questão
	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 cientista implica na existência de algoritmos polinomiais para todos os problemas NP-Completos.
A respeito dessas asserções, assinale a opção correta.
 
 
		
	
	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 falsas.
 
	 
	 As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
 
	
	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.
 
	Respondido em 23/03/2021 14:06:55
	
	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.