Mdcvbg sdfg dfgsgf gdfsdfgs

Disponível somente no TrabalhosFeitos
  • Páginas : 3 (539 palavras )
  • Download(s) : 0
  • Publicado : 24 de março de 2013
Ler documento completo
Amostra do texto
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çãosobrejetora?
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: Demonstreexibindo 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 noconjunto 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)
Mostrepara 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 cadapar 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 sejamexplicitamente 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, asconstantes 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) =...
tracking img