Baixe o app para aproveitar ainda mais
Prévia do material em texto
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: V, V, F, F. V, V, F, V. V, F, V, F. F, F, V, V. F, V, F, V. 1 pontos PERGUNTA 2 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. {17,1/n,log(n^20 ),〖log〗^2 (n),n^2 √n,n^3/log(n) }. {1/n,17,log(n^20 ),〖log〗^2 (n),n^3/log(n) ,n^2 √n}. {1/n,17,〖log〗^2 (n),log(n^20 ),n^2 √n,n^3/log(n) }. {17,1/n,log(n^20 ),〖log〗^2 (n),n^3/log(n) ,n^2 √n}. {1/n,17,log(n^20 ),〖log〗^2 (n),n^2 √n,n^3/log(n) }. 1 pontos PERGUNTA 3 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: I e II. II e IV. III e IV. II e III. I e III. 1 pontos PERGUNTA 4 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 O termo independente da relação pode ser substituído por n3, sem interferência no seu comportamento assintótico. A relação pode ser classificada como homogênea. O k-ésimo termo da relação é da forma T(n – k) + 3k. A relação tem limite assintótico superior O(n2). O caso base da relação tem complexidade linear. 1 pontos PERGUNTA 5 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 verdadeira, e a II é uma proposição falsa. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta 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. As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. 1 pontos PERGUNTA 6 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, V, F, F. F, V, F, V. F, F, V, V. V, F, V, F. V, V, F, V. 1 pontos PERGUNTA 7 Á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. O custo de todos os nós (subproblemas) a cada nível é T(a). Tomando T(n) ≥ cn2, T(n) = Ω(n2), se a for igual a 1. Se T(n) ≤ cn2, então T(n) = O(n2) para qualquer valor de a e n. A recorrência pode ser classificada como homogênea. A árvore de recursão apresentará altura de valor igual (n/a) + 1. 1 pontos PERGUNTA 8 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). 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 por n. Agora, assinale a alternativa que apresenta a sequência correta: F, F, V, V. F, V, F, V. V, F, V, F. V, V, F, F. V, V, F, V. 1 pontos PERGUNTA 9 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. Θ(n). Θ(log(n)). Θ(n3). Θ(n2). Θ(1).PERGUNTA 10 Relações de recorrência possibilitam que um problema seja modelado a partir de si mesmo, considerando instâncias de menor tamanho. A cada iteração de uma recorrência, o problema em análise é reduzido até o limite de um caso base. PERGUNTA 10 Considerando essas informações e o conteúdo estudado, analise a sequência de números a seguir S = ( 1, 2, 22, 23, ..., 2n, …) e assinale a alternativa que apresenta a recorrência correta para S. T(n) = 2n × T(n – 1), se n ≥ 1 e T(n) = 1, se n = 1. T(n) = T(n/2) + n, se n ≥ 1 e T(n) = 1, se n = 0. T(n) = T(n – 1) + n, se n ≥ 1 e T(n) = 2, se n = 1. T(n) = 2 × T(n – 1), se n ≥ 1 e T(n) = 1, se n = 0. T(n) = T(n – 1) + 2, se n ≥ 1 e T(n) = 1, se n = 0.
Compartilhar