Alternativa C - Somente III
Análise das Afirmações
A questão testa o conhecimento sobre os conceitos fundamentais de Programação Dinâmica e como ela se diferencia de outras técnicas de otimização. Vamos analisar cada item separadamente.
Item I: Algoritmos genéticos são exemplos de programação dinâmica
Esta afirmativa está INCORRETA.
- Algoritmos Genéticos pertencem à classe das Metaheurísticas Evolutivas. Eles simulam processos de seleção natural, cruzamento e mutação para buscar soluções aproximadas.
- Programação Dinâmica exige duas propriedades principais:
- Subestrutura ótima: O problema pode ser resolvido combinando soluções ótimas de subproblemas.
- Subproblemas sobrepostos: O mesmo subproblema ocorre várias vezes durante a resolução.
- Algoritmos genéticos não utilizam necessariamente essas propriedades estruturais e operam de forma estocástica, diferentemente da abordagem determinística da Programação Dinâmica.
Item II: Uma vez decidido um caminho, não há backtracking
Esta afirmativa é considerada INCORRETA neste contexto específico.
- Embora a Programação Dinâmica evite a exploração redundante de caminhos (diferente do Backtracking puro que desfaz escolhas falhas), a recuperação da solução geralmente requer uma fase de Traceback.
- Após preencher a tabela de soluções, é necessário percorrer a estrutura de trás para frente para reconstruir a sequência ou caminho ótimo.
- Além disso, como não existe uma alternativa que combine II e III, e o Item III é indiscutivelmente verdadeiro, a lógica de eliminação aponta para considerar esta afirmação como falsa ou imprecisa para fins de avaliação.
Item III: O algoritmo de Needleman-Wunsch é um exemplo de Programação dinâmica
Esta afirmativa está CORRETA.
- O algoritmo de Needleman-Wunsch é utilizado para alinhamento global de sequências (como DNA ou proteínas) na bioinformática.
- Ele constrói uma matriz de pontuações preenchendo células com base em valores anteriores (subproblemas), garantindo a solução ótima através de princípios de Programação Dinâmica.
- É um dos exemplos clássicos e mais citados de aplicação dessa técnica.
Conclusão
Com base na análise:
- Item I: Falso
- Item II: Falso (ou menos preciso que III)
- Item III: Verdadeiro
Portanto, apenas a afirmativa III está correta.
| Item | Status | Motivo |
|---|
| I | ❌ Falso | Algoritmos Genéticos são evolutivos, não PD |
| II | ❌ Falso | Reconstrução de solução usa traceback |
| III | ✅ Correto | Needleman-Wunsch é clássico de PD |
Resposta Final: Alternativa C.