TEORIA DA COMPUTAÇÃO

Prévia do material em texto

Disciplina: TEORIA DA COMPUTAÇÃO 
	AV
	
	
	Professor: 
	Turma: 9001
	CC_AV (AG) 
	 11/06/2022 18:44:37 (F) 
			Avaliação:
8,0
	Nota SIA:
10,0 pts
	 
		
	TEORIA DA COMPUTAÇÃO
	 
	 
	 1.
	Ref.: 3556770
	Pontos: 1,00  / 1,00
	
	O componente da teoria da computação que é utilizado para modelar redes de transporte é o:
		
	
	AUTOMATOS FINITOS
	 
	GRAFO
	
	MAQUINA DE TURING
 
	
	LINGUAGEM REGULAR
	
	EXPRESSÕES REGULARES
	
	
	 2.
	Ref.: 3555879
	Pontos: 1,00  / 1,00
	
	"Grafo onde todos os seus vértices têm o mesmo grau". Esta é uma característica de qual tipo de grafo? 
		
	
	Grafo Simples
	
	Grafo Ponderado
	 
	Grafo Regular
	
	Grafo Completo
	
	Grafo Trivial
	
	
	 3.
	Ref.: 3555933
	Pontos: 1,00  / 1,00
	
	Trantando-se de propriedade em árvores, a maior distância entre qualquer par de vértices é denominado:
		
	
	Raio
	
	Centro
	 
	Diâmetro
	
	Base
	
	Raiz
	
	
	 4.
	Ref.: 3557624
	Pontos: 1,00  / 1,00
	
	Quanto aos automatos indeterministicos 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 todo estado e todo símbolo de entrada sempre há 0 ou 1  transição possível.
 
	
	Não  é representado por uma quíntupla
	
	É definido pela propriedade do determinismo
	
	Para todo estado e todo símbolo de entrada sempre há 0 ou 1 transição possível
	
	
	 5.
	Ref.: 3555971
	Pontos: 1,00  / 1,00
	
	Seja um autômato finito não determinístico com 6 estados. Aplicando o algorítmo de conversão para um autômato finito determinístico, em quantos estados, no máximo, resultaria os autômato finito determinístico considerando os estados inúteis?
		
	
	46656
	
	12
	
	1024
	 
	64
	
	36
	
	
	 6.
	Ref.: 3556159
	Pontos: 0,00  / 1,00
	
	A operação (0 ∪ 1) 0* é chamada de:
		
	
	Expressão Algébrica
	 
	Expressão Linear
	
	Expressão Finita
	
	Expressão Aritmética
	 
	Expressão Regular
	
	
	 7.
	Ref.: 3556234
	Pontos: 0,00  / 1,00
	
	Como é comumente chamada a  sequência de substituições para se obter uma cadeia?
		
	 
	Integralidade
	
	Variável
	
	Regra de substituição
	 
	Derivação
	
	Cadeia de variável inicial
	
	
	 8.
	Ref.: 3557877
	Pontos: 1,00  / 1,00
	
	Um máquina de turing é composta de:
		
	
	Mémoria , Processador e Instruções
 
	
	Unidade de controle de Programa
	
	Fita e Programa
	
	Memoria e Unidade de Controle
	 
	Fita, Unidade de Controle e Programa
	
	
	 9.
	Ref.: 3557858
	Pontos: 1,00  / 1,00
	
	Em uma gramática sensível ao contexto definida por  G = {V, T, P, S} o que  S significa?
		
	
	Conjunto finito de símbolos ou variáveis Não-Terminais
	
	Conjunto finito de símbolos terminais DISJUNTOS
	
	Regras de produção da forma
	
	Uma palavra ¿final¿, composta dos símbolos terminais
 
	 
	Um símbolo especial escolhido aparte de V denominado inicial
	
	
	 10.
	Ref.: 3557847
	Pontos: 1,00  / 1,00
	
	Um algoritmo com complexidade  O(n) significa que ele possui:
		
	
	complexidade neperiana
 
	 
	complexidade linear
	
	complexidade logaritmica
	
	complexidade natural
	
	complexidade exponencial