Questão de Algoritmos e Estrutura de Dados — Conceitos Básicos e Algoritmos — IBFC 2024
Algoritmos e Estrutura de Dados›Conceitos Básicos e Algoritmos
Código
qg220665
Banca
IBFC
Órgão
TRF - 5ª REGIÃO
Ano
2024
Nível
Superior
Cargo
Analista Judiciário - Área Apoio Especializado - Especialidade: Análise de Sistemas de Informação
Considere as definições de algoritmos determinísticos e não determinísticos e as classes de problemas P e NP. De acordo com Ziviani (2007), um problema pode ser classificado como pertencente à classe NP caso ______. Assinale a alternativa que preencha corretamente a lacuna.
Ao problema seja resolvido por um algoritmo não determinístico que opera em tempo exponencial
Ba verificação de uma solução válida possa ser realizada em tempo polinomial
Cum algoritmo determinístico gere uma solução válida em tempo constante
Do comportamento do algoritmo seja sempre o mesmo, independente das execuções
Revelar gabarito e comentário▾
GabaritoB — a verificação de uma solução válida possa ser realizada em tempo polinomial
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”.
Classes P e NP
Gabarito: letra B. A classe NP (Nondeterministic Polynomial time) é definida como o conjunto de problemas para os quais uma solução pode ser verificada em tempo polinomial. Essa é a definição clássica adotada por Ziviani (2007) e pela literatura de complexidade computacional.
A banca testa o conhecimento da definição formal de NP, que frequentemente é confundida com resolução em tempo exponencial ou com determinismo. A chave é lembrar que NP se refere à verificação eficiente de soluções, não necessariamente à resolução eficiente.
Classes de problemas
1P (Polinomial)
Resolvido em tempo polinomial
Algoritmo determinístico
2NP (Nondeterministic Polynomial)
Verificação em tempo polinomial
Resolução pode ser difícil
Exemplos: SAT, caixeiro-viajante
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
Afirma que NP seria resolvido por um algoritmo não determinístico em tempo exponencial. O erro está em trocar o tempo polinomial (característico de NP) por exponencial. A definição correta de NP é baseada em tempo polinomial, tanto para a máquina não determinística quanto para a verificação de soluções.
Alternativa B — ✅ Correta ⟵ GABARITO
Define corretamente a classe NP: a verificação de uma solução válida pode ser feita em tempo polinomial. Essa é a propriedade fundamental que caracteriza os problemas NP.
Alternativa C — ❌ Incorreta
Afirma que um algoritmo determinístico gera solução em tempo constante, o que não é a definição de NP. A classe NP não impõe restrição de tempo constante para geração; ela trata da verificação polinomial de soluções, independentemente de como a solução é obtida.
Alternativa D — ❌ Incorreta
Descreve o comportamento determinístico de um algoritmo (sempre o mesmo resultado para as mesmas entradas), mas isso não é a definição de NP. Determinismo é uma propriedade de algoritmos, não uma caracterização de classe de complexidade.
NÃO CAIA NESSA!
Para fixar: NP = "verificação polinomial". Não confunda com "não polinomial" ou "exponencial". A verificação é rápida (polinomial), mesmo que a resolução do problema possa ser difícil.