AV_Teoriada Computação 2023 - Estacio

Prévia do material em texto

Disciplina: TEORIA DA COMPUTAÇÃO AV
Turma: 9004
 (AG) 15/03/2023 09:01:53 (F) 
Avaliação: 8,00 pts Nota SIA: 9,50 pts
 
TEORIA DA COMPUTAÇÃO 
 
 1. Ref.: 3555877 Pontos: 1,00 / 1,00
É possível de nir o conceito de linguagem como:
Um conjunto nito de símbolos.
Qualquer número de símbolos
Resoluções de problemas envolvendo o processamento de dados.
Uma sequência nita de símbolos.
 Um conjunto de palavras sobre um alfabeto.
 2. Ref.: 3555883 Pontos: 1,00 / 1,00
Se precisarmos representar/armazenar um grafo em um computador, uma das estruturas mas comumentes utilizada
é:
Grafo Bipartido
Grafo Euleriano
Matriz proporcional
 Matriz de adjacência
Matriz Inversa
 3. Ref.: 3556990 Pontos: 0,00 / 1,00
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 arvore é o numero 
3
1
9
 
 7
 5
 4. Ref.: 3557624 Pontos: 0,00 / 1,00
Quanto aos automatos indeterministicos podemos a rmar que:
Não é representado por uma quíntupla
Para todo estado e todo símbolo de entrada sempre há 0 ou 1 transição possível.
24/04/2024, 12:54 EPS
https://ead.estacio.br/alunos/ 1/3
 
 É de nido pela propriedade do determinismo
 É 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
 5. Ref.: 3557634 Pontos: 1,00 / 1,00
Se em um automato nito F for igual a q0 podemos a rmar que:
 
é determinístico.
não aceita a cadeia vazia.
não possui transições.
 aceita a cadeia vazia.
é não determinístico.
 
 6. Ref.: 3563592 Pontos: 1,00 / 1,00
a operação regular unária é a :
INTERSECÇÃO
 ESTRELA
DIFERENÇA
CONCATENAÇÃO
 
UNIÃO
 7. Ref.: 3557882 Pontos: 1,00 / 1,00
O autômato nito determinístico com saídas associadas aos estados, só que nesse caso as saídas são produzidas por
uma função que determina esta saída (podendo também ser vazia) determinando o estado da máquina denomina-se.
 Maquina de Moore
Máquina de Church
Máquina de Estados Finitos
Maquina de Turing
Máquina de Kleene
 
 8. Ref.: 3557880 Pontos: 1,00 / 1,00
Dentre as teoria dos automatos a mais abrangente é :
O Automato Finito
 A Maquina de Turing
A Lógica Combinacional
24/04/2024, 12:54 EPS
https://ead.estacio.br/alunos/ 2/3
O Automato de Pilha
A Máquina de Estados Finitos
 
 9. Ref.: 3563164 Pontos: 1,00 / 1,00
Considere a seguinte gramática G, onde S é o símbolo inicial:
SABA→AcB→cA|aB→cB|aA→ε
Assinale a alternativa que apresenta a palavra que NÃO pertence à linguagem gerada pela gramática G.
 
 aaa
aaaca
 
aaca
 
ccac
 
 ccca
 
 10. Ref.: 3557849 Pontos: 1,00 / 1,00
Um problema NP Completo é aquele que :
Possui solução computacional possível em um tempo aceitavel
É resolvido em tempo polinomial
Pertence a classe de toda as linguagens polinomialmente decidíveis
 
Cresce linearmente em função do volume de dados de entrada
 Não pode ser resolvido em tempo polinomial
24/04/2024, 12:54 EPS
https://ead.estacio.br/alunos/ 3/3
	Página 1
	Página 2
	Página 3