ALGORITMOS E FUNDAMENTOS DA TEORIA DA COMPUTAÇÃO

ALGORITMOS E FUNDAMENTOS DA TEORIA DA COMPUTAÇÃO

TEORIA DA COMPUTAÇÃO

Prova Parcial II

1) (6,0) Marque V ou F. Cada questão vale 0,5 pontos. Uma errada anula uma certa (pode deixar sem marcar caso não tenha certeza).

( ) A “taxa de crescimento” de uma função mede o aumento dos valores da função quando a entrada se torna arbitrariamente grande.

( ) Um algoritmo é dito ser de tempo polinomial se seu tempo de execução no seu pior caso é O(nc), onde c é uma constante não negativa.

( ) Um algoritmo é dito ser de tempo exponencial se a taxa de crescimento é pelo menos cn para uma constante c>1.

( ) Um algoritmo é dito eficiente se possui tempo polinomial.

( ) A classe NP pode ser descrita pela classe de problemas em que se você puder solucionar qualquer um deles em tempo polinomial, então você poderia solucionar todos eles em tempo polinomial.

( ) P = NP implica que todos os problemas complexos na ciência da computação possuem solução em tempo polinomial.

( ) A classe P é a classe de todos os problemas de decisão que podem ser solucionados em tempo polinomial (no pior caso).

( ) NP é o conjunto de todas as linguagens que podem ser verificadas em tempo polinomial.

( ) NP é o conjunto de todos os problemas que podem ser solucionados em tempo polinomial por um algoritmo não-determístico.

( ) P ⊆ NP pois se um problema pode ser resolvido em tempo polinomial, ele também pode ser verificado em tempo polinomial.

( ) Uma redução polinomial do problema A para o problema B pode ser descrita como um algoritmo não-deterministico polinomial transformador de uma entrada de A para uma entrada de B e mais um algoritmo não-determinístico polinomial transformador da saída de B para uma saída de A.

( ) Todo problema na classe NP-Difícil está também na classe NP, mas nem todo problema NP está na classe NP-Difícil.

( ) O Teorema de Cook mostra que todos os problemas em NP podem ser reduzidos ao problema Independent Set.

2) (2,0) Cada grupo apresentou em sala uma redução para um problema específico mostrando que tal problema fazia parte da classe NP-Completo. Mostre que esse mesmo problema também é um problema pertencente à classe NP-Difícil.

3) (2,0) Escolha um problema apresentado por outro grupo diferente ao seu e mostre que o problema faz parte da classe NP.