teoria da computacao AV simulada

Prévia do material em texto

1a
          Questão
	Acerto:  0,0  / 1,0
	
	Um grafo é:
		
	 
	Um conjunto de nós interligados por arestas
	 
	Um conjunto de arestas interligadas por nós
 
	
	Apenas um conjunto de arestas
	
	Um conjunto de nós e de arestas disjuntos
	
	Apenas um conjunto de no.
	
	
	Explicação:
Grafos são um conjunto de vértices (ou nós), interconectados dois a dois por arestas. 
	
		2a
          Questão
	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ó é
		
	
	 um número associado ao arco, também chamado de peso.
	
	a posição deste nó em relação ao nó raiz do grafo
	
	o número de pares ordenados que formam o arco.
 
	 
	 o número de arcos incidentes nesse nó.
	
	a distância entre este nó e um outro nó qualquer do grafo.
	
	
	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
	
		3a
          Questão
	Acerto:  1,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.
	
	Uma estrutura de vértices que é definida por meio de um conjunto de vértices.
	 
	Um tipo especial de árvore que apresenta um vértice (raiz) que se distingue dos demais
	
	
	Explicação:
Tipo especial de árvore que apresenta um vértice (raiz) que se distingue dos demais. É utilizado o termo nó para fazer referência aos vértices. 
	
		4a
          Questão
	Acerto:  0,0  / 1,0
	
	Uma das formas de representação do autômato finito indeterminístico mais comum é:
		
	 
	Conjunto
	
	Símbolo
	 
	Diagrama
	
	Matriz
	
	Setas
	
	Explicação:
.
	
		5a
          Questão
	Acerto:  1,0  / 1,0
	
	Se o estado inicial for também estado final em um autômato finito, então esse autômato
		
	 
	aceita a cadeia vazia.
	
	não aceita a cadeia vazia.
	
	é não determinístico.
 
	
	não tem outros estados finais.
	
	é determinístico.
	
	
	Explicação:
Quando o estado inicial também é final num AF, então ele aceita a cadeia vazia. 
	
		6a
          Questão
	Acerto:  1,0  / 1,0
	
	Uma gramática G é definida por G=({x,y,z},{S,W,X,Y,Z},P,S) na qual os membros de P são
S→WZW→X|YX→x|xXY→y|yYZ→z|zZ
Qual das expressões regulares abaixo corresponde a esta gramática?
		
	 
	(xx∗|yy∗)zz∗
	
	(xx|yy)∗zz∗
	
	 xx∗yy∗zz∗
	
	xx∗(yy∗|zz∗)
	
	 xx∗|yy∗|zz∗
 
	
	
	Explicação:
Os símbolos não terminais X, Y e Z produzem, respectivamente, xx∗, yy∗ e zz∗. Além disso, podemos eliminar W substituindo-o na primeira produção:
SXYZ→(X|Y)Z→xx∗→yy∗→zz∗
Substituindo X, Y e Z na primeira produção, obtemos
Portanto a solução é S→(xx∗|yy∗)zz∗   
	
		7a
          Questão
	Acerto:  1,0  / 1,0
	
	Para gerar o automâto finito mínimo  a partir um automâto finito o devemos  pelo algoritmo de minimização é necessario que:
		
	
	Ele tenha destinos inalcançaveis
	
	A função programa seja parcial
	
	Todos os estados sejam  alcançaveis a partir de qualquer outro estado
	 
	Ele seja  deterministico
	
	A partir de uma estado existam  0, 1 ou n transições
 
	
	
	Explicação:
Algoritmo de Minimização de Autômatos
PRE-REQUISITOS DO AUTÔMATO A SER MINIMIZADO
a.Deve ser determinístico
b.Todos os estados devem poder ser alcançados a partir do estado inicial (Sem estados inalcançáveis
c.A função programa deve ser total, ou seja, a partir de qualquer estado deve haver transições para todos os símbolos do alfabeto
	
		8a
          Questão
	Acerto:  0,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 polinomial que o soluciona, fornecendo respostas aproximadas.
 
	
	existe algoritmo exato de tempo de execução exponencial para solucioná-lo.
 
	 
	existe algoritmo exato de tempo de execução polinomial para solucioná-lo.
 
	 
	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 exponencial que o soluciona, fornecendo respostas aproximadas.
 
	
	
	Explicação:
O problema da parada pode ser definido como:
Seja S o conjunto de todos os pares (A,D), em que A é um algoritmo, e D, dado de entrada; (A,D) tem a propriedade P se o algoritmo A, quando recebe o dado D, eventualmente produz um resultado (ou seja, eventualmente para) A tese de Church-Turing mostra que o problema da parada é não decidível, ou seja, não existe um algoritmo H tal que para todo (A,D) que pertence à S: H(A,D)= { 1 se A(D) eventualmente para; 
0 caso contrário 
A prova informal de que tal H não existe é obtida por contradição.
Suponha que H existe. Seja C o algoritmo: ¿entrada A; executa H(A,A); se H(A,A)=0, então, retorna 1, senão entra em loop¿.
Então, ∀A,(H(A,A)=0 ⇿ ¬A(A) eventualmente para ⇿ H(A,A)=0) (pois H é função total) e ∀A,(H(A,A)=0 ⇿ ¬A(A) eventualmente para).
Tomando A como sendo C, obtemos que C(C) eventualmente para, se e somente se ¬C(C) eventualmente para, e isto é uma contradição!
Logo, não existe um algoritmo que solucione o problema.
As respostas das alternativas A e B não estão corretas, pois afirmam que existe um algoritmo que resolve o problema.
As respostas das alternativas D e E não estão corretas, pois afirmam que existe um algoritmo de aproximação e, pelo exposto na justificativa da resposta correta, tal algoritmo não existe.
	
		9a
          Questão
	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
		
	
	III e IV.
 
	
	I.
	
	II e IV.
	 
	II.
	
	I e III.
	
	
	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 zerosseguidos.)
 => 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 regra S->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.)
	
		10a
          Questã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 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.
	
	O(log2N), em caso de transferência dos nomes para uma árvore binária e, então, realizar a busca.
	
	
	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