View
105
Download
1
Category
Preview:
Citation preview
Para Computação
Aula de Monitoria – Prova 12011.2
oAlberto TrindadeoGisely Meloo José Araújo
Roteiro
• Crescimento de Funções
• Inclusão-Exclusão
• Indução Matemática
• Definições Recursivas
• Teorema Binomial
• Triângulo de Pascal
Crescimento de Funções
NOTAÇÃO NOMEO(xx) ordem exponencialO(x!) Ordem fatorialO(cx) ordem exponencialO(xc) Ordem polinomial
O(x · log x) ordem linear-logarítmica
O(x) ordem linearO(log x) ordem logarítmica
O(1) ordem constante
A letra c denota uma constante qualquer
Gisely Melo
Crescimento de Funções
Gisely Melo
Crescimento de Funções
Retire todas as Constantes: f(x): 3x2 + 9f(x): x2 O(x2)
Fica sendo o big-O aquele que possuir maior expoente.
g(x) = 3x2 + 70x5
= x2 + x5 = x5 O(x5
)reduzir os expoentes...h(x) = 3x2 + 70x5 + 10 x12/x4
= x2 + x5 + x12/x4
= x2 + x5 + x8 = x8
O(x8)
ampliar os expoentes...
r(x) = 3x2 + 70x5 + 5(x6 . x4)r(x) = x2 + x5 + (x6 . x4) = x2 + x5 + (x10) = (x10)
O(x10)
Gisely Melo
Crescimento de Funções
12n4 + 55 n3
78n2 + 10 n log n
log n + 240
O(n4) O(n5) O(n3)
O(n2) O(n5) O(n)
O(log n) O(n)
Gisely Melo
Crescimento de Funções
Gisely Melo
Crescimento de Funções
Gisely Melo
Crescimento de Funções
Gisely Melo
Crescimento de Funções
Gisely Melo
Crescimento de Funções
E se aparecer um sinal de MENOS na equação?
Gisely Melo
Crescimento de Funções
o BIG–O é pra estimar o tempo que um algoritmo leva pra ser realizado..
Essas equações que vocês veem, é como se fosse a “soma dos tempos”. E não faz sentido aparecer tempo negativo na
equação...
Gisely Melo
Inclusão-Exclusão
Gisely Melo
Inclusão-Exclusão
Exemplo QUANTAS CADEIAS DE 6 BITS COMEÇAM E TERMINAM COM BITS IGUAIS
2 X 2 X 2 X 2 X 2 X 1
321/0 1/0 1/0 1/0 1/0 *
Esse valor vai depender do primeiro, logo nessa posição só vai ter uma opção: A QUE FOI COLOCADA NO PRIMEIRO QUADRADO
Gisely Melo
Inclusão-ExclusãoExemplo
QUANTAS CADEIAS DE 8 BITS PODEMOS FORMAR DE MODO QUE ELAS SEJAM PALÍDROMOS?
2 X 2 X 2 X 2 X 1 X 1 X 1 X 1
16 CADEIAS
1/0 1/0 1/0 1/0 . . . .
Essas ultimas quatro posições vão procurar saber o que a correspondente a ela colocou...
Gisely Melo
Inclusão-Exclusão
1) Encontre a quantidade de inteiros positivos que são menores ou iguais a 100 que ñ são divisíveis por 5 e por 7.
Por 5 Por 7
Por 5 e por 7
Calcularemos primeiro a quantidade de inteiros positivos:
De 1 até 100100 números
Depois Calcularemos a quantidade de inteiros positivos divisíveis por 5 e por 7:
{35, 70} = 2 números
Resposta100 – 2 = 98
Gisely Melo
Inclusão-Exclusão
Exemplo:1) Quantas cadeias de tamanho 8 ou começam com o bit 1,
ou terminam com 2 bits 00?
1 1/0 1/0 1/0 1/0 1/0 1/0 1/0
1/0 1/0 1/0 1/0 1/0 1/0 0 0
1 1/0 1/0 1/0 1/0 1/0 0 0
Essa opção já esta incluída em A e em B
Gisely Melo
Inclusão-Exclusão Exemplo : questão 5 da lista de vocês:
QUANTAS CADEIAS DE 6 BITS COM 4BITS “1” JUNTOS EXISTEM?
Gisely Melo
Provar que a quantidade de subconjuntos de um conjunto finito S é .....
existem cadeias de bits de tamanho | S |. Logo, | P(S) |=
Inclusão-Exclusão
Gisely Melo
6) Entre 100 pessoas quantas pelo menos nasceram no mesmo mês?
• Eu vou dividir 100 por 12 pra ver quantos grupos de 12 certinho eu consigo formar
• Depois percebo que da 8,333333?
RespostaFunção teto de: 8,333 = 9
Gisely Melo
Crescimento de Funções
Inclusão-Exclusão
Exemplo
QUANTAS CADEIAS DE 6 BITS COMEÇAM E TERMINAM COM BITS IGUAIS
Gisely Melo
Indução matemática
1ª) Use a indução matemática para provar que para qualquer inteiro positivo n:
a) 2 + 6 + 10 + ... + (4n - 2) = 2n²
b) - 1 é divisível por 7
Alberto Trindade
Definições recursivas
2ª) Dê uma definição recursiva para a seqüência {An}, n = 1, 2, 3, ... se:
a) An = 5n – 3
b) An = n(n + 1)
c) An = n²
Alberto Trindade
Definições recursivas e Indução matemática
Alberto Trindade
Indução matemática
1ª) Use a indução matemática para provar que para qualquer inteiro positivo n:
a) 2 + 6 + 10 + ... + (4n - 2) = 2n²
b) - 1 é divisível por 7
Alberto Trindade
Definições recursivas
2ª) Dê uma definição recursiva para a seqüência {An}, n = 1, 2, 3, ... se:
a) An = 5n – 3
b) An = n(n + 1)
c) An = n²
Alberto Trindade
Definições recursivas e Indução matemática
3ª) Seja o n-ésimo número de Fibonacci. Use indução matemática para provar que )² + )² + ... + )² = )² . )², sendo n um inteiro positivo.
Alberto Trindade
Teorema binomial / Triângulo de Pascal
4ª) Prove, usando argumento combinatorial, que:
Ligeiro
Teorema binomial / Triângulo de Pascal
5ª) Prove
a) Usando argumento combinatório
b) Usando identidade de Pascal
Ligeiro
Teorema binomial / Triângulo de Pascal
6ª) ProveUse uma interpretação combinatória
Ligeiro
Recommended