Upload
internet
View
109
Download
1
Embed Size (px)
Citation preview
Para Computação
Aula de Monitoria – Prova 12012.1 – Gisely Melo
Livro!
Monitoria [12/04/2012] - Parte Gisely 2
1) Notas sobre crescimento de função – 180
2) Notas sobre Indução – 263
3) Notas sobre Definições Recursivas – 295
4) Contagem – 335
5) inclusão-exclusão – 499
6) Teorema binomial, Triângulo de Pascal(permutações) - 355
Contagem
Monitoria [12/04/2012] - Parte Gisely 3
exemplo 1QUANTAS CADEIAS DE 6 BITS COMEÇAM E TERMINAM COM BITS IGUAIS
2 X 2 X 2 X 2 X 2 X 1
32
1/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
Contagem
Monitoria [12/04/2012] - Parte Gisely 4
exemplo 2QUANTAS 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...
Contagem
Monitoria [12/04/2012] - Parte Gisely 5
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
Contagem
Monitoria [12/04/2012] - Parte Gisely 6
|A1 U A2 U A3|= |A1| + |A2| + |A3| − |A1 A2| − |A2 A3| − |A1 A3| + |A1 A2 A3|....????????????
Contagem
Monitoria [12/04/2012] - Parte Gisely 7
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
|A| =
|B| =
|AB| =
(A U B) = |A| + |B| - |AB|
Essa opção já esta incluída em A e em B
+ = 192
Exemplo:1) Quantas cadeias de tamanho 8 ou começam com o bit 1, ou terminam com 2 bits
00?
Contagem
Monitoria [12/04/2012] - Parte Gisely 8
Exemplo : questão 5 da lista de vocês:QUANTAS CADEIAS DE 6 BITS COM 4BITS “1” JUNTOS EXISTEM?
Contagem
Monitoria [12/04/2012] - Parte Gisely 9
Exemplo:QUANTAS CADEIAS DE 5 BITS COMEÇAM OU TERMINAM COM ”00”?
Contagem
Monitoria [12/04/2012] - Parte Gisely 10
Provar que a quantidade de subconjuntos de um conjunto finito S é .....
existem cadeias de bits de tamanho | S |. Logo, | P(S) |=
Cada elemento pode estar presente ou
não no conjunto das partes. Temos duas possibilidades pra
cada um
Casa dos pombos
Monitoria [12/04/2012] - Parte Gisely 11
Casa dos pombos
Monitoria [12/04/2012] - Parte Gisely 12
5) Qual o número mínimo de pessoas que deveríamos agrupar para garantir que pelo menos 2 nasceram no mesmo mês e com a mesma
letra inicial do nome?1. JANEIRO2. FEVEREIRO3. MARÇO4. ABRIL5. MAIO6. JUNHO7. JULHO8. AGOSTO9. SETEMBRO10. OUTUBRO11. NOVEMBRO12. DEZEMBRO
QRSTUVWXYZ
• No pior caso, se tivermos 26*12=312 pessoas em todos os meses do ano,
• portanto, se adicionarmos mais uma sempre haverá alguma outra pessoa que nasceu no mesmo mês e seu nome tem a mesma letra inicial.
Resposta312 + 1 = 313
ABCDEFGHIJKLM
Casa dos pombos
Monitoria [12/04/2012] - Parte Gisely 13
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
Mas Rafael Acevedo e João Pedro Existem...
Monitoria [12/04/2012] - Parte Gisely 14
Mas Rafael e João Existem...
Monitoria [12/04/2012] - Parte Gisely 15
Na cabeça deles, a resposta era 8 e isso fez com que os dois ficassem no meu pé depois da aula. Tô mentindo? eheheh
• Vamo FINGIR que eles estão certos e imagina que a resposta é 8 beleza?
?• Multiplica ai 8 por 12, da quanto
• 96 né? Mas são 100 pessoas. Aonde vão parar aos outras 4?
Mas Rafael e João Existem...
Monitoria [12/04/2012] - Parte Gisely 16
É só imaginar que já tem 12 grupos com 8 pessoas fechados ta ligado?
• E as 4 que estão perambulando por ai?
janeiro
8 pessoas
fevereiro
8 pessoas
março
8 pessoas
abril
8 pessoas
maio
8 pessoas
junho
8 pessoas
julho
8 pessoas
agosto
8 pessoas
setembro
8 pessoas
outubro
8 pessoas
novembro
8 pessoas
dezembro
8 pessoas
• Elas vão ter que entrar em algum mês desse ai.• Vamo colocar cada uma em um mês diferente.
+1 +1
+1 +1
Mas Rafael e João Existem...
Monitoria [12/04/2012] - Parte Gisely 17
É só imaginar que já tem 12 grupos com 8 pessoas fechados ta ligado?
janeiro
8 pessoas
fevereiro
8 pessoas
março
8 pessoas
abril
8 pessoas
maio
8 pessoas
junho
8 pessoas
julho
8 pessoas
agosto
8 pessoas
setembro
8 pessoas
outubro
8 pessoas
novembro
8 pessoas
dezembro
8 pessoas
+1 +1
+1 +1
Essas 4 pessoas a mais são justamente a parte decimal do 8,333 sacaram?
Monitoria [12/04/2012] - Parte Gisely 18
Aritmética Modular!
Aritmética Modular!
Monitoria [12/04/2012] - Parte Gisely 19
Dizemos que a ≡ b(mod m) se e somente se a mod m = b mod m.
16 mod 5
7 ≡ 2(mod 5)
Aritmética Modular!
Monitoria [12/04/2012] - Parte Gisely 20
10) Indique o inverso de: a) 4 mod 9 b) 3 mod 5
c) 7 mod 17
Monitoria [12/04/2012] - Parte Gisely 21
Teorema Chinês...
Teorema Chinês!
Monitoria [12/04/2012] - Parte Gisely 22
11) Indique as soluções para os seguintes sistemas
a) X ≡ 3 (mod 9) X ≡ 4 (mod 7) X ≡ 2 (mod 5)
Teorema Chinês!
Monitoria [12/04/2012] - Parte Gisely 23
X ≡ a1 (mod m1)
X ≡ a2 (mod m2)
X ≡ a3 (mod m3)
M1.Y1 ≡ 1(mod m1)M2.Y2 ≡ 1(mod m2)M3.Y3 ≡ 1(mod m3)
M = m1 X m2 X m3
Mk = M/mk
X = a3 . M1. Y1 + a2.M2.Y2 + a3.M3.Y3(mod M)
Teorema Chinês!
Monitoria [12/04/2012] - Parte Gisely 24
LOCALIZANDO OS VALORES DAS VARIÁVEIS NO SISTEMA:a) X ≡ 3 (mod 9) X ≡ 4 (mod 7) X ≡ 2 (mod 5)
M1 = m2.m3 = 35M2 = m1.m3 = 45M3 = m2.m1 = 63M = m1 X m2 X m3
M = 315
X = a1 . M1. Y1 + a2.M2.Y2 + a3.M3.Y3(mod M)
a1 = 3
a2 = 4
a3 = 2
m1 = 9
m2 = 7
m3 = 5
Teorema Chinês!
Monitoria [12/04/2012] - Parte Gisely 25
35.Y1 ≡ 1(mod 9)Primeiro veja qual o numero Z, tal que Z é o RESTO da divisão de 35 por 9
nesse caso Z = 8(8) .Y1 ≡ 1(mod 9)
9 = 8.1 + 11= 9 – 1.8
O INVERSO NÃO PODE SER UM NUMERO NEGATIVO. PORTANTO MESMO EU TENDO ACHADO (-1), PRA O NUMERO FICAR POSITIVO EU SOMO 9..... O INVERSO
NESSE CASO VAI SER:
Y1 = 8
SÓ FALTAM OS INVERSOS
35.Y1 ≡ 1(mod 9)45.Y2 ≡ 1(mod 7)63.Y3 ≡ 1(mod5)
M1.Y1 ≡ 1(mod m1)
Teorema Chinês!
Monitoria [12/04/2012] - Parte Gisely 26
63.Y3 ≡ 1(mod5)Primeiro veja qual o numero Z, tal que Z é o RESTO da divisão de 63 por 5nesse caso Z = 3
(3) .Y2 ≡ 1(mod 5)5 = 3.1 + 2 2 = 5 -1.3 (equação 1)3 = 2.1 + 1 1 = 3 -1.2 (equação 2)Substituindo a equação1 na 2 temos:
1 = 3 – 1.[5 -1.3]1 = 3 -1.5 +1.31= -1.5 + 2.3OBSERVE: o resultado já é positivo, logo eu não somo mais nada e esse já é o meu inverso
Y3 = 2
M3.Y3 ≡ 1(mod m3)
Teorema Chinês!
Monitoria [12/04/2012] - Parte Gisely 27
X = a1 . M1. Y1 + a2.M2.Y2 + a3.M3.Y3(mod M)X = {3 . 35. 8 + 4.45.5 + 2.63.2}(mod 315)X = 840+ 900 + 252(mod 315)X = 1992(mod 315)X = 102
a1 = 3 a2 = 4 a3 = 2
M1 = 35 M2 = 45 M3 = 63
M = 315Y1 = 8 Y2 = 5 Y3 = 2
Agora que temos todos os valores necessários, podemos aplicar na fórmula:
Teorema Chinês!
Monitoria [12/04/2012] - Parte Gisely 28
X ≡ 5 (mod 11) X ≡ 3 (mod 7) X ≡ 2 (mod 3)
Crescimento de Função!
Monitoria [12/04/2012] - Parte Gisely 29
Crescimento de Função!
Monitoria [12/04/2012] - Parte Gisely 30
A letra c denota uma
constante qualquer
NOTAÇÃO NOMEO(xx) ordem exponencialO(x!) Ordem fatorialO(cx) ordem exponencialO(xc) Ordem polinomialO(x · log x) ordem linear-logarítmica
O(x) ordem linearO(log x) ordem logarítmicaO(1) ordem constante
Abaixo há uma lista de classes de funções que são bastante utilizadas para análise de algoritmos, por ordem decrescente de crescimento de funções.
Crescimento de Função!
Monitoria [12/04/2012] - Parte Gisely 31
PROPRIEDADES:
Crescimento de Função!
Monitoria [12/04/2012] - Parte Gisely 32
n!2n
n2
n log nnlog n1
1 <= log n <= n <= n log n <= n2 <= 2n <= n! <= nn
O resto é derivada deles...
Crescimento de Função!
Monitoria [12/04/2012] - Parte Gisely 33
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
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)
O(x5 )
Crescimento de Função!
Monitoria [12/04/2012] - Parte Gisely 34
Outro exemplo.... + (=
O() = O()
Mas se ele pedisse o valor de a para O()Ai você arredondaria pra cima
O() = O() =
Arredondando...O()O()
a = 4
Crescimento de Função!
Monitoria [12/04/2012] - Parte Gisely 35
Outro exemplo....=
Vejam: nesse caso, sabemos que ganha de x!Mas a resposta vai ser
O(.)Por que a gente não pode eliminar um membro de um produto, só se for
soma que a gente desconsidera, ou se o membro for uma constante..
Mas se ele pedisse o valor de a para O()?A gente não pediria... Essas funções são as maiores, como a gente ia
chegar em X elevado a alguma coisa? Certo?
Crescimento de Função!
Monitoria [12/04/2012] - Parte Gisely 36
Ai tu pode se perguntar: e se a equação for um produto bem grande ?Não simplifica nada... Se for um produto NÃO MEXAM NELE Exemplo:
O big-O disso é:
O()
Crescimento de Função!
Monitoria [12/04/2012] - Parte Gisely 37
Outro exemplo....Quem ganha?
Quem cresce mais rápido é quem tem o coeficiente que cresce mais rápido..No caso a resposta seria:
O
Crescimento de Função!
Monitoria [12/04/2012] - Parte Gisely 38
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...
Monitoria [12/04/2012] - Parte Gisely 39
Tem mais ó...
A questão diz que f e g são sobrejetoras, e pergunta se fog também é!