Teoria da Computação - AVP

Prévia do material em texto

04/06/2020 Estácio: Alunos
simulado.estacio.br/alunos/ 1/4
 
 
Disc.: TEORIA DA COMPUTAÇÃO 
Aluno(a): JOSEILDON DA SILVA DANTAS 201908040459
Acertos: 9,0 de 10,0 04/06/2020
Acerto: 1,0 / 1,0
Quando operamos dois conjuntos e retornamos os elementos existentens no primeiro que não existem no
segundo temos a operação
UNIÃO
 DIFERENÇA
INTERSECÇÃO
PRODUTO CARTESIANO
 
COMPLEMENTO
Respondido em 04/06/2020 10:10:37
Acerto: 1,0 / 1,0
Pode-se defir o conceito de Grafo bipartido como sendo:
Grafo que tem pesos associados a cada uma de suas arestas.
Grafo não direcionado
Grafo que tem um único vértice e nenhuma aresta
Grafo onde todos os seus vértices têm o mesmo grau
 Grafo onde seus vértices podem ser divididos em dois conjuntos disjuntos, tais que cada aresta ligue
apenas vértices de grupos diferentes. 
Respondido em 04/06/2020 10:11:00
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
 7
9
 
 3
5
Respondido em 04/06/2020 10:11:39
 Questão1
a
 Questão2
a
 Questão3
a
http://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
04/06/2020 Estácio: Alunos
simulado.estacio.br/alunos/ 2/4
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:
Suas transições são incompletas
Há tabelas de transição
 Para todo estado e todo símbolo de entrada sempre há zero ou uma transição possível.
Para todo estado e todo símbolo de entrada sempre há zero ou uma ou n transições possíveis.
Contém diversos números infinito de estados
Respondido em 04/06/2020 10:12:18
Acerto: 1,0 / 1,0
Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde F representa 
 
 o conjunto de estados finais
os simbolos de entrada
as transições
O número de estados
o estado inicial
 
Respondido em 04/06/2020 10:12:41
Acerto: 1,0 / 1,0
Analise as seguintes igualdades de expressões regulares:
I. a∗=(a∗)∗
II. (a+b)∗=(b+a)∗
III. a∗+b∗=(a+b)∗
A análise permite concluir que.
nenhuma das igualdades é verdadeira.
todas as igualdades são verdadeiras.
somente as igualdades II e III são verdadeiras.
somente a igualdade I é verdadeira.
 somente as igualdades I e II são verdadeiras.
 
Respondido em 04/06/2020 10:12:59
Acerto: 1,0 / 1,0
Seja a linguagem formal L={anb2nc,n≥0}. Analise as seguintes assertivas.
I. L é uma linguagem livre de contexto.
II. A gramática G=({S,X},{a,b,c},{S→Xc,X→aXbb|ϵ},S) gera a linguagem L.
III. L não pode ser reconhecida por um autômato com pilha.
A análise permite concluir que estão CORRETAS
 
 apenas as assertivas I e II.
 
nenhuma das assertivas.
todas as assertivas.
 
apenas as assertivas I e III.
 Questão4
a
 Questão5
a
 Questão6
a
 Questão7
a
04/06/2020 Estácio: Alunos
simulado.estacio.br/alunos/ 3/4
apenas as assertivas II e III.
 
Respondido em 04/06/2020 10:13:19
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
finita, decidir se o algoritmo termina ou se executará indefinidamente.
Para o problema da parada, 
 não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução exponencial
que o soluciona, fornecendo respostas aproximadas.
 
 não existe algoritmo que o solucione, não importa quanto tempo seja disponibilizado.
 
 não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução polinomial
que o soluciona, fornecendo respostas aproximadas.
 
existe algoritmo exato de tempo de execução polinomial para solucioná-lo.
 
existe algoritmo exato de tempo de execução exponencial para solucioná-lo.
 
Respondido em 04/06/2020 10:13:56
Acerto: 1,0 / 1,0
Em uma gramática sensível ao contexto definida por G = {V, T, P, S} o que T significa?
Um símbolo especial escolhido aparte de V denominado inicial
Uma palavra ¿final¿, composta dos símbolos terminais
 
Conjunto finito de símbolos ou variáveis Não-Terminais
Regras de produção da forma
 Conjunto finito de símbolos terminais DISJUNTOS
Respondido em 04/06/2020 10:14:10
Acerto: 1,0 / 1,0
A área de complexidade de algoritmos abrange a medição da eficiência de um algoritmo frente
à quantidade de operações realizadas até que ele encontre seu resultado final.
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 fim de linha e
classificado 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, verifica-se que a complexidade desse programa é:
O(log2N), em caso de busca binária.
O(log2N), em caso de transferência dos nomes para uma árvore binária e, então, realizar a busca.
O(1), em caso de busca sequencial.
 O(N), 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 04/06/2020 10:15:05
 Questão8
a
 Questão9
a
 Questão10
a
javascript:abre_colabore('38403','198507938','3985838220');
04/06/2020 Estácio: Alunos
simulado.estacio.br/alunos/ 4/4
04/06/2020 Estácio: Alunos
simulado.estacio.br/alunos/ 1/4
 
 
Disc.: TEORIA DA COMPUTAÇÃO 
Aluno(a): JOSEILDON DA SILVA DANTAS 201908040459
Acertos: 3,0 de 10,0 04/06/2020
Acerto: 0,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
 
 GRAFO
LINGUAGENS FORMAIS
 
 MAQUINA DE TURING
AUTOMATOS FINITOS
EXPRESSÕES REGULARES
Respondido em 04/06/2020 10:17:03
Acerto: 0,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:
 Árvore
Arestas
 Grafos
Caminho direcionado.
Algoritmo
Respondido em 04/06/2020 10:16:46
Acerto: 1,0 / 1,0
Ao percorrermos uma arvore se visitamos por ultimo o centro estamos no percurso
 Pós Ordem
Ordem Natural
Pré Ordem
Ordem
Ordem Central
 
Respondido em 04/06/2020 10:16:47
 Questão1
a
 Questão2
a
 Questão3
a
http://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
04/06/2020 Estácio: Alunos
simulado.estacio.br/alunos/ 2/4
Acerto: 0,0 / 1,0
Os movimentos realizado pelos automatos finitos constituem :
 Os dados representados
O estado final 
 
O controle
 O conjunto de transições
O conjunto de estados
Respondido em 04/06/2020 10:16:49
Acerto: 1,0 / 1,0
A definição formal diz que um autômato finito é uma lista de cinco objetos: conjunto de estados, alfabeto de
entrada, regras para movimentação, estado inicial, e estados de aceitação. Essa lista de cinco elementos é
frequentemente chamada:
 quíntupla
Array
Five elements
Autômato quinto
Mapeamento
Respondido em 04/06/2020 10:16:51
Acerto: 0,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:
 {legal, ruim, legallegal, legalruim, ruimruim, legallegal}
{meninolegal, meninaruim, meninoruim, meninalegal}
 {meninolegal, meninalegal, meninoruim meninaruim}
{legal, ruim, menino, menina}
{menino, menina, ruim, legal}
Respondido em 04/06/2020 10:17:11
Acerto: 0,0 / 1,0
Analise as seguintes afirmativas.I. Todo autômato finito não-determinístico pode ser simuladopor 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 I, II e IV.
 apenas as afirmativas I, II, III e V.
 
apenas as afirmativas II, III e V.
apenas as afirmativas II e IV.
apenas as afirmativas I, II, III e IV.
Respondido em 04/06/2020 10:17:12
Acerto: 1,0 / 1,0
 Questão4
a
 Questão5
a
 Questão6
a
 Questão7
a
 Questão8
a
04/06/2020 Estácio: Alunos
simulado.estacio.br/alunos/ 3/4
Na máquina de turing o componente que contem o estado corrente da máquina é:
 
 A unidade de controle
 
A fita
O programa
A memoria
O processador
Respondido em 04/06/2020 10:17:14
Acerto: 0,0 / 1,0
A gramática dada pelos descritores abaixo é:
G= 
N={S,A}
T={0,1} e P é o conjunto de produções
{S → 0S 1A 01ε e A → 0S 1A 0}
 Uma gramática do tipo 0 que não é gramática sensível a contexto.
Uma gramática livre de contexto que não é gramática regular
Uma gramática sem categorização possível e que gera a coleção das palíndromas em {0,1}
exclusivamente de tamanho par.
 
 Uma gramática regular. 
Uma gramática sensível a contexto que não é gramática livre de contexto
Respondido em 04/06/2020 10:17:15
Acerto: 0,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
 
 A solução do problema é obtida em tempo de ordem O(nlogn), utilizando um algoritmo ótimo de
ordenação.
 
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.
 
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.
 
 Qualquer algoritmo conhecido para a solução do problema descrito possui ordem de complexidade de
tempo não-polinomial, uma vez que o problema do caixeiro viajante se reduz a ele.
 
Uma heurística para a solução do problema de coloração de grafos solucionará o problema em tempo
polinomial.
 
Respondido em 04/06/2020 10:17:17
 Questão9
a
 Questão10
a
javascript:abre_colabore('38403','198509668','3985880038');
04/06/2020 Estácio: Alunos
simulado.estacio.br/alunos/ 4/4
04/06/2020 Estácio: Alunos
simulado.estacio.br/alunos/ 1/4
 
 
Disc.: TEORIA DA COMPUTAÇÃO 
Aluno(a): JOSEILDON DA SILVA DANTAS 201908040459
Acertos: 3,0 de 10,0 04/06/2020
Acerto: 1,0 / 1,0
Um grupo de objetos representado como uma unidade é chamado de:
 Conjunto
Membro
Complemento
Elemento
Operação
Respondido em 04/06/2020 10:17:50
Acerto: 0,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 distância entre este nó e um outro nó qualquer do grafo.
 o número de arcos incidentes nesse nó.
o número de pares ordenados que formam o arco.
 
a posição deste nó em relação ao nó raiz do grafo
 um número associado ao arco, também chamado de peso.
Respondido em 04/06/2020 10:17:52
Acerto: 0,0 / 1,0
Entre os diversos tipos de árvores, a árvore enraizada se caracteriza por:
 Não apresentar um vértice (raiz) que se distingue dos demais.
Um grafo acíclico, não orientado e conectado.
Um grafo acíclico, não orientado mas, possivelmente desconectado.
 Um tipo especial de árvore que apresenta um vértice (raiz) que se distingue dos demais
Uma estrutura de vértices que é definida por meio de um conjunto de vértices.
Respondido em 04/06/2020 10:17:53
Acerto: 0,0 / 1,0
 Questão1
a
 Questão2
a
 Questão3
a
 Questão4
a
http://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
04/06/2020 Estácio: Alunos
simulado.estacio.br/alunos/ 2/4
Quanto aos automatos deterministicos podemos afirmar que:
 Pode estar em muitos estados ao mesmo tempo.
 Para cada estado e para cada entrada só há zero ou uma transição possível
 
Não é representado por uma quíntupla
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.
Respondido em 04/06/2020 10:17:54
Acerto: 0,0 / 1,0
Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde q0 representa 
 
 os simbolos de entrada
 o estado inicial
 
as transições
o conjunto de estados finais
O número de estados
Respondido em 04/06/2020 10:17:55
Acerto: 0,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
 
 Um autômato finito não determinístico que reconheça L(R1) ∪ L(R2) tem, pelo menos, quatro estados.
 
 
 Existe um autômato finito determinístico cuja linguagem é igual a L(R1) ∪ L(R2).
L(R1) = L(r2) 
Se R3 é uma expressão regular tal que L(R3) = L(R1) ∩ L(R2), então L(R3) é uma linguagem
infinita.2). 
L(R2) = {w | w termina com b}
Respondido em 04/06/2020 10:17:57
Acerto: 0,0 / 1,0
Sobre a hierarquia de Chomsky podemos afirmar que: 
 Uma linguagem que não é regular é livre de contexto
 
 As linguagens livres de contexto e as linguagens sensíveis ao contexto se excluem
 
 As linguagens reconhecidas por autômatos a pilha são as linguagens regulares
 Há linguagens que não são nem livres de contexto nem sensíveis ao contexto
 
Uma linguagem que é recursivamente enumerável não pode ser uma linguagem regular
 
 Questão5
a
 Questão6
a
 Questão7
a
04/06/2020 Estácio: Alunos
simulado.estacio.br/alunos/ 3/4
 
Respondido em 04/06/2020 10:17:58
Acerto: 0,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
 livres do contexto. 
 sem restrição.
 
regulares. 
irregulares. 
sensíveis ao contexto. 
Respondido em 04/06/2020 10:17:42
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.
III e IV.
 
I.
II e IV.
I e III.
Respondido em 04/06/2020 10:17:43
Acerto: 1,0 / 1,0
Um cientista afirma ter encontrado uma redução polinomial de um problema NP-Completo para um problema
pertencente à classe P. Considerando que esta afirmação tem implicações importantes no que diz respeito à
complexidade computacional, avalie as seguintes asserções e a relação proposta entre elas.
I. Adescoberta do cientista implica que P = NP
PORQUE
II. A descoberta do cientista implica na existência de algoritmos polinomiais para todos os problemas NP-
Completos.
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 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.
 
As asserções I e II são proposições falsas.
 
 Questão8
a
 Questão9
a
 Questão10
a
04/06/2020 Estácio: Alunos
simulado.estacio.br/alunos/ 4/4
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
 
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
 
Respondido em 04/06/2020 10:18:03
javascript:abre_colabore('38403','198509884','3985884943');