1. O Problema da Mochila Inteira pode ser de forma ótima em tempo polinomial? 2. A apostila do curso aborda diversos problemas e suas resoluções usando as técnicas de projeto aqui estudadas. Podemos então discutir outros problem: e as estratégias usadas para resolv@-los de forma eficiente. 3. Vamos encontrar problemas, cujas soluções conhecidas são exponenciais Esses problemas são considerados intratáveis. 0 que podemos fazer para trat esses problemas? 4. Podemos usar, por exemplo, a técnica gulosa para tratar o problema da mochila, mas não consiguimos desenvolver algortimos eficientes para quebrar algoritmos modernos de criptografia. Por que? interessante nesse estudo è que embora não saibamos a resposta de P=NP? acrediamentos que P seja diferente de NP. Considerando Plt gt NP, podemo concluir que problemas NP-completos e NP -dificies não possuem soluções polinomiais. Assim, ao classifica um problema como NP -completo (ou dificl), temos que trabalhar com o uso de algoritmos aproximados ou o problema de modo à tratá-lo, ou seja conseguir uma solução adequada (mesmo que não a melhor de todas)para resolvê-lo computaci onalmente. então incluir nessa discussão exemplos de problemas e suas classes além de descrever como podemos provar a classe indicada. Uma técnica importante nesse estudo é a de Redutibilidade.

1. O Problema da Mochila Inteira pode ser resolvido de forma ótima em tempo polinomial?<br />2. A apostila do curso aborda diversos problemas e suas resoluções usando as técnicas de projeto aqui estudadas. Podemos então discutir outros problemas e as estratégias usadas para resolvê-los de forma eficiente.<br />3. Vamos exemplificar problemas, cujas soluções conhecidas são exponenciais. Esses problemas são considerados intratáveis. O que podemos fazer para tratar esses problemas?<br />4. Podemos usar, por exemplo, a técnica gulosa para tratar o problema da mochila, mas não conseguimos desenvolver algoritmos eficientes para quebrar algoritmos modernos de criptografia. Por que?<br />É interessante nesse estudo é que embora não saibamos a resposta de $P=NP?$, acreditamos que P seja diferente de NP. Considerando $P\lt \gt NP,$ podemos concluir que problemas NP-completos e NP difíceis não possuem soluções polinomiais. Assim, ao classificar um problema como NP-completo, temos que trabalhar com o uso de algoritmos aproximados ou o problema de modo à tratá-lo, ou seja, conseguir uma solução adequada (mesmo que não a melhor de todas) para resolvê-lo computacionalmente.<br /><br />Vamos incluir nessa discussão exemplos de problemas e suas classes, além de descrever como podemos provar a classe indicada. Uma técnica importante nesse estudo é a de Redutibilidade.