Teoria da Computação - Testes de Conhecimento

Prévia do material em texto

AULA 01
Questão 1
	Quando operamos dois conjuntos e retornamos  os elementos existentens no primeiro que não existem no segundo temos  a operação
		
	
	INTERSECÇÃO
	 
	DIFERENÇA
	
	COMPLEMENTO
	
	UNIÃO
	
	PRODUTO CARTESIANO
Questão 2
	Um grupo de objetos representado como uma unidade é chamado de:
		
	 
	Conjunto
	
	Operação
	
	Complemento
	
	Membro
	
	Elemento
Questão 3
	Um grafo é:
		
	 
	Um conjunto de nós interligados por arestas
	
	Apenas um conjunto de no.
	
	Um conjunto de arestas interligadas por nós 
	
	Apenas um conjunto de arestas
	
	Um conjunto de nós e de arestas disjuntos
Questão 4
	Quando operamos dois conjuntos e retornamos todos os elementos existentes tanto no primeiro como no segundo conjunto temos  a operação
		
	
	COMPLEMENTO
	
	PRODUTO CARTESIANO 
	
	DIFERENÇA
	
	INTERSECÇÃO
	 
	UNIÃO
Questão 5
	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
Questão 6
	Considerando A um conjunto e R uma relação em A, há algumas propriedades a serem respeitadas. No que tange a propriedade Reflexiva é correto afirmar:
		
	
	aRb, então bRa 
	
	aRb e bRc, então aRc
	
	aRb e bRa, então a≠b
	
	aRb e bRa, então a=b
	 
	Para todo a ∈ A, aRa
AULA 02
Questão 1
	Com relação ao tema Estrutura de Dados ¿ Grafos, entendese por ¿grau de um nó":
		
	
	 uma relação que liga dois nós.
	
	uma entidade, tal como "uma fruta", "uma pessoa".
	
	 sequência de nós interligados que liga um nó (origem) a um outro nó (destino). 
	
	 um conjunto de nós e um conjunto de arestas.
	 
	 o número de arestas a ele ligadas.
Questão 2
	É uma noção simples, abstrata e intuitiva, usada para representar a ideia de alguma espécie de relação entre os objetos. Graficamente, aparece representado por uma figura com nós ou vértices. Trata-se dos
		
	
	triângulos.
	
	objetos geométricos.
	 
	grafos.
	
	dados.
	
	registros.
Questão 3
	Considerando-se os conceitos básicos de grafos e algoritmos em grafos, assinale a  alternativa INCORRETA.
 
		
	
	Grafo: conjunto de vértices e arestas. 
	
	Vértice: objeto simples que pode ter nome e outros atributos. 
	
	Grafo trivial: Grafo que possui um único vértice e nenhuma aresta                 
 
	 
	Aresta: conexão entre dois grafos 
	
	Grafo completo: grafo não direcionado, no qual todos os pares de vértices são adjacentes.
Questão 4
	"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:
		
	
	Caminho direcionado.
	
	Árvore
	 
	Grafos
	
	Algoritmo
	
	Arestas
Questão 5
	Pode-se defir o conceito de Grafo bipartido como sendo:
		
	
	Grafo não direcionado
	
	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. 
	
	Grafo que tem pesos associados a cada uma de suas arestas.
	
	Grafo que tem um único vértice e nenhuma aresta
Questão 6
	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.
	
	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.
	
	a posição deste nó em relação ao nó raiz do grafo
AULA 03
Questão 1
	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 
		
	
	5
	 
	3
	
	7
	
	1
	
	9
Questão 2
	Entre os diversos tipos de árvores, a árvore enraizada se caracteriza por:
		
	
	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
	
	Um grafo acíclico, não orientado e conectado.
	
	Uma estrutura de vértices que é definida por meio de um conjunto de vértices.
	
	Não apresentar um vértice (raiz) que se distingue dos demais.
Questão 3
	Ao percorrermos uma arvore se visitamos primeiro a subarvore esquerda  estamos no percurso em:
		
	 
	Ordem
	
	Pré Ordem
	 
	Ordem Natural
	
	Pós Ordem
	
	Ordem Central
Questão 4
	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 
		
	 
	7
	
	9 
	
	1
	
	3
	
	5
Questão 5
	Ao percorrermos uma arvore se visitamos por ultimo o centro estamos no percurso
		
	 
	Pós Ordem
	
	Ordem Natural
	
	Pré Ordem
	
	Ordem Central 
	
	Ordem
Quesão 6
	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 ramo
	
	infinita de nós
	
	finita de ramo
	 
	finita de nós.
	
	infinita de folha
AULA 04
Questão 1
	Quanto aos automatos deterministicos podemos afirmar que:
		
	 
	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
	
	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.
Questão 2
	Uma das formas de representação do autômato finito indeterminístico mais comum é:
		
	
	Matriz
	
	Setas
	
	Símbolo
	
	Conjunto
	 
	Diagrama
Questão 3
	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
	 
	Para todo estado e todo símbolo de entrada sempre há zero ou uma transição possível.
	
	Há tabelas de transição
	
	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
Questão 4
	Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde Q representa 
		
	 
	O número de estados
	
	o estado inicial 
	
	as transições
	
	o conjunto de estados finais
	
	os simbolos de entrada
Questão 5
	Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F)  onde Ʃ representa 
		
	 
	os simbolos de entrada
	
	o conjunto de estados finais
	
	O número de estados
	
	as transições
	
	o estado inicial
Questão 6
	Os  movimentos realizado pelos automatos finitos constituem :
		
	
	O conjunto de estados
	
	O controle
	
	Os dados representados
	
	O estado final  
	 
	O conjunto de transições
AULA 05
Questão 1
	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? 
		
	
	32
	
	8
	
	64
	 
	16
	
	128
Questão 2
	Constituem um conjunto de linguagens decidíveis bastante simples e com propriedades bem definidas e compreendidas. Está é uma característica encontrada nos:
		
	
	Grafos
	 
	Autômatos Finitos
	
	Árvores Binária
	
	Autômatos Indeterminados
	
	Autômatos Infinitos
Questão 3
	Se o estado inicial for também estado final em um autômato finito, então esse autômato
		
	
	não tem outros estados finais.
	
	não aceita a cadeia vazia.
	 
	aceita a cadeia vazia.
	
	é não determinístico. 
	
	é determinístico.
Questão 4
	A definiçãoformal 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:
		
	
	Five elements
	 
	quíntupla
	
	Mapeamento
	
	Autômato quinto
	
	Array
Questão 5
	Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde q0 representa  
		
	
	O número de estados
	 
	o estado inicial 
	
	as transições
	
	os simbolos de entrada
	
	o conjunto de estados finais
Questão 6
	Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde F representa  
		
	 
	o conjunto de estados finais
	
	os simbolos de entrada
	
	O número de estados
	
	o estado inicial 
	
	as transições
AULA 06
Questão 1
	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}
	
	{legal, ruim, legallegal, legalruim, ruimruim, legallegal}
	
	{legal, ruim, menino, menina}
	 
	{meninolegal, meninalegal, meninoruim meninaruim}
	
	{menino, menina, ruim, legal}
Questão 2
	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.
		
	 
	todas as igualdades são verdadeiras.
	
	somente a igualdade I é verdadeira.
	 
	somente as igualdades I e II são verdadeiras. 
	
	nenhuma das igualdades é verdadeira.
	
	somente as igualdades II e III são verdadeiras.
Questão 3
	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∗
Questão 4
	Seja Σ={a,b}. Uma expressão regular denotando a linguagem L = {w∈Σ∗ tal que toda ocorrência de "a" em w é imediatamente seguida de "b"} é:
		
	 
	(b+ab)∗
	
	 b+(ab)∗
	
	(a∗b)∗
	
	 a∗b
	
	(ab)∗
Questão 5
	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 
		
	
	L(R2) = {w | w termina com b}
	
	Se R3 é uma expressão regular tal que L(R3) = L(R1) ∩ L(R2), então L(R3) é uma linguagem infinita.2). 
	 
	Existe um autômato finito determinístico cuja linguagem é igual a L(R1) ∪ L(R2).
	
	L(R1) = L(r2) 
	
	Um autômato finito não determinístico que reconheça L(R1) ∪ L(R2) tem, pelo menos, quatro estados.
Questão 6
	Considere as seguintes afirmações sobre autômatos finitos 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 afirmativa correta:
		
	
	As afirmativas II e III são falsas
	
	As afirmativas I e II são verdadeiras
	 
	Apenas a afirmativa III é verdadeira
	
	As afirmativas I e III são falsas
	 
	As afirmativas I e III são verdadeiras
AULA 07
Questão 1
	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 I, II e IV.
	
	apenas as afirmativas II e IV.
	
	apenas as afirmativas I, II, III e IV.
	 
	 apenas as afirmativas I, II, III e V. 
	
	apenas as afirmativas II, III e V.
Questão 2
	Sobre a hierarquia de Chomsky podemos afirmar que: 
		
	 
	 Há linguagens que não são nem livres de contexto nem sensíveis ao contexto 
	
	 As linguagens reconhecidas por autômatos a pilha são as linguagens regulares
	
	Uma linguagem que é recursivamente enumerável não pode ser uma linguagem regular 
	
	 As linguagens livres de contexto e as linguagens sensíveis ao contexto se excluem 
	
	 Uma linguagem que não é regular é livre de contexto
Questão 3
	Para gerar o automâto finito mínimo  a partir um automâto finito o devemos  pelo algoritmo de minimização é necessario que:
		
	
	A função programa seja parcial
	
	A partir de uma estado existam  0, 1 ou n transições 
	
	Todos os estados sejam  alcançaveis a partir de qualquer outro estado
	
	Ele tenha destinos inalcançaveis
	 
	Ele seja  deterministico
Questão 4
	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 
		
	
	nenhuma das assertivas.
	 
	apenas as assertivas I e II. 
	
	apenas as assertivas I e III.
	
	apenas as assertivas II e III. 
	
	todas as assertivas.
Questão 5
	Seja a seguinte linguagem, onde ϵ representa a sentença vazia
SABCD→AB|CD→a|ϵ→b|f→c|g→h|i
Qual o conjunto de terminais que podem começar sentenças derivadas de S?
		
	
	{a,b,f,c,g,h,i} 
	
	{a,b,f}
	
	{a,c,g}
	
	{a,c,g,h,i} 
	 
	{a,b,f,c,g}
Questão 6
	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 I, II e IV.
	
	apenas as afirmativas II, III e V. 
	
	apenas as afirmativas II e IV. 
	
	apenas as afirmativas I, II, III e IV. 
	 
	apenas as afirmativas I, II, III e V.
AULA 08
Questão 1
	No que concerne a utilização e o processamento de máquina de Turing, assinale a opção correta. 
		
	
	A máquina em questão registra o valor da palavra de entrada e depois pára, quando a função indicar um movimento da cabeça para a esquerda e ela já se encontrar no início da fita. 
	
	As saídas podem ser apenas binárias, pois as referidas máquinas trabalham com representações lógicas. 
	
	O conjunto de símbolos usados pela máquina de Turing é infinito. 
	
	Uma máquina de Turing pode alterar várias entradas em cada vez, pois ela é capaz de transferir sua atenção para mais de uma posição da fita em cada argumento da função de transição. 
	 
	Na máquina de Turing, o processamento inclui a sucessiva aplicação da função programada até ocorrer uma condição de parada. 
Questão 2
	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, 
		
	
	existe algoritmo exato de tempo de execução exponencial para solucioná-lo. 
	
	 não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução polinomial que o soluciona, fornecendo respostas aproximadas. 
	
	 não existe algoritmo exato, mas existealgoritmo de aproximação de tempo de execução exponencial que o soluciona, fornecendo respostas aproximadas. 
	
	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.
Questão 3
	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
		
	
	irregulares. 
	
	regulares. 
	
	livres do contexto. 
	 
	sem restrição. 
	
	sensíveis ao contexto. 
Questão 4
	Na máquina de turing o componente que contem o estado corrente da máquina é: 
		
	
	A fita
	
	A memoria
	 
	A unidade de controle 
	
	O programa
	
	O processador
Questão 5
	Considere a máquina de Turing descrita pelas seguintes  regras, iniciando no estado q0:
(q0, 0)  (q0, 0, D)
(q0, 1)  (q1, 0, D)
(q2, 0)  (q2, 1, D)
O que essa máquina faz?
		
	 
	Anda para a direita até encontrar um 1, substitui por 0 e para. 
	
	Substitui todos os 0¿s por 1¿s na fita.
	
	Substitui todos os 1¿s por 0¿s na fita. 
	
	Anda para a direita indefinidamente, sem modificar a fita.
	
	Para assim que encontrar um 0.
Questão 6
	Qual das seguintes afirmações é falsa? 
		
	
	 O problema da parada é indecidível. 
	 
	 Não existe autômato finito determinístico que reconheça alguma linguagem livre de contexto. 
	
	Um autômato com duas pilhas pode ser simulado por uma máquina de Turing. 
	
	 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 algoritmo que determina quando uma gramática livre de contexto arbitrária é ambígua.
AULA 09
Questão 1
	Considere a gramática G definida pelas regras de produção abaixo, em que os símbolos não-terminais são S, A e B, e os símbolos terminais são a e b. 
S -> AB
AB -> AAB
A -> a
B -> b
Com relação a essa gramática, é correto afirmar que
		
	
	a cadeia aabbb é gerada por essa gramática.
	
	a gramática G é ambígua.
	
	a gramática G é uma gramática livre de contexto.
	
	a gramática G gera a cadeia nula.. 
	 
	é possível encontrar uma gramática regular equivalente a G.
Questão 2
	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 infinitos
	
	Autômatos finitos
	
	Expressões regulares
	 
	Gramáticas livres-do-contexto
	
	Pilha
Questão 3
	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
		
	
	I e III.
	
	III e IV. 
	 
	II e IV.
	 
	II.
	
	I.
Questão 4
	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 regular. 
	
	Uma gramática sensível a contexto que não é gramática livre de contexto
	
	Uma gramática livre de contexto que não é gramática regular
	
	Uma gramática do tipo 0 que não é gramática sensível a contexto.
	
	Uma gramática sem categorização possível e que gera a coleção das palíndromas em {0,1} exclusivamente de tamanho par.
Questão 5
	Em uma gramática sensível ao contexto definida por  G = {V, T, P, S} o P significa?
		
	
	Um símbolo especial escolhido aparte de V denominado inicial
	
	Conjunto finito de símbolos ou variáveis Não-Terminais
	 
	Regras de produção da forma
	
	Uma palavra ¿final¿, composta dos símbolos terminais 
	
	Conjunto finito de símbolos terminais DISJUNTOS
Questão 6
	Em uma gramática sensível ao contexto definida por  G = {V, T, P, S} o que  T significa?
		
	
	Conjunto finito de símbolos ou variáveis Não-Terminais
	
	Uma palavra ¿final¿, composta dos símbolos terminais 
	 
	Conjunto finito de símbolos terminais DISJUNTOS
	
	Um símbolo especial escolhido aparte de V denominado inicial
	
	Regras de produção da forma
AULA 10
Questão 1
	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. A descoberta 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, mas a II não é uma justificativa correta da I. 
	
	As asserções I e II são proposições falsas. 
	
	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. 
	 
	 As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
Questão 2
	Analise o custo computacional dos algoritmos a seguir, que calculam o valor de um polinômio de grau n, da forma: P(x) = an xn+an-1 + xn-1+ ... +a1x + a0, onde os coeficientes são números de ponto flutuante armazenados no vetor a[0..n], e o valor de n é maior que zero. Todos os coeficientes podem assumir qualquer valor, exceto o coeficiente an que é diferente de zero.
Algoritmo 1:
soma = a[0]
Repita para i = 1 até n
Se a[i] ≠ 0.0 então
potencia = x
Repita para j = 2 até i
potencia = potência * x
Fim repita
soma = soma + a[i] * potencia
 Fim se
Fim repita
Imprima (soma)
Algoritmo 2:
soma = a[n]
Repita para i = n-1 até 0 passo -1
soma = soma * x + a[i]
Fim repita
Imprima (soma)
Com base nos algoritmos 1 e 2, avalie as asserções a seguir e a relação proposta entre elas.
I. Os algoritmos possuem a mesma complexidade assintótica.
PORQUE
II. Para o melhor caso, ambos os algoritmos possuem complexidade O(n).
A respeito dessas asserções, assinale a opção correta.
		
	
	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. 
	 
	A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
	
	As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
	
	A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
Questão 3
	Qual das complexidades abaixo é a menor?
		
	
	O(log n)
	 
	O (n)
	
	O (2n)
	
	O (n3)
	
	O (n2)
Questão 4
	O problema P versus NP é um problema ainda não resolvido e um dos mais estudados em Computação. Em inhas gerais, deseja-se saber se todo problema cuja solução pode ser eficientemente verificada por um computador, também pode ser eficientemente obtida por um computador. Por ¿eficientemente¿ ou ¿eficiente¿ significa ¿em tempo polinomial¿.
A classe dos problemas cujas soluções podem ser eficientemente obtidas por um computador é chamada de classe P. Os algoritmos que solucionam os problemas dessa classe têm complexidade de pior caso polinomial no tamanho das suas entradas.
Para alguns problemas computacionais, não se conhece solução eficiente, isto é, não se conhece algoritmo eficiente para resolvê-los. No entanto, se para uma dada solução de um problema é possível verificá-la eficientemente, então o problema é dito estar em NP. Dessa forma, a classe de problemas para os quais suas soluções podem ser eficientemente verificadas é chamada de classe NP.
Um problema é dito ser NP-completo se pertence à classe NP e, além disso, se qualquer outro problema na classe NP pode ser eficientementetransformado nesse problema. Essa transformação eficiente envolve as entradas e saídas dos problemas.
Considerando as noções de complexidade computacional apresentadas acima, analise as afirmações que se seguem.
I. Existem problemas na classe P que não estão na classe NP.
II. Se o problema A pode ser eficientemente transformado no problema B e B está na classe P,
então A está na classe P.
III. Se P = NP, então um problema NP-completo pode ser solucionado eficientemente.
IV. Se P é diferente de NP, então existem problemas na classe P que são NP-completos.
É correto apenas o que se afirma em
		
	
	 IV.
	 
	 I e III..
	
	 I.
	 
	 II e III.
	
	 II e IV.
Questão 5
	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
		
	 
	 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. 
	
	A solução do problema é obtida em tempo de ordem O(nlogn), utilizando um algoritmo ótimo de ordenação. 
	
	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. 
	
	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.