SIMULADO 1_TEORIA DA COMPUTAÇÃO

Prévia do material em texto

16/04/2023, 12:30 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=306271019&cod_prova=6185824158&f_cod_disc= 1/6
 
Meus
Simulados
Teste seu conhecimento acumulado
Disc.: TEORIA DA COMPUTAÇÃO   
Aluno(a): JUCELINO COSTA DE OLIVEIRA 202107065796
Acertos: 8,0 de 10,0 16/04/2023
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
            
LINGUAGENS FORMAIS
 
EXPRESSÕES REGULARES
 MAQUINA DE TURING
GRAFO
AUTOMATOS FINITOS
Respondido em 16/04/2023 12:17:34
Explicação:
Máquina de Turing é um modelo de computador, com fundamentos lógicos em seu funcionamento. Em máquinas de
Turing é feita a análise de computação, combinação e extensões das Máquinas de Turing e ao �nal Máquinas de Turing
não-deterministas
Acerto: 1,0  / 1,0
É uma noção simples, abstrata e intuitiva, usada para representar a ideia de alguma espécie de relação entre os
objetos. Gra�camente, aparece representado por uma �gura com nós ou vértices. Trata-se dos
registros.
 
triângulos.
dados.
 grafos.
objetos geométricos.
Respondido em 16/04/2023 12:14:55
 Questão1
a
 Questão2
a
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
16/04/2023, 12:30 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=306271019&cod_prova=6185824158&f_cod_disc= 2/6
Explicação:
Grafo (graph) é um conjunto de vértices (ou nodos), interconectados dois a dois por arestas (ou arcos). 
Acerto: 0,0  / 1,0
Considere que uma árvore binária foi criada a partir da inserção de dados na seguinte ordem, Dados = { 5, 7, 8, 3,
2, 4, 1, 9}
A raiz da subárvore esquerda é o número
 7
5
1
 3
9
Respondido em 16/04/2023 12:19:00
Explicação:
A raiz será o primeiro valor na subárvore esquerda, ou seja, o primeiro elemento menor que a raiz que é o 3
Acerto: 1,0  / 1,0
Quanto aos automatos deterministicos podemos a�rmar que:
Pode estar em muitos estados ao mesmo tempo.
É um autômato que permite zero, uma ou mais transições a partir de um estado e para um mesmo
símbolo de entrada.
Para todo estado e todo símbolo de entrada sempre há 0 ou 1 ou n transições possíveis.
Não  é representado por uma quíntupla
 Para cada estado e para cada entrada só há zero ou uma transição possível
 
Respondido em 16/04/2023 12:22:31
Explicação:
Um autômato �nito determinístico é um autômato onde para cada estado e para cada entrada só há zero ou uma
transição possível
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?
 
32
 Questão3
a
 Questão4
a
 Questão5
a
16/04/2023, 12:30 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=306271019&cod_prova=6185824158&f_cod_disc= 3/6
 16
128
 
64
8
Respondido em 16/04/2023 12:23:25
Explicação:
O cálculo é simples. Basta calcular 2 elevado ao número de estados do AFN: portanto 16 estados
Acerto: 1,0  / 1,0
Uma gramática G é de�nida 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 16/04/2023 12:24:37
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
Seja a seguinte linguagem, onde ϵ representa a sentença vazia
SABCD→AB|CD→a|ϵ→b|f→c|g→h|i
Qual o conjunto de terminais que podem começar sentenças derivadas de S?
{a,b,f}
{a,b,f,c,g,h,i}
 
{a,c,g}
 {a,b,f,c,g}
 
{a,c,g,h,i}
 
 Questão6
a
 Questão7
a
16/04/2023, 12:30 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=306271019&cod_prova=6185824158&f_cod_disc= 4/6
Respondido em 16/04/2023 12:28:56
Explicação:
(A) {a,c,g}
(B) {a,b,f,c,g}
(C) {a,b,f,c,g,h,i}
(D) {a,c,g,h,i}
(E) {a,b,f}
Resolução
Na prática, o enunciado solicita o conjunto FIRST de S.
Todos os terminais que iniciam sentenças produzidas pelos não terminais A e C fazem parte do conjunto: {a,c,g}. Como
A produz a cadeia vazia, então devemos também incluir os não terminais que iniciam sentenças produzidas pelo não
terminal B: {b,f}.
Unindo os conjuntos, temos: {a,b,c,f,g}. Portanto, a alternativa correta é a B.
Acerto: 1,0  / 1,0
O problema da parada para máquinas de Turing, ou simplesmente problema da parada, pode ser assim descrito:
determinar, para quaisquer máquinas de Turing M e palavra w, se M irá eventualmente parar com entrada w.
Mais informalmente, o mesmo problema também pode ser assim descrito: dados um algoritmo e uma entrada
�nita, decidir se o algoritmo termina ou se executará inde�nidamente.
Para o problema da parada, 
existe algoritmo exato de tempo de execução exponencial para solucioná-lo.
 
 não existe algoritmo que o solucione, não importa quanto tempo seja disponibilizado.
 
existe algoritmo exato de tempo de execução polinomial para solucioná-lo.
 
 não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução polinomial que
o soluciona, fornecendo respostas aproximadas.
 
 não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução exponencial
que o soluciona, fornecendo respostas aproximadas.
 
Respondido em 16/04/2023 12:26:23
Explicação:
O problema da parada pode ser de�nido como:
Seja S o conjunto de todos os pares (A,D), em que A é um algoritmo, e D, dado de entrada; (A,D) tem a propriedade P se
o algoritmo A, quando recebe o dado D, eventualmente produz um resultado (ou seja, eventualmente para) A tese de
Church-Turing mostra que o problema da parada é não decidível, ou seja, não existe um algoritmo H tal que para todo
(A,D) que pertence à S: H(A,D)= { 1 se A(D) eventualmente para; 
0 caso contrário 
A prova informal de que tal H não existe é obtida por contradição.
Suponha que H existe. Seja C o algoritmo: ¿entrada A; executa H(A,A); se H(A,A)=0, então, retorna 1, senão entra em
loop¿.
Então, ∀A,(H(A,A)=0 ⇿ ¬A(A) eventualmente para ⇿ H(A,A)=0) (pois H é função total) e ∀A,(H(A,A)=0 ⇿ ¬A(A)
eventualmente para).
Tomando A como sendo C, obtemos que C(C) eventualmente para, se e somente se ¬C(C) eventualmente para, e isto é
uma contradição!
Logo, não existe um algoritmo que solucione o problema.
 Questão8
a
16/04/2023, 12:30 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=306271019&cod_prova=6185824158&f_cod_disc= 5/6
As respostas das alternativas A e B não estão corretas, pois a�rmam que existe um algoritmo que resolve o problema.
As respostas das alternativas D e E não estão corretas, pois a�rmam que existe um algoritmo de aproximação e, pelo
exposto na justi�cativa da resposta correta, tal algoritmo não existe.
Acerto: 0,0  / 1,0
Em uma gramática sensível ao contexto de�nida por  G = {V, T, P, S} o que  T signi�ca?
Conjunto �nito de símbolos ou variáveis Não-Terminais
Um símbolo especial escolhido aparte de V denominado inicial
Uma palavra ¿�nal¿, composta dos símbolos terminais
 
 Regras de produção da forma
 Conjunto �nito de símbolos terminais DISJUNTOS
Respondido em 16/04/2023 12:27:12
Explicação:
V - Conjunto �nito 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 �nais da linguagem gerada por ela.T -Conjunto �nito 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 coe�cientes são números de ponto �utuante
armazenados no vetor a[0..n], e o valor de n é maior que zero. Todos os coe�cientes podem assumir qualquer
valor, exceto o coe�ciente 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.
 Questão9
a
 Questão10
a
16/04/2023, 12:30 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=306271019&cod_prova=6185824158&f_cod_disc= 6/6
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, e a II é uma justi�cativa 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, mas a II não é uma justi�cativa 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 16/04/2023 12:27:43
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 do algoritmo 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. 
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 veri�car que a questão não
exige que se veri�que 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