Para Computação Aula de Monitoria – Prova 1 2012.1 – Gisely Melo

  • View
    107

  • Download
    1

Embed Size (px)

Text of Para Computação Aula de Monitoria – Prova 1 2012.1 – Gisely Melo

  • Slide 1
  • Para Computao Aula de Monitoria Prova 1 2012.1 Gisely Melo
  • Slide 2
  • Livro! Monitoria [12/04/2012] - Parte Gisely2 1) Notas sobre crescimento de funo 180 2) Notas sobre Induo 263 3) Notas sobre Definies Recursivas 295 4) Contagem 335 5) incluso-excluso 499 6) Teorema binomial, Tringulo de Pascal (permutaes) - 355
  • Slide 3
  • Contagem Monitoria [12/04/2012] - Parte Gisely3 exemplo 1 QUANTAS CADEIAS DE 6 BITS COMEAM E TERMINAM COM BITS IGUAIS 2 X 2 X 2 X 2 X 2 X 1 32 1/01/01/01/01/0 * Esse valor vai depender do primeiro, logo nessa posio s vai ter uma opo: A QUE FOI COLOCADA NO PRIMEIRO QUADRADO
  • Slide 4
  • Contagem Monitoria [12/04/2012] - Parte Gisely4 exemplo 2 QUANTAS CADEIAS DE 8 BITS PODEMOS FORMAR DE MODO QUE ELAS SEJAM PALDROMOS? 2 X 2 X 2 X 2 X 1 X 1 X 1 X 1 16 CADEIAS 1/0.... Essas ultimas quatro posies vo procurar saber o que a correspondente a ela colocou...
  • Slide 5
  • Contagem Monitoria [12/04/2012] - Parte Gisely5 1)Encontre a quantidade de inteiros positivos que so menores ou iguais a 100 que so divisveis por 5 e por 7. Por 5 Por 7 Por 5 e por 7 Calcularemos primeiro a quantidade de inteiros positivos: De 1 at 100 100 nmeros Depois Calcularemos a quantidade de inteiros positivos divisveis por 5 e por 7: {35, 70} = 2 nmeros Resposta 100 2 = 98
  • Slide 6
  • Contagem Monitoria [12/04/2012] - Parte Gisely6
  • Slide 7
  • Contagem Monitoria [12/04/2012] - Parte Gisely7 11/0 0 0 1 0 0 Essa opo j esta includa em A e em B Exemplo: 1) Quantas cadeias de tamanho 8 ou comeam com o bit 1, ou terminam com 2 bits 00?
  • Slide 8
  • Contagem Monitoria [12/04/2012] - Parte Gisely8 Exemplo : questo 5 da lista de vocs: QUANTAS CADEIAS DE 6 BITS COM 4BITS 1 JUNTOS EXISTEM?
  • Slide 9
  • Contagem Monitoria [12/04/2012] - Parte Gisely9 Exemplo: QUANTAS CADEIAS DE 5 BITS COMEAM OU TERMINAM COM 00?
  • Slide 10
  • Contagem Monitoria [12/04/2012] - Parte Gisely10 Cada elemento pode estar presente ou no no conjunto das partes. Temos duas possibilidades pra cada um
  • Slide 11
  • Casa dos pombos Monitoria [12/04/2012] - Parte Gisely11
  • Slide 12
  • Casa dos pombos Monitoria [12/04/2012] - Parte Gisely12 5) Qual o nmero mnimo de pessoas que deveramos agrupar para garantir que pelo menos 2 nasceram no mesmo ms e com a mesma letra inicial do nome? 1.JANEIRO 2.FEVEREIRO 3.MARO 4.ABRIL 5.MAIO 6.JUNHO 7.JULHO 8.AGOSTO 9.SETEMBRO 10.OUTUBRO 11.NOVEMBRO 12.DEZEMBRO QRSTUVWXYZQRSTUVWXYZ 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 ms e seu nome tem a mesma letra inicial. Resposta 312 + 1 = 313 ABCDEFGHIJKLMABCDEFGHIJKLM
  • Slide 13
  • Casa dos pombos Monitoria [12/04/2012] - Parte Gisely13 6) Entre 100 pessoas quantas pelo menos nasceram no mesmo ms? Eu vou dividir 100 por 12 pra ver quantos grupos de 12 certinho eu consigo formar Depois percebo que da 8,333333 ? Resposta Funo teto de: 8,333 = 9
  • Slide 14
  • Rafael Acevedo Joo Pedro Mas Rafael Acevedo e Joo Pedro Existem... Monitoria [12/04/2012] - Parte Gisely14
  • Slide 15
  • Mas Rafael e Joo Existem... Monitoria [12/04/2012] - Parte Gisely15 Na cabea 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 esto certos e imagina que a resposta 8 beleza? ? Multiplica ai 8 por 12, da quanto 96 n? Mas so 100 pessoas. Aonde vo parar aos outras 4?
  • Slide 16
  • Mas Rafael e Joo Existem... Monitoria [12/04/2012] - Parte Gisely16 s imaginar que j tem 12 grupos com 8 pessoas fechados ta ligado? E as 4 que esto perambulando por ai? janeiro 8 pessoas fevereiro 8 pessoas maro 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 vo ter que entrar em algum ms desse ai. Vamo colocar cada uma em um ms diferente. +1+1 +1+1
  • Slide 17
  • Mas Rafael e Joo Existem... Monitoria [12/04/2012] - Parte Gisely17 s imaginar que j tem 12 grupos com 8 pessoas fechados ta ligado? janeiro 8 pessoas fevereiro 8 pessoas maro 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 so justamente a parte decimal do 8,333 sacaram?
  • Slide 18
  • Monitoria [12/04/2012] - Parte Gisely18 Aritmtica Modular!
  • Slide 19
  • Monitoria [12/04/2012] - Parte Gisely19 Dizemos que a b(mod m) se e somente se a mod m = b mod m. 16 mod 5 7 2(mod 5)
  • Slide 20
  • Aritmtica Modular! Monitoria [12/04/2012] - Parte Gisely20 10) Indique o inverso de: a) 4 mod 9 b) 3 mod 5 c) 7 mod 17
  • Slide 21
  • Monitoria [12/04/2012] - Parte Gisely21 Teorema Chins...
  • Slide 22
  • Teorema Chins! Monitoria [12/04/2012] - Parte Gisely22 11) Indique as solues para os seguintes sistemas a) X 3 (mod 9) X 4 (mod 7) X 2 (mod 5)
  • Slide 23
  • Teorema Chins! Monitoria [12/04/2012] - Parte Gisely23 M M = m 1 X m 2 X m 3 M M k = M /m k M X = a 3. M 1. Y 1 + a 2.M 2.Y 2 + a 3.M 3.Y 3 (mod M)
  • Slide 24
  • Teorema Chins! Monitoria [12/04/2012] - Parte Gisely24 LOCALIZANDO OS VALORES DAS VARIVEIS NO SISTEMA: a) X 3 (mod 9) X 4 (mod 7) X 2 (mod 5) M M = m 1 X m 2 X m 3 M M = 315 M X = a 1. M 1. Y 1 + a 2.M 2.Y 2 + a 3.M 3.Y 3 (mod M) a 1 = 3 a 2 = 4 a 3 = 2 a 1 = 3 a 2 = 4 a 3 = 2 m 1 = 9 m 2 = 7 m 3 = 5 m 1 = 9 m 2 = 7 m 3 = 5
  • Slide 25
  • Teorema Chins! Monitoria [12/04/2012] - Parte Gisely25 S FALTAM OS INVERSOS
  • Slide 26
  • Teorema Chins! Monitoria [12/04/2012] - Parte Gisely26
  • Slide 27
  • Teorema Chins! Monitoria [12/04/2012] - Parte Gisely27 X = a 1. M 1. Y 1 + a 2.M 2.Y 2 + a 3.M 3.Y 3 (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 X = a 1. M 1. Y 1 + a 2.M 2.Y 2 + a 3.M 3.Y 3 (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 a 1 = 3 a 2 = 4 a 3 = 2 M 1 = 35 M 2 = 45 M 3 = 63 M = 315 Y 1 = 8 Y 2 = 5 Y 3 = 2 a 1 = 3 a 2 = 4 a 3 = 2 M 1 = 35 M 2 = 45 M 3 = 63 M = 315 Y 1 = 8 Y 2 = 5 Y 3 = 2 Agora que temos todos os valores necessrios, podemos aplicar na frmula:
  • Slide 28
  • Teorema Chins! Monitoria [12/04/2012] - Parte Gisely28
  • Slide 29
  • Crescimento de Funo! Monitoria [12/04/2012] - Parte Gisely29
  • Slide 30
  • Crescimento de Funo! Monitoria [12/04/2012] - Parte Gisely30 A letra c denota uma constante qualquer NOTAONOME O(x x )ordem exponencial O(x!)Ordem fatorial O(c x )ordem exponencial O(x c )Ordem polinomial O(x log x)ordem linear-logartmica O(x)ordem linear O(log x)ordem logartmica O(1)ordem constante Abaixo h uma lista de classes de funes que so bastante utilizadas para anlise de algoritmos, por ordem decrescente de crescimento de funes.
  • Slide 31
  • Crescimento de Funo! Monitoria [12/04/2012] - Parte Gisely31 PROPRIEDADES:
  • Slide 32
  • Crescimento de Funo! Monitoria [12/04/2012] - Parte Gisely32 n! 2n2n n2n2 n log n n log n 1 1