Grátis: 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 imp... – Questões Respondidas

Algoritmos

Outros

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 relação tem limite assintótico superior O(n 2).
O k-ésimo termo da relação é da forma T(n – k) + 3k.
O caso base da relação tem complexidade linear.
O termo independente da relação pode ser substituído por n 3, sem interferência no seu comportamento assintótico.
A relação pode ser classificada como homogênea.

Exercícios Para o Aprendizado

há 2 anos

Exercícios Para o Aprendizado

há 2 anos

ANÁLISE DE ALGORITMOS - N2

ANÁLISE DE ALGORITMOS - N2

UAM

Respostas

Ed

há 2 anos

Vamos analisar a relação de recorrência dada: 1. T(1) = 1; T(n) = T(n - 1) + 3. Para resolver essa relação, podemos expandi-la: - T(n) = T(n - 1) + 3 - T(n - 1) = T(n - 2) + 3 - T(n - 2) = T(n - 3) + 3 Se continuarmos esse processo, teremos: T(n) = T(n - k) + 3k, onde k = n - 1. Portanto, o k-ésimo termo da relação é da forma T(n – k) + 3k, o que confirma a segunda alternativa. Agora, vamos analisar as outras opções: - Limite assintótico superior O(n²: A relação é linear, pois a cada passo adicionamos uma constante (3). Portanto, essa afirmação é falsa. - Caso base da relação tem complexidade linear: O caso base T(1) = 1 é constante, não linear. Portanto, essa afirmação é falsa. - Termo independente da relação pode ser substituído por n³: Isso não é verdade, pois o termo independente é constante e não pode ser substituído por n³ sem alterar o comportamento assintótico. Portanto, essa afirmação é falsa. - A relação pode ser classificada como homogênea: A relação não é homogênea, pois tem um termo constante (3). Portanto, essa afirmação é falsa. Assim, a alternativa correta é: O k-ésimo termo da relação é da forma T(n – k) + 3k.

Essa resposta te ajudou?

0

0

Ainda não achou a resposta?

Integrado com os principais modelos de IA do mercado
Respostas em segundos
IA treinada para estudantes brasileiros.

Evolua sua forma de estudar

Cadastre-se ou realize login

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

ANÁLISE DE ALGORITMOS - N2

ANÁLISE DE ALGORITMOS - N2

UAM

Mais perguntas desse material

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.
II. Para um vetor de N posições, o seu processo de ordenação usa entre (1/2) NlogN e NlogN comparações.
As asserções I e II são proposições falsas.
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, e a II é 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 verdadeiras, mas a II não é uma justificativa correta da I.

O teorema mestre apresenta importantes resultados, que podem ser aplicados para a descrição do comportamento assintótico de algoritmos modelados por recorrências. Porém, a sua correta utilização depende da identificação de qual dos três casos podem ser empregados e da satisfação das condições exigidas por ele.
Considerando essas informações e conteúdo estudado, analise as asserções a seguir e a relação proposta entre elas.
I. Um algoritmo modelado com a recorrência T(n) = 2T(n/2) + 10n pode ter seu limite assintótico definido através da aplicação do teorema mestre.
II. Como as condições do segundo caso do teorema são satisfeitas, a complexidade do algoritmo é dada por Θ(n).
As asserções I e II são proposições falsas.
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, e a II é 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 verdadeiras, mas a II não é uma justificativa correta da I.

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 identificadas 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 afirmativas de acordo com essa técnica utilizada para indicar um limite superior para funções.
I. 2 n+1 = O(2 n)
II. Se f(n) = O(h(n)) e g(n) = O(h(n)), então f(n) + g(n) = O(h(n)).
III. n 2/10 = O(n)
IV. 6n 3 = O(n 2)
Está correto apenas o que se afirma em: II e III.
Está correto apenas o que se afirma em: I e III.
Está correto apenas o que se afirma em: II e IV.
Está correto apenas o que se afirma em: III e IV.
Está correto apenas o que se afirma em: I e II.

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 afirmação verdadeira sobre a relação assintótica entre essas duas funções.
Como log(n!) = O(nlogn), então nlogn ≤ clog(n!) para algum c > 0.
Uma constante c = ½ valida o limite assintótico inferior de log(n!).
Se log(n!) ≤ log(n/2) n/2, então nlog(n) também limita log(n!) inferiormente.
A soma dos n/2 últimos termos de log(n!) é menor que log(n/2) n/2.
O limite assintótico superior da soma das duas funções é O(nlog(n!)).

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.
Θ(log(n)).
Θ(n).
Θ(n 2).
Θ(n 3).
Θ(1).

Uma das operações computacionais utilizadas para medir a complexidade dos algoritmos de ordenação é o número de comparações realizadas com a chave que está sendo reposicionada. No entanto, esta não é a única operação que pode ser empregada. O número de movimentações efetuadas entre as chaves em ordenação também constitui outra operação relevante a ser analisada.
Considerando o número de movimentações entre chaves, efetuadas pelo método de ordenação por inserção direta, analise as asserções a seguir e a relação proposta entre elas.
I. O comportamento assintótico do algoritmo é invariante em relação ao tipo de operação elemental considerada - seja o número de comparações com a chave em reposicionamento ou o número de movimentações entre chaves.
II. A contagem do número de operações básicas, realizadas no pior caso do algoritmo, resulta em um mesmo valor, assim como acontece em seu melhor caso, independentemente do tipo de operação considerada.
As asserções I e II são proposições falsas.
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, e a II é uma justificativa correta da II.
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 verdadeiras, mas a II não é uma justificativa correta da I.

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(n 2) é 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(n 2 - 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 III.
Está correto apenas o que se afirma em: I e III.
Está correto apenas o que se afirma em: II e IV.
Está correto apenas o que se afirma em: III e IV.
Está correto apenas o que se afirma em: I e II.

Verificar que determinada operação ou afirmaçã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 afirmativas a respeito da aplicação da técnica de indução matemática para verificar 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: k2 + 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.
✓ V, V, F, F.
F, F, V, V.
V, F, V, F.
V, V, F, V.
F, V, F, V.

O algoritmo Quick Sort é considerado um dos mais eficientes 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 eficiência do algoritmo. Considerando as seguintes modificaçõ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.
As metades à esquerda e à direita do vetor demandam o mesmo número de chamadas recursivas para serem ordenadas.
Após a ordenação da metade à esquerda do vetor, a metade à direita já se encontra ordenada.
Na primeira iteração, são feitas três trocas de posições de elementos.
O elemento 5 sofre duas mudanças de posição até alcançar a posição definitiva.
O elemento 2 é o último pivô escolhido durante a ordenação da metade à esquerda do vetor original.