Simulado 01

Prévia do material em texto

5/19/2020 Estácio: Alunos
estacio.webaula.com.br/Classroom/index.html?id=2223314&courseId=13687&classId=1251420&topicId=3083972&p0=03c7c0ace395d80182db07ae2… 1/4
 
 
Disc.: TEORIA DA COMPUTAÇÃO 
Aluno(a): THIAGO UBIRATAN SANTOS DE LIMA 201708337431
Acertos: 4,0 de 10,0 19/05/2020
Acerto: 1,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
 
 MAQUINA DE TURING
AUTOMATOS FINITOS
GRAFO
EXPRESSÕES REGULARES
LINGUAGENS FORMAIS
 
Respondido em 19/05/2020 20:18:05
Acerto: 1,0 / 1,0
Considerando-se os conceitos básicos de grafos e algoritmos em grafos, assinale a alternativa INCORRETA.
 
Grafo trivial: Grafo que possui um único vértice e nenhuma aresta
 
 
Grafo completo: grafo não direcionado, no qual todos os pares de vértices são adjacentes.
 
Vértice: objeto simples que pode ter nome e outros atributos.
 
 Aresta: conexão entre dois grafos
 
Grafo: conjunto de vértices e arestas.
 
Respondido em 19/05/2020 20:13:52
Acerto: 0,0 / 1,0
Ao percorrermos uma arvore se visitamos primeiro a subarvore esquerda estamos no percurso em:
 Questão1
a
 Questão2
a
 Questão3
a
http://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
5/19/2020 Estácio: Alunos
estacio.webaula.com.br/Classroom/index.html?id=2223314&courseId=13687&classId=1251420&topicId=3083972&p0=03c7c0ace395d80182db07ae2… 2/4
Pós Ordem
 Ordem
Pré Ordem
 Ordem Natural
Ordem Central
 
Respondido em 19/05/2020 20:18:29
Acerto: 0,0 / 1,0
Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde Q representa 
 o estado inicial
 
 O número de estados
os simbolos de entrada
o conjunto de estados finais
as transições
Respondido em 19/05/2020 20:18:28
Acerto: 0,0 / 1,0
Constituem um conjunto de linguagens decidíveis bastante simples e com propriedades bem definidas e
compreendidas. Está é uma característica encontrada nos:
Árvores Binária
Autômatos Indeterminados
Autômatos Infinitos
 Grafos
 Autômatos Finitos
Respondido em 19/05/2020 20:19:20
Acerto: 0,0 / 1,0
Uma gramática G é definida por G=({x,y,z},{S,W,X,Y,Z},P,S) na qual os membros de P são
S→WZW→X|YX→x|xXY→y|yYZ→z|zZ
Qual das expressões regulares abaixo corresponde a esta gramática?
xx∗(yy∗|zz∗)
 xx∗|yy∗|zz∗
 
 (xx∗|yy∗)zz∗
 xx∗yy∗zz∗
(xx|yy)∗zz∗
Respondido em 19/05/2020 20:20:32
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.
 Questão4
a
 Questão5
a
 Questão6
a
 Questão7
a
5/19/2020 Estácio: Alunos
estacio.webaula.com.br/Classroom/index.html?id=2223314&courseId=13687&classId=1251420&topicId=3083972&p0=03c7c0ace395d80182db07ae2… 3/4
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, III e V.
 
apenas as afirmativas I, II e IV.
 apenas as afirmativas II, III e V.
 
apenas as afirmativas II e IV.
 
apenas as afirmativas I, II, III e IV.
 
Respondido em 19/05/2020 20:19:30
Acerto: 1,0 / 1,0
No que concerne a utilização e o processamento de máquina de Turing, assinale a opção correta.
 
Uma máquina de Turing pode alterar várias entradas em cada vez, pois ela é capaz de transferir sua
atenção para mais de uma posição da fita em cada argumento da função de transição.
 
 
 Na máquina de Turing, o processamento inclui a sucessiva aplicação da função programada até ocorrer
uma condição de parada. 
A máquina em questão registra o valor da palavra de entrada e depois pára, quando a função indicar um
movimento da cabeça para a esquerda e ela já se encontrar no início da fita. 
O conjunto de símbolos usados pela máquina de Turing é infinito. 
As saídas podem ser apenas binárias, pois as referidas máquinas trabalham com representações lógicas. 
Respondido em 19/05/2020 20:19:25
Acerto: 1,0 / 1,0
Em uma gramática sensível ao contexto definida por G = {V, T, P, S} o P significa?
Conjunto finito de símbolos ou variáveis Não-Terminais
 Regras de produção da forma
Um símbolo especial escolhido aparte de V denominado inicial
Conjunto finito de símbolos terminais DISJUNTOS
Uma palavra ¿final¿, composta dos símbolos terminais
 
Respondido em 19/05/2020 20:19:27
Acerto: 0,0 / 1,0
Analise o custo computacional dos algoritmos a seguir, que calculam o valor de um polinômio de grau n, da forma:
P(x) = an xn+an-1 + xn-1+ ... +a1x + a0, onde os coeficientes são números de ponto flutuante armazenados no
vetor a[0..n], e o valor de n é maior que zero. Todos os coeficientes podem assumir qualquer valor, exceto o
coeficiente an que é diferente de zero.
Algoritmo 1:
soma = a[0]
Repita para i = 1 até n
Se a[i] ≠ 0.0 então
potencia = x
Repita para j = 2 até i
 Questão8
a
 Questão9
a
 Questão10
a
5/19/2020 Estácio: Alunos
estacio.webaula.com.br/Classroom/index.html?id=2223314&courseId=13687&classId=1251420&topicId=3083972&p0=03c7c0ace395d80182db07ae2… 4/4
potencia = potência * x
Fim repita
soma = soma + a[i] * potencia
 Fim se
Fim repita
Imprima (soma)
Algoritmo 2:
soma = a[n]
Repita para i = n-1 até 0 passo -1
soma = soma * x + a[i]
Fim repita
Imprima (soma)
Com base nos algoritmos 1 e 2, avalie as asserções a seguir e a relação proposta entre elas.
I. Os algoritmos possuem a mesma complexidade assintótica.
PORQUE
II. Para o melhor caso, ambos os algoritmos possuem complexidade O(n).
A respeito dessas asserções, assinale a opção correta.
 As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
 A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
As asserções I e II são proposições falsas.
 
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
Respondido em 19/05/2020 20:19:45
javascript:abre_colabore('38403','194346982','3880821759');