Prévia do material em texto
13/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-14790.01 https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_670514_1 1/8 Pergunta 1 Resposta Selecionada: Resposta Correta: Comentário da resposta: 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 fim, combina as duas partes em um tempoO(n). Em relação ao comportamento recursivo e ao limite assintótico desse algoritmo, analise as afirmativas 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 log2(n). II. Cada nível k da árvore de recursão é composto por 2k subproblemas. III. O algoritmo tem complexidade da ordem de O(nlog2) IV. A recursão pode ser descrita pela função T(n) = T(2n) + n. Está correto apenas o que se afirma em: I, II e III. 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 2k subproblemas, cada um com tamanho n/2k e, no nível K, os subproblemas terão tamanho 1. Isso quer dizer que a altura da árvore será dada por log2(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 ≤ log2(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 2k × O(n/2k) = O(n). Portanto, a complexidade do algoritmo será de T(n) = O(nlog(n)). Pergunta 2 É comum que algoritmos sejam fracionados em múltiplos procedimentos que, quando executados de maneira conjunta, têm seus resultados parciais combinados para gerar a solução final. Essa divisão tem impacto direto no cálculo da complexidade do algoritmo. Um algoritmo ALG é composto de dois subalgoritmos ALGA e ALGB, que devem ser executados sequencialmente – ALGA seguido de ALGB. No entanto, dada uma função f(n), ambos 1 em 1 pontos 1 em 1 pontos 13/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-14790.01 https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_670514_1 2/8 Resposta Selecionada: Resposta Correta: Comentário da resposta: subalgoritmos podem ser otimizados de forma que ALGA rode a uma taxa de Θ(f(n)) e ALGB à taxa de Θ(n/f(n)). Considerando esse cenário, analise as asserções a seguir e a relação proposta entre elas. I. O tempo de execução geral de ALG pode ser minimizado através da escolha de uma função . Porque: II. Como ambos subalgoritmos ALGA e ALGB, são executados sequencialmente, a função vai apresentar a menor taxa de crescimento no algoritmo completo. As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. Resposta correta. Como os dois subalgoritmos são executados sequencialmente, o tempo de execução total de ALG será dado por Θ(f(n) + n/f(n)) = Θ(max{ f(n), n/f(n) }). Para que esse valor seja minimizado, é preciso definir f(n), de tal maneira que ambas as partes sejam iguais, ou seja: f(n)=n/f(n) →(f(n))^2=n→f(n)=√n Pergunta 3 Resposta Selecionada: Resposta Correta: 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 eficiência entre eles. Considerando as funções T1(n) = log2n + 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 eficiê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 asserção I é uma proposição falsa, e a II é uma proposição verdadeira. 1 em 1 pontos 13/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-14790.01 https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_670514_1 3/8 Comentário da resposta: A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. Resposta correta. É preciso observar que n = O(log2n + n). Adicionalmente, temos que verificar se log2n + n = O(n), ou seja, log2n + n ≤ cn, c > 0. Como log2n ≤ n (pois n ≤ 2n), temos que log2n + n ≤ 2n, tomando c = 2 e n ≥ 1. Portanto, T1(n) = Θ(T2(n)). Pergunta 4 Resposta Selecionada: Resposta Correta: Comentário da resposta: O limite assintótico de algoritmos recursivos pode ser estimado com boa precisão, através da modelagem via árvores de recursão. Para isso, os termos recursivos desempenham papel chave para o entendimento de como o algoritmo se comporta a cada iteração. Considerando que um algoritmo é modelado pela recursão T(n) = T(n/3) + T(2n/3) + cn, onde c é uma constante, analise as afirmativas a seguir. I. A árvore de recursão mostra que o custo de cada nível é cn. II. O limite assintótico inferior do algoritmo é Ω(nlog(n)). III. O caminho mais curto entre a raiz e um nó folha é log3(n). IV. O tamanho dos subproblemas decresce a um fator de 2/3. Está correto apenas o que se afirma em: I, II e III. I, II e III. Resposta correta. Como os termos recursivos são divididos por 3, cada subproblema tem seu tamanho decrementado a um fator de 3. Porém, cada nível tem um acréscimo de cn termos, o que corresponde ao custo de cada nível. Para a definição do limite inferior do custo do algoritmo temos, cn(log3(n)) + 1 ≥ cnlog3(n) = (c/log(3))nlog(n) = Ω(nlog(n)). Pergunta 5 Á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. 1 em 1 pontos 1 em 1 pontos 13/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-14790.01 https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_670514_1 4/8 Resposta Selecionada: Resposta Correta: Comentário da resposta: A árvore de recursão apresentará altura de valor igual (n/a) + 1. A árvore de recursão apresentará altura de valor igual (n/a) + 1. 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) ≤ cn2, teremos T(n) ≤ c(n – a)2 + ca + cn ≤ cn2 – 2can + ca + cn ≤ cn2 – c(2an - a – n) (para a < ½ e n > 2a) ≤ cn2 – cn ≤ cn2 ≤ O(n2). Se, T(n) ≥ cn2, temos T(n) ≥ c(n – a)2 + ca + cn ≥ cn2 – 2can + ca + cn ≥ cn2 – c(2an - a – n) (para a < 1 e n > 2a) ≥ cn2 + cn ≥ cn2 = Ω(n2). Pergunta 6 Resposta Selecionada: Soluções fechadas para recursões podem ser validadas pelo método da substituição. Esse método depende da identificaçãode 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 definir 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: As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. 1 em 1 pontos 13/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-14790.01 https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_670514_1 5/8 Resposta Correta: Comentário da resposta: As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. Resposta correta. A verificaçã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) Pergunta 7 Resposta Selecionada: Resposta Correta: Comentário da resposta: A eficácia do método de substituição tem dependência intrínseca da proposição de uma boa solução (bom “palpite”), para a recorrência, e a verificação da solução é feita por indução matemática. Neste caso, o caso base com o passo indutivo deve ser avaliado. Considerando a recorrência T(n) = T(n – 1) + T(n/2) + n, analise as afirmativas a seguir e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s). I. ( ) O limite assintótico superior de T(n) é O(2n). II. ( ) Se T(n) ≤ c2n – 4n, então T(n) ≤ c(2n – 1 + 2n/2) – 4n, para n ≥ 0 e c > 0. III. ( ) O limite assintótico inferior de T(n) é Ω(n2) IV. ( ) Se T(n) ≥ cn2 e c ≤ ½, então T(n) ≤ cn2 + (1 – 2c)n + c. Agora, assinale a alternativa que apresenta a sequência correta: V, F, V, F. V, F, V, F. ~ Resposta correta. Supondo que T(n) ≤ c2n – 4n para c > 0, temos pelo método da substituição: T(n) ≤ c2n-1 – 4(n – 1) + c2n/2 - 4n/2 + n = c(2n – 1 + 2n/2) – 5n + 4 (para n ≥ 1/4) ≤ c(2n – 1 + 2n/2) – 4n (para n ≥ 2) = c(2n – 1 + 2n - 1) – 4n ≤ c2n – 4n = O(2n) Agora, supondo T(n) ≥ cn2 pelo método da substituição, temos: T(n) = c(n – 1)2 + c(n/2)2 + n = cn2 – 2cn + c + cn2/4 + n = (5/4)cn2 + (1 – 2c)n + c ≥ cn2 + (1 – 2c)n + c (para c ≤ ½) 1 em 1 pontos 13/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-14790.01 https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_670514_1 6/8 ≥ cn2 = Ω(n2) Pergunta 8 Resposta Selecionada: Resposta Correta: Comentário da resposta: Um dos métodos amplamente utilizados para a solução de recorrências é conhecido como o método da substituição. Sua aplicação é baseada na proposição de uma solução fechada para a recorrência, seguida de uma validação dessa solução. Considerando o uso desse método para verificar se O(n2) é solução para a recorrência T(n) = T(n - 1) + n, analise as afirmativas a seguir. I. Após a construção da desigualdade inicial, o próximo passo envolve a avaliação de n na solução proposta. II. Um dos passos da resolução envolve a avaliação de uma diferença, elevada à potência de 2, entre dois termos. III. A aplicação do método se inicia com a construção da desigualdade T(n) ≤ c(n2 – n), onde c > 0. IV. A conclusão da aplicação do método é que a solução proposta resolve a recorrência em questão. Está correto apenas o que se afirma em: II e IV. II e IV. Resposta correta. A aplicação do método implica nos seguintes passos: T(n) = T(n – 1) + n ≤ c(n – 1)2 + n = cn2 – 2cn + c + n = cn2 – n(2c – 1) + c ≤ O(n2) Logo, O(n2) é solução para a recorrência. Pergunta 9 A definição do limite assintótico auxilia no entendimento sobre como as funções delimitam umas às outras, superior e/ou inferiormente. No entanto, há relações em que a identificação das constantes que cauterizam esses limites demanda manipulações algébricas mais elaboradas. Supondo r e s inteiros não-negativos, com r < s, e tomando c ≠ 0, o seguinte resultado é comprovadamente verdadeiro: . A partir dessas informações, analise as afirmativas a seguir e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s). 1 em 1 pontos 1 em 1 pontos 13/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-14790.01 https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_670514_1 7/8 Resposta Selecionada: Resposta Correta: Comentário da resposta: I. ( ) A partir da desigualdade ns ≤ ns + cnr, é possível atestar que ns = O(ns + cnr) para c > 0. II. ( ) A validade da relação é condição para que o limite ns = O(ns + ns + cnr) seja verificado. III. ( ) O limite assintótico ns + cnr = O(ns) é verificado tanto para r < s como para s < r. IV. ( ) Se c < 0, então ns + cnr = O(ns) para qualquer que seja o valor assumido porn. Agora, assinale a alternativa que apresenta a sequência correta: V, V, F, F. V, V, F, F. ~ Resposta correta. Primeiro, vamos considerar o caso c > 0. Para n ≥ 0, temos ns ≤ ns + cnr e, portanto, ns = O(ns + cnr). Por outro lado, como r < s, para qualquer n ≥ 0, temos que ns + cnr e ≤ ns + cns = (1 + c)ns, portanto ns + cnr = O(ns). Agora, é preciso considerar o caso c < 0. Então, para n ≥ 0, temos que cnr e ≤ 0 e, portanto, ns + cnr ≤ ns, implicando em ns + cnr = O(ns). Por outro lado, sabendo que , temos ns – r ≥ -2c > 0, implicando em ns – r + 2c ≥ 0. Logo, ns < ns+ nr(ns – r + 2c) = 2(ns + cnr), e, portanto, ns = O(ns + cnr). Pergunta 10 Resposta Selecionada: Resposta Correta: Comentário da resposta: 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 identificar 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. {1/n,17,log(n^20 ),〖log〗^2 (n),n^2 √n,n^3/log(n) }. {1/n,17,log(n^20 ),〖log〗^2 (n),n^2 √n,n^3/log(n) }. 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, 1 em 1 pontos 13/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-14790.01 https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_670514_1 8/8 como log(n20) = 20log(n) é Θ(log(n)), temos que ela cresce a uma taxa inferior que seu quadrado, log2(n). Logo, log(n20) e log2(n) são as próximas. Para a definiçã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.