Mdcvbg sdfg dfgsgf gdfsdfgs

Exercício de Revisão EX Segundo Semestre 2012 Data: 21/02/2013

Questão 1: Sob que circunstâncias um grafo dirigido representa uma função? E uma função injetora? E uma função sobrejetora?
Questão 2: Sejam f:S -->T e g: T --> U funções: a) Prove que se g°f é injetora, então f também o é. b) Prove que se g°f é sobrejetora, então g também o é.
Questão 3: Demonstre exibindo constantes que satisfaçam à definição de ordem de grandeza, que: a) g = Θ(f), f(x) = 3x³ - 7x e g(x) = x³/2; b) 300x³ + x² + 2 = Θ(x³)
Questão 4: Apresente uma função definida no conjunto dos inteiros não negativos que construa a sequência abaixo:
1, -13,15,-17,19, -111,…
Questão 5: Sejam as seguintes funções:

e os seguintes fatos (a > 0, b > 0, c > 0, n ϵ R)
Mostre para cada par de funções gi e gi+1 para 1 <= i <= 11 se gi é O ou Θ de gi+1.

Questão 6: A seguinte hierarquia de funções pode ser definida do ponto de vista assintótico:

Indique para cada par de expressões (A, B) na tabela abaixo, se a função A é O, o, Ω, ω ou Θ da função B. Assuma que k >= 1 e 0 < ϵ < 1 < c são constantes. Sua resposta deve ser na forma SIM ou NÃO. JUSTIFIQUE SUA RESPOSTA.
Nota: logk n ≡ log log ... n; log² n ≡ log log n; log³ n ≡ log log log n. Na letra (v), m é um número inteiro positivo.

Questão 7: Usando a definição formal de Θ, prove que 6n³ ≠ Θ(n²).
Questão 8: O que significa um algoritmo ser O(2) ou O(5)?
Questão 9: Para os itens abaixo considere que: I. Todas as variáveis e constantes são inteiras e positivas, a menos que sejam explicitamente identificadas de outra forma; II. As funções f(n) e g(n) são positivas e f(n) ˂ g(n) do ponto de vista de crescimento assintótico; III. p(n)=i=0gaini é um polinômio de grau g, as constantes ai, (1 <= i <= g) reais, sendo ag ≠0, e k uma constante.
Para cada afirmação dos itens, diga se é verdadeira ou falsa, provando ou fornecendo um contra-exemplo: a) f(n) =