AO2 - Complexidade de Algoritmos - NOTA 4.2 de 6.0

Prévia do material em texto

AO2
Iniciado: 4 dez em 10:24
Instruções do teste
Importante:
Caso você esteja realizando a atividade através do aplicativo "Canvas Student", é necessário que
você clique em "FAZER O QUESTIONÁRIO", no final da página.
0,6 ptsPergunta 1
Leia o texto a seguir:
Algumas linguagens de programação, como o Python, possibilitam o
desenvolvimento de códigos utilizando estruturas de armazenamento de dados
chamada vetores ou arrays. O objetivo desse tipo de estrutura é armazenar mais
de um valor em uma região de memória. Veja um exemplo de desenvolvimento
de código utilizando um vetor:
Considerando o código apresentado, qual a técnica mais eficiente para realizar a
pesquisa do número 6 neste vetor?
Utilizar o algoritmo de quick sort e, em seguida, busca binária.
Utilizar o algoritmo de busca binária.
Utilizar o algoritmo de busca sequencial.
Utilizar o algoritmo de quick sort e, em seguida, busca sequencial.
Utilizar o algoritmo de merge sort e, em seguida, busca binária.
A+
A
A-
NOTA: 4.2 de 6.0
0,6 ptsPergunta 2
Leia o texto e observe o código-fonte a seguir:
Em Python, podemos utilizar os operadores aritméticos para manipular os dados
de variáveis, bem como realizar cálculos - assim como na matemática.
Considerando as informações apresentadas, avalie as seguintes asserções e a
relação proposta entre elas.
I. O algoritmo apresentado tem a complexidade de tempo O(1), sendo
considerada a complexidade de tempo mais eficiente.
PORQUE
II. Ao executar um algoritmo no tempo O(1), não importa o valor do elemento que
você está pedindo para a função imprimir, apenas uma etapa é necessária.
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
da I.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
As asserções I e II são proposições falsas.
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
0,6 ptsPergunta 3
Leia o texto a seguir:
A+
A
A-
Um algoritmo é uma lista passo a passo de instruções usadas para executar uma
tarefa final. Um bom engenheiro de software considerará a complexidade do
tempo ao planejar seu programa. Desde o início, um engenheiro deve considerar
um cenário que seu programa pode encontrar e que exigirá mais tempo para ser
concluído. Isso é conhecido como a complexidade de tempo do pior caso de um
algoritmo.
Considerando as informações apresentadas, avalie as seguintes asserções e a
relação proposta entre elas.
I. O tempo de execução de uma tarefa constante não mudará,
independentemente de qual seja o valor de entrada, sendo representada por
O(n), onde O é chamado de Big O.
PORQUE
II. A notação Big O é a métrica mais comum para calcular a complexidade do
tempo.
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
da I.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
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 falsas.
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
0,6 ptsPergunta 4
Leia o texto e observe o código a seguir:
Em Python e em outras linguagens de programação, para que seja possível
manipular dados uma das necessidades é criar variáveis que armazenem
temporariamente valores, os quais podem ser numéricos (int ou float), textos
(string) ou booleanos (bool).
A+
A
A-
Qual a classe de complexidade de tempo do algoritmo apresentado?
O(log n) – Complexidade Logarítmica.
O(n²) – Complexidade Quadrática.
O(n) – Complexidade Linear.
O(1) – Complexidade Constante.
O(2n) – Complexidade Exponencial.
0,6 ptsPergunta 5
Leia o texto e observe o pseudocódigo a seguir:
Um algoritmo é uma sequência finita de instruções que podem ser representadas
de maneira declarativa, por meio de fluxogramas ou em um pseudocódigo, por
exemplo. Essa sequência de instruções pode ser mais longa ou mais curta e
pode ser alterada preservando a essência do algoritmo, ou seja, mantendo seu
propósito.
Considerando as informações apresentadas, assinale a alternativa correta:
O algoritmo executará 7 instruções e, para diminuir esse valor, basta colocar um
“else if” substituindo a segunda instrução “se” (na linha 6).
A+
A
A-
O algoritmo executará 5 instruções e, para diminuir esse valor, basta remover uma
das linhas de instruções do tipo escreva.
O algoritmo executará 4 instruções e, para diminuir esse valor, basta colocar um
“else” substituindo a segunda instrução “se” (na linha 6).
O algoritmo executará 5 instruções e, devido às características do algoritmo, torna-se
inviável diminuir o número de instruções.
O algoritmo executará 5 instruções e, para diminuir esse valor, basta colocar um
“else” substituindo a segunda instrução “se” (na linha 6).
0,6 ptsPergunta 6
Leia com atenção a definição a seguir.
A programação dinâmica é uma técnica que divide os problemas em
subproblemas e salva o resultado para fins futuros, para que não precisemos
computar o resultado novamente. Os subproblemas são desenvolvidos para
otimizar a solução geral, o que é conhecida como propriedade de subestrutura
ótima. O principal uso da programação dinâmica é resolver problemas de
otimização. Aqui, problemas de otimização significam quando estamos tentando
descobrir a solução mínima ou máxima de um problema.
Considerando as informações apresentado, avalie as afirmações a seguir:
I. A programação dinâmica divide o problema complexo em subproblemas mais
simples, encontrando a solução para esses subproblemas e armazenando a
solução em memória.
II. A complexidade de tempo e a complexidade de espaço aumentam com o uso
da programação dinâmica, ao contrário do que vemos nos algoritmos de força
bruta.
III. As principais abordagens da programação dinâmica são Top-Down e Bottom-
Up.
É correto o que se afirma em: 
I e II, apenas.
I, apenas.
II, apenas.
III, apenas.
I e III, apenas.
A+
A
A-
0,6 ptsPergunta 7
Leia a descrição a seguir.
Digamos que queremos pesquisar um número específico em um array. Considere
que essa estrutura de dados possuí 20 números e, dentre eles, queremos
encontrar o número 100. Nesse exemplo, pesquisar 20 números não é um
problema. Mas imagine que estamos lidando com conjuntos de dados que
armazenam informações de perfil de milhões de usuários. Pesquisar cada valor
de índice do início ao fim seria muito ineficiente. Especialmente se tiver que ser
feito várias vezes.
Considerando as informações apresentadas, avalie as afirmações a seguir:
I. Em uma pesquisa sequencial, cada rodada de pesquisa consiste em um
conjunto de dados menor que o anterior. 
II. Um algoritmo logarítmico que realiza uma pesquisa binária examina as duas
metades de um conjunto de dados.
III. A complexidade logarítmica log n trata de um tipo de algoritmo que torna a
computação incrivelmente mais rápida que a complexidade linear.
IV. Localizar uma palavra em um dicionário possui a mesma complexidade de
tempo que um algoritmo de busca binária.
É correto o que se afirma em:
II e III, apenas.
III e IV, apenas.
II e IV, apenas.
I e II, apenas.
I e IV, apenas.
0,6 ptsPergunta 8
Leia o texto a seguir:
A+
A
A-
Em uma época em que o poder computacional nos cerca, é fácil se confundir com
a ideia de que a informação é processada e entregue como mágica. O
processamento é algo tão rápido que às vezes esquecemos que milhões de
cálculos por segundo estão sendo feitos entre o momento em que solicitamos a
informação e o momento em que ela é entregue.
Considerando as informações apresentadas, avalie as afirmações a seguir:
I. Cada instrução de um algoritmo deve ser executada em uma ordem específica
para resolver um problema computacional ou não.
II. A complexidade de tempo em uma taxa exponencial significa que, a cada etapa
que a função executa, a próxima etapa será executadamais rapidamente.
III. A notação Big O ou Big Ômega é a métrica mais comum para calcular a
complexidade do tempo, juntamente com Big Teta.
IV. Um algoritmo de complexidade quadrática requer uma quantidade de tempo
ou execução e instruções igual ao quadrado de seu valor de entrada.
É correto o que se afirma em:
I, III e IV apenas.
I e IV, apenas.
III e IV, apenas.
II e III, apenas.
I e II, apenas.
0,6 ptsPergunta 9
Leia o texto a seguir:
A técnica de divisão e conquista é dividida em três etapas. Na primeira (dividir), é
realizada a divisão do problema em subproblemas menores. Na segunda
(conquistar), os subproblemas são resolvidos por chamadas recursivas até a
completa resolução. Por fim, os subproblemas são combinados para obter a
solução final de todo o problema.
Considerando as informações apresentadas, analise as asserções a seguir e a
relação proposta entre elas.
I. O algoritmo Merge Sort divide o vetor em duas metades, ordenando-as
recursivamente e, finalmente, mescla as duas metades ordenadas. Sua
complexidade de tempo é O(n log n).
A+
A
A-
PORQUE
II. A eficiência e a baixa complexidade de tempo do Merge Sort ocorrem graças
ao algoritmo que escolhe um elemento central chamado pivô, o qual ajuda a
reorganizar os elementos do vetor.
A respeito dessas asserções, assinale a alternativa correta:
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 falsas.
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 verdadeiras, e a II é uma justificativa correta
da I.
0,6 ptsPergunta 10
Leia o texto a seguir:
Do ponto de vista da complexidade computacional, existem alguns tipos de
problemas para os quais não existem algoritmos eficientes para resolvê-los. A
maioria desses problemas tem um algoritmo que fornece uma solução, e esse
algoritmo é a busca de força bruta. Esse algoritmo, no entanto, não fornece uma
solução eficiente e, portanto, não é viável para computação com nada mais do
que a menor entrada. A razão pela qual não há algoritmos eficientes para esses
problemas é que esses problemas estão todos em uma categoria que poderia ser
chamada de “um pouco menos que aleatório”. Eles são próximos do aleatório, de
fato, ainda que não permitam nenhum algoritmo significativo além do de força
bruta.
Considerando as informações apresentadas, assinale a alternativa correta.
Problemas Intratáveis, os quais geralmente requerem tempos exponenciais de
processamento, não podem ser resolvidos dentro de um tempo aceitável.
Problemas Insolúveis, os quais dificilmente serão resolvidos em um tempo
polinomial, não podem ser resolvidos dentro de um tempo aceitável.
Problemas Tratáveis, como aqueles de complexidade NP e NP-Hard, não podem ser
resolvidos dentro de um tempo aceitável.
A+
A
A-
Salvo em 23:09 
Problemas Heurísticos, os quais são resolvidos utilizando heurísticas e técnicas de
força bruta, não podem ser resolvidos dentro de um tempo aceitável.
Problemas de Parada, os quais geralmente requerem tempos polinomiais de
processamento, não podem ser resolvidos dentro de um tempo aceitável.
Enviar teste
A+
A
A-