Blog

UFG – Instituto de Informática Bacharelado em Ciências da Computação Análise e Projeto de Algoritmos Prof. Humberto Longo 1a 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 I F] Se f (n) e g(n) então h(n) e (n)). Solução: Verdadeiro. é transitivo. (b) 0. 2 [VI (n)).

Solução: Ver mesmo que f (n) e O OF2 Swipe to view nextp então h(n) h(n) (n)) é o [V I F] Se f (n) E e g(n) E O(f (n)), então f (n) = g(n). (c) 0. 2 Solução: Falso. Conside Swige to next page Considere f (n) = n e g(n) = n + 1. n (d) 0. 2 [V F] f (n) 100 e Q(n). n Solução: Verdadeiro. 100< c. n para c- 1 . 200 (e) 0. 2 [V I F] se f(n) = 25. n. + 5. n e I . n. Ig(n), então f (n) 2 Solução: Falso. lim f (n) = f (n) g(n)

Observações: • As questões nao 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.