Questões de Concurso
Comentadas para fcm
Foram encontradas 7.966 questões
Resolva questões gratuitamente!
Junte-se a mais de 4 milhões de concurseiros!
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 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.
T1 (n) = 9T1 (n/3) + n
T2 (n) = T2 (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:
Conheça nossos planos