Questão de Algoritmos e Estrutura de Dados — Algoritmos — FCM 2018
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq337485
Banca
FCM
Órgão
IFN-MG
Ano
2018
Nível
Superior
Cargo
Ciências da Computação: Teoria da Computação
A teoria de algoritmos de aproximação, às vezes chamados de algoritmos aproximativos, é extremamente útil para tratar problemas NP-difíceis.Sobre algoritmos de aproximação, é correto afirmar que
Aum algoritmo de aproximação, embora não encontre a resposta correta sempre, pode ser executado em tempo polinomial.
Bum algoritmo de aproximação pode ou não fornecer garantias sobre a qualidade da solução encontrada.
Cseu tempo de execução pode ser uma função da qualidade da solução a ser encontrada.
Dpodem ser utilizados apenas em problemas de maximização.
Epodem apenas ser utilizados para tratar problemas NP-difíceis.
Revelar gabarito e comentário▾
GabaritoC — seu tempo de execução pode ser uma função da qualidade da solução a ser encontrada.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Algoritmos de Aproximação
Gabarito: letra C. Algoritmos de aproximação são projetados para problemas NP-difíceis e, embora não garantam a solução ótima, executam em tempo polinomial. A característica central é que seu tempo de execução pode ser uma função da qualidade desejada (como em PTAS e FPTAS), o que está correto na alternativa C.
Alternativa A — ❌ Incorreta
A afirmação é verdadeira em parte (algoritmos de aproximação são polinomiais), mas é imprecisa e não captura a essência: o trade-off entre tempo e qualidade. Além disso, a expressão "não encontra a resposta correta sempre" pode ser mal interpretada, pois eles encontram uma solução aproximada, não necessariamente incorreta.
Alternativa B — ❌ Incorreta
Por definição, algoritmos de aproximação fornecem garantias sobre a qualidade da solução (razão de aproximação). Heurísticas sem garantia não são consideradas algoritmos de aproximação na teoria.
Alternativa C — ✅ Correta ⟵ GABARITO
O tempo de execução pode depender da qualidade desejada. Por exemplo, em esquemas de aproximação polinomial (PTAS), o tempo é polinomial no tamanho da entrada, mas pode ser exponencial em , onde é o fator de aproximação.
Alternativa D — ❌ Incorreta
Algoritmos de aproximação são aplicáveis a problemas de maximização e minimização, como o problema da mochila (maximização) ou do caixeiro viajante (minimização).
Alternativa E — ❌ Incorreta
Embora sejam frequentemente usados para problemas NP-difíceis, algoritmos de aproximação também podem ser aplicados a problemas polinomiais, quando se deseja uma solução aproximada mais rápida.
NÃO CAIA NESSA!
A alternativa A pode parecer correta, pois muitos algoritmos de aproximação são polinomiais. No entanto, a banca explora a definição precisa: a característica distintiva é a dependência do tempo de execução com a qualidade, não apenas o fato de serem polinomiais. Fique atento a afirmações genéricas que não refletem o conceito central cobrado pela teoria.