Questões de Ciência da Computação da Banca não informada

Analise as afirmativas referentes à classe de problemas computacionais e assinale V para as alternativas verdadeiras e F para as falsas.

( ) Sejam A, B dois problemas tais que A ϵ NP - Completo e B ϵ P. Então, B é polinomialmente transformável em A, somente se P = NP.

( ) Todo problema P não pertence à classe de problemas NP.

A partir dessa análise, assinale a sequência CORRETA.

Analise as afirmativas referentes ao algoritmo de Dijkstra, e assinale V para as alternativas verdadeiras e F para as falsas.

( ) O algoritmo de Dijkstra é ótimo para a situação do problema do caminho mínimo.

( ) O algoritmo de Dijkstra consegue encontrar o menor caminho em um grafo com pesos negativos.

A partir dessa análise, assinale a sequência CORRETA.

Considerando essa premissa, é CORRETO afirmar que

Considere dois algoritmos A1 e A2, cujas funções de custo são, respectivamente, T1(n) = n² − n + 1 e T2(n) = 7n log₂ n + 10n. Para simplificar a análise, admita que n > 0 e é sempre uma potência de 2.

A partir dessa premissa, assinale a alternativa CORRETA.

Analise as afirmativas concernentes à análise assintótica de funções, assinalando V para as verdadeiras e F para as falsas.

( ) Dadas duas funções f1 e f2. Se f1 < f2 então f2 ≠ O (f1).

( ) 3²ⁿ = O(3ⁿ).

A partir dessa análise, assinale a sequência CORRETA.