TEORIA DA COMPUTAÇÃO

Prévia do material em texto

Simulado AV
Teste seu conhecimento acumulado
 
Disc.: TEORIA DA COMPUTAÇÃO 
Aluno(a): ALBENIDES FERNANDES DE LIMA 201901298426
Acertos: 8,0 de 10,0 05/11/2021
 
 
Acerto: 1,0 / 1,0
Um grafo é:
Um conjunto de arestas interligadas por nós
 
Apenas um conjunto de arestas
Um conjunto de nós e de arestas disjuntos
 Um conjunto de nós interligados por arestas
Apenas um conjunto de no.
Respondido em 05/11/2021 18:18:09
 
 
Explicação:
Grafos são um conjunto de vértices (ou nós), interconectados dois a dois por arestas. 
 
 
Acerto: 1,0 / 1,0
Um grafo consiste num conjunto de nós (ou vértices) e num conjunto de arcos (ou arestas). É correto afirmar
que o grau de um nó é
a posição deste nó em relação ao nó raiz do grafo
 o número de arcos incidentes nesse nó.
o número de pares ordenados que formam o arco.
 
a distância entre este nó e um outro nó qualquer do grafo.
 um número associado ao arco, também chamado de peso.
Respondido em 05/11/2021 18:20:31
 
 
Explicação:
O grau de um grafo indica o número de arestas que conectam um vértice do grafo a outros vértices, ou seja,
número de vizinhos que aquele vértice possui no grafo (que chegam ou partem dele). Para grafos direcionados
são indicados dois tipos de grau, grau de entrada (número de arestas que chegam ao vértice) e grau de saída
(número de arestas que partem do vértice
 Questão1
a
 Questão2
a
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
 
 
Acerto: 0,0 / 1,0
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 subarvore esquerda arvore é o numero 
1
5
9
 
 3
 7
Respondido em 05/11/2021 18:22:06
 
 
Explicação:
A raiz será o primeiro valor na subarvore direita, ou seja maior que a raiz que é o 7
 
 
Acerto: 1,0 / 1,0
Um autômato finito determinístico , também chamado máquina de estados finita determinística (AFD), é uma
Máquina de estados finita que aceita ou rejeita cadeias de símbolos gerando um único ramo de computação
para cada cadeia de entrada. É uma de suas propriedades:
Contém diversos números infinito de estados
Há tabelas de transição
 Para todo estado e todo símbolo de entrada sempre há zero ou uma transição possível.
Suas transições são incompletas
Para todo estado e todo símbolo de entrada sempre há zero ou uma ou n transições possíveis.
Respondido em 05/11/2021 18:24:58
 
 
Explicação:
Um autômato finito tem um conjunto de estados, alguns dos quais são denominados estados finais. À medida
que caracteres da string de entrada são lidos, o controle da máquina passa de um estado a outro, segundo um
conjunto de regras de transição especificadas para o autômato.
 
 
Acerto: 0,0 / 1,0
Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde q0 representa 
 
as transições
 o estado inicial
 
 os simbolos de entrada
o conjunto de estados finais
O número de estados
Respondido em 05/11/2021 18:26:37
 Questão3
a
 Questão4
a
 Questão5
a
 
 
Explicação:
Seguindo a propriedade de um autômato finito que é representado por uma quíntupla (Q, Ʃ, δ, q0, F):
 Q = número de estados = {q0, q1, q2, q3}
 Ʃ = símbolos de entrada = {0,1}
 δ = transições = 
 δ (q0, 0) = q2
 δ (q0, 1) = q1
 δ (q1, 0) = q3
 δ (q1, 1) = q0
 δ (q2, 0) = q0
 δ (q2, 1) = q3
 δ (q3, 0) = não possui = Ø (vazio)
 δ (q3, 1) = q2
 q0 = estado inicial = {q0}
 F = conjunto de estados finais = {q0}
 
 
Acerto: 1,0 / 1,0
Considere as seguintes expressões regulares cujo alfabeto é {a,b}.
 R1 = a(a ∪ b)*
 R2 = b(a ∪ b)*
Se L(R) é uma linguagem associada a uma expressão regular R, é correto afirmar que
 
 
Se R3 é uma expressão regular tal que L(R3) = L(R1) ∩ L(R2), então L(R3) é uma linguagem
infinita.2). 
 Existe um autômato finito determinístico cuja linguagem é igual a L(R1) ∪ L(R2).
Um autômato finito não determinístico que reconheça L(R1) ∪ L(R2) tem, pelo menos, quatro estados.
 
 
L(R2) = {w | w termina com b}
L(R1) = L(r2) 
Respondido em 05/11/2021 18:29:29
 
 
Explicação:
linguagem L(R1) é composta das palavras ou sequências que iniciam com ¿a¿ e a linguagem L(R2) é composta
das palavras ou sequências que iniciam com ¿b¿. Note que a expressão regular (a ∪ b)* gera qualquer
sequência de a´s e b´s. 
Logo, L(R2) não termina com b necessariamente. Sabemos ainda que a união de L(R1) e L(R2) são todas as
palavras que comecem com ¿a¿ ou com ¿b¿, ou seja qualquer palavra sobre o alfabeto, exceto a palavra vazia.
Este AFD pode ser representado com dois estados apenas. Portanto, resta apenas a alternativa C, e como
afirmado anteriormente, um AFD de dois estados reconhece L(R1) ∪ L(R
 
 
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,c,g,h,i}
 
{a,c,g}
{a,b,f}
{a,c,g,h,i}
 Questão6
a
 Questão7
a
 
 {a,b,f,c,g}
 
Respondido em 05/11/2021 18:31:26
 
 
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
No que concerne a utilização e o processamento de máquina de Turing, assinale a opção correta.
 
As saídas podem ser apenas binárias, pois as referidas máquinas trabalham com representações
lógicas. 
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. 
 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.
 
 
Respondido em 05/11/2021 20:00:22
 
 
Explicação:
.
 
 
Acerto: 1,0 / 1,0
Considere a gramática G definida pelas regras de produção abaixo, em que os símbolos não-terminais são S, A
e B, e os símbolos terminais são a e b. 
S -> AB
AB -> AAB
A -> a
B -> b
Com relação a essa gramática, é correto afirmar que
a gramática G é uma gramática livre de contexto.
 é possível encontrar uma gramática regular equivalente a G.
a gramática G gera a cadeia nula.. 
a cadeia aabbb é gerada por essa gramática.
a gramática G é ambígua.
Respondido em 05/11/2021 20:03:53
 Questão8
a
 Questão9
a
 
 
Explicação:
Quanto ao tipo da gramática, ela não é livre de contexto (alternativa B), pois uma das regras, a segunda, tem
dois símbolos do lado esquerdo. 
As alternativas C e E estão incorretas porque nem a sentença nula, nem a sentença aabbb têm o formato aa*b
(note que as sentenças da linguagem têm exatamente um b)
 
 
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-1até 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.
 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 verdadeiras, mas a II não é uma justificativa correta da I.
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
As asserções I e II são proposições falsas.
 
Respondido em 05/11/2021 20:06:07
 
 
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 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
 
 
 
 Questão10
a
 
 
 
 
 
 
 
 
javascript:abre_colabore('38403','271496034','4965556571');