Questões de Concurso Para fcm

Sejam A e B duas linguagens sobre o alfabeto binário, isto é, sobre o alfabeto composto apenas por 0’s e 1’s. Seja A a linguagem na qual a quantidade de 0’s e 1’s é igual. Seja B a linguagem onde nenhum 0 ocorre após um caractere 1.

Sobre essas linguagens, é correto afirmar que

Avalie as afirmações abaixo:

I. A classe P e a classe NP são disjuntas.

II. A classe P é um subconjunto da classe co-NP.

III. Problemas coNP-completos admitem um certificado tal que uma resposta negativa pode ser verificada em tempo polinomial.

IV. A interseção das classes NP e co-NP é vazia.

Está correto apenas o que se afirma em

A teoria de algoritmos de aproximação, às vezes chamados de algoritmos aproximativos, é extremamente útil para tratar problemas NP-difíceis.

Sobre algoritmos de aproximação, é correto afirmar que

Uma transformação polinomial é uma ferramenta fundamental na demonstração de que determinado problema é NP-difícil.

Avalie as afirmações sobre propriedades que transformações polinomiais devem satisfazer.

I. Para toda transformação polinomial, deve existir uma Máquina de Turing determinística que a computa em tempo polinomial.

II. Se uma transformação polinomial transforma um elemento de linguagem A em um elemento de linguagem B, então A é um subconjunto não necessariamente próprio de B.

III. Se uma transformação polinomial transforma um elemento de uma linguagem A em um elemento de linguagem B, e A pertence a NP, então B pertence a NP.

IV. A quantidade de espaço utilizada pela transformação pode ser limitada por uma constante.

Está correto apenas o que se afirma em

Considere o grafo abaixo assim como sua representação por lista de adjacência.

A Árvore em Largura e a Árvore em Profundidade, respectivamente, tendo como raiz o vértice 1,são

Considere a matriz de adjacência abaixo correspondente a um grafo direcionado ponderado.

Avalie as afirmações referentes ao menor caminho tendo como origem o vértice 1.

I. O menor caminho do vértice 1 até o vértice 7 passa pelos vértices 3 e 8.

II. O menor caminho do vértice 1 até o vértice 5 passa pelo vértice 2.

III. O menor caminho do vértice 1 até o vértice 9 passa pelos vértices 2 e 6.

IV. O menor caminho do vértice 1 até o vértice 8 passa pelos vértices 3 e 6.

V. O menor caminho do vértice 1 até o vértice 6 passa pelo vértice 4.

Está correto apenas o que se afirma em

Considere a equação de recorrência abaixo.

T(n) = 0 para n = 1.

T(n) = 2T(n/2) + n – 1 para n > 1.

Após a resolução, a solução encontrada é

Utilize o método mestre para resolver recorrências das equações abaixo.

T₁ (n) = 9T₁ (n/3) + n

T₂ (n) = T₂ (2n/3) + 1

As ordens de complexidade correspondentes são

O Manifesto Ágil para o Desenvolvimento de Software, proposto por Beck, K. et al. (2001), propõe 12 princípios.

NÃO correspondem a um desses princípios criados por esses autores:

Sobre as afirmativas abaixo relacionadas aos conceitos de serviços Web

Considere os acrônimos:

•REST - Representational State Transfer;

•SOAP - Simple Object Access Protocol .

É correrto afirmar que o