TEORIA DA COMPUTAÇÃO

Prévia do material em texto

Disc.: TEORIA DA COMPUTAÇÃO   
	Aluno(a): 
	
	Acertos: 10,0 de 10,0
	27/04/2022
		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:
		
	
	aRb e bRc, então aRc
	
	aRb, então bRa 
	 
	Para todo a ∈ A, aRa
	
	aRb e bRa, então a≠b
	
	aRb e bRa, então a=b
	Respondido em 27/04/2022 22: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
	
	Um grafo consiste num conjunto de nós (ou vértices) e num conjunto de arcos (ou arestas). É correto afirmar que o grau de um nó é
		
	
	o número de pares ordenados que formam o arco.
 
	
	 um número associado ao arco, também chamado de peso.
	 
	 o número de arcos incidentes nesse nó.
	
	a distância entre este nó e um outro nó qualquer do grafo.
	
	a posição deste nó em relação ao nó raiz do grafo
	Respondido em 27/04/2022 23:01:38
	
	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
	
	Complete o seguinte Teorema sobre árvores: "Se todo nó em uma árvore tem uma quantidade finita de filhos e todo ramo da árvore tem uma quantidade finita de nós, a árvore propriamente dita tem uma quantidade ........"
		
	
	infinita de nós
	
	finita de ramo
	 
	finita de nós.
	
	infinita de ramo
	
	infinita de folha
	Respondido em 27/04/2022 23:02:59
	
	Explicação:
Como pode ser visto na aula 3 em Percorrendo árvores binárias. 
	
		4a
          Questão
	Acerto: 1,0  / 1,0
	
	Quanto aos automatos deterministicos podemos afirmar que:
		
	
	É um autômato que permite zero, uma ou mais transições a partir de um estado e para um mesmo símbolo de entrada.
	 
	Para cada estado e para cada entrada só há zero ou uma transição possível
 
	
	Não  é representado por uma quíntupla
	
	Pode estar em muitos estados ao mesmo tempo.
	
	Para todo estado e todo símbolo de entrada sempre há 0 ou 1 ou n transições possíveis.
	Respondido em 27/04/2022 23:09:26
	
	Explicação:
Um autômato finito determinístico é um autômato onde para cada estado e para cada entrada só há zero ou uma transição possível
	
		5a
          Questão
	Acerto: 1,0  / 1,0
	
	Seja um Autômato Finito Não Determinístico (AFN) com 4 estados. Aplicando-se o algoritmo de conversão de um AFN para um Autômato Finito Determinístico (AFD), em quantos estados, no máximo, resultaria o AFD considerando-se os estados inúteis?
 
		
	 
	16
	
	8
	
	64
	
	128
 
	
	32
	Respondido em 27/04/2022 23:07:37
	
	Explicação:
O cálculo é simples. Basta calcular 2 elevado ao número de estados do AFN: portanto 16 estados
	
		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:
		
	
	{legal, ruim, legallegal, legalruim, ruimruim, legallegal}
	
	{menino, menina, ruim, legal}
	
	{legal, ruim, menino, menina}
	 
	{meninolegal, meninalegal, meninoruim meninaruim}
	
	{meninolegal, meninaruim, meninoruim, meninalegal}
	Respondido em 27/04/2022 23:23:36
	
	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 II e IV.
	
	apenas as afirmativas I, II, III e IV.
	 
	 apenas as afirmativas I, II, III e V.
 
	
	apenas as afirmativas I, II e IV.
	
	apenas as afirmativas II, III e V.
	Respondido em 27/04/2022 23:11:22
	
	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
	
	Correlacionando a hierarquia de Chomsky com os reconhecedores de linguagem, é correto afirmar que a máquina de Turing, tradicional ou básica, corresponde às gramáticas
		
	
	sensíveis ao contexto. 
	 
	sem restrição.
 
	
	livres do contexto. 
	
	regulares. 
	
	irregulares. 
	Respondido em 27/04/2022 23:17:30
	
	Explicação:
A MAQUINA DE TURING CORRESPONDE A GRAMATICAS SEM RESTRIÇÕES
	
		9a
          Questão
	Acerto: 1,0  / 1,0
	
	Um método mais poderoso de descrever linguagens que podem descrever certas características que têm uma estrutura recursiva o que as torna úteis em uma variedade de aplicações. O texto refere-se a:
		
	
	Autômatos infinitos
	
	Pilha
	 
	Gramáticas livres-do-contexto
	
	Autômatos finitos
	
	Expressões regulares
	Respondido em 27/04/2022 23:15:26
	
	Explicação:
Conforme visto na aula 9, o ponto principal das gramáticas sensíveis ao contexto é que suas regras de produção não são independentes de uma pré-existência de condições da palavra que está sendo reconhecida.
	
		10a
          Questão
	Acerto: 1,0  / 1,0
	
	Qual das complexidades abaixo é a menor?
		
	 
	O (n)
	
	O (n2)
	
	O (n3)
	
	O (2n)
	
	O(log n)
	Respondido em 27/04/2022 23:12:54
	
	Explicação:
A menor complexidade é a linear