Baixe o app para aproveitar ainda mais
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
Compartilhar