AS I e II e III e IV e VComplexibilidade de algorítmo

Prévia do material em texto

PERGUNTA 1
1. 
 
	
	a.
	100000
	
	b.
	111010
	
	c.
	101010
	
	d.
	010101
	
	e.
	000000
0,2 pontos   
PERGUNTA 2
1. 
 
	
	a.
	 aabbab;
	
	b.
	 aaaabb;
	
	c.
	aaabbb;
	
	d.
	 aabbab;
	
	e.
	 abbbbb.
0,2 pontos   
PERGUNTA 3
1. 
 
	
	a.
	aabbbbb;
	
	b.
	  abbbbba;
	
	c.
	  aabbbba.
	
	d.
	  aaabaaa;
	
	e.
	 aaaaaaa;
0,2 pontos   
PERGUNTA 4
1. QUESTÃO ANULADA, POR FAVOR, ESCOLHA QUALQUER UMA DAS ALTERNATIVAS PARA GANHAR OS PONTOS DA QUESTÃO. 
QUESTÃO ANULADA, POR FAVOR, ESCOLHA QUALQUER UMA DAS ALTERNATIVAS PARA GANHAR OS PONTOS DA QUESTÃO.
 
	
	a.
	11001
	
	b.
	10101
	
	c.
	ϵ.
	
	d.
	σ;
	
	e.
	δ
PERGUNTA 1
1. 
 
	
	a.
	
	
	b.
	
	
	c.
	
	
	d.
	
	
	e.
	
0,2 pontos   
PERGUNTA 2
1. Sobre algoritmos de ordenação, analise as seguintes afirmações.
 
I. Melhor caso é quando a instância de entrada já está ordenada e não será necessário realizar nenhuma troca de posições entre os elementos.
II. Pior caso é quando uma instância de entrada tem seus elementos posicionados na ordem inversa daquela que desejamos, ou seja, os elementos estão organizados em ordem decrescente.
III. Considerando-se o algoritmo Insertion Sort, o seu tempo de execução é representado pela função , no melhor caso.
IV. O caso médio, comumente, tem quase o mesmo comportamento do pior caso.
 
É CORRETO o que se afirma APENAS em:
 
	
	a.
	  II, III e IV.
	
	b.
	  I, III e IV.
	
	c.
	  I, II e III.
	
	d.
	 I, II e IV.
	
	e.
	  II e III.
 
0,2 pontos   
PERGUNTA 3
1. Sobre a área de análise de algoritmos, considere as seguintes afirmações.
 
I. A análise de complexidade de algoritmos é referente ao estudo do tempo que os algoritmos gastam para produzir uma saída.
II. A análise de computabilidade de algoritmos é referente ao estudo de recursos de hardware que são demandados pelos algoritmos.
III. O tempo gasto por um algoritmo está associado a uma constante que representa o custo da instrução e a quantidade de vezes que a instrução será executada.
IV. O fator determinante para o número de vezes que uma instrução é executada é o tamanho da instância de entrada.
 
É CORRETO o que se afirma APENAS em:
 
	
	a.
	  II, III e IV.
	
	b.
	  II e III.
 
 
	
	c.
	  I, III e IV.
	
	d.
	I, II e IV.
	
	e.
	  I, II e III.
0,2 pontos   
PERGUNTA 4
1. Sobre a notação assintótica O (Big Oh), assinale a alternativa que apresenta a definição CORRETA para o conjunto de funções Ο(g(n)).
	
	a.
	
	
	b.
	
	
	c.
	
	
	d.
	
	
	e.
	
0,2 pontos   
Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para salvar todas as respostas.
PERGUNTA 1
1. Considere o seguinte texto e assinale a alternativa que preenche CORRETA e RESPECTIVAMENTE as lacunas.
 
“__________ que são realizadas uma única vez, ou seja, aquelas que __________, não impactam o tempo de execução do algoritmo. Veja que quando identificamos__________ que representa esse tempo de execução, consideramos somente __________ de maior grau, desconsiderando, assim, __________. Desse modo, uma instrução fora de um laço contabilizará __________ que, na classificação em termos de__________, será desconsiderado por não contribuir efetivamente na __________ da função.”
 
	
	a.
	  As constantes; não estão inseridas em laços; a variável; a função; instruções; um valor constante; notação assintótica; velocidade de crescimento.
	
	b.
	 As constantes; não estão inseridas em laços; a função; a variável; instruções; um valor constante; notação assintótica; velocidade de crescimento.
	
	c.
	  Instruções; não estão inseridas em laços; a função; a variável; as constantes; um valor constante; notação assintótica; velocidade de crescimento.
 
 
	
	d.
	  Instruções; não estão inseridas em laços; a variável; a função; as constantes; um valor constante; notação assintótica; velocidade de crescimento.
	
	e.
	 Instruções; não estão inseridas em laços; a variável; a função; as constantes; um valor constante; velocidade de crescimento; notação assintótica.
0,2 pontos   
PERGUNTA 2
1. Considere o seguinte texto e assinale a alternativa que preenche CORRETA e RESPECTIVAMENTE as lacunas.
 
“A existência de __________ é uma observação que deve chamar nossa atenção. A primeira característica importante a ser observada em um laço é __________ que ele irá __________ que o compõem. Comumente, _________ está ligada __________.”
 
 
	
	a.
	 execução dos laços; a existência de laços nos algoritmos; executar pelo tamanho das instâncias de entrada; a quantidade de vezes; à execução das instruções.
	
	b.
	laços nos algoritmos; a quantidade de vezes; executar as instruções; a execução dos laços; ao tamanho da instância de entrada.
	
	c.
	 laços nos algoritmos; a execução dos laços; executar para as instruções; a quantidade de vezes; ao tamanho da instância de entrada.
	
	d.
	 laços nos algoritmos; o tamanho da instância de entrada; executar nos laços; a quantidade de vezes; à execução das instruções.
	
	e.
	  execução dos laços; a existência de laços nos algoritmos; executar em certa quantidade de vezes; a execução das instruções; ao tamanho da instância de entrada.
0,2 pontos   
PERGUNTA 3
1. Considere que o algoritmo BuscaBinaria() recebe, como parâmetros de entrada, V=[a,b,c,d,e,f,g], p=0, q=6 e x=d. Nesse contexto, o valor que será retornado pelo algoritmo é:
	
	a.
	 4.
	
	b.
	 a.
	
	c.
	 d.
	
	d.
	 3.
	
	e.
	  5.
 
0,2 pontos   
PERGUNTA 4
1. O algoritmo que utiliza o método da intercalação, conhecido por Merge Sort, é um algoritmo mais eficiente que, por exemplo, o Bubble Sort. Nesse contexto, o procedimento Merge() gasta tempo proporcional a Θ(n), com n=r-p+1, isso significa que o procedimento Merge() tem tempo de execução igual a Θ(n)
	
	a.
	 para o melhor caso, apenas.
	
	b.
	 para o pior caso, apenas.
	
	c.
	 seja qual for o caso.
	
	d.
	  para o pior caso e para o caso médio, apenas.
 
	
	e.
	  para o caso médio, apenas.
PERGUNTA 1
1. Considerando as técnicas de projeto de algoritmos, um algoritmo é considerado completo quando atende a determinada característica. Assim, assinale a alternativa que apresenta CORRETAMENTE o conceito de algoritmo completo.
 
	
	a.
	 Um algoritmo é considerado completo quando as instruções que o compõem são perfeitamente compreendidas pelo destinatário.
	
	b.
	  Um algoritmo é considerado completo quando as instruções que o compõem são organizadas sem que haja aninhamento de laços.
	
	c.
	  Um algoritmo é considerado completo quando as instâncias de um problema são resolvidas em qualquer complexidade de tempo.
	
	d.
	 Um algoritmo é considerado completo quando as instâncias de um problema são resolvidas por ele em tempo ótimo.
	
	e.
	  Um algoritmo é considerado completo quando as instruções que o compõem são únicas, sem que haja redundância de tarefas.
 
0,2 pontos   
PERGUNTA 2
1. Considerando a análise da técnica de divisão e conquista, considere o seguinte texto e assinale a alternativa que preenche CORRETA e RESPECTIVAMENTE as lacunas.
 
“Quando comparamos o algoritmo recursivo de Fibonacci e o algoritmo de ordenação Merge Sort, é possível observar diferenças fundamentais, apesar de ambos utilizarem __________. Cada __________, no Merge Sort, resolve __________, ou seja, são __________ do mesmo problema. Isso não ocorre com o Fibonacci, que computa __________ diversas vezes, podendo gerar ineficiência. Além disso, a __________ de problemas pela abordagem da __________ não ocorre de forma trivial, como é o caso do cálculo do fatorial.”
 
	
	a.
	 divisão e conquista; metade do problema; chamada recursiva; instâncias diferentes; as mesmas instâncias; recursão; redução.
	
	b.
	 recursão; chamada recursiva; metade do problema; instâncias diferentes; as mesmas instâncias; redução; divisão e conquista.
	
	c.
	 divisão e conquista; metade do problema; chamada recursiva; as mesmas instâncias; instâncias diferentes; recursão; redução.
 
	
	d.
	  redução; metade do problema; chamada recursiva; instâncias diferentes; as mesmas instâncias; recursão; divisão e conquista.e.
	redução; chamada recursiva; metade do problema; instâncias diferentes; as mesmas instâncias; recursão; divisão e conquista.
0,2 pontos   
PERGUNTA 3
1. Sobre as técnicas de projeto de algoritmos, analise as seguintes afirmações.
 
2. 
I. O refinamento é caracterizado pelo desdobramento das instruções de um algoritmo em instruções mais específicas.
II. O limite a ser considerado para o refinamento de algoritmos depende das características do destinatário.
III. Os algoritmos iterativos são aqueles que possibilitam uma comunicação entre o usuário e o próprio algoritmo.
IV. Os algoritmos interativos são aqueles que repetem determinados blocos de instruções diversas vezes.
 
É CORRETO o que se afirma APENAS em:
 
	
	a.
	  II e IV.
 
 
	
	b.
	  I e IV.
	
	c.
	  I e III.
	
	d.
	  I e II.
	
	e.
	  II e III.
0,2 pontos   
PERGUNTA 4
1. Considere o seguinte texto e assinale a alternativa que preenche CORRETA e RESPECTIVAMENTE as lacunas.
 
“__________ podem consumir__________, para os casos nos quais existam__________. Cada __________é empilhada e fica aguardando até que o __________seja atingido. Assim, podemos ter __________ na memória, o que pode ser um problema a depender da__________.”
 
	
	a.
	 Várias chamadas empilhadas; uma grande quantidade de memória; muitas chamadas recursivas; chamada; caso base; algoritmos recursivos; quantidade de memória disponível.
	
	b.
	  Os algoritmos recursivos; muitas chamadas recursivas; uma grande quantidade de memória; chamada; caso base; várias chamadas empilhadas; quantidade de memória disponível.
 
	
	c.
	 Os algoritmos recursivos; uma grande quantidade de memória; muitas chamadas recursivas; chamada; caso base; várias chamadas empilhadas; quantidade de memória disponível.
	
	d.
	 Muitas chamadas recursivas; uma grande quantidade de memória; várias chamadas empilhadas; chamada; caso base; algoritmos recursivos; quantidade de memória disponível.
	
	e.
	 Os algoritmos recursivos; uma grande quantidade de memória; várias chamadas empilhadas; chamada; caso base; muitas chamadas recursivas; quantidade de memória disponível.
1. 
Considere o texto a seguir e assinale a alternativa que completa CORRETA e RESPECTIVAMENTE as lacunas.
 
“Uma __________ é o conjunto de __________ que são reconhecidas por uma __________; assim, dizemos que uma linguagem é __________ se alguma máquina de Turing a reconhece. Quando uma máquina de Turing está computando uma __________, podemos ter três resultados sobre ela, a máquina pode aceitar ou rejeitar a entrada, ou ainda nunca parar (entrar em looping).”
 
	
	a.
	  entrada; cadeias; máquina de Turing; Turing-reconhecível; linguagem.
	
	b.
	 máquina de Turing; cadeias; entrada; Turing-reconhecível; linguagem.
	
	c.
	  linguagem; cadeias; máquina de Turing; Turing-reconhecível; entrada.
	
	d.
	 máquina de Turing; cadeias; linguagem; Turing-reconhecível; entrada.
	
	e.
	entrada; cadeias; Turing-reconhecível; máquina de Turing; linguagem.
 
 
0,2 pontos   
PERGUNTA 2
1. Considere o texto a seguir e assinale a alternativa que completa CORRETA e RESPECTIVAMENTE as lacunas.
 
“Os __________ recebem __________, o primeiro é __________, que é representada por __________ que compõem __________ reconhecida pelo __________, e o segundo argumento é uma __________ o algoritmo.”
 
 
	
	a.
	 dois argumentos; dois algoritmos de verificação; a cadeia de entrada; todas as cadeias; a linguagem; algoritmo; cadeia que certificará.
	
	b.
	 dois argumentos; todas as cadeias; a linguagem; algoritmos de verificação; a cadeia de entrada; algoritmo; cadeia que certificará.
	
	c.
	 dois argumentos; dois algoritmos de verificação; a linguagem; todas as cadeias; a cadeia de entrada; algoritmo; cadeia que certificará.
	
	d.
	 algoritmos de verificação; dois argumentos; a linguagem; todas as cadeias; a cadeia de entrada; algoritmo; cadeia que certificará.
	
	e.
	algoritmos de verificação; dois argumentos; a cadeia de entrada; todas as cadeias; a linguagem; algoritmo; cadeia que certificará.
 
0,2 pontos   
PERGUNTA 3
1. Analise as seguintes afirmações.
 
2. 
I. Um polinômio é uma expressão algébrica que é composta por monômios e por operadores aritméticos. Um monômio apresenta em sua constituição um coeficiente que multiplica uma variável. O grau de um polinômio é definido pelo maior coeficiente que multiplica uma variável.
II. Um algoritmo de tempo polinomial é aquele que tem seu tempo de execução proporcional a Ο (kn)para o pior caso. Assim, n representa o tamanho da entrada (instância) do algoritmo e k é alguma constante;
III. Os problemas que podem ser resolvidos com um algoritmo de tempo polinomial são definidos como problemas tratáveis; caso contrário, são definidos como intratáveis.
IV. A classe P é aquela que reúne problemas que têm solução em tempo polinomial em uma máquina de Turing determinística.
 
É CORRETO o que se afirma APENAS em:
	
	a.
	II e IV.
	
	b.
	 III e IV.
	
	c.
	 I e II.
	
	d.
	  I e IV.
	
	e.
	  I e III.
0,2 pontos   
PERGUNTA 4
1. Um algoritmo de verificação poderia verificar, em tempo polinomial, se um grafo é ou não hamiltoniano. Nesse caso, o algoritmo receberia o grafo a ser verificado e uma lista ordenada de vértices que compõem o ciclo hamiltoniano. Nesse contexto, assinale a alternativa que descreve CORRETAMENTE um grafo hamiltoniano.
 
	
	a.
	 Um grafo é hamiltoniano se ele possuir um ciclo simples com todas as arestas do grafo.
	
	b.
	 Um grafo é hamiltoniano se ele possuir um ciclo alternado com todas as arestas do grafo.
 
	
	c.
	 Um grafo é hamiltoniano se ele possuir um ciclo completo com todas as arestas do grafo.
	
	d.
	 Um grafo é hamiltoniano se ele possuir um ciclo simples com todos os vértices do grafo.
	
	e.
	  Um grafo é hamiltoniano se ele possuir um ciclo completo com todos os vértices do grafo.
PERGUNTA 2
1. A classe de problemas que chamamos de NP, em referência a tempo superpolinomial, reúne os problemas cuja solução não pode ser obtida em tempo polinomial. Outra forma de definir a classe NP é como um conjunto de problemas que podem ser verificáveis em tempo polinomial. Veja que há uma diferença entre resolver e verificar um problema. Nesse contexto, analise as seguintes afirmações.
 
2. 
I. Um algoritmo que encontra um ciclo hamiltoniano em um grafo está resolvendo o problema.
II. Um algoritmo que encontra um ciclo hamiltoniano em um grafo está verificando o problema.
III. Um algoritmo que recebe uma lista de vértices e retorna 1 caso os vértices componham um ciclo hamiltoniano em um grafo está verificando o problema.
IV. Um algoritmo que recebe uma lista de vértices e retorna 1 caso os vértices componham um ciclo hamiltoniano em um grafo está resolvendo o problema.
 
É CORRETO o que se afirma APENAS em:
 
	
	a.
	  II e IV.
	
	b.
	 I e III.
	
	c.
	  I e IV.
	
	d.
	  III e IV.
 
 
	
	e.
	 II e III.