Teoria da Computação - AVP02

Prévia do material em texto

04/06/2020 Estácio: Alunos
simulado.estacio.br/alunos/ 1/4
 
 
Disc.: TEORIA DA COMPUTAÇÃO 
Aluno(a): JOSEILDON DA SILVA DANTAS 201908040459
Acertos: 3,0 de 10,0 04/06/2020
Acerto: 0,0 / 1,0
O modelo de computador, com fundamentos lógicos em seu funcionamento onde é feita a análise de
computação combinação e extensões denomina-se
 
 GRAFO
LINGUAGENS FORMAIS
 
 MAQUINA DE TURING
AUTOMATOS FINITOS
EXPRESSÕES REGULARES
Respondido em 04/06/2020 10:17:03
Acerto: 0,0 / 1,0
"Um conjunto de pontos com linhas conectando alguns dos pontos, na qual os pontos são chamados nós ou
vértices , e as linhas são chamadas arestas". Esse conceito é a definição de:
 Árvore
Arestas
 Grafos
Caminho direcionado.
Algoritmo
Respondido em 04/06/2020 10:16:46
Acerto: 1,0 / 1,0
Ao percorrermos uma arvore se visitamos por ultimo o centro estamos no percurso
 Pós Ordem
Ordem Natural
Pré Ordem
Ordem
Ordem Central
 
Respondido em 04/06/2020 10:16:47
 Questão1
a
 Questão2
a
 Questão3
a
http://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
04/06/2020 Estácio: Alunos
simulado.estacio.br/alunos/ 2/4
Acerto: 0,0 / 1,0
Os movimentos realizado pelos automatos finitos constituem :
 Os dados representados
O estado final 
 
O controle
 O conjunto de transições
O conjunto de estados
Respondido em 04/06/2020 10:16:49
Acerto: 1,0 / 1,0
A definição formal diz que um autômato finito é uma lista de cinco objetos: conjunto de estados, alfabeto de
entrada, regras para movimentação, estado inicial, e estados de aceitação. Essa lista de cinco elementos é
frequentemente chamada:
 quíntupla
Array
Five elements
Autômato quinto
Mapeamento
Respondido em 04/06/2020 10:16:51
Acerto: 0,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}
{meninolegal, meninaruim, meninoruim, meninalegal}
 {meninolegal, meninalegal, meninoruim meninaruim}
{legal, ruim, menino, menina}
{menino, menina, ruim, legal}
Respondido em 04/06/2020 10:17:11
Acerto: 0,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 I, II e IV.
 apenas as afirmativas I, II, III e V.
 
apenas as afirmativas II, III e V.
apenas as afirmativas II e IV.
apenas as afirmativas I, II, III e IV.
Respondido em 04/06/2020 10:17:12
Acerto: 1,0 / 1,0
 Questão4
a
 Questão5
a
 Questão6
a
 Questão7
a
 Questão8
a
04/06/2020 Estácio: Alunos
simulado.estacio.br/alunos/ 3/4
Na máquina de turing o componente que contem o estado corrente da máquina é:
 
 A unidade de controle
 
A fita
O programa
A memoria
O processador
Respondido em 04/06/2020 10:17:14
Acerto: 0,0 / 1,0
A gramática dada pelos descritores abaixo é:
G= 
N={S,A}
T={0,1} e P é o conjunto de produções
{S → 0S 1A 01ε e A → 0S 1A 0}
 Uma gramática do tipo 0 que não é gramática sensível a contexto.
Uma gramática livre de contexto que não é gramática regular
Uma gramática sem categorização possível e que gera a coleção das palíndromas em {0,1}
exclusivamente de tamanho par.
 
 Uma gramática regular. 
Uma gramática sensível a contexto que não é gramática livre de contexto
Respondido em 04/06/2020 10:17:15
Acerto: 0,0 / 1,0
Considere o processo de fabricação de um produto siderúrgico que necessita passar por n tratamentos
térmicos e químicos para ficar pronto. Cada uma das n etapas de tratamento é realizada uma única vez na
mesma caldeira. Além do custo próprio de cada etapa do tratamento, existe o custo de se passar de uma
etapa para a outra, uma vez que, dependendo da sequência escolhida, pode ser necessário alterar a
temperatura da caldeira e limpá-la para evitar a reação entre os produtos químicos utilizados. Assuma que o
processo de fabricação
inicia e termina com a caldeira limpa. Deseja-se projetar um algoritmo para indicar a sequência de
tratamentos que possibilite fabricar o produto com o menor custo total. Nesta situação, conclui-se que
 
 A solução do problema é obtida em tempo de ordem O(nlogn), utilizando um algoritmo ótimo de
ordenação.
 
O problema se reduz a encontrar a árvore geradora mínima para o conjunto de etapas do processo,
requerendo tempo de ordem polinomial para ser solucionado.
 
A utilização do algoritmo de Dijkstra para se determinar o caminho de custo mínimo entre o estado
inicial e o final soluciona o problema em tempo polinomial.
 
 Qualquer algoritmo conhecido para a solução do problema descrito possui ordem de complexidade de
tempo não-polinomial, uma vez que o problema do caixeiro viajante se reduz a ele.
 
Uma heurística para a solução do problema de coloração de grafos solucionará o problema em tempo
polinomial.
 
Respondido em 04/06/2020 10:17:17
 Questão9
a
 Questão10
a
javascript:abre_colabore('38403','198509668','3985880038');
04/06/2020 Estácio: Alunos
simulado.estacio.br/alunos/ 4/4