Prova 3 Teoria da Computação

Prova 3 Teoria da Computação

1. Marque a correta

   • Nas Linguagens Recursivas Loop(M) = Vazio.
   • Um problema da Classe NP-Dificil é a busca por uma solução ótima em um problema da classe NP.
   • A Classe dos problemas Parcialmente Solucionáveis é equivalente à classe das linguagens Enumeráveis Recursivamente.
   • II, III, IV

2. Como provamos que um problema está em NP? :

   • Um problema está em NP quando seu algoritmo tem tempo exponencial para sua solução de acordo com sua entrada, porem a sua verificação pode ser em tempo polinomial

3. Explique como provar que um problema é NP - COMPLETO?

   • Um problema é NP completo caso ele se encaixe nas seguintes restrições
     • 1. Deve pertencer a classe dos problemas NP
     • 2.Pode ser transformado, usando um NP-Completo conhecido como exemplo e transforma-lo para o desejado

4. 6) Um grande problema em aberto na Computação é a questão P vs NP. Que pergunta esta questão visa responder?

5. 7) A equipe de desenvolvimento do Google está enfrentando o seguinte problema: O Navegador Chrome vem apresentando grande instabilidade: ao inserir uma url válida o sistema funciona normalmente. Ao informar uma url inválida o sistema hora apresenta a tela abaixo e hora fica simplesmente "carregando" e não apresenta nenhuma informação

   • A)Explique aos desenvoivedores do Google que tipo de (Classe) de problema eles tem em mãos:
     • A) Classe 2 problema parcialmente solucionável; Se existir um algoritmo tal que para quando a resposta é afirmativa(aceita) e quando a resposta é negativa pode parar em rejeita ou permanecer em LOOP inifinito.

6. b) Se fossemos converter o problema em uma Linguagem e olhássemos para a Hierarquia de Chomsky. Que tipo de linguagem seria esta?

   • b) Linguagem Enumerável Recursivamente

7. 9. Diferencie problema Completamente lnsolúvel de problema Intratável:

   • No problema completamente insolúvel eu conheço a sua função de entrada e sei qual a sua saída porém não conheço algoritmo que resolva este problema. Já o intratável não tem algortimo que o responda em tempo polinomial para todas as suas entradas

8. 10. De três exemplos de problemas NP-Completos

   • Problema da Mochila
   • Cobertura de Vertices
   • Problema do Click
   • Tetris
   • Torre de Hanoi
   • Problema da Satisfatibilidade Booleana