Codigo so

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 as respostas 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.