Algoritmos e Estrutura de Dados · IF-ES · 2024 | Questão sqc-qg239053

Programação Dinâmica (PD)

Gabarito: letra C. Estão corretas as afirmativas I, II e IV. A Programação Dinâmica resolve problemas complexos dividindo-os em subproblemas sobrepostos, armazenando suas soluções (I); segue o princípio da otimalidade de Bellman, que afirma que uma solução ótima global pode ser construída a partir de soluções ótimas locais (II); e constrói a função de valor recursivamente com base em estados e decisões (IV). A afirmativa III é incorreta pois a PD não se restringe a decisões discretas — há aplicações em problemas contínuos, como controle ótimo.

Afirmativa	Descrição	Correta?	Justificativa
I	A PD divide problemas em subproblemas, resolve cada um uma vez e armazena soluções	✅ Sim	Definição clássica: memoização evita recálculos
II	Princípio da otimalidade de Bellman: solução ótima global a partir de subproblemas ótimos	✅ Sim	Base da recursão em PD
III	PD só se aplica a decisões discretas	❌ Não	Também aplicável a problemas contínuos (ex.: controle ótimo)
IV	Função de valor construída recursivamente com base em estados e decisões	✅ Sim	Equação de Bellman é a espinha dorsal da PD

Programação Dinâmica

1Princípios
- Subproblemas sobrepostos
- Memoização
- Princípio da otimalidade (Bellman)
- Função de valor recursiva
2Aplicabilidade
- Decisões discretas
- Decisões contínuas (controle ótimo)

LEVEL · soulevel.com.br

Afirmativa I — ✅ Correta

A definição clássica de PD envolve dividir o problema em subproblemas menores, resolver cada um uma única vez (memoização), e armazenar os resultados para uso futuro. Isso evita recálculos e reduz a complexidade.

Afirmativa II — ✅ Correta

O princípio da otimalidade de Bellman estabelece que, em um problema de PD, uma política ótima tem a propriedade de que, quaisquer que sejam o estado e a decisão iniciais, as decisões restantes devem constituir uma política ótima para o estado resultante. É a base para a recursão em PD.

Afirmativa III — ❌ Incorreta

A PD é frequentemente aplicada a problemas com decisões discretas (como mochila, caminhos mínimos), mas também pode ser estendida para problemas contínuos, como em controle ótimo com variáveis contínuas (programação dinâmica contínua). Portanto, a afirmação é falsa.

Afirmativa IV — ✅ Correta

Em PD, a função de valor (ou função objetivo) é definida recursivamente por meio da equação de Bellman, que relaciona o valor de um estado com as decisões tomadas e os valores dos estados subsequentes. Essa recursão é a espinha dorsal dos algoritmos de PD.

Conclusão: As afirmativas I, II e IV estão corretas, o que corresponde à alternativa C.