AV_TEORIA_COMPUTACAO

Prévia do material em texto

WENDELL DE NAZARE DE JESUS GONCALVES
202203675516
 
Disciplina: TEORIA DA COMPUTAÇÃO AV
Aluno: WENDELL DE NAZARE DE JESUS GONCALVES 202203675516
Professor: JULIANA AUGUSTO CLEMENTI
 Turma: 9001
CCT0832_AV_202203675516 (AG) 17/05/2022 20:44:56 (F) 
 
Avaliação:
8,0
Nota Partic.: Av. Parcial.:
2,0
Nota SIA:
10,0 pts
 
 
TEORIA DA COMPUTAÇÃO 
 
 1. Ref.: 3555877 Pontos: 1,00 / 1,00
É possível definir o conceito de linguagem como:
Um conjunto finito de símbolos.
Resoluções de problemas envolvendo o processamento de dados.
Uma sequência finita de símbolos.
Qualquer número 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 proporcional
Grafo Bipartido
Grafo Euleriano
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
7
1
 5
9
 Educational Performace Solution EPS ® - Alunos 
javascript:voltar();
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('Educational Performace Solution\n\nEPS: M%C3%B3dulo do Aluno\n\nAxiom Consultoria em Tecnologia da Informa%C3%A7%C3%A3o Ltda.')
 
 4. Ref.: 3557621 Pontos: 1,00 / 1,00
O funcionamento do automato é definido pelo(a)
Entrada Realizada
 
Conjunto dos Estados
Ligação da entrada
Conjunto de Saida
 Função de Transição
 
 5. Ref.: 3557636 Pontos: 1,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 ?
 8
2
4
3
6
 
 6. Ref.: 3563592 Pontos: 1,00 / 1,00
a operação regular unária é a :
CONCATENAÇÃO
 
DIFERENÇA
UNIÃO
 ESTRELA
INTERSECÇÃO
 
 7. Ref.: 3557882 Pontos: 1,00 / 1,00
O autômato finito 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 Kleene
 
 Maquina de Moore
Maquina de Turing
Máquina de Estados Finitos
Máquina de Church
 
 8. Ref.: 3557880 Pontos: 1,00 / 1,00
Dentre as teoria dos automatos a mais abrangente é :
Educational Performace Solution EPS ® - Alunos 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3557621.');
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.');
javascript:alert('Educational Performace Solution\n\nEPS: M%C3%B3dulo do Aluno\n\nAxiom Consultoria em Tecnologia da Informa%C3%A7%C3%A3o Ltda.')
 A Maquina de Turing
A Máquina de Estados Finitos
 
A Lógica Combinacional
O Automato de Pilha
O Automato Finito
 
 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
 
aaaca
 
ccac
 
 aaa
 
 10. Ref.: 3557849 Pontos: 0,00 / 1,00
Um problema NP Completo é aquele que :
Possui solução computacional possível em um tempo aceitavel
Pertence a classe de toda as linguagens polinomialmente decidíveis
 
 É resolvido em tempo polinomial
 Não pode ser resolvido em tempo polinomial
Cresce linearmente em função do volume de dados de entrada
 
 
 
Educational Performace Solution EPS ® - Alunos 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3563164.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3557849.');
javascript:alert('Educational Performace Solution\n\nEPS: M%C3%B3dulo do Aluno\n\nAxiom Consultoria em Tecnologia da Informa%C3%A7%C3%A3o Ltda.')