SIMULADO Teoria da Computação

Prévia do material em texto

30/09/2020 Estácio: Alunos
https://simulado.estacio.br/alunos/?user_cod=2267290&matr_integracao=201902104129 1/5
 
 
Disc.: TEORIA DA COMPUTAÇÃO 
Aluno(a): GUILHERME ANTONIO RIBEIRO DE SOUZA 201902104129
Acertos: 10,0 de 10,0 30/09/2020
 
 
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
 
 MAQUINA DE TURING
GRAFO
LINGUAGENS FORMAIS
 
AUTOMATOS FINITOS
EXPRESSÕES REGULARES
Respondido em 30/09/2020 22:52:41
 
 
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
Com relação ao tema Estrutura de Dados ¿ Grafos, entende se por ¿grau de um nó":
 sequência de nós interligados que liga um nó (origem) a um outro nó (destino).
 
 o número de arestas a ele ligadas.
uma entidade, tal como "uma fruta", "uma pessoa".
 um conjunto de nós e um conjunto de arestas.
 uma relação que liga dois nós.
Respondido em 30/09/2020 23:09:48
 
 
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
 Questão1
a
 Questão2
a
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
30/09/2020 Estácio: Alunos
https://simulado.estacio.br/alunos/?user_cod=2267290&matr_integracao=201902104129 2/5
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
 
 
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 quantidade ........"
infinita de folha
infinita de ramo
infinita de nós
finita de ramo
 finita de nós.
Respondido em 30/09/2020 22:54:23
 
 
Explicação:
Como pode ser visto na aula 3 em Percorrendo árvores binárias. 
 
 
Acerto: 1,0 / 1,0
Uma das formas de representação do autômato finito indeterminístico mais comum é:
Conjunto
Setas
Matriz
Símbolo
 Diagrama
Respondido em 30/09/2020 22:55:12
 
 
Explicação:
.
 
 
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:
Mapeamento
Array
 quíntupla
Autômato quinto
Five elements
Respondido em 30/09/2020 22:58:20
 
 
Explicação:
 Questão3
a
 Questão4
a
 Questão5
a
30/09/2020 Estácio: Alunos
https://simulado.estacio.br/alunos/?user_cod=2267290&matr_integracao=201902104129 3/5
Dizemos que um autômato finito é representado por uma quíntupla (Q, Ʃ, δ, q0, F), onde Q é o conjunto finito
de estados, Ʃ é o conjunto finito de símbolos de entrada, δ é a função de transição, q0 é o estado inicial (q0 ∈ Q
 o estado inicial é apontado por uma seta) e F o conjunto de estados finais ou de aceitação (os estados de
aceitação são apontados por um círculo dentro de outro ou asterisco e um estado inicial também pode ser final).
 
 
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:
{legal, ruim, legallegal, legalruim, ruimruim, legallegal}
{meninolegal, meninaruim, meninoruim, meninalegal}
{menino, menina, ruim, legal}
 {meninolegal, meninalegal, meninoruim meninaruim}
{legal, ruim, menino, menina}
Respondido em 30/09/2020 22:56:55
 
 
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, III e V.
apenas as afirmativas II e IV.
 apenas as afirmativas I, II, III e V.
 
apenas as afirmativas I, II, III e IV.
apenas as afirmativas I, II e IV.
Respondido em 30/09/2020 23:01:57
 
 
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.
 
 Questão6
a
 Questão7
a
30/09/2020 Estácio: Alunos
https://simulado.estacio.br/alunos/?user_cod=2267290&matr_integracao=201902104129 4/5
 
Acerto: 1,0 / 1,0
Na máquina de turing o componente que contem o estado corrente da máquina é:
 
O programa
A fita
 A unidade de controle
 
O processador
A memoria
Respondido em 30/09/2020 23:02:52
 
 
Explicação:
UNIDADE DE CONTROLE ¿ Contém o estado corrente da máquina, lê ou escreve dados na fita e pode se mover
para a ¿frente¿(direita) ou para ¿trás¿(esquerda)
 
 
Acerto: 1,0 / 1,0
Em uma gramática sensível ao contexto definida por G = {V, T, P, S} o P significa?
 Regras de produção da forma
Uma palavra ¿final¿, composta dos símbolos terminais
 
Um símbolo especial escolhido aparte de V denominado inicial
Conjunto finito de símbolos terminais DISJUNTOS
Conjunto finito de símbolos ou variáveis Não-Terminais
Respondido em 30/09/2020 23:06:38
 
 
Explicação:
V - Conjunto finito 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 finais da linguagem gerada por ela. 
 T -Conjunto finito 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
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 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 transferência dos nomes para uma árvore binária e, então, realizar a busca.
O(1), em casode busca sequencial.
 Questão8
a
 Questão9
a
 Questão10
a
30/09/2020 Estácio: Alunos
https://simulado.estacio.br/alunos/?user_cod=2267290&matr_integracao=201902104129 5/5
 O(N), em caso de busca sequencial.
Respondido em 30/09/2020 23:06:09
 
 
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 ficamos sabendo que: (a) o tamanho da entrada é definido 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;
 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 final 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 final 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 define 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 especificar 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
 
 
 
 
 
 
 
 
 
 
javascript:abre_colabore('38403','207146933','4137175259');