Para Computação
Aula de Monitoria – Prova 1
2011.2
o Alberto Trindade
o Gisely Melo
o 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
O(xx)
O(x!)
O(cx)
O(xc)
NOME
ordem exponencial
Ordem fatorial
ordem exponencial
Ordem polinomial
O(x · log x)
ordem linear-logarítmica
O(x)
O(log x)
O(1)
ordem linear
ordem logarítmica
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 + 9
f(x): x2
O(x2)
Fica sendo o big-O aquele que
possuir maior expoente.
g(x) = 3x2 + 70x5
= x 2 + x5
= x5
O(x5 )
reduzir os expoentes...
ampliar os expoentes...
2
5
12
4
h(x) = 3x + 70x + 10 x /x
r(x) = 3x2 + 70x5 + 5(x6 . x4)
= x2 + x5 + x12/x4
2 + x5 + (x6 . x4)
r(x)
=
x
2
5
8
=x +x + x
= x2 + x5 + (x10)
= (x10)
= x8
10)
O(x
8
O(x )
Gisely Melo
Crescimento de Funções
12n4 + 55 n3
O(n4)
78n2 + 10 n log n
O(n2)
log n + 240
O(n5)
O(n5)
O(log n)
Gisely Melo
O(n)
O(n3)
O(n)
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
2X2X2X2X2X1
1/0
1/0
1/0
1/0
1/0
*
32
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ão
Exemplo
QUANTAS CADEIAS DE 8 BITS PODEMOS FORMAR DE MODO QUE ELAS SEJAM
PALÍDROMOS?
2X2X2X2X1X1X1X1
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 7
Por 5
Calcularemos primeiro a quantidade de
inteiros positivos:
De 1 até 100
100 números
Depois Calcularemos a quantidade de
inteiros positivos divisíveis por 5 e por 7:
Por 5 e por 7
{35, 70} = 2 números
Resposta
100 – 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
Inclusão-Exclusão
Provar que a quantidade de subconjuntos
de um conjunto finito S é 2|𝑠| .....
existem 2|𝑠| cadeias de bits de tamanho | S |. Logo, | P(S) |= 2|𝑠|
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
?
Resposta
Funçã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) 23n - 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) 23n - 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
(𝑓1 )² + (𝑓2 )² + ... + (𝑓𝑛 )² = (𝑓𝑛 )² . (𝑓𝑛+1 )², sendo n um
inteiro positivo.
Alberto Trindade
Teorema binomial / Triângulo de Pascal
4ª) Prove, usando argumento combinatorial, que:
𝑛
0
2
𝑛
+
1
2
𝑛
+ ⋯+
𝑛
Ligeiro
2
2𝑛
=
𝑛
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ª) Prove
Use uma interpretação combinatória
Ligeiro