Teoria da Computação - AV2

Prévia do material em texto

06/05/2021 Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=50772420&user_cod=3070659&matr_integracao=202008191076 1/5
 
 
Disc.: TEORIA DA COMPUTAÇÃO 
Aluno(a): YURI CID DA SILVA LIMA 202008191076
Acertos: 10,0 de 10,0 06/05/2021
 
 
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
 
GRAFO
EXPRESSÕES REGULARES
 MAQUINA DE TURING
AUTOMATOS FINITOS
Respondido em 06/05/2021 13:32:27
 
 
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 final
Máquinas de Turing não-deterministas
 
 
Acerto: 1,0 / 1,0
"Um conjunto de pontos com linhas conectando alguns dos pontos, na qual os pontos são chamados nós ou vértices ,
e as linhas são chamadas arestas". Esse conceito é a definição de:
Algoritmo
Árvore
 Grafos
Arestas
Caminho direcionado.
Respondido em 06/05/2021 13:32:40
 
 
Explicação:
Conforme visto na aula 2, Grafo (graph) é um conjunto de vértices (ou nodos), interconectados dois a dois por
arestas (ou arcos).
 
 
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
 Questão1
a
 Questão2
a
 Questão3
a
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
06/05/2021 Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=50772420&user_cod=3070659&matr_integracao=202008191076 2/5
quantidade ........"
infinita de nós
 finita de nós.
infinita de ramo
finita de ramo
infinita de folha
Respondido em 06/05/2021 13:32:55
 
 
Explicação:
Como pode ser visto na aula 3 em Percorrendo árvores binárias. 
 
 
Acerto: 1,0 / 1,0
Quanto aos automatos deterministicos podemos afirmar que:
Para todo estado e todo símbolo de entrada sempre há 0 ou 1 ou n transições possíveis.
É 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 cada estado e para cada entrada só há zero ou uma transição possível
 
Pode estar em muitos estados ao mesmo tempo.
Não é representado por uma quíntupla
Respondido em 06/05/2021 13:33:16
 
 
Explicação:
Um autômato finito 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?
 
64
 16
32
128
 
8
Respondido em 06/05/2021 13:33:37
 
 
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
Seja o alfabeto ∑ constituído das 23 letras {a, b,c ...,z}. Se A= {legal, ruim} e B= {menino, menina} então o resultado
de B concatenado A (B.A) será respectivamente:
{meninolegal, meninaruim, meninoruim, meninalegal}
 Questão4
a
 Questão5
a
 Questão6
a
06/05/2021 Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=50772420&user_cod=3070659&matr_integracao=202008191076 3/5
{menino, menina, ruim, legal}
{legal, ruim, menino, menina}
 {meninolegal, meninalegal, meninoruim meninaruim}
{legal, ruim, legallegal, legalruim, ruimruim, legallegal}
Respondido em 06/05/2021 13:34:01
 
 
Explicação:
Lembrando que concatenação é uma operação que junta cadeias de um conjunto com cadeias de um outro
conjunto. 
 
 
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 I, II, III e V.
 
apenas as afirmativas II, III e V.
apenas as afirmativas I, II, III e IV.
Respondido em 06/05/2021 13:34:26
 
 
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
Correlacionando a hierarquia de Chomsky com os reconhecedores de linguagem, é correto afirmar que a máquina de
Turing, tradicional ou básica, corresponde às gramáticas
regulares. 
irregulares. 
 sem restrição.
 
sensíveis ao contexto. 
livres do contexto. 
Respondido em 06/05/2021 13:34:46
 
 
Explicação:
A MAQUINA DE TURING CORRESPONDE A GRAMATICAS SEM RESTRIÇÕES
 
 Questão7
a
 Questão8
a
06/05/2021 Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=50772420&user_cod=3070659&matr_integracao=202008191076 4/5
 
Acerto: 1,0 / 1,0
Considere a gramática a seguir, em que S, A e B são símbolos não terminais, 0 e 1 são terminais e ε é a cadeia vazia.
S-> 1S|0A|ε
A-> 1S|0B|ε
B-> 1S|ε
A respeito dessa gramática, analise as afirmações a seguir.
I. Nas cadeias geradas por essa gramática, o último símbolo é 1.
II. O número de zeros consecutivos nas cadeias geradas pela gramática é, no máximo, dois.
III. O número de uns em cada cadeia gerada pela gramática é maior que o número de zeros.
IV. Nas cadeias geradas por essa gramática, todos os uns estão à esquerda de todos os zeros.
É correto apenas o que se afirma em
II e IV.
III e IV.
 
I.
I e III.
 II.
Respondido em 06/05/2021 13:35:05
 
 
Explicação:
 
 É uma questão de fácil resolução a partir da correta aplicação das regras de derivação da gramática para a
construção de palavras.
A técnica a ser utilizada para a justificativa de uma alternativa como falsa é a apresentação de um
contraexemplo de sequência de derivações que demonstre a falsidade.
A afirmativa I deve ser considerada falsa. O contraexemplo é a geração da palavra-vazia a partir do símbolo
inicial S (nota do autor: essa é uma suposição, já que a questão pode ser considerada mal construída já que
não informa qual dos símbolos, S, A ou B, é o símbolo inicial).
S => e (aplicação da regra S->e)
A afirmativa II é verdadeira. Considere a seguinte sequência de derivações, na qual W representa uma cadeia
de símbolos terminais. A derivação demonstra as duas únicas regras que podem ser aplicadas a qualquer
momento para remover o símbolo terminal B da palavra sendo gerada, de forma que número de zeros
consecutivos será sempre no máximo dois.
S =>* W0A
 => W00B (Aplicação da regra S->0B é a única que gera zeros seguidos.)
 => W001S (Aplicação da regra B->1S.)
 ou
 => W00 (Aplicação da regra B->e.)
A afirmativa III é trivialmente falsa, já que a palavra-vazia pertence ao conjunto de palavras da linguagem
gerada pela gramática apresentada. Ou seja, a quantidade zero de símbolos uns e zeros torna a afirmativa
falsa. A seguinte sequência de derivações é o contraexemplo que justifica a afirmativa.
S => e (aplicação da regraS->e)
A afirmativa IV deve ser considerada falsa, pois é possível gerar a palavra 01 (na qual uns aparecem à direita
de zeros) a partir da seguinte sequência de derivações do contraexemplo.
S => 0A (Aplicação da regra S->0A.)
S => 01S (Aplicação da regra A->1S.)
S => 01 (Aplicação da regra S->e.)
 
 
Acerto: 1,0 / 1,0
Considere o processo de fabricação de um produto siderúrgico que necessita passar por n tratamentos térmicos e
químicos para ficar pronto. Cada uma das n etapas de tratamento é realizada uma única vez na mesma caldeira. Além
do custo próprio de cada etapa do tratamento, existe o custo de se passar de uma etapa para a outra, uma vez que,
dependendo da sequência escolhida, pode ser necessário alterar a temperatura da caldeira e limpá-la para evitar a
reação entre os produtos químicos utilizados. Assuma que o processo de fabricação
inicia e termina com a caldeira limpa. Deseja-se projetar um algoritmo para indicar a sequência de tratamentos que
possibilite fabricar o produto com o menor custo total. Nesta situação, conclui-se que
 
O problema se reduz a encontrar a árvore geradora mínima para o conjunto de etapas do processo,
requerendo tempo de ordem polinomial para ser solucionado.
 
Uma heurística para a solução do problema de coloração de grafos solucionará o problema em tempo
polinomial.
 
A utilização do algoritmo de Dijkstra para se determinar o caminho de custo mínimo entre o estado inicial e o
final soluciona o problema em tempo polinomial.
 
A solução do problema é obtida em tempo de ordem O(nlogn), utilizando um algoritmo ótimo de ordenação.
 
 Qualquer algoritmo conhecido para a solução do problema descrito possui ordem de complexidade de tempo
 Questão9
a
 Questão10
a
06/05/2021 Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=50772420&user_cod=3070659&matr_integracao=202008191076 5/5
não-polinomial, uma vez que o problema do caixeiro viajante se reduz a ele.
 
Respondido em 06/05/2021 13:35:21
 
 
Explicação:
Para modelar este problema utilizando grafos se usa um grafo completo com n+1 vértices representando cada
uma das etapas e a etapa inicial caldeira limpa. 
As arestas contêm pesos que representam o custo de se passar de uma etapa para a outra. Deseja se sair do
vértice que representa a caldeira limpa passar por todos os vértices uma única vez e retornar ao vértice caldeira
limpa de forma que o custo seja mínimo. O problema não pode ser resolvido através de uma arvore geradora
mínima, pois temos que encontrar um ciclo (exclui C). Não podemos aplicar Dijkstra, pois
temos que garantir que todos os vértices sejam visitados (exclui D). O problema de coloração determina
conjuntos de tarefas e não uma ordem de tarefas (exclui B). Não é suficiente fazer uma ordenação dos valores
pois isso não garante que os vértices serão todos visitados uma única vez de forma mínima. Se colocarmos
todas as etapas com o mesmo custo como garantir que será encontrado um ciclo que visite todas os vértices.
O problema em questão corresponde ao problema do Caixeiro Viajante ou Ciclo Hamiltoniano, que é NP-
Completo.
 
 
 
 
 
 
 
 
 
 
 
javascript:abre_colabore('38403','224867864','4560784351');