Teoria da Computação - AV

Prévia do material em texto

21/03/23, 10:58 EPS
https://simulado.estacio.br/alunos/ 1/3
Disciplina: TEORIA DA COMPUTAÇÃO  AV
Aluno: ELVISLAN SANTANA 202103326994
Professor: MAIARA HEIL CANCIAN
 
Turma: 9002
CCT0832_AV_202103326994 (AG)   11/03/2023 17:30:48 (F) 
Avaliação: 3,00 pts Nota SIA: 3,00 pts
O aproveitamento da Avaliação Parcial será considerado apenas para as provas com nota maior ou igual a 4,0.
 
TEORIA DA COMPUTAÇÃO  
 
 1. Ref.: 3555877 Pontos: 1,00  / 1,00
É possível de�nir o conceito de linguagem como:
Uma sequência �nita de símbolos.
Resoluções de problemas envolvendo o processamento de dados.
Qualquer número de símbolos
Um conjunto �nito 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
é:
 Matriz de adjacência
Matriz Inversa
Matriz proporcional
Grafo Euleriano
Grafo Bipartido
 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 
9
 
 7
 5
1
3
 4. Ref.: 3557630 Pontos: 0,00  / 1,00
Um automato �nito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde δ representa 
 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3555877.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3555883.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3556990.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3557630.');
21/03/23, 10:58 EPS
https://simulado.estacio.br/alunos/ 2/3
os simbolos de entrada
o conjunto de estados �nais
 as transições
o estado inicial
 
 O número de estados
 5. Ref.: 3557636 Pontos: 0,00  / 1,00
Considere a seguinte informação de um quintupla de um automato não deterministico
Q = {q0, q1, q2 }
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 ?
3
4
6
 2
 8
 6. Ref.: 3563592 Pontos: 0,00  / 1,00
a operação regular unária é a :
INTERSECÇÃO
 DIFERENÇA
 ESTRELA
CONCATENAÇÃO
 
UNIÃO
 7. Ref.: 3557882 Pontos: 0,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.
Máquina de Estados Finitos
Máquina de Church
 Maquina de Turing
Máquina de Kleene
 
 Maquina de Moore
 8. Ref.: 3557880 Pontos: 0,00  / 1,00
Dentre as teoria dos automatos a mais abrangente é :
A  Lógica Combinacional
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3557636.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3563592.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3557882.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3557880.');
21/03/23, 10:58 EPS
https://simulado.estacio.br/alunos/ 3/3
 A  Máquina de Estados Finitos
 
O  Automato Finito
 A  Maquina de Turing
O  Automato de Pilha
 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.
 
 ccca
 
aaca
 
 aaa
ccac
 
aaaca
 
 10. Ref.: 3557849 Pontos: 0,00  / 1,00
Um problema NP Completo é aquele que :
Pertence a classe de toda as linguagens polinomialmente decidíveis
 
Cresce linearmente em função do volume de dados de entrada
 É resolvido em tempo polinomial
Possui solução computacional possível em um tempo aceitavel
 Não pode ser resolvido em tempo polinomial
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3563164.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3557849.');