Prova N2 (A5)_ Analise de algoritmos FMU

Prévia do material em texto

26/06/2023, 09:50 Prova N2 (A5): Revisão da tentativa
https://ambienteacademico.com.br/mod/quiz/review.php?attempt=2667570&cmid=920845 1/7
Iniciado em sexta, 23 jun 2023, 15:29
Estado Finalizada
Concluída em sexta, 23 jun 2023, 15:51
Tempo
empregado
22 minutos 9 segundos
Avaliar 4,00 de um máximo de 10,00(40%)
Questão 1
Correto
Atingiu 1,00 de 1,00
A comparação precisa, 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. Se log(n!) ≤ log(n/2) , então nlog(n) também limita log(n!) inferiormente.
b. Como log(n!) = O(nlogn), então nlogn ≤ clog(n!) para algum c > 0.
c. 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)).
d. O limite assintótico superior da soma das duas funções é O(nlog(n!)).
e. A soma dos n/2 últimos termos de log(n!) é menor que log(n/2) ,
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
 SA 
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
26/06/2023, 09:50 Prova N2 (A5): Revisão da tentativa
https://ambienteacademico.com.br/mod/quiz/review.php?attempt=2667570&cmid=920845 2/7
Questão 2
Incorreto
Atingiu 0,00 de 1,00
Questão 3
Incorreto
Atingiu 0,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. F, F, V, V.
b. V, V,
F, F.
 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, V, F, V.
d. F, V, F, V.
e. V, F, V, F.
A resposta correta é: F, V, F, V.
Funções de recorrência podem ser exploradas com várias manipulações algébricas de forma a encontrar uma solução fechada. Isso é
particularmente importante para a descrição do comportamento assintótico de algoritmos. No entanto, é fundamental saber
reconhecer semelhanças e diferenças entre elas.
Considerando a relação de recorrência a seguir, indique a alternativa correta a respeito dela:
.                   T(1) = 1
.                   T(n) = T(n - 1) + 3
a. O caso base da relação tem complexidade linear.
b. O termo independente da relação pode ser substituído por n , sem interferência no seu comportamento assintótico.
c. A relação tem limite assintótico
superior O(n ).
 Resposta incorreta. Aplique a de�nição de recursão e analise o signi�cado de cada
termo que compõe esse tipo de função.
d. A relação pode ser classi�cada como homogênea.
e. O k-ésimo termo da relação é da forma T(n - k) + 3k.
3
2
A resposta correta é: O k-ésimo termo da relação é da forma T(n - k) + 3k.
Guia Digital Carreiras e Internacionalização NAP CPA Responsabilidade Socioambiental
Minhas Disciplinas Minhas Bibliotecas
 SA 
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
26/06/2023, 09:50 Prova N2 (A5): Revisão da tentativa
https://ambienteacademico.com.br/mod/quiz/review.php?attempt=2667570&cmid=920845 3/7
Questão 4
Correto
Atingiu 1,00 de 1,00
Questão 5
Incorreto
Atingiu 0,00 de 1,00
A descrição da complexidade de um algoritmo, por meio da notação Theta, é geralmente obtida a partir da análise feita sobre os passos
executados por ele. No entanto, nem sempre o código implementado está acessível, nem os detalhes do algoritmo são conhecidos. Em
casos assim, é preciso observar o seu desempenho, quando submetido a entradas de diferentes tamanhos. Considere a seguinte tabela
contendo os dados coletados dos tempos de execução de um algoritmo.
Assinale a alternativa que apresente a melhor aproximação do comportamento assintótico do algoritmo, em termos da notação Theta.
a. Θ(log(n)).
b. Θ(n).
c. Θ(1).
d. Θ(n ). Resposta correta. Cada vez que a entrada tem o seu tamanho dobrado de tamanho, o tempo de execução do
algoritmo aumenta a um fator de, aproximadamente, 4. Então, dentre as opções disponíveis, a ordem assintótica
mais próxima para o algoritmo é Θ(n ).
e. Θ(n ).
2
2
3
A resposta correta é: Θ(n ).2
Embora existam outros métodos que podem ser aplicados para a obtenção de soluções fechadas para recorrências, o teorema mestre
oferece uma maneira direta para se resolver esse tipo de função, considerando que certas condições sejam satisfeitas.
A respeito da recorrência T(n) = 4T(n/2) + n , assinale a alternativa que indica a a�rmativa correta sobre sua solução.
a. A desigualdade af(n/b) ≤ cf(n) pode ser satisfeita se o valor 1
for utilizado na constante c, o que possibilita o emprego do
terceiro caso do teorema.
 Resposta incorreta. Identi�que os termos da recorrência
em seu formato padrão e aplique o caso adequado do
teorema mestre.
b. A condição de f(n) ser limitado inferiormente é condição su�ciente para a aplicação do terceiro caso do teorema.
c. O uso do teorema leva à aplicação do seu terceiro caso, o que implica T(n) apresentar um comportamento assintótico de n .
d. Como f(n) < , o primeiro caso do teorema mestre pode ser aplicado.
e. Uma constante ε = -1 pode ser utilizada para tornar a igualdade , o que possibilita o uso do segundo caso do teorema.
3
3
A resposta correta é: O uso do teorema leva à aplicação do seu terceiro caso, o que implica T(n) apresentar um comportamento
assintótico de n .3
Guia Digital Carreiras e Internacionalização NAP CPA Responsabilidade Socioambiental
Minhas Disciplinas Minhas Bibliotecas
 SA 
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.htmlhttps://portal.fmu.br/sustentabilidade
https://ambienteacademico.com.br/
https://ambienteacademico.com.br/
https://ambienteacademico.com.br/course/view.php?id=236
26/06/2023, 09:50 Prova N2 (A5): Revisão da tentativa
https://ambienteacademico.com.br/mod/quiz/review.php?attempt=2667570&cmid=920845 4/7
Questão 6
Incorreto
Atingiu 0,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 II.
b. I e III.
c. III e IV.
d. II
e
IV.
 Resposta incorreta. Para veri�car cada limite assintótico, é preciso lembrar que a de�nição f(n) = O(g(n)) corresponde
à desigualdade f(n) ≤ cg(n) para uma constante c > 0 e n > m > 0. As alternativas selecionadas contém a�rmações de
limites assintóticos que não podem ser comprovadas pela desigualdade gerada a partir da de�nição.
e. II e III.
n+1 n
2
3 2
A resposta correta é: I e II.
Guia Digital Carreiras e Internacionalização NAP CPA Responsabilidade Socioambiental
Minhas Disciplinas Minhas Bibliotecas
 SA 
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
26/06/2023, 09:50 Prova N2 (A5): Revisão da tentativa
https://ambienteacademico.com.br/mod/quiz/review.php?attempt=2667570&cmid=920845 5/7
Questão 7
Correto
Atingiu 1,00 de 1,00
O cálculo de complexidade é parte essencial do projeto e da análise de algoritmos. Uma ferramenta chave usada nesta atividade é a
notação Theta (Θ). Ela oferece uma maneira objetiva de descrever o comportamento assintótico de algoritmos e possibilita a
comparação da e�ciência entre eles.
Considerando as funções T1(n) = log n + n e T2(n) = n, analise as asserções a seguir e a relação proposta entre elas.
I. Um algoritmo A2 com uma complexidade T2 tem uma e�ciência computacional melhor que um algoritmo A1 com complexidade T1.
Porque:
II. A função T1 tem limite assintótico dado por T1(n) = Θ(T2(n)).
A seguir, assinale a alternativa correta.
a. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
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 verdadeiras, e a II é uma justi�cativa correta da I.
d. A asserção I é uma
proposição falsa, e a II é
uma proposição
verdadeira.
 Resposta correta. É preciso observar que n = O(log n + n). Adicionalmente, temos que veri�car
se log n + n = O(n), ou seja, log n + n ≤ cn, c > 0. Como log n ≤ n (pois n ≤ 2 ), temos que log n +
n ≤ 2n, tomando c = 2 e n ≥ 1. Portanto, T1(n) = Θ(T2(n)).
e. As asserções I e II são proposições falsas.
2
2
2 2 2
n
2
A resposta correta é: A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
Guia Digital Carreiras e Internacionalização NAP CPA Responsabilidade Socioambiental
Minhas Disciplinas Minhas Bibliotecas
 SA 
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
26/06/2023, 09:50 Prova N2 (A5): Revisão da tentativa
https://ambienteacademico.com.br/mod/quiz/review.php?attempt=2667570&cmid=920845 6/7
Questão 8
Correto
Atingiu 1,00 de 1,00
O desempenho no pior caso de um algoritmo pode ser descrito por meio do uso da notação de complexidade assintótica. Esse é o
caso de algoritmos que solucionam problemas de tamanho n, que tem seu tamanho reduzido a cada iteração.
 
Analise o algoritmo a seguir:
Algoritmo A
Entrada: Inteiro de valor positivo
Saída: Valor 1 se o valor informado for 1
1. se n = 1 então
2. retornar 1
3. senão
4. retornar 2 × A(n/2) + 1
 
Considerando essas informações e o algoritmo apresentado, analise as afirmativas a seguir e assinale V para a(s) verdadeira(s) e
F para a(s) falsa(s).
 
I. ( ) A solução fechada da recorrência para o algoritmo pode ser descrita pela função T(n) = (n – 1) + c, em que c é uma constante
positiva.
II. ( ) O algoritmo gera subproblemas, cujos tamanhos são ¼ do tamanho do subproblema da iteração anterior.
III. ( ) O algoritmo tem como chamada recursiva um comando que gera subproblemas de tamanho n/2.
IV. ( ) O limite superior da recorrência que descreve o algoritmo pode ser expressa por T(n) = O(log(n)).
 
Agora, assinale a alternativa que apresenta a sequência correta:
a. F, V, F, V.
b. V, V, F, V.
c. V, F, V, F.
d. V, V, F, F.
e. F,
F,
V,
V.
 Resposta correta. Este algoritmo tem como recursão uma chamada a “A(n/2)”, ou seja, a solução de um problema de
tamanho igual a n é reduzida à solução de um problema de tamanho igual a n/2 mais algum tempo constante - k ,
para multiplicar o resultado por 2 e somar 1. A solução do problema para o caso base é resolvido em um tempo
constante - k . Assim, a relação de recorrência que descreve o comportamento do algoritmo pode ser descrita pela
seguinte função: T(n) = 2T(n/2) + k (em que k é constante) e T(1) = k (em que k é constante).  Supondo que T(n) = O
( log n ), pelo método da substituição temos
T(n)     ≤ 2log(n/2) + k 
            = 2(log(n) - log 2) + k 
            = 2 log(n) - 2 + k (k   <  2)
≤ 2log(n)
= O( log n )
Logo, a solução da relação de recorrência é T(n) = O ( log n ).
1
2
1 1 2 2 
1
1
1       1
A resposta correta é: F, F, V, V.
Guia Digital Carreiras e Internacionalização NAP CPA Responsabilidade Socioambiental
Minhas Disciplinas Minhas Bibliotecas
 SA 
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
26/06/2023, 09:50 Prova N2 (A5): Revisão da tentativa
https://ambienteacademico.com.br/mod/quiz/review.php?attempt=2667570&cmid=920845 7/7
Questão 9
Incorreto
Atingiu 0,00 de 1,00
Questão 10
Incorreto
Atingiu 0,00 de 1,00
O algoritmo Quick Sort é considerado um dos mais e�cientes na operação de ordenação de dados em memória principal. Um aspecto
crítico do algoritmo é a escolha do elemento para atuar como pivô em cada iteração. Essa escolha tem impacto direto na e�ciência do
algoritmo. Considerando as seguintes modi�cações no algoritmo:
.                    A estratégia de escolha do pivô é a seleção do elemento na primeira posição do vetor;
.                    A primeira posição do vetor tem índice zero;
.                    Ao término da iteração (cruzamento dos índices), o pivô é trocado com o elemento na posição atual do índice iniciado na
extremidade à direita do vetor.
Considerando essas informações e conteúdo estudado, assinale a alternativa correta a respeito da execução do Quick Sort sobre o
vetor 5, 3, 1, 9,8, 2, 4, 7.
a. O elemento 5 sofre duas mudanças de posição até alcançar a posição de�nitiva.
b. Após a ordenação da metade à esquerda do vetor, a metade à direita já se encontra ordenada.
c. Na primeira iteração, são feitas três trocas de posições de elementos.
d. O elemento 2 é o último pivô escolhido
durante a ordenação da metade à
esquerda do vetor original.
 Resposta errada. Execute o passo-a-passo de ordenação do algoritmo
considerando a nova política de escolha do elemento pivô e identi�que as trocas
de posições que acontecem a cada iteração.
e. As metades à esquerda e à direita do vetor demandam o mesmo número de chamadas recursivas para serem ordenadas.
A resposta correta é: Na primeira iteração, são feitas três trocas de posições de elementos.
O algoritmo de ordenação por inserção direta é baseado no aninhamento de dois laços, que vão, a cada iteração, conduzindo a chave
de maior valor para a sua posição correta. Considere o seguinte vetor, que precisa ser ordenado via inserção direta:
15        5          4          18        12        19        14        10        8          20
Indique a alternativa que apresenta o vetor parcialmente ordenado após os quatro primeiros passos dos algoritmos terem sido
executados.  
a. 15  5  4  10  12  8  14  18  19  20.
b. 15  5  4  18  12  19  14  8  10  20.
c. 4  5  8 
10  12 
14  15 
18  19 
20.
 Resposta incorreta. Para acompanhar o processo de ordenação do algoritmo, �que atento à forma como as
chaves são movimentadas da direita para a esquerda. Essa movimentação é incremental, começando da posição
2 e, a cada iteração, uma chave mais à direita é considerada para ser deslocada para sua posição mais à
esquerda.
d. 4  5  12  15  18  19  14  10  8  20.
e. 4  5  15  18  12  19  14  10  8  20.
A resposta correta é: 4  5  12  15  18  19  14  10  8  20.
Guia Digital Carreiras e Internacionalização NAP CPA Responsabilidade Socioambiental
Minhas Disciplinas Minhas Bibliotecas
 SA 
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