TEORIA DA COMPUTACAO_SIMULADO 1

Prévia do material em texto

Parte superior do formulário
		
	 
	
		
		Meus Simulados
	Teste seu conhecimento acumulado
	
		
		Disc.: TEORIA DA COMPUTAÇÃO   
	
	
	Acertos: 8,0 de 10,0
	19/10/2022
		1a
          Questão 
	Acerto: 1,0  / 1,0 
	
	Quando operamos dois conjuntos e retornamos todos os elementos existentes tanto no primeiro como no segundo conjunto temos  a operação
		
	
	PRODUTO CARTESIANO
 
	
	INTERSECÇÃO
	
	DIFERENÇA
	
	COMPLEMENTO
	
	UNIÃO
	Respondido em 19/10/2022 21:54:26
	
	Explicação: 
a União corresponde a operação A ∪ B = {x | x ∈ A ou x ∈ B}
Ex: Seja A = {0, 1, 2} e B = {2, 3}, então A ∪ B = {0, 1, 2, 3} 
	
		2a
          Questão 
	Acerto: 1,0  / 1,0 
	
	Pode-se defir o conceito de Grafo bipartido como sendo:
		
	
	Grafo que tem um único vértice e nenhuma aresta
	
	Grafo onde seus vértices podem ser divididos em dois conjuntos disjuntos, tais que cada aresta ligue apenas vértices de grupos diferentes. 
	
	Grafo não direcionado
	
	Grafo onde todos os seus vértices têm o mesmo grau
	
	Grafo que tem pesos associados a cada uma de suas arestas.
	Respondido em 19/10/2022 21:56:09
	
	Explicação: 
Um grafo G(V, A) é bipartido quando o seu conjunto de vértices, V, puder ser particionado em dois conjuntos V1 e V2 tais que toda aresta de G tem uma extremidade em V1 e outra em V2.
	
		3a
          Questão 
	Acerto: 0,0  / 1,0 
	
	Considere que uma árvore binária foi criada a partir da inserção de dados na seguinte ordem, Dados = {5, 7, 8, 3, 2, 4, 1, 9}
A raiz da subárvore direita é o número
		
	
	5
	
	7
	
	3
	
	9
	
	1
	Respondido em 19/10/2022 21:57:51
	
	Explicação: 
A raiz será o primeiro valor na subárvore direita, ou seja, o primeiro elemento maior que a raiz que é o 7
	
		4a
          Questão 
	Acerto: 1,0  / 1,0 
	
	Uma das formas de representação do autômato finito indeterminístico mais comum é:
		
	
	Diagrama
	
	Setas
	
	Símbolo
	
	Conjunto
	
	Matriz
	Respondido em 19/10/2022 21:59:24
	
	Explicação: 
.
	
		5a
          Questão 
	Acerto: 0,0  / 1,0 
	
	Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde F representa 
 
		
	
	as transições
	
	os simbolos de entrada
	
	o estado inicial
 
	
	O número de estados
	
	o conjunto de estados finais
	Respondido em 19/10/2022 21:59:47
	
	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}
	
		6a
          Questão 
	Acerto: 1,0  / 1,0 
	
	Seja o alfabeto ∑ constituído das 23 letras {a, b,c ...,z}. Se A= {legal, ruim} e B= {menino, menina} então o resultado de B concatenado A (B.A) será respectivamente:
		
	
	{menino, menina, ruim, legal}
	
	{meninolegal, meninaruim, meninoruim, meninalegal}
	
	{meninolegal, meninalegal, meninoruim meninaruim}
	
	{legal, ruim, menino, menina}
	
	{legal, ruim, legallegal, legalruim, ruimruim, legallegal}
	Respondido em 19/10/2022 22:01:17
	
	Explicação: 
Lembrando que concatenação é uma operação que junta cadeias de um conjunto com cadeias de um outro conjunto. 
	
		7a
          Questão 
	Acerto: 1,0  / 1,0 
	
	Analise as seguintes afirmativas.
I. Todo autômato finito não-determinístico pode ser simulado por um autômato finito determinístico.
II. Todo autômato finito determinístico pode ser simulado por um autômato finito não-determinístico.
III. Todo autômato finito não-determinístico pode ser simulado por um autômato de pilha determinístico.
IV. Todo autômato de pilha determinístico pode ser simulado por um autômato finito não-determinístico.
V. Todo autômato finito não-determinístico pode ser simulado por uma máquina de Turing determinística.
A análise permite concluir que estão CORRETAS
		
	
	apenas as afirmativas I, II, III e IV.
 
	
	apenas as afirmativas II e IV.
 
	
	apenas as afirmativas II, III e V.
 
	
	apenas as afirmativas I, II e IV.
	
	apenas as afirmativas I, II, III e V.
 
	Respondido em 19/10/2022 22:02:10
	
	Explicação: 
(A) apenas as afirmativas I, II, III e IV.
(B) apenas as afirmativas II, III e V.
(C) apenas as afirmativas I, II, III e V.
(D) apenas as afirmativas II e IV.
(E) apenas as afirmativas I, II e IV.
Resolução
A única afirmativa falsa é a IV. Autômatos de pilha reconhecem linguagens livres de contexto, enquanto que autômatos finitos reconhecem linguagens regulares.
Portanto, é impossível simular um autômato de pilha utilizando um autômato finito, pois a classe de linguagens que esse último reconhece é hierarquicamente inferior.
Além disso, autômatos finitos não possuem memória auxiliar para simular a pilha.
Logo, a alternativa correta é a C.
	
		8a
          Questão 
	Acerto: 1,0  / 1,0 
	
	Na máquina de turing o componente que contem o estado corrente da máquina é:
 
		
	
	A unidade de controle
 
	
	A memoria
	
	O processador
	
	A fita
	
	O programa
	Respondido em 19/10/2022 22:02:20
	
	Explicação: 
UNIDADE DE CONTROLE ¿ Contém o estado corrente da máquina, lê ou escreve dados na fita e pode se mover para a ¿frente¿(direita) ou para ¿trás¿(esquerda)
	
		9a
          Questão 
	Acerto: 1,0  / 1,0 
	
	Considere a gramática a seguir, em que S, A e B são símbolos não terminais, 0 e 1 são terminais e ε é a cadeia vazia.
S-> 1S|0A|ε
A-> 1S|0B|ε
B-> 1S|ε
A respeito dessa gramática, analise as afirmações a seguir.
I. Nas cadeias geradas por essa gramática, o último símbolo é 1.
II. O número de zeros consecutivos nas cadeias geradas pela gramática é, no máximo, dois.
III. O número de uns em cada cadeia gerada pela gramática é maior que o número de zeros.
IV. Nas cadeias geradas por essa gramática, todos os uns estão à esquerda de todos os zeros.
É correto apenas o que se afirma em
		
	
	II e IV.
	
	III e IV.
 
	
	I.
	
	II.
	
	I e III.
	Respondido em 19/10/2022 22:03:52
	
	Explicação: 
 É uma questão de fácil resolução a partir da correta aplicação das regras de derivação da gramática para a construção de palavras.
A técnica a ser utilizada para a justificativa de uma alternativa como falsa é a apresentação de um contraexemplo de sequência de derivações que demonstre a falsidade.
A afirmativa I deve ser considerada falsa. O contraexemplo é a geração da palavra-vazia a partir do símbolo inicial S (nota do autor: essa é uma suposição, já que a questão pode ser considerada mal construída já que não informa qual dos símbolos, S, A ou B, é o símbolo inicial).
S => e (aplicação da regra S->e)
A afirmativa II é verdadeira. Considere a seguinte sequência de derivações, na qual W representa uma cadeia de símbolos terminais. A derivação demonstra as duas únicas regras que podem ser aplicadas a qualquer momento para remover o símbolo terminal B da palavra sendo gerada, de forma que número de zeros consecutivos será sempre no máximo dois.
S =>* W0A
 => W00B (Aplicação da regra S->0B é a única que gera zeros seguidos.)
 => W001S (Aplicação da regra B->1S.)
 ou
 => W00 (Aplicação da regra B->e.)
A afirmativa III é trivialmente falsa, já que a palavra-vazia pertence ao conjunto de palavras da linguagem gerada pela gramática apresentada. Ou seja, a quantidade zero de símbolos uns e zeros torna a afirmativa falsa. A seguinte sequência de derivações é o contraexemplo que justifica a afirmativa.
S => e (aplicação da regra S->e)
A afirmativa IV deve ser considerada falsa, pois é possível gerar a palavra 01 (na qual uns aparecem à direita de zeros) a partir da seguinte sequência de derivações do contraexemplo.
S => 0A (Aplicação da regra S->0A.)
S => 01S (Aplicação da regra A->1S.)
S => 01 (Aplicaçãoda regra S->e.)
	
		10a
          Questão 
	Acerto: 1,0  / 1,0 
	
	Qual das complexidades abaixo é a menor?
		
	
	O (n2)
	
	O (n)
	
	O (2n)
	
	O(log n)
	
	O (n3)
	Respondido em 19/10/2022 22:06:05
	
	Explicação: 
A menor complexidade é a linear
	
	
Parte inferior do formulário