Codigo so

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (276 palavras )
  • Download(s) : 0
  • Publicado : 21 de março de 2012
Ler documento completo
Amostra do texto
UFG - Instituto de Informática Bacharelado em Ciências da Computação

Análise e Projeto de Algoritmos Prof. Humberto Longo

1ªAvaliação – 2012/1
Nome: Data: 08 / 03 / 2012

1. Decida se as afirmações a seguir são verdadeiras ou falsas. Justifique brevemente todas asrespostas para receber todo o crédito. (a) 0.2 [ V | F ] Se f (n) ∈ Θ(g(n)) e g(n) ∈ Θ(h(n)), então h(n) ∈ Θ(f (n)). Solução: Verdadeiro. Θ étransitivo.

(b) 0.2 [ V | F ] Se f (n) ∈ O(g(n)) e g(n) ∈ O(h(n)), então h(n) ∈ Ω(f (n)). Solução: Verdadeiro. O é transitivo e h(n) ∈ Ω(f(n)) é o mesmo que f (n) ∈ O(h(n)).

[ V | F ] Se f (n) ∈ O(g(n)) e g(n) ∈ O(f (n)), então f (n) = g(n). (c) 0.2 Solução: Falso.Considere f (n) = n e g(n) = n + 1.

n (d) 0.2 [ V | F ] f (n) = 100 ∈ Ω(n). n Solução: Verdadeiro. 100 < c.n para c =

1 . 200

(e) 0.2 [ V| F ] Se f (n) = 25.n. ln(n) + 5.n e g(n) = 1 .n. lg(n), então f (n) ∈ O(g(n)). 2 Solução: Falso. lim f (n) = ∞ ⇒ f (n) ∈ ω(g(n)). g(n)n→∞

Observações: • As questões não precisam ser respondidas na mesma ordem em que foram enunciadas. • As respostas podem ser escritas a lápis.• A avaliação é individual e sem qualquer tipo de consulta. • Para a correção da avaliação será levada em consideração, além da exatidão,o rigor e o formalismo empregados nas respostas. • Defina a notação utilizada, justifique suas afirmações e os conceitos empregados.

tracking img