Grátis: Analisando a árvore de recursão para um problema de tamanho 4, percebe-se que a abordagem recursiva resolve repetidamente de recursos computacionai... – Questões Respondidas

Ao vivo

Arquitetura de Rede

Outros

Analisando a árvore de recursão para um problema de tamanho 4, percebe-se que a abordagem recursiva resolve repetidamente de recursos computacionais. Para resolver isso, utiliza-se a programação dinâmica.
Com base na explicação acima, identifique e assinale a alternativa correta que exemplifica corretamente a aplicação da programação dinâmica.
a. A programação dinâmica armazena as soluções dos subproblemas já resolvidos para evitar cálculos redundantes.
b. A abordagem recursiva é mais eficiente que a programação dinâmica para problemas de grande tamanho.
c. A árvore de recursão é utilizada na programação dinâmica para aumentar número de cálculos necessários.
d. A programação dinâmica utiliza a árvore de recursão para resolver cada subproblema múltiplas vezes.
e. A programação dinâmica resolve um problema de forma direta sem a necessidade de armazenar subproblemas já resolvidos.

Aprimorando com Questões

há 2 meses

Aprimorando com Questões

há 2 meses

Analise de Algoritmos Sem 6

Analise de Algoritmos Sem 6

UNIVESP

Respostas

Ed

há 2 meses

Vamos analisar as alternativas com base na definição e nos princípios da programação dinâmica. a) A programação dinâmica armazena as soluções dos subproblemas já resolvidos para evitar cálculos redundantes. - Esta é a definição correta da programação dinâmica, que visa otimizar a resolução de problemas armazenando resultados de subproblemas. b) A abordagem recursiva é mais eficiente que a programação dinâmica para problemas de grande tamanho. - Isso não é verdade, pois a programação dinâmica é geralmente mais eficiente em problemas que envolvem subproblemas sobrepostos. c) A árvore de recursão é utilizada na programação dinâmica para aumentar o número de cálculos necessários. - Isso é incorreto, pois a programação dinâmica visa reduzir o número de cálculos, não aumentá-los. d) A programação dinâmica utiliza a árvore de recursão para resolver cada subproblema múltiplas vezes. - Isso é errado, já que a programação dinâmica evita resolver subproblemas múltiplas vezes. e) A programação dinâmica resolve um problema de forma direta sem a necessidade de armazenar subproblemas já resolvidos. - Isso é incorreto, pois a essência da programação dinâmica é exatamente armazenar soluções de subproblemas. Portanto, a alternativa correta é: a) A programação dinâmica armazena as soluções dos subproblemas já resolvidos para evitar cálculos redundantes.

Essa resposta te ajudou?

0

0

Ainda com dúvidas?

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

Essa pergunta também está no material:

Analise de Algoritmos Sem 6

Analise de Algoritmos Sem 6

UNIVESP

Mais perguntas desse material

O problema do corte da haste visa estabelecer uma configuração de corte ótima para uma determinada haste. Cada tamanho de pedaços da haste possui um valor com que pode ser comercializado, daí tenta-se encontrar conjunto de pedaços que se atinge um maior valor. Um algoritmo para esta solução está apresentada a seguir.
Assinale a alternativa que possui uma informação correta a respeito deste problema e do algoritmo apresentado.
a. vetor S armazena os valores dos lucros que está se querendo otimizar.
b. As linhas 11 e 12 demonstram que o algoritmo usa programação dinâmica.
c. algoritmo aplica a programação dinâmica em uma versão bottom-up.
d. A versão implementada adota a estratégia de solução via força-bruta.
e. O problema apresenta uma subestrutura ótima que pode ser constado na linha 13.

O problema da multiplicação de cadeia de matrizes envolve estabelecer a forma como as operações de multiplicação serão associadas, isto é, como serão colocados os parênteses ou a parentização da multiplicação. Isso é relevante pois os parênteses indicam a sequência com que as multiplicações ocorrem e isso impacta no número de operações com termos das matrizes, enfim, este arranjo otimiza tempo computacional da multiplicação da cadeia de matrizes.
A respeito do problema de multiplicação de matrizes e desta solução, analise as afirmativas a seguir:
I. A variável S armazena, para cada subcadeia definida pelos índices i e j, qual índice k atingiu custo ótimo.
II. comando "para" da linha 6 serve para percorrer todas as subcadeias de comprimento para obter custo ótimo delas.
III. Por conta dos quatro loops determinados com comando "para" tempo computacional do algoritmo é O(n 4).
IV. O problema da multiplicação de matrizes apresenta uma subestrutura ótima e isso pode ser melhor constado na linha 11.
a. III e IV, apenas.
b. I, II, III e IV.
c. I e II, apenas.
d. IV, apenas.
e. II, III e IV, apenas.

Utilizando um algoritmo top-down, são criados dois vetores: um vetor B para armazenar lucro máximo para uma barra de tamanho K, e um vetor S para armazenar a posição onde corte foi executa-se procedimento, caso contrário, devolve-se valor já resolvido. Uma empresa deseja maximizar lucro cortando barras de aço de diferentes comprimentos.
Agora, utilize a programação dinâmica e o algoritmo top-down, calcule a combinação de cortes que maximiza lucro para uma barra de 5 polegadas e valor do lucro máximo e assinale a alternativa que corresponde a esses valores.
a. Combinação: 2+2+1, Lucro máximo: R$12,00
b. Combinação: 1+4, Lucro máximo: R$10,00
c. Combinação: 1+1+3, Lucro máximo: R$12,00
d. Combinação: 2+3, Lucro máximo: R$13,00
e. Combinação: 5, Lucro máximo: R$10,00

Uma técnica para projeto de algoritmos possui algumas características que conduzem jeito de raciocinar, estruturar e codificar uma determinada solução computacional para um problema. Em um problema de corte de barras é desejado achar uma melhor configuração de cortes que otimiza um determinado lucro e algoritmo está descrito a seguir.
Neste contexto, identifique a linha que caracteriza a aplicação da técnica de programação dinâmica no algoritmo e assinale a alternativa correspondente.
a. Linha 4, por contar com um comando de loop.
b. Linha 8, ao comparar valores para otimização.
c. Linha 6, por contar com um loop aninhado.
d. Linha 7, ao usar cálculos armazenados no vetor.
e. Linha 3, ao inicializar o vetor.

Na programação dinâmica, existem duas abordagens principais: Top-Down e Bottom-Up. Essas técnicas surgiram como soluções para melhorar a eficiência de algoritmos que resolvem problemas complexos. Cada abordagem possui suas vantagens e desvantagens, e a escolha entre elas pode depender do problema específico e das preferências de implementação do desenvolvedor.
Com base na explicação acima, reconheça e assinale a alternativa correta que exemplifica as características e a escolha de uma abordagem dependendo do problema e das preferências.
a. A abordagem Top-Down é recursiva, pode sofrer de sobrecarga de chamadas recursivas, enquanto a Bottom-Up é iterativa e preferida para menor sobrecarga.
b. A abordagem Top-Down é sempre mais eficiente que a abordagem Bottom-Up em termos de complexidade de tempo, sendo preferida para todos os tipos de problemas.
c. Ambas as abordagens, Top-Down e Bottom-Up, são recursivas, sofrem de sobrecarga de chamadas recursivas, e são preferidas em problemas simples.
d. A abordagem Bottom-Up é recursiva, resolve subproblemas um de cada vez, e é preferida para problemas que requerem menos inicialização.
e. A abordagem Top-Down é iterativa, resolve todos os subproblemas de uma vez, e é preferida para problemas que requerem menos chamadas recursivas.