Um problema computacional é dito NP-completo qu...

Um problema computacional é dito NP-completo quando

Q907058 • Algoritmos e Estrutura de Dados • Complexidade de Algoritmos • IADES • BRB • Analista de Tecnologia da Informação • 2024

Um problema computacional é dito NP-completo quando

a) a complexidade de tempo no caso médio é igual à complexidade do pior caso.
b) sua solução não é garantida em tempo polinomial.
c) a completude do programa pode ser demonstrada matematicamente.
d) a complexidade de tempo no pior caso é igual a O(n^k), para algum k.
e) o resultado obtido não pode ser otimizado.

Analisando...

Questões sobre Complexidade de Algoritmos

1

Q895492 • Algoritmos e Estrutura de Dados • Complexidade de Algoritmos • Gama Consult • Câmara de Alto Paraíso RO • Gestor de Tecnologia da Informação • 2024
Na área de Análise de Algoritmos, a notação assintótica é fundamental para descrever a complexidade de algoritmos. Considere as seguintes definições e propriedades da notação assintótica: O-notation (O grande), Ω-notation (Ômega grande), e Θ-notation (Theta grande). Qual das afirmativas a seguir é a mais correta em relação à análise assintótica de algoritmos?
- a) O-notation descreve o limite superior exato do tempo de execução de um algoritmo.
- b) Ω-notation descreve o limite inferior exato do tempo de execução de um algoritmo.
- c) Um algoritmo com complexidade O(n^2) é sempre mais eficiente do que um algoritmo com complexidade Ω(n).
- d) Θ-notation descreve tanto o limite superior quanto o inferior do tempo de execução de um algoritmo.
Analisando...
Carregando informações...
2

Q895491 • Algoritmos e Estrutura de Dados • Complexidade de Algoritmos • Gama Consult • Câmara de Alto Paraíso RO • Gestor de Tecnologia da Informação • 2024
Na computação, várias disciplinas aplicam conceitos matemáticos avançados para resolver problemas complexos. Uma dessas disciplinas é a Teoria da Complexidade Computacional, que estuda a eficiência dos algoritmos e a dificuldade dos problemas. Considere os conceitos de classes de complexidade, problemas NP-completos e algoritmos aproximados. Qual das seguintes afirmações sobre essas disciplinas é a mais correta?
- a) Todo problema na classe NP pode ser resolvido em tempo polinomial por um algoritmo determinístico.
- b) Um problema NP-completo é aquele para o qual não existe nenhum algoritmo de aproximação eficiente conhecido.
- c) Se um problema NP-completo puder ser resolvido em tempo polinomial, todos os problemas em NP também poderão ser resolvidos em tempo polinomial.
- d) Algoritmos aproximados garantem sempre a solução exata de problemas NP-difíceis em tempo polinomial.
Analisando...
Carregando informações...

Mais questões de Algoritmos e Estrutura de Dados →

Um problema computacional é dito NP-completo qu...

Um problema computacional é dito NP-completo quando

Reportar erro em questao

Reportar erro em questao

Reportar erro em questao

Busca no Site