1. Considere as seguintes funções:
   
   
   1. 10.n^p
   2. log n
   3. log ( n² )
   4. 0.005 . n^0.00001
   5. 1000. (log n)²
   6. 30.n³.log n
   7. 50.n.log² n
   8. (log n)^{log n}
   9. n/log n
   10. 70.n
   11. log log n
   12. (1.5)^{(log n)2}
   13. 90.n².log n + n³. log n
   
   
   • Coloque as funoeacima em ordem de crescimento assintótico, i.e. valor
     quando n ¾® ¥.
     
     
   • Utilize pelo menos três vezes cada um dos símbolos O,    W,    Q,    o, e w para indicar a relação existente entre pares das funoeacima (não vale recíprocos).
   
   
2. Verdadeiro ou Falso. Justifique.
   1. (log n)¹⁰⁰ = O(n^e), " e > 0.
   2. 2ⁿ⁺¹ = O (2ⁿ).
   3. Se g(n,m) = m log_d n onde d = [ m/n + 2] ( [x] é o menor inteiro maior que x), m = O(n²), então g(n,m) = O(m^{(1 + e)}) " e > 0.
   
   
3. Encontre contra-exemplos para as proposições abaixo.
   1. Se f(n) = O(s(n)) e g(n) = O(r(n)), então f(n) - g(n) = O(s(n)-r(n))
   2. Se f(n) = O(s(n)) e g(n) = O(r(n)), então f(n)/g(n) = O(s(n)/r(n))
   
   
4. Sejam P₁, P₂ e P₃ três problemas tais que P₁ a_n P₂ a_n³logn P₃ (i.e., P₁ é redutível a P₂ em tempo linear e P₂ a P₃ em tempo n³ log n). Assuma a hipótese de que P₁ é W(n log n). Assuma também que você conhece um algoritmo O (n³) para resolver P₃. Discuta as afirmações abaixo, considerando que somente o conhecimento acima está disponível.
   1. O que você pode dizer sobre a complexidade de resolução de P₂ ? Qual a complexidade do melhor algoritmo que você conhece para P₂ ?
   2. Todo algoritmo que resolve P₂ tem que gastar pelo menos tempo quadrático (P₂ é W(n²)).
   3. W(n log n) é um limite inferior para a complexidade de P₃.
   4. Todo algoritmo que resolve P₁ pode ser usado para resolver P₂.
   5. Todo algoritmo que resolve P₃ pode ser usado para resolver P₂.
   6. P₂ pode ser resolvido no pior caso em tempo O(n log n).
   
   
5. Seja P o conjunto dos problemas para os quais existem algoritmos determinísticos polinomias para a sua resolução . Seja NP o conjunto dos problemas para os quais existem algoritmos não-determinísticos polinomias para a sua resolução . Naturalmente P está contido em NP. Considere os problemas P₁ Î P e P₂ Î NP-completo. Indique se cada afirmação abaixo é verdadeira, falsa ou se não se sabe.
   1. Conhece-se uma redução de P₁ para P₂ que toma tempo polinomial (O(n^k)).
   2. Se existe um algoritmo determinístico polinomial para a resolução de P₂ então podemos afirmar que P₁ Î NP-completo assim como P₂ Î P.
   3. P₂ é pelo menos tão difícil quanto 3-SAT.
   4. 3-SAT é pelo menos tão difícil quanto P₂.
   5. Existe uma redução de P₂ para P₁ que toma tempo polinomial.
   
   
6. Defina as classes de problemas P, NP e NP-completo Relacione estas classes e dê um exemplo de problema para cada classe.
   
   
7. Dado que você conhece um algoritmo determinístico polinomial para a resolução do problema (CMC) abaixo, USE ESTE CONHECIMENTO para provar que você também conhece um algoritmo determinístico polinomial para a resolução do problema (VMC) apresentado em seguida.
   
   (CMC) Dado um grafo orientado G=(V,A) com comprimentos positivos associados aos arcos (i,j) Î A, dois vértices i,j Î V e uma constante K. Pergunta-se se existe um caminho do vértice i ao vértice j que possua comprimento menor ou igual à K.
   
   (VMC) Dado um grafo orientado G=(V,A), com comprimentos positivos associados aos arcos (i,j) Î A, e uma constante K. Pergunta-se se existe um par de vértices (i,j) para o qual exista um caminho de i a j e de j a i que tenha comprimento menor ou igual à K.

This document was translated from L^AT_EX by H^EV^EA.