Estácio: Alunos

Prévia do material em texto

Disc.: TEORIA DA COMPUTAÇÃO 
Aluno(a): MIGUEL DOS REIS PEREIRA DE ALMEIDA 201902512162
Acertos: 8,0 de 10,0 11/10/2020
Acerto: 0,0 / 1,0
Quando operamos dois conjuntos e retornamos os elementos existentens no primeiro que não existem no
segundo temos a operação
PRODUTO CARTESIANO
 
 DIFERENÇA
INTERSECÇÃO
 UNIÃO
COMPLEMENTO
Respondido em 11/10/2020 14:24:09
Explicação:
a diferença corresponde a operação
A - B = {x | x ∈ A e x ∉ B} 
Ex: Seja A = {0, 1, 2} e B = {2, 3}, então A - B = {0, 1}
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
 
 
 Aresta: conexão entre dois grafos
 
Grafo: conjunto de vértices e arestas.
 
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.
 Questão1
a
 Questão2
a
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
 
Respondido em 11/10/2020 14:23:54
Explicação:
Grafo (graph) é um conjunto de vértices (ou nodos), interconectados dois a dois por arestas (ou arcos). 
 
 A aresta portanto interliga nós e não grafos 
Acerto: 1,0 / 1,0
Complete o seguinte Teorema sobre árvores: "Se todo nó em uma árvore tem uma quantidade finita de
filhos e todo ramo da árvore tem uma quantidade finita de nós, a árvore propriamente dita tem uma
quantidade ........"
 finita de nós.
infinita de folha
infinita de ramo
infinita de nós
finita de ramo
Respondido em 11/10/2020 14:25:05
Explicação:
Como pode ser visto na aula 3 em Percorrendo árvores binárias. 
Acerto: 1,0 / 1,0
Uma das formas de representação do autômato finito indeterminístico mais comum é:
 Diagrama
Símbolo
Conjunto
Matriz
Setas
Respondido em 11/10/2020 14:28:14
Explicação:
.
Acerto: 1,0 / 1,0
Seja um Autômato Finito Não Determinístico (AFN) com 4 estados. 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
considerando-se os estados inúteis?
 
 Questão3
a
 Questão4
a
 Questão5
a
 16
64
32
128
 
8
Respondido em 11/10/2020 14:27:19
Explicação:
 
O cálculo é simples. Basta calcular 2 elevado ao número de estados do AFN: portanto 16 estados
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 11/10/2020 14:29:01
Explicação:
Os símbolos não terminais X, Y e Z produzem, respectivamente, xx∗, yy∗ e zz∗. Além disso, podemos eliminar W
substituindo-o na primeira produção:
SXYZ→(X|Y)Z→xx∗→yy∗→zz∗
Substituindo X, Y e Z na primeira produção, obtemos
Portanto a solução é S→(xx∗|yy∗)zz∗ 
Acerto: 1,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 II e IV.
 
apenas as afirmativas I, II e IV.
apenas as afirmativas II, III e V.
 Questão6
a
 Questão7
a
 
apenas as afirmativas I, II, III e IV.
 
 apenas as afirmativas I, II, III e V.
 
Respondido em 11/10/2020 14:32:29
Explicação:
(A) apenas as afirmativas I, II, III e IV.
(B) apenas as afirmativas II, III e V.
(C) apenas as afirmativas I, II, III e V.
(D) apenas as afirmativas II e IV.
(E) apenas as afirmativas I, II e IV.
Resolução
A única afirmativa falsa é a IV. Autômatos de pilha reconhecem linguagens livres de contexto, enquanto que
autômatos finitos reconhecem linguagens regulares.
Portanto, é impossível simular um autômato de pilha utilizando um autômato finito, pois a classe de linguagens que
esse último reconhece é hierarquicamente inferior.
Além disso, autômatos finitos não possuem memória auxiliar para simular a pilha.
Logo, a alternativa correta é a C.
Acerto: 1,0 / 1,0
No que concerne a utilização e o processamento de máquina de Turing, assinale a opção correta.
 
 Na máquina de Turing, o processamento inclui a sucessiva aplicação da função programada até ocorrer
uma condição de parada. 
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.
 
 
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 11/10/2020 14:30:54
Explicação:
.
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
Conjunto finito de símbolos terminais DISJUNTOS
Uma palavra ¿final¿, composta dos símbolos terminais
 
 Questão8
a
 Questão9
a
 Regras de produção da forma
Um símbolo especial escolhido aparte de V denominado inicial
Respondido em 11/10/2020 14:32:05
Explicação:
V - Conjunto finito de símbolos ou variáveis Não-Terminais, ou seja, são variáveis a serem substituídas por outras
variáveis ou símbolos terminais nos passos de produção das palavras da gramática e nenhum deles deverá aparecer
nas palavras finais da linguagem gerada por ela. 
T -Conjunto finito de símbolos terminais DISJUNTOS , ou seja, que não façam parte de V. Eles são ditos ¿terminais¿
pois são os que farão parte das palavras geradas por essa gramática.
P - Regras de produção da forma: 
S - Um símbolo especial escolhido aparte de V denominado inicial. Este é o símbolo por onde começamos a
substituição das regras de produção.
Acerto: 1,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
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 11/10/2020 14:33:06
Explicação:
Observa-se que o algoritmo 1 contêm dois laços, um externo e um interno, e o algoritmo 1 apresenta 1 laço. O laço
externo doalgoritmo 1 e o laço do algoritmo 2 tem a mesma complexidade, mas a existência de 2 laços no
algoritmo 1 invalida a asserção I. 
 Questão10
a
O algoritmo 1 não necessariamente executa o laço interno, sendo que, no melhor caso, não executa o laço interno
vez alguma. Portanto, a asserção II está correta, e a alternativa D indica esta situação. Pode-se verificar que a
questão não exige que se verifique detalhadamente se os algoritmos realmente calculam o valor do polinômio,
apenas que se analise a complexidade dos algoritmos,o que se reduz a analisar o possível número de iterações dos
mes
javascript:abre_colabore('38403','208704641','4170144627');