Questão de Algoritmos e Estrutura de Dados — Algoritmos — FCM 2018
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq337492
Banca
FCM
Órgão
IFN-MG
Ano
2018
Nível
Superior
Cargo
Ciências da Computação: Teoria da Computação
Para se projetar um Algoritmo por indução, deve-se garantir que seja possível solucionar
Aum problema a partir da solução de subproblemas sobrepostos.
Bum problema recursivamente a partir de soluções locais para os subproblemas.
Cum conjunto de subproblemas de maneira recursiva, e a solução deve ser polinomial.
Dum problema a partir da solução de subproblemas com subestrutura ótima.
Euma pequena instância do problema, e a solução para todo problema pode ser construída a partir da solução de problemas menores.
Revelar gabarito e comentário▾
GabaritoE — uma pequena instância do problema, e a solução para todo problema pode ser construída a partir da solução de problemas menores.
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”.
Algoritmo por indução
Gabarito: letra E. O projeto de algoritmos por indução segue o princípio matemático da indução: resolve-se uma pequena instância (caso base) e, supondo resolvidos problemas menores, constrói-se a solução para o problema maior (passo indutivo). A alternativa E descreve exatamente esse processo: "uma pequena instância do problema, e a solução para todo problema pode ser construída a partir da solução de problemas menores."
As demais alternativas confundem indução com outras técnicas de projeto de algoritmos.
Alternativa A — ❌ Incorreta
Descreve a programação dinâmica, que lida com subproblemas sobrepostos e memoização. Na indução, os subproblemas são menores, mas não necessariamente sobrepostos.
Alternativa B — ❌ Incorreta
A recursão é um mecanismo comum, mas não é exclusiva da indução. A expressão "soluções locais" remete mais a algoritmos gulosos.
Alternativa C — ❌ Incorreta
Indução não garante solução polinomial. A exigência de polinomialidade não faz parte do conceito.
Alternativa D — ❌ Incorreta
Subestrutura ótima é característica de problemas resolvíveis por programação dinâmica ou algoritmos gulosos. Na indução, não é necessário que a solução ótima global seja composta de soluções ótimas locais.
Alternativa E — ✅ Correta ⟵ GABARITO
É a definição clássica de algoritmo por indução: base (pequena instância) e passo indutivo (construção a partir de instâncias menores).
NÃO CAIA NESSA!
A banca troca conceitos de diferentes paradigmas: programação dinâmica (sobreposição, subestrutura ótima), recursão genérica e exigências de complexidade. A chave é lembrar que a indução se baseia em um caso base e na redução a instâncias menores, sem requisitos adicionais como otimalidade ou polinomialidade.