SIMULADO 3_TEORIA DA COMPUTAÇÃO

Prévia do material em texto

17/04/2023, 22:06 Estácio: Alunos
https://simulado.estacio.br/alunos/ 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 17/04/2023
Acerto: 0,0  / 1,0
Quando operamos dois conjuntos e retornamos todos os elementos existentes tanto no primeiro como no
segundo conjunto temos  a operação
COMPLEMENTO
 DIFERENÇA
 UNIÃO
INTERSECÇÃO
PRODUTO CARTESIANO
 
Respondido em 17/04/2023 20:55:19
Explicação:
a União corresponde a operação A ∪ B = {x | x ∈ A ou x ∈ B}
Ex: Seja A = {0, 1, 2} e B = {2, 3}, então A ∪ B = {0, 1, 2, 3} 
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: conjunto de vértices e arestas.
 
 Aresta: conexão entre dois grafos
 
Vértice: objeto simples que pode ter nome e outros atributos.
 
Grafo completo: grafo não direcionado, no qual todos os pares de vértices são adjacentes.
 
Respondido em 17/04/2023 20:55:56
 Questão1
a
 Questão2
a
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
17/04/2023, 22:06 Estácio: Alunos
https://simulado.estacio.br/alunos/ 2/6
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
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 direita é o número
9
1
3
5
 7
Respondido em 17/04/2023 20:56:22
Explicação:
A raiz será o primeiro valor na subárvore direita, ou seja, o primeiro elemento maior que a raiz que é o 7
Acerto: 1,0  / 1,0
Um automato �nito é representado por um quintupla (Q, Ʃ, δ, q0, F)  onde Ʃ representa 
o conjunto de estados �nais
o estado inicial
 
 os simbolos de entrada
as transições
O número de estados
Respondido em 17/04/2023 20:56:53
Explicação:
Seguindo a propriedade de um autômato �nito 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 �nais = {q0}
 Questão3
a
 Questão4
a
17/04/2023, 22:06 Estácio: Alunos
https://simulado.estacio.br/alunos/ 3/6
Acerto: 1,0  / 1,0
Se o estado inicial for também estado �nal em um autômato �nito, então esse autômato
é não determinístico.
 
 aceita a cadeia vazia.
não tem outros estados �nais.
não aceita a cadeia vazia.
é determinístico.
Respondido em 17/04/2023 20:57:05
Explicação:
Quando o estado inicial também é �nal num AF, então ele aceita a cadeia vazia. 
Acerto: 1,0  / 1,0
Considere as seguintes a�rmações sobre autômatos �nitos e expressões regulares:
I A classe de linguagens aceita por um Autômato Finito Determinístico (AFD) não é a mesma que um Autômato
Finito Não Determinístico (AFND).
II Para algumas expressões regulares não é possível construir um AFD.
III A expressão regular (b+ba)+ aceita os "strings" de b's e a's começando com b e não tendo dois a's
consecutivos.
Selecione a a�rmativa correta:
As a�rmativas I e III são verdadeiras
 
 Apenas a a�rmativa III é verdadeira
As a�rmativas I e III são falsas
As a�rmativas II e III são falsas
As a�rmativas I e II são verdadeiras
Respondido em 17/04/2023 20:57:29
Explicação:
A primeira a�rmação é falsa porque AFDs e AFNDs reconhecem a mesma classe de linguagens (linguagens regulares).
Além disso, essas duas classes de autômatos são equivalentes.
A a�rmativa II também é falsa. Toda expressão regular representa uma linguagem regular que, consequentemente, é
reconhecida por um AFD. Logo, é sempre possível construir um AFD para uma expressão regular.
A a�rmativa III está correta. O único problema é a notação utilizada na expressão regular, que causa confusão. A ER
pode ser escrita da seguinte forma: (b|ba)+. Observe que toda cadeia reconhecida pela ER inicia com b e que não é
possível ter dois a's consecutivos.
Acerto: 0,0  / 1,0
 Questão5
a
 Questão6
a
 Questão7
a
17/04/2023, 22:06 Estácio: Alunos
https://simulado.estacio.br/alunos/ 4/6
Analise as seguintes a�rmativas.I. Todo autômato �nito não-determinístico pode ser simulado por um autômato
�nito determinístico.
II. Todo autômato �nito determinístico pode ser simulado por um autômato �nito não-determinístico.
III. Todo autômato �nito 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 �nito não-determinístico.
V. Todo autômato �nito 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 a�rmativas II e IV.
 apenas as a�rmativas I, II, III e IV.
apenas as a�rmativas I, II e IV.
apenas as a�rmativas II, III e V.
  apenas as a�rmativas I, II, III e V.
 
Respondido em 17/04/2023 20:58:39
Explicação:
(A) apenas as a�rmativas I, II, III e IV.
(B) apenas as a�rmativas II, III e V.
(C) apenas as a�rmativas I, II, III e V.
(D) apenas as a�rmativas II e IV.
(E) apenas as a�rmativas I, II e IV.
Resolução
A única a�rmativa falsa é a IV. Autômatos de pilha reconhecem linguagens livres de contexto, enquanto que
autômatos �nitos reconhecem linguagens regulares.
Portanto, é impossível simular um autômato de pilha utilizando um autômato �nito, pois a classe de linguagens que
esse último reconhece é hierarquicamente inferior.
Além disso, autômatos �nitos não possuem memória auxiliar para simular a pilha.
Logo, a alternativa correta é a C.
Acerto: 1,0  / 1,0
Qual das seguintes a�rmações é falsa?
 
Um autômato com duas pilhas pode ser simulado por uma máquina de Turing.
 
 Não existe algoritmo que determina quando uma gramática livre de contexto arbitrária é ambígua.
 
 O problema da parada é indecidível.
 
 Dada uma máquina de Turing M com alfabeto de entrada Σ e uma string w∈Σ, não se sabe se a
computação de M com entrada w vai ou não parar.
 
  Não existe autômato �nito determinístico que reconheça alguma linguagem livre de contexto.
 
Respondido em 17/04/2023 20:58:57
Explicação:
 Questão8
a
17/04/2023, 22:06 Estácio: Alunos
https://simulado.estacio.br/alunos/ 5/6
(A) Dada uma máquina de Turing M com alfabeto de entrada Σ e uma string w∈Σ, não se sabe se a computação de M
com entrada w vai ou não parar.
(B) O problema da parada é indecidível.
(C) Não existe algoritmo que determina quando uma gramática livre de contexto arbitrária é ambígua.
(D) Não existe autômato �nito determinístico que reconheça alguma linguagem livre de contexto.
(E) Um autômato com duas pilhas pode ser simulado por uma máquina de Turing.
A única alternativa falsa é a D. Linguagens regulares são reconhecidas por autômatos �nitos determinístico e, pela
hierarquia de Chomsky, toda linguagem regular também é livre de contexto.
Acerto: 1,0  / 1,0
Um método mais poderoso de descrever linguagens que podem descrever certas características que têm uma
estrutura recursiva o que as torna úteis em uma variedade de aplicações. O texto refere-se a:
Autômatos in�nitos
Expressões regulares
Autômatos �nitos
 Gramáticas livres-do-contexto
Pilha
Respondido em 17/04/2023 20:59:10
Explicação:
Conforme visto na aula 9, o ponto principal das gramáticas sensíveis ao contexto é que suas regras de produção não
são independentes de uma pré-existência de condições da palavra que está sendo reconhecida.
Acerto: 1,0  / 1,0A área de complexidade de algoritmos abrange a medição da e�ciência de um algoritmo frente
à quantidade de operações realizadas até que ele encontre seu resultado �nal.
A respeito desse contexto, suponha que um arquivo texto contenha o nome de N cidades de determinado
estado, que cada nome de cidade esteja separado do seguinte por um caractere especial de �m de linha e
classi�cado em ordem alfabética crescente. Considere um programa que realize a leitura linha a linha desse
arquivo, à procura de nome de cidade.
Com base nessa descrição, veri�ca-se que a complexidade desse programa é:
O(log2N), em caso de transferência dos nomes para uma árvore binária e, então, realizar a busca.
O(log2N), em caso de busca binária.
 O(N), em caso de busca sequencial.
O(1), em caso de busca sequencial.
O(N), em caso de transferência dos nomes para uma árvore binária e, então, realizar a busca.
Respondido em 17/04/2023 20:59:38
Explicação:
A análise de complexidade de algoritmos é realizada através da análise assintótica, que utiliza a notação O. Existe um
arquivo em formato texto e �camos sabendo que: (a) o tamanho da entrada é de�nido pelo número de cidades N, (b)
os nomes estão em ordem alfabética e (c) cada nome de cidade está em uma linha. O programa que deve ser analisado
procura o nome de uma cidade no arquivo, realizando a leitura linha a linha.
A alternativa A assume que a busca sequencial pode ser realizada em tempo constante (0(1)), ou seja, encontrar o
elemento da primeira posição do arquivo tem o mesmo tempo de execução que encontrar o elemento da segunda
posição ou mesmo a última (posição N). Como o arquivo é lido linha a linha, claramente para encontrar o primeiro
elemento será necessário ler apenas a primeira linha;
 Questão9
a
 Questão10
a
17/04/2023, 22:06 Estácio: Alunos
https://simulado.estacio.br/alunos/ 6/6
para o segundo elemento, as duas primeiras linhas; e assim sucessivamente até necessitar realizar a leitura das N
linhas do arquivo para o último elemento. Desta forma temos um crescimento linear no número de elementos e não
constante, correspondendo à alternativa B, que é a correta para a questão.
Para a análise da alternativa C, assumimos que não é possível fazer acesso aleatório ao arquivo, pois as linhas podem
ter tamanho variável e o deslocamento para a linha de posição (N/2) teria de ser realizado linha a linha (sequencial)
até encontrar N/2 marcadores de �nal de linha (e desta forma não será possível executar o algoritmo em tempo
logarítmico). Podemos projetar, ainda, um algoritmo que calcula o ponto médio do arquivo a partir do seu tamanho em
número de bytes e que ¿ajusta¿ para o marcador de �nal de linha mais próximo. Este algoritmo poderia executar em
tempo logarítmico se o sistema permitisse acesso aleatório por caracteres, o que não é possível, pois o enunciado
de�ne que a leitura é realizada linha a linha; logo a alternativa é falsa.
As duas últimas alternativas supõem a transferência dos dados para uma árvore binária, sem especi�car qual o seu
tipo. Em uma árvore binária de pesquisa balanceada, o tempo de busca é O(log2N) e, em uma implementação simples
de árvore binária, o tempo de busca é O(N), que fazem com que essas alternativas pareçam plausíveis. O tempo de
construção da árvore balanceada é O(N*log2N), com N operações de leitura ao arquivo e, para cada elemento, no
mínimo log2N operações para realizar a inserção. Caso a árvore não seja balanceada, o custo de inserção de cada
elemento é O(N) e o tempo de construção O(N^2). Logo as duas últimas alternativas são falsas, pois o tempo total do
algoritmo será a soma do tempo de construção mais o tempo de busca