Buscar

N2 (A5)_ algoritimoprova

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes
Você viu 3, do total de 9 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes
Você viu 6, do total de 9 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes
Você viu 9, do total de 9 páginas

Prévia do material em texto

27/09/23, 10:21 N2 (A5): Revisão da tentativa
https://ambienteacademico.com.br/mod/quiz/review.php?attempt=2621458&cmid=778672 1/9
Iniciado em quarta, 21 jun 2023, 13:38
Estado Finalizada
Concluída em quarta, 21 jun 2023, 14:07
Tempo
empregado
28 minutos 47 segundos
Avaliar 7,00 de um máximo de 10,00(70%)
Questão 1
Correto
Atingiu 1,00 de 1,00
Umas das aplicações da notação Theta (Θ) é estabelecer uma métrica para comparação de funções. Com isso, um dado conjunto de
funções pode ser ordenado de maneira a identi�car aquelas que têm maior e menor crescimento assintótico.
Considerando o seguinte conjuntos de funções:
     Assinale a alternativa que apresenta a ordenação correta de forma crescente das funções, em termos da notação Theta.
a. .
b. .
c. .
d.  Resposta correta. Como n é linear no seu crescimento, a função 1/n decresce
rapidamente, o que a torna a função com menor limite assintótico, seguida da
função constante 17. Na sequência, como log(n ) = 20log(n) é Θ(log(n)), temos que
ela cresce a uma taxa inferior que seu quadrado, log (n). Logo, log(n ) e log (n)
são as próximas. Para a de�nição das duas últimas funções, é preciso perceber
que  cresce a uma taxa superior que log(n). Então, temos que
Portanto, as duas últimas funções são  nesta
ordem.
e. .
20
2 20 2
A resposta correta é: 
Guia Digital Carreiras e Internacionalização NAP CPA Responsabilidade Socioambiental
Minhas Disciplinas Minhas Bibliotecas
 DD 
https://codely-fmu-content.s3.amazonaws.com/Moodle/GuiaDigital/Guia+digital/index.html
https://carreiras.fmu.br/
https://codely-fmu-content.s3.amazonaws.com/Moodle/NAP/inicial/nap/fmu/index.html
https://codely-fmu-content.s3.amazonaws.com/Moodle/CPA/landing_CPA/index.html
https://portal.fmu.br/sustentabilidade
https://ambienteacademico.com.br/
https://ambienteacademico.com.br/
https://ambienteacademico.com.br/course/view.php?id=236
27/09/23, 10:21 N2 (A5): Revisão da tentativa
https://ambienteacademico.com.br/mod/quiz/review.php?attempt=2621458&cmid=778672 2/9
Questão 2
Correto
Atingiu 1,00 de 1,00
Saber analisar uma recorrência a partir da descrição de um dado problema, é importante para a correta avaliação da complexidade do
algoritmo que será projetado. E o entendimento de como cada subproblema é expandido deve ser parte integrante dessa análise.
Considere um algoritmo recursivo que, dada uma entrada de tamanho n, divide a entrada em 2 (dois) subproblemas de tamanho n/2,
resolve cada um recursivamente e, por �m, combina as duas partes em um tempo O(n).
Em relação ao comportamento recursivo e ao limite assintótico desse algoritmo, analise as a�rmativas a seguir (o tempo de execução
do algoritmo para uma entrada de tamanho n será denotado por T(n)).
I. A árvore de recursão gerada pelo algoritmo terá tamanho log (n).
II. Cada nível k da árvore de recursão é composto por 2 subproblemas.
III. O algoritmo tem complexidade da ordem de O(nlog )
IV. A recursão pode ser descrita pela função T(n) = T(2 ) + n.
Está correto apenas o que se a�rma em:
a. II e III.
b. I e II.
c. II e IV.
d. I,
II
e
III.
 Resposta correta. Seja k = {1, 2, …, K} denotar os níveis da árvore de recursão. Neste caso, k = 1 corresponde ao
problema original de tamanho n, k = 2 é o primeiro nível da recursão com dois subproblemas de tamanho n/2 e,
seguindo a expansão, no nível K, teremos 2 subproblemas, cada um com tamanho n/2 e, no nível K, os
subproblemas terão tamanho 1. Isso quer dizer que a altura da árvore será dada por log (n). A recursão pode ser
descrita pela função T(n) = 2T(n/2) + O(n). Logo, os subproblemas serão de tamanho 1. Após K ≤ log (n), níveis
recursivos e o tempo para resolver cada subproblema de tamanho 1 será de O(1). Além disso, para um subproblema
de tamanho n, há o tempo extra de combinação O(n). Então, no nível de recursão k, haverá o custo extra de 2 ×
O(n/2 ) = O(n). Portanto, a complexidade do algoritmo será de T(n) = O(nlog(n)).
e. III e IV.
2
k
2
n
k k
2
2
k
k
A resposta correta é: I, II e III.
Guia Digital Carreiras e Internacionalização NAP CPA Responsabilidade Socioambiental
Minhas Disciplinas Minhas Bibliotecas
 DD 
https://codely-fmu-content.s3.amazonaws.com/Moodle/GuiaDigital/Guia+digital/index.html
https://carreiras.fmu.br/
https://codely-fmu-content.s3.amazonaws.com/Moodle/NAP/inicial/nap/fmu/index.html
https://codely-fmu-content.s3.amazonaws.com/Moodle/CPA/landing_CPA/index.html
https://portal.fmu.br/sustentabilidade
https://ambienteacademico.com.br/
https://ambienteacademico.com.br/
https://ambienteacademico.com.br/course/view.php?id=236
27/09/23, 10:21 N2 (A5): Revisão da tentativa
https://ambienteacademico.com.br/mod/quiz/review.php?attempt=2621458&cmid=778672 3/9
Questão 3
Incorreto
Atingiu 0,00 de 1,00
Questão 4
Correto
Atingiu 1,00 de 1,00
O teorema mestre constitui uma poderosa ferramenta para a solução de recorrências. No entanto, a aplicação de um dos casos
previstos por ele depende de a recorrência estar em determinado formato e satisfazer um certo conjunto de condições.
Considerando a recorrência T(n) = 2T(n/4) + 1, analise as a�rmativas a seguir e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s).
I. ( ) As constantes a e b, que compõem o termo , têm valores 4 e 2, respectivamente.
II. ( ) A recorrência é limitada superiormente por 
III. ( ) O tempo de execução relativo aos passos de combinação da recorrência é da ordem de Θ(n).
IV. ( ) O primeiro caso do teorema mestre pode ser aplicado, já que uma constante ε = 0,5 pode ser empregada.
Agora, assinale a alternativa que apresenta a sequência correta.
a. V, V, F, F.
b. F, F, V,
V.
 Resposta errada. Identi�que os termos que compõem a recorrência em seu formato padrão e aplique o caso
adequado do teorema mestre.
c. V, F, V, F.
d. V, V, F, V.
e. F, V, F, V.
A resposta correta é: F, V, F, V.
Soluções fechadas para recursões podem ser validadas pelo método da substituição. Esse método depende da identi�cação de
constantes positivas, que possam ser usadas para delimitar a função cujo comportamento está sendo analisado.
Nesse cenário, analise as asserções a seguir e a relação proposta entre elas.
I. A recorrência T(n) = 2T(n/2) + n é limitada superiormente por O(nlog(n)).
Porque:
II. É possível de�nir uma constante positiva c, que torna verdadeira a desigualdade 2c(n/2)log(n/2) + n ≤ cnlog(n/2) + n.
A seguir, assinale a alternativa correta:
a. As asserções I e II são proposições verdadeiras, mas a II não é uma justi�cativa correta da I.
b. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
c. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
d. As asserções I e II são proposições falsas.
e. As asserções I e II são proposições verdadeiras, e a II é uma
justi�cativa correta da I.
 Resposta correta. A veri�cação pode ser feita
como segue:
T(n)                 ≤ cnlog(n)
                        ≤ 2cn(n/2)(log(n/2)) + n      
                        ≤ cnlog(n/2) + n       
                        = cnlog(n) - cnlog(2) + n    
                        = cnlog(n) + (1 - c)n
                        ≤ cnlog(n)
A resposta correta é: As asserções I e II são proposições verdadeiras, e a II é uma justi�cativa correta da I.
Guia Digital Carreiras e Internacionalização NAP CPA Responsabilidade Socioambiental
Minhas Disciplinas Minhas Bibliotecas
 DD 
https://codely-fmu-content.s3.amazonaws.com/Moodle/GuiaDigital/Guia+digital/index.html
https://carreiras.fmu.br/
https://codely-fmu-content.s3.amazonaws.com/Moodle/NAP/inicial/nap/fmu/index.html
https://codely-fmu-content.s3.amazonaws.com/Moodle/CPA/landing_CPA/index.html
https://portal.fmu.br/sustentabilidade
https://ambienteacademico.com.br/
https://ambienteacademico.com.br/
https://ambienteacademico.com.br/course/view.php?id=236
27/09/23, 10:21 N2 (A5): Revisão da tentativa
https://ambienteacademico.com.br/mod/quiz/review.php?attempt=2621458&cmid=778672 4/9
Questão 5
Correto
Atingiu 1,00 de 1,00
A comparaçãoprecisa, entre algumas funções, envolve um esforço para descobrir elementos intermediários, que podem ressaltar os
limites assintóticos procurados. Esse trabalho vai possibilitar o emprego da notação Theta de maneira precisa.
Sabe-se que a função log(n!) é limitada superiormente pela função nlog(n). Com base nisso, assinale a alternativa que indica uma
a�rmação verdadeira sobre a relação assintótica entre essas duas funções.
a. Uma constante c = ½ valida o limite assintótico inferior
de log(n!).
 Resposta certa. É preciso veri�car se log(n!) = Ω(nlog(n)). Então,
log(n!) = log (1 × 2 × … × n)
                        = log 1 + log 2 + … + log n
                        = log 1 + … + log n/2 + … + log n
                        ≥ log(n/2) + log(n/2 + 1) + … + log n (metade maior
da soma)
                        ≥ log(n/2) + log(n/2) + … + log(n/2)
                        = log(n/2 × n/2 × … × n/2) (n/2 vezes)
                        = log(n/2)
= (n/2)log(n/2)           (constante c = 1/2)
                        = Ω(nlog(n))
Portanto, log(n!) = Θ(nlog(n)).
b. Se log(n!) ≤ log(n/2) , então nlog(n) também limita log(n!) inferiormente.
c. A soma dos n/2 últimos termos de log(n!) é menor que log(n/2) ,
d. Como log(n!) = O(nlogn), então nlogn ≤ clog(n!) para algum c > 0.
e. O limite assintótico superior da soma das duas funções é O(nlog(n!)).
n/2
n/2
n/2
A resposta correta é: Uma constante c = ½ valida o limite assintótico inferior de log(n!).
Guia Digital Carreiras e Internacionalização NAP CPA Responsabilidade Socioambiental
Minhas Disciplinas Minhas Bibliotecas
 DD 
https://codely-fmu-content.s3.amazonaws.com/Moodle/GuiaDigital/Guia+digital/index.html
https://carreiras.fmu.br/
https://codely-fmu-content.s3.amazonaws.com/Moodle/NAP/inicial/nap/fmu/index.html
https://codely-fmu-content.s3.amazonaws.com/Moodle/CPA/landing_CPA/index.html
https://portal.fmu.br/sustentabilidade
https://ambienteacademico.com.br/
https://ambienteacademico.com.br/
https://ambienteacademico.com.br/course/view.php?id=236
27/09/23, 10:21 N2 (A5): Revisão da tentativa
https://ambienteacademico.com.br/mod/quiz/review.php?attempt=2621458&cmid=778672 5/9
Questão 6
Correto
Atingiu 1,00 de 1,00
Diversas estratégias são conhecidas para a ordenação de dados na memória principal. Uma delas é implementada pelo algoritmo
Merge Sort que usa uma abordagem de divisão e conquista. Seu comportamento assintótico pode ser descrito tendo como base o
número de comparações realizadas durante o processo de ordenação.
Nesse contexto, analise as asserções a seguir e a relação proposta entre elas.
I. O número de comparações realizadas pelo algoritmo Merge Sort pode ser delimitado tanto superior como inferiormente.
Porque:
II. Para um vetor de N posições, o seu processo de ordenação usa entre (1/2) NlogN e NlogN comparações.
a. As asserções I e II
são proposições
verdadeiras, e a II
é uma justi�cativa
correta da I.
 Resposta certa. Seja C(N) o número de comparações realizadas para ordenar um vetor de tamanho N.
Neste caso, C(0) = C(1) = 0 e, para N > 0, podemos escrever a seguinte relação de recorrência para o
limite superior:
C(N) ≤ C(⌊N/2⌋) + C(⌈N/2⌉) + N
O primeiro termo à direita corresponde ao número de comparações para ordenar a metade à
esquerda do vetor, o segundo termo é o número de comparações para ordenar a metade direita e o
terceiro termo é o número de comparações realizadas pela mesclagem. Tomando N = 2 , temos que
⌊N/2⌋ = ⌈N/2⌉ = 2 . Logo, C(2 ) ≤ 2C(2 ) + 2 . Dividindo ambos os lados por 2 temos C(2 )/2 ≤ C(2
)/2
+ 1. Expandindo a mesma equação para o primeiro termo à direita, temos C(2 )/2 ≤ C(2 )/2 + 1 +
1. Repetindo esse mesmo processo n -1 vezes, obtemos C(2 )/2 ≤ C(2 )/2 +n. Após multiplicar ambos
os lados por 2 , temos:
C(N) ≤ C(2 ) = n2
= NlogN.
Por outro lado, o limite inferior é dado por:
C(N) ≥ C(⌊N/2⌋) + C(⌈N/2⌉) + ⌊N/2⌋
já que o número de comparações pelo procedimento de mesclagem é, pelo menos, ⌊N/2⌋. De maneira
análoga ao limite superior, obtemos que:
C(N) ≥ (1/2)NlogN
b. As asserções I e II são proposições verdadeiras, mas a II não é uma justi�cativa correta da I.
c. As asserções I e II são proposições falsas.
d. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
e. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
n
n - 1 n n-1 n n n n n-
1 n-1
n n n-2 n-2
n n 0 0 
n
n n
A resposta correta é: As asserções I e II são proposições verdadeiras, e a II é uma justi�cativa correta da I.
Guia Digital Carreiras e Internacionalização NAP CPA Responsabilidade Socioambiental
Minhas Disciplinas Minhas Bibliotecas
 DD 
https://codely-fmu-content.s3.amazonaws.com/Moodle/GuiaDigital/Guia+digital/index.html
https://carreiras.fmu.br/
https://codely-fmu-content.s3.amazonaws.com/Moodle/NAP/inicial/nap/fmu/index.html
https://codely-fmu-content.s3.amazonaws.com/Moodle/CPA/landing_CPA/index.html
https://portal.fmu.br/sustentabilidade
https://ambienteacademico.com.br/
https://ambienteacademico.com.br/
https://ambienteacademico.com.br/course/view.php?id=236
27/09/23, 10:21 N2 (A5): Revisão da tentativa
https://ambienteacademico.com.br/mod/quiz/review.php?attempt=2621458&cmid=778672 6/9
Questão 7
Correto
Atingiu 1,00 de 1,00
Árvores de recursão podem ser empregadas para a obtenção de soluções assintoticamente justas para recorrências. Esses limites
são expressos por meio da notação Theta e oferecem um poderoso recurso para a análise do desempenho de algoritmos.
 
Considere a recursão T(n) = T(n – a) + T(a) + cn, onde a ≥ 1 e c > 0 são constantes, e assinale a alternativa que indica uma afirmação correta a
respeito de sua análise.
a. Tomando T(n) ≥ cn , T(n) = Ω(n ), se a for igual a 1.
b. Se T(n) ≤ cn , então T(n) = O(n ) para qualquer valor de a e n.
c. A recorrência pode ser classificada como homogênea.
d. A árvore de recursão
apresentará altura de
valor igual (n/a) + 1.
  O ( log n ).
Resposta correta. Como a cada nível da árvore o tamanho dos subproblemas é reduzido de a,
serão gerados (n/a) + 1 níveis até o fim da recorrência. Como a recorrência tem um termo
independente T(1), ela é classificada como heterogênea. Se T(n) ≤ cn , teremos
T(n) ≤ c(n – a) + ca + cn
 ≤ cn – 2can + ca + cn
 ≤ cn – c(2an - a – n) (para a < ½ e n > 2a)
 ≤ cn – cn
 ≤ cn
 ≤ O(n ).
Se, T(n) ≥ cn , temos
T(n) ≥ c(n – a) + ca + cn
 ≥ cn – 2can + ca + cn
 ≥ cn – c(2an - a – n) (para a < 1 e n > 2a)
 ≥ cn + cn
 ≥ cn
 = Ω(n ).
e. O custo de todos os nós (subproblemas) a cada nível é T(a).
2 2
2 2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
A resposta correta é:
A árvore de recursão apresentará altura de valor igual (n/a) + 1.
Guia Digital Carreiras e Internacionalização NAP CPA Responsabilidade Socioambiental
Minhas Disciplinas Minhas Bibliotecas
 DD 
https://codely-fmu-content.s3.amazonaws.com/Moodle/GuiaDigital/Guia+digital/index.html
https://carreiras.fmu.br/
https://codely-fmu-content.s3.amazonaws.com/Moodle/NAP/inicial/nap/fmu/index.html
https://codely-fmu-content.s3.amazonaws.com/Moodle/CPA/landing_CPA/index.html
https://portal.fmu.br/sustentabilidade
https://ambienteacademico.com.br/
https://ambienteacademico.com.br/
https://ambienteacademico.com.br/course/view.php?id=236
27/09/23, 10:21 N2 (A5): Revisão da tentativa
https://ambienteacademico.com.br/mod/quiz/review.php?attempt=2621458&cmid=778672 7/9
Questão 8
Incorreto
Atingiu 0,00 de 1,00
A análise de complexidade do método de ordenação por inserção direta leva a duas funções distintas, dependendo do caso analisado.
No pior caso, o domínio assintótico é dado pela função f(n) = (n – n)/2; enquanto que, no melhor caso, a função é g(n) = n – 1.
Com base nessas funções e levando em conta as de�nições relacionadasà notação Ômega, responda: por que é possível a�rmar que
f(n) = Ω(g(n))?
a. Porque qualquer que seja o valor de n, a função g(n) sempre assumirá um valor inferior à função g(n).
b. Porque a desigualdade n/2 ≥ c é válida para qualquer n maior que a constante c com valor 1.
c. Porque, como também é
verdadeiro que f(n) = O(g(n)),
então é válido a�rmar
inversamente que f(n) = Ω(g(n)).
 Resposta incorreta. Para identi�car a validade do limite assintótico, é fundamental
aplicar a de�nição da notação ômega para a relação entre as duas funções. Neste caso,
é preciso cuidar da escolha correta dos valores das constantes c e m, que fazem parte
da de�nição.
d. Porque, para qualquer valor de c
constante, temos que f(n) ≤ cg(n) para qualquer n > m com m positivo.
e. Porque, para uma constante c = 3, a desigualdade (n – n)/2 ≥ n - 1 é veri�cada para qualquer n≥ m com m positivo.
2
2
A resposta correta é: Porque a desigualdade n/2 ≥ c é válida para qualquer n maior que a constante c com valor 1.
Guia Digital Carreiras e Internacionalização NAP CPA Responsabilidade Socioambiental
Minhas Disciplinas Minhas Bibliotecas
 DD 
https://codely-fmu-content.s3.amazonaws.com/Moodle/GuiaDigital/Guia+digital/index.html
https://carreiras.fmu.br/
https://codely-fmu-content.s3.amazonaws.com/Moodle/NAP/inicial/nap/fmu/index.html
https://codely-fmu-content.s3.amazonaws.com/Moodle/CPA/landing_CPA/index.html
https://portal.fmu.br/sustentabilidade
https://ambienteacademico.com.br/
https://ambienteacademico.com.br/
https://ambienteacademico.com.br/course/view.php?id=236
27/09/23, 10:21 N2 (A5): Revisão da tentativa
https://ambienteacademico.com.br/mod/quiz/review.php?attempt=2621458&cmid=778672 8/9
Questão 9
Correto
Atingiu 1,00 de 1,00
A análise do comportamento assintótico de funções é uma técnica comumente utilizada para a avaliação do desempenho de
algoritmos. Uma maneira de      expressar as relações identi�cadas neste tipo de análise é por meio da notação O. O uso dessa notação
estabelece uma métrica objetiva para comparação entre algoritmos.
Considerando essas informações e o conteúdo estudado, analise as a�rmativas de acordo com essa técnica utilizada para indicar um
limite superior para funções.
I. 2 = O(2 )
II. Se f(n) = O(h(n)) e g(n) = O(h(n)), então f(n) + g(n) = O(h(n)).
III. n /10 = O(n)
IV. 6n = O(n )
Está correto apenas o que se a�rma em:
a. I e III.
b. III e IV.
c. I
e
II.
 Resposta correta. Para veri�car que a a�rmativa I está correta, basta tomar uma constante c que garanta a
desigualdade 2 ≤ c2 . Se escolhermos c = 2, temos que 2 
 ≤ 2 é sempre verdadeiro. A a�rmativa II também pode ser veri�cada, considerando válidas as desigualdades f(n) ≤
ch(n) com n > m, e g(n) ≤ c’h(n) com n > m’, e assumindo c e c’
constantes positivas. Neste caso, teremos que f(n) + g(n) ≤ (c + c’)h(n), com n > max{m, m’}. Logo, f(n) + g(n) = O(h(n)).
d. II e III.
e. II e IV.
n+1 n
2
3 2
n+1 n+1
n+1
A resposta correta é: I e II.
Guia Digital Carreiras e Internacionalização NAP CPA Responsabilidade Socioambiental
Minhas Disciplinas Minhas Bibliotecas
 DD 
https://codely-fmu-content.s3.amazonaws.com/Moodle/GuiaDigital/Guia+digital/index.html
https://carreiras.fmu.br/
https://codely-fmu-content.s3.amazonaws.com/Moodle/NAP/inicial/nap/fmu/index.html
https://codely-fmu-content.s3.amazonaws.com/Moodle/CPA/landing_CPA/index.html
https://portal.fmu.br/sustentabilidade
https://ambienteacademico.com.br/
https://ambienteacademico.com.br/
https://ambienteacademico.com.br/course/view.php?id=236
27/09/23, 10:21 N2 (A5): Revisão da tentativa
https://ambienteacademico.com.br/mod/quiz/review.php?attempt=2621458&cmid=778672 9/9
Questão 10
Incorreto
Atingiu 0,00 de 1,00
Veri�car que determinada operação ou a�rmação matemática é válida para qualquer valor positivo é uma técnica muito utilizada para
garantir os corretos procedimentos computacionais. Assim, depois do projeto de certo algoritmo de ordenação, observou-se que a
contagem do número de comparações feitas para ordenar um vetor de n posições poderia ser descrita pelo somatório:
Com base nessas informações, analise as a�rmativas a respeito da aplicação da técnica de indução matemática para veri�car a validade
dessa contagem, para qualquer valor n positivo, e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s).
I. ( ) Pelo uso da hipótese de indução com n = k e k > 0, a seguinte expressão intermediária pode ser obtida: k + 2( k + 1) – 1.
II. ( ) No passo de indução, o uso da hipótese indutiva depende de uma expansão que decremente o índice do somatório.
III. ( ) Tomando como caso base n = 0, a demonstração pode ser desenvolvida a partir da hipótese de indução.
IV. ( ) Para validar o somatório tendo como passo de indução n = k +1 e k> 0, é preciso concluir que a soma será dada por k +1.
Agora, assinale a alternativa que apresenta a sequência correta.
a. V, V, F, F.
b. F,
V,
F,
V.
 Resposta incorreta. Nesta técnica, é fundamental observar os valores que se deseja obter, tanto com a de�nição do
caso base como com a aplicação do passo de indução. Em ambos os casos, é preciso concluir que o valor do somatório
é comprovado pelos valores de�nidos para n.
c. V, V, F, V.
d. V, F, V, F.
e. F, F, V, V.
2
A resposta correta é: V, V, F, F.
◄ Revisão Atividade 4 (A4)
Seguir para...
Revisão Prova N2 (A5) ►
Guia Digital Carreiras e Internacionalização NAP CPA Responsabilidade Socioambiental
Minhas Disciplinas Minhas Bibliotecas
 DD 
https://ambienteacademico.com.br/mod/quiz/view.php?id=778671&forceview=1
https://ambienteacademico.com.br/mod/quiz/view.php?id=778674&forceview=1
https://codely-fmu-content.s3.amazonaws.com/Moodle/GuiaDigital/Guia+digital/index.html
https://carreiras.fmu.br/
https://codely-fmu-content.s3.amazonaws.com/Moodle/NAP/inicial/nap/fmu/index.html
https://codely-fmu-content.s3.amazonaws.com/Moodle/CPA/landing_CPA/index.html
https://portal.fmu.br/sustentabilidade
https://ambienteacademico.com.br/
https://ambienteacademico.com.br/
https://ambienteacademico.com.br/course/view.php?id=236

Continue navegando

Outros materiais