Programação dinâmica

Prévia do material em texto

Programação dinâmica 
Qual das alternativas abaixo descreve corretamente o conceito de programacao dinamica?
a) A programacao dinamica e uma tecnica que resolve problemas dividindo-os em subproblemas
independentes e resolvendo-os em paralelo.
b) A programacao dinamica resolve problemas armazenando os resultados de subproblemas para
evitar calculos repetitivos.
c) A programacao dinamica utiliza a forca bruta para resolver problemas otimizando o tempo de
execucao.
d) A programacao dinamica divide o problema em subproblemas e resolve cada um recursivamente
sem armazenar resultados.
Resposta correta: b) A programacao dinamica resolve problemas armazenando os resultados de
subproblemas para evitar calculos repetitivos.
Explicacao: A principal caracteristica da programacao dinamica e a reutilizacao de solucoes de
subproblemas, armazenando as solucoes ja calculadas em uma estrutura de dados, como uma
tabela, para evitar o recalculo de resultados.
Em qual das situacoes abaixo a programacao dinamica e particularmente util?
a) Quando o problema pode ser resolvido por forca bruta sem grandes prejuizos de desempenho.
b) Quando o problema possui multiplos subproblemas que se sobrepoem e podem ser resolvidos
de forma eficiente.
c) Quando o problema exige que todas as solucoes possiveis sejam exploradas sem otimizacao.
d) Quando o problema envolve somente operacoes aritmeticas simples.
Resposta correta: b) Quando o problema possui multiplos subproblemas que se sobrepoem e
podem ser resolvidos de forma eficiente.
Explicacao: A programacao dinamica e eficaz quando o problema pode ser dividido em
subproblemas que se sobrepoem, ou seja, que sao resolvidos repetidamente. Nesse contexto, a
solucao de um subproblema pode ser armazenada para uso posterior, evitando calculos repetidos.
Qual e a principal diferenca entre programacao dinamica e divisao e conquista?
a) A programacao dinamica resolve subproblemas de forma independente, enquanto a divisao e
conquista resolve subproblemas interdependentes.
b) Na programacao dinamica, os subproblemas se sobrepoem e suas solucoes sao armazenadas,
enquanto na divisao e conquista os subproblemas sao independentes e nao compartilham
solucoes.
c) A programacao dinamica divide os problemas em subproblemas e resolve recursivamente,
enquanto a divisao e conquista tenta resolver problemas iterativamente.
d) A programacao dinamica resolve problemas de otimizacao, enquanto a divisao e conquista e
usada para problemas de ordenacao.
Resposta correta: b) Na programacao dinamica, os subproblemas se sobrepoem e suas solucoes
sao armazenadas, enquanto na divisao e conquista os subproblemas sao independentes e nao
compartilham solucoes.
Explicacao: A principal diferenca entre essas abordagens e que na programacao dinamica, os
subproblemas geralmente se sobrepoem e suas solucoes sao armazenadas para uso posterior. Ja
na divisao e conquista, os subproblemas sao independentes, e nao ha necessidade de reuso de
solucoes.
No problema da mochila (0/1 Knapsack Problem), qual das alternativas abaixo descreve a
aplicacao de programacao dinamica?
a) A solucao e obtida testando todas as combinacoes possiveis de itens.
b) A solucao envolve armazenar as combinacoes de peso e valor para cada item, para que cada
subproblema seja resolvido apenas uma vez.
c) O problema e resolvido sem considerar a capacidade da mochila.
d) A solucao e encontrada por meio de uma simples ordenacao dos itens por valor.
Resposta correta: b) A solucao envolve armazenar as combinacoes de peso e valor para cada item,
para que cada subproblema seja resolvido apenas uma vez.
Explicacao: No problema da mochila, a programacao dinamica utiliza uma tabela para armazenar
as solucoes de subproblemas, evitando a recomputacao e permitindo que se encontre a solucao
otima de forma eficiente.
Qual das alternativas a seguir representa um exemplo classico de problema que pode ser resolvido
com programacao dinamica?
a) Algoritmo de ordenacao por bolha (Bubble Sort).
b) Algoritmo de busca binaria.
c) Problema do caminho mais curto em um grafico ponderado (como o algoritmo de Dijkstra).
d) Sequencia de Fibonacci.
Resposta correta: d) Sequencia de Fibonacci.
Explicacao: A sequencia de Fibonacci e um exemplo classico onde a programacao dinamica pode
ser aplicada. Em vez de recalcular os termos de forma recursiva a cada chamada, podemos
armazenar os resultados intermediarios para acelerar o calculo.
Em qual cenario a utilizacao de programacao dinamica nao seria adequada?
a) Quando o problema possui subproblemas independentes que podem ser resolvidos de forma
eficiente com uma abordagem recursiva.
b) Quando os subproblemas se sobrepoem, mas a solucao precisa ser encontrada sem otimizacao
de tempo.
c) Quando o problema exige uma solucao exata e nao ha subproblemas que podem ser
reutilizados.
d) Quando o tempo de execucao nao e uma preocupacao importante.
Resposta correta: b) Quando os subproblemas se sobrepoem, mas a solucao precisa ser
encontrada sem otimizacao de tempo.
Explicacao: A programacao dinamica e mais eficaz quando se busca otimizar o tempo de execucao
ao resolver problemas que envolvem subproblemas sobrepostos. Se o tempo de execucao nao for
uma preocupacao ou a otimizacao nao for necessaria, pode nao ser a melhor escolha.
Qual das opcoes abaixo descreve melhor o conceito de "memoizacao" na programacao dinamica?
a) A memoizacao refere-se ao processo de dividir um problema em partes menores e
independentes.
b) A memoizacao e a tecnica de armazenar os resultados dos subproblemas ja resolvidos para
evitar recalcular solucoes repetidas.
c) A memoizacao envolve a ordenacao dos subproblemas antes de serem resolvidos.
d) A memoizacao refere-se a aplicacao de um algoritmo iterativo para resolver um problema
recursivamente.
Resposta correta: b) A memoizacao e a tecnica de armazenar os resultados dos subproblemas ja
resolvidos para evitar recalcular solucoes repetidas.
Explicacao: Memoizacao e uma tecnica fundamental na programacao dinamica, onde os resultados
de subproblemas sao armazenados para evitar o retrabalho e, assim, melhorar a eficiencia do
algoritmo.
No problema do numero de maneiras de fazer troco (Change Making Problem), como a
programacao dinamica pode ser aplicada?
a) Calculando todas as combinacoes possiveis de moedas e somando as solucoes.
b) Armazenando os resultados parciais para evitar recomputacoes e encontrar a solucao mais
eficiente.
c) Usando uma abordagem gulosa, sempre escolhendo a maior moeda disponivel.
d) Aplicando um algoritmo de forca bruta para testar todas as opcoes possiveis.
Resposta correta: b) Armazenando os resultados parciais para evitar recomputacoes e encontrar a
solucao mais eficiente.
Explicacao: A programacao dinamica e util nesse tipo de problema porque permite armazenar as
solucoes parciais para cada valor de troco, evitando recalcular as solucoes para valores menores
multiplas vezes.
Qual das alternativas a seguir e uma caracteristica de um problema que pode ser resolvido por
programacao dinamica?
a) O problema envolve subproblemas independentes que podem ser resolvidos de forma paralela.
b) O problema pode ser resolvido apenas com recursao simples sem necessidade de otimizacao.
c) O problema possui subproblemas que se sobrepoem, e a solucao de cada subproblema pode ser
reutilizada em outras partes do problema.
d) O problema exige apenas operacoes aritmeticas simples para chegar a solucao.
Resposta correta: c) O problema possui subproblemas que se sobrepoem, e a solucao de cada
subproblema pode ser reutilizada em outras partes do problema.
Explicacao: Para que a programacao dinamica seja aplicada, e necessario que o problema tenha
subproblemas que se sobrepoem, ou seja, que aparecam mais de uma vez durante a resolucao do
problema, permitindo a reutilizacao de solucoes.
No caso do algoritmo de programacao dinamica para o problema do maior subsequencia comum
(Longest Common Subsequence -LCS), qual e a abordagem correta?
a) Usar recursao simples sem armazenar os resultados intermediarios.
b) Armazenar os resultados dos subproblemas em uma tabela para evitar recomputacao e
encontrar a solucao otima.
c) Resolver o problema de forma iterativa, sem precisar de recursao.
d) Testar todas as combinacoes possiveis de subsequencias e escolher a mais longa.
Resposta correta: b) Armazenar os resultados dos subproblemas em uma tabela para evitar
recomputacao e encontrar a solucao otima.
Explicacao: O algoritmo de LCS usa programacao dinamica para armazenar as solucoes parciais
em uma tabela 2D, que evita a recomputacao e torna o algoritmo mais eficiente.