Questões de Ciência da Computação do ano 2014

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.

• A. V V.
• B. V F.
• C. F F.
• D. F V.

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.

• A. V V.
• B. V F.
• C. F F.
• D. F V.

O algoritmo de Floyd-Warshall resolve o problema de calcular o caminho mais curto entre todos os pares de vértices em um grafo orientado (com direção) e valorado (com peso).

Sobre o algoritmo e dado que V é o número de vértices e E o número de arestas do grafo, podemos afirmar que:

• A. Sua complexidade é O(V³).
• B. Sua complexidade é O(V²+E).
• C. Sua complexidade é O(V).
• D. Sua complexidade é O(V²).

Considerando essa premissa, é CORRETO afirmar que

• A. a complexidade do Algoritmo A1 em relação ao algoritmo A2 não pode ser determinada.
• B. o algoritmo A1 tem complexidade menor que A2.
• C. o algoritmo A1 tem complexidade igual a A2.
• D. o algoritmo A1 tem complexidade maior que A2.

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.

• A. T1 e T2 são assintoticamente equivalentes.
• B. A2 é sempre mais eficiente que A1.
• C. O limite superior T1(n) = O(n³) é correto e assintoticamente restrito.
• D. A1 é mais eficiente que A2 para n suficientemente pequeno.

Sejam duas funções f(n) e g(n) que mapeiam números inteiros positivos em números reais positivos.

Analise as afirmativas relativas às notações assintóticas de complexidade, assinalando V para as verdadeiras e F para as falsas.

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

• A. F V.
• B. F F.
• C. F V.
• D. V V.

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.

• A. F V.
• B. V V.
• C. F F.
• D. F V.

Analise as afirmativas referentes à classe de problemas computacionais.

I. Uma linguagem L pertence à classe NP.

II. Uma linguagem L pertence à classe P. III. Toda linguagem L’ pertence à classe NP, L’ é redutível em tempo polinomial a uma linguagem L.

IV. L’ pertence à classe NP. L é redutível em tempo polinomial a uma linguagem L’.

Após sua análise, considerando que uma linguagem L é NP – completa, estão CORRETAS:

• A. I e IV apenas.
• B. I e III apenas.
• C. II e IV apenas.
• D. I, II, III e IV.

Considerando o teste de software, é INCORRETO afirmar

• A. que, nos métodos similares à cascata, o maior esforço de testes ocorre ao final de um ciclo de desenvolvimento.
• B. que, nos métodos Ágeis os testes de unidade, normalmente, fazem parte das prescrições de como desenvolver o software.
• C. que, nos métodos Ágeis deve ser evitado o teste de sistemas.
• D. que os esforços de teste devem ser exigidos desde o início do desenvolvimento.

Considerando as estimativas e os fatores de contingência no planejamento de um projeto de desenvolvimento de software, assinale a alternativa CORRETA.

• A. Os erros de estimativas ampliam-se ao longo da execução do projeto.
• B. Nos replanejamentos do projeto, devem ser modificadas as equipes.
• C. Se houver modificações nos fatores de contingência, o normal são eles serem reduzidos.
• D. Se houver replanejamentos, então eles devem ampliar o escopo dos requisitos.