Algoritmos e Estrutura de Dados · CESPE / CEBRASPE · 2022 | Questão sqc-ce134526

Algoritmos: Métodos de Design

Gabarito: letra A. A descrição — redução da complexidade exponencial para polinomial com manutenção de uma tabela de subproblemas resolvidos — é a definição clássica de programação dinâmica. Esse paradigma explora a sobreposição de subproblemas (overlapping subproblems) e a subestrutura ótima, armazenando resultados em uma tabela para evitar recálculos, transformando algoritmos exponenciais (como Fibonacci recursivo ingênuo) em polinomiais.

A questão cobra a distinção entre as principais técnicas de projeto de algoritmos. Vamos analisar cada alternativa:

Método de Design	Característica Principal	Reduz Complexidade Exponencial para Polinomial?	Mantém Tabela de Subproblemas?
Programação Dinâmica	Armazena soluções de subproblemas sobrepostos para reutilização	Sim	Sim
Método Ganancioso	Escolhas localmente ótimas em cada passo	Não necessariamente	Não
Dividir e Conquistar	Divide em subproblemas independentes e combina soluções	Não (pode ser exponencial)	Não
Programação Linear	Otimização matemática com restrições lineares	Não se aplica	Não
Redução (Transformar e Conquistar)	Transforma problema em outro mais simples	Não se aplica	Não

Métodos de design de algoritmos: Programação dinâmica (Tabela de subproblemas, Reduz exponencial para polinomial); Método ganancioso (Escolha localmente ótima, Sem tabela de subproblemas); Dividir e conquistar (Subproblemas independentes, Sem sobreposição); Programação linear (Otimização matemática, Não é método de design)

Alternativa A — ✅ Correta ⟵ GABARITO

A programação dinâmica (DP) é exatamente o método que utiliza uma tabela (memoização ou bottom-up) para armazenar soluções de subproblemas já resolvidos, reutilizando-as quando necessário. Com isso, muitos problemas que seriam resolvidos em tempo exponencial por força bruta (ex.: problema da mochila, menor caminho em grafos com pesos) passam a ser solucionados em tempo polinomial. A descrição do enunciado é uma síntese precisa desse conceito.

Alternativa B — ❌ Incorreta

O método ganancioso (greedy) faz escolhas localmente ótimas a cada passo, sem armazenar uma tabela de subproblemas resolvidos. Embora também resolva alguns problemas de forma eficiente (ex.: árvore geradora mínima, código de Huffman), não se caracteriza por redução de complexidade exponencial para polinomial via armazenamento de subproblemas.

Alternativa C — ❌ Incorreta

Dividir e conquistar (divide and conquer) divide o problema em subproblemas independentes, resolve-os recursivamente e combina as soluções. Subproblemas não se sobrepõem (não há tabela de reutilização), e a complexidade resultante pode ser polinomial (ex.: Mergesort) ou exponencial (ex.: Fibonacci recursivo ingênuo). A técnica não envolve tabela para subproblemas já resolvidos.

Alternativa D — ❌ Incorreta

Programação linear é uma técnica de otimização matemática para resolver problemas com restrições lineares, e não um método de design de algoritmos que usa tabela de subproblemas. Embora problemas de programação linear possam ser resolvidos em tempo polinomial (ex.: algoritmo de Khachiyan), a descrição não se aplica.

Alternativa E — ❌ Incorreta

Redução (transformar e conquistar) consiste em transformar um problema em outro mais simples ou já conhecido para resolvê-lo (ex.: redução de um problema de grafos para um problema de ordenação). Não envolve, em geral, manutenção de tabela de subproblemas nem redução de exponencial para polinomial como característica definidora.

PEGA ESSA DICA!

Para fixar, lembre-se dos três ingredientes da programação dinâmica: subestrutura ótima, subproblemas sobrepostos e memoização/tabela. Sempre que a questão mencionar "tabela para subproblemas já resolvidos" e "redução de complexidade", a resposta será programação dinâmica.

Gabarito: letra A