Questões de Concurso
Para ifn-mg
Foram encontradas 1.498 questões
Resolva questões gratuitamente!
Junte-se a mais de 4 milhões de concurseiros!
Leia, com atenção, o texto a seguir.
“Uns eram pela maioridade; outros achavam que o melhor mesmo era que uma junta de homens direitos e sábios ficasse no governo.”
(VERÍSSIMO, Érico. Um certo capitão Rodrigo. São Paulo: Companhia das Letras, 2005. p.132.)
No texto, as palavras uns e uma são, respectivamente,
Seja A um autômato finito não determinístico que reconhece uma linguagem L. Seja B um autômato finito determinístico que reconhece a mesma linguagem.
Sobre o número de estados de A e de B, é correto afirmar que
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 é
Conheça nossos planos