Baixe o app para aproveitar ainda mais
Prévia do material em texto
FACULDADE ESTACIO DO RECIFE. CURSO SISTEMAS DE INFORMAÇÃO/ADS MATEMATICA APLICADA A COMPUTAÇÃO LISTA 04: PRINCÍPIOS DE CONTAGEM: como contar? A Combinatória é a parte da matemática que tem como objetivo o estudo de problemas de contagem do número de agrupamentos que podem ser obtidos com os elementos de um dado conjunto. Fazer contagem é uma tarefa que temos em diversas situações. Por exemplo, quando queremos dimensionar quantos espaços um banco de dados consome, quantos usuários a configuração de um computador suporta, quantos cálculos certo algoritmo resolve, quantas linhas tem a tabela-verdade de uma proposição composta por n proposições simples, quantas senhas de acesso a um caixa eletrônico podem ser formadas, com quatro algarismos, entre outros casos. Inicialmente, o que é uma lista? 7.1 LISTAS – Uma lista é uma seqüência ordenada de objetos. Para escrevermos uma lista, escrevemos os seus elementos entre parênteses. Por exemplo, (2, a ,3, X ) é uma lista cujo primeiro elemento é 2, o segundo é a, o terceiro é 3 e o quarto elemento é X. Isso significa que a ordem em que os elementos figuram na lista é relevante: a lista (a, c, h) é diferente da lista (c, a, h). Além disso, uma lista pode conter elementos repetidos: (1, a , 2, 2 ). O número de elementos de uma lista é dito comprimento da lista. A lista (1, a, 2, 2 ) tem comprimento 4. Uma lista de comprimento 2 é chamada de par ordenado, como por exemplo, (1,2). Claro que ( ) é uma lista vazia, de comprimento 0. Dizemos que duas listas são iguais se tem o mesmo comprimento e se os elementos nas posições correspondentes são iguais. Exemplo 7.1. 1 a) Senha numérica com quatro algarismos é uma lista de comprimento 4. b) CPF é uma lista de comprimento 11. c) Matricula de aluno de uma faculdade: 2015 2 169 034 é uma lista de comprimento 11. d) O Código de Endereçamento Postal – CEP é uma lista de comprimento 8 (Veja exercício 15). Como se calcula o número de listas? O cálculo é feito por meio de princípios de contagem. Estudaremos dois deles. 7.2. PRINCÍPIO MULTIPLICATIVO: contagem de listas de comprimento dois. Considere as listas de dois elementos em que o primeiro pode ser escolhido de n maneiras e, para cada uma dessas escolhas, há m escolhas do segundo elemento da lista. Então, o número de listas de comprimento dois é n.m. Exemplo 7.2.1. Com os números 1, 2, 3, 4 e 5 podemos formar quantas dezenas? Uma dezena é uma lista de comprimento dois, constituída por dois algarismos, escolhidos dentre 1, 2, 3, 4 e 5. Assim, queremos formar listas do tipo (x, y). Temos 5 escolhas para o primeiro elemento x e, para cada escolha do primeiro, existem, 5 escolhas para o segundo elemento. Logo, podemos formar 5 x 5 = 25 dezenas. Exemplo 7. 2. 2. Suponha agora que queremos formar dezenas de dois algarismos diferentes com os algarismos 1, 2, 3, 4 e 5. A escolha do primeiro elemento do par pode ser feita de 5 maneiras. Escolhido o primeiro, restam 4 escolhas para o segundo elemento da lista. De modo que, podemos formar 5 x 4 = 20 listas de comprimento 2 , com elementos distintos. Exemplo 7. 2. 3. Uma seqüência de dois bits é uma lista de comprimento dois formada por ZERO (0) e UM (1) de comprimento dois. Podemos formar 2 x 2 = 4 listas: 00, 01, 10 e 11. E quando as listas têm comprimento maior do que dois? Como é feito o cálculo delas? 7.3 LISTAS DE COMPRIMENTO MAIOR DO QUE DOIS. Suponhamos que temos n elementos e queremos formar listas de comprimento k. O primeiro elemento da lista pode ser escolhido de n formas diferentes, o segundo também de n maneiras diferentes e, assim, até o k- ésimo elemento que pode ser escolhido de n maneiras. Logo, a quantidade de listas será Fatoresk ........n n.n n ..n = n k Exemplo 7.3.1. Um número binário é uma lista de ZERO e UM. Um número binário com 8 dígitos é chamado “byte”. a) Quantos “bytes” podem-se formar? Como um byte é uma lista de comprimento 8 tal que cada posição pode ser ocupada por zero (0) ou um (1), podemos formar 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 = 2 8 =256 bytes. b) Quantos bytes começam por 10 e terminam por 01? As duas primeiras posições e as duas últimas são ocupadas cada uma delas por um único determinado bit, então podemos formar 1x1x 2 x 2x 2 x 2 x 1x1= 16 bytes c) Quantos bytes começam por 10 e não terminam por 01? Existe apenas uma maneira de preencher as duas primeiras posições e três maneiras de preencher as duas últimas: 00,10 e 11. De modo que podemos formar 1x2x2x2x2x3 = 48 bytes. Exemplo 7.3.2. Os aeroportos, embora tendo nomes diferentes, têm códigos de três letras. Por exemplo, o aeroporto que serve Recife é REC, o aeroporto que serve São Paulo (Guarulhos) é GRU e o que serve Brasília é BSB. Com as 26 letras do nosso alfabeto podemos formar 26.26.26 = 26 3 códigos diferentes. Quando as listas têm repetição de elementos, como se processa o seu cálculo? 7.4 LISTAS DE COMPRIMENTO K SEM REPETIÇÀO DE ELEMENTOS. Agora, dispondo de n elementos, se queremos formar listas de k elementos (k n ) , sem repetições, procedemos assim: temos n escolhas para o 1º elemento da lista, n-1 escolhas para o 2º elemento da lista, n-2 escolhas para o 3º, e finalmente n- (k-1) escolhas para o k o elemento da lista. De modo que podemos formar n x (n-1) x (n-2) x .... x (n – (k-1) ) listas de comprimento k. Exemplo 7.4.1. As placas de licença de carros em certo estado dos Estados Unidos consistem em sete elementos: os três primeiros são letras maiúsculas (A-Z) e os quatro últimos são algarismos (0-9). Podemos formar 26 3 x10 4 placas distintas, das quais 26x25x24x10x9x8x7 são placas em que nenhum elemento é repetido. 7.5. PRINCÍPIO ADITIVO – Se dois eventos A e B disjuntos (não ocorrem simultaneamente) tem n e m possibilidades, respectivamente, então, o número total de possibilidades para o evento A ou B é m + n. Exemplo 7.5.1. Se A é o evento de escolher um número primo entre 10 e 20 inclusive e B escolher um número par entre 10 e 20 inclusive, de quantas maneiras podemos escolher um número primo ou um número par entre 10 e 20, inclusive? Bom, A = {11, 13, 17, 19} e B = {10, 12, 14, 16, 18, 20}, então (AB) = A + B = 4 + 6 = 10. O Princípio Aditivo pode ser usado apenas quando os eventos são disjuntos, isto é, quando não houver possibilidade em comum. Os dois princípios podem ser usados simultaneamente num problema? Sim, veja o seguinte exemplo. Exemplo 7.5.2. Uma rede de computadores é constituída por quatro nodos (ou nós): 1, 2, 3 e 4. Existem dois caminhos entre 1 e 3, dois entre 2 e 4, três entre 1 e 2 e quatro entre 3 e 4. Uma mensagem pode ser enviada do nodo 1 para o nodo 4 por meio 3.2 + 2.4 = 6 + 8 = 14 caminhos distintos. Observe que os caminhos do nó 1 até o nó 4, indo pelo nó 2 ou nó 3, são eventos disjuntos. Exemplo 7.5.3. As variáveis A, i, j e k no programa seguinte são variáveis inteiras. Qual o valor de A após o seguinte código ter sido executado? A: = 0for i: = 1 to 10 do A: = A + 1; for j: = 1 to 9 do A: = A + 1; for: = 1 to 8 do A: = A + 1; No primeiro for a variável A recebe o acréscimo +1 no total de 10 vezes, no segundo for, 9 vezes e no terceiro for, 8 vezes. De modo que ao final, da execução do programa o valor da variável A será A = 0 + (10+9+8).1 = 0 + 27 = 27 Exemplo 7.5.4. Qual o valor de A após o seguinte código ter sido executado? As variáveis A, i, j, e k são inteiras. A : = 100 for i : = 1 to 10 do for j: = 1 to 9 do for k : = 1 to 8 do A: = A + 1; end; end; end; Em cada for, a variável A é incrementada de 1 unidade, de modo que ao final da execução dos três for, teremos 10.9.8 incrementos de 1 unidade ao valor de A. Assim, teremos A = 100 + (10.9.8).1 = 100 + 720 = 820 APRENDA PRATICANDO: EXERCÍCIO PROPOSTO 7.1 Bem, agora é a sua vez! Verifique se você entendeu os assuntos desse capítulo, resolvendo os exercícios propostos. As respostas dos exercícios de número par serão apresentadas logo a seguir. Se tiver dúvidas, tente esclarecê-las com os seus colegas. 1. O número de telefone no país X é composto de dez algarismos, onde o primeiro não pode ser nem ZERO nem UM. Quantos telefones são possíveis? 2. Um número de inscrição no Seguro Social de um país X é composto de nove algarismos (0-9). a) Quantos números de Seguro Social são possíveis? b) Quantos deles são números pares? c) Quantos têm todos os algarismos números pares ? d) Quantos podem ser lidos igualmente para trás e para frente (por exemplo, 122070221)? e) Quantos não têm nenhum dos seus algarismos igual a 8 ? f) Quantos têm exatamente um algarismo igual a 8 ? g) Quantos têm ao menos um algarismo igual a 8 ? 3. Um sistema de computador permite atribuir nomes aos arquivos utilizando qualquer combinação de letras maiúsculas (A-Z) e de algarismos (0-9), mas o número de caracteres no nome deve ser no máximo oito (e deve haver ao menos um caractere no nome do arquivo). Por exemplo, A423, WJ, 4AA e CDEF4321 são nomes de arquivo válidos, mas J-31 e TURBINADA não são válidos. Quantos nomes de arquivo diferentes podem ser formados nesse sistema? 4. Uma prateleira contém 20 livros. De quantas maneiras diferentes esses livros podem ser dispostos na prateleira? 5. Um compact disc player tem espaço para 5 CDs; há cinco bandejas numeradas de 1 a 5 em que se colocam os CDs. Possuo 50 CDs. a) De quantas maneiras o CD player pode ser carregado, se todas as bandejas são ocupadas por CDs ? b) De quantas maneiras o CD player pode ser carregado se eu coloco apenas um CD no aparelho? 6. Uma prova de múltipla-escolha tem 15 perguntas, cada qual com quatro respostas possíveis, e 15 perguntas adicionais, cada uma das quais com cinco respostas possíveis. Quantas folhas de respostas diferentes são possíveis ? 7. Uma senha de um usuário em um computador de grande porte consiste em três letras seguidas de dois dígitos. Quantas senhas diferentes são possíveis (considere o alfabeto com 26 letras)? 8. Quantas senhas são possíveis, na questão anterior, se diferenciarmos as letras maiúsculas das minúsculas? 9. Quantos números de CPF são possíveis? 10. Uma pessoa pode viajar no trecho Recife/Natal/Recife de ônibus, automóvel, avião, navio ou trem. Se o meio de transporte da ida não é o mesmo da volta, de quantas maneiras essa pessoa pode realizar a viagem? 11. Um alfabeto consiste em três letras: A, B, C. Nessa língua, uma palavra é uma seqüência arbitrária de no máximo três letras. Quantas palavras existem nessa língua? 12. Qual o valor de A após o seguinte código ter sido executado? As variáveis A, i, j e k são inteiras. A: = 1 for i: = 1 to 10 do for j: = 1 to 9 do for k: = 1 to 8 do A:= A + 2; end; end; end; 13. Qual o valor de A após o seguinte código ter sido executado? A: = 100 for i: = 1 to 10 do A := A - 1; for j: = 1 to 20 do A: = A - 1 for k : = 1 to 30 do A= A - 1; end; 14. Qual o valor de A após o seguinte código ter sido executado? A: = 1 for i : = 2 to 12 do for j: = 3 to 11 do for k : = 10 downto 1 do A: = A + 2; end; end; end; 15. O Código de Endereçamento Postal ( CEP: - ) usado no Brasil tem como objetivo principal orientar e acelerar o tratamento e distribuição de objetos de correspondência. É constituído de 8 dígitos, cada um variando de 0 a 9, de modo que o 1º dígito representa a Região do Brasil, o 2º a Sub-região, o 3º o Setor, o 4º o Sub-setor, o 5º o Divisor de Sub-setor e os três últimos, recebem o nome de Sufixo e destinam-se à identificação individual de localidades, Caixas Postais Comunitárias, Logradouros, códigos especiais., etc. Região Sub-Região Setor Sub-setor Div de Setor Sufixo Sufixo Sufixo a) Quantos são os CEP’s possíveis ? b) Quantos são os CEP’s são possíveis para atender à região 3 (Sede em Salvador) c) Quantos são os CEP’s são possíveis para atender à região 5 (Sede em Recife) ? 16. Um cofre tem três discos, cada um com as mesmas 26 letras e só pode ser aberto quando se colocar uma determinada letra de cada um dos discos numa determinada posição. Supondo que se ignora o segredo do cofre, de quantas maneiras diferentes se podem colocar as letras dos discos nas referidas posições ?17. Quantos números diferentes de 3 algarismos podemos formar com os algarismos 1, 3 e 9 no sistema decimal. ? 18. Quantos números de quatro algarismos podemos formar com os algarismos 0, 2, 4, 6 e 8 no sistema decimal? Resp 19. Com cinco pedaços de tecidos nas cores amarela, azul, verde, vermelho e branco, quantas bandeiras tricolores podemos formar supondo que os tecidos são colocados só em tiras verticais? 20. Uma senha de computador é constituída por seis caracteres: três letras (de 26 letras) seguidas de três dígitos (de 0-9). Determinar o número de senhas possíveis, nos seguintes casos: a) tanto as letras como os dígitos podem ser repetidos; b) os dígitos não podem ser repetidos; c) as letras não podem ser repetidos; d) nem as letras nem os dígitos podem ser repetidos. 21. Quantas senhas são possíveis no exercício anterior se elas apresentam as três letras e os três dígitos de forma alternada: LDLDLD ou DLDLDL? 22. Com os dígitos 0, 1, 2, 5 e 8, quantos números de quatro algarismos diferentes podemos formar? Quantos são múltiplos de 5 ? Quantos são múltiplos de 10? 23. Os clientes de uma livraria virtual são todos cadastrados ao criarem uma senha de quatro ou cinco dígitos, seguindo as seguintes instruções: a senha deve conter apenas vogais ou os algarismos 1, 2, 3; o primeiro e o último dígitos devem ser vogais; os caracteres não podem ser repetidos. Quantos clientes podem ser cadastrados com senha, segundo este procedimento, sabendo que a cada cliente corresponde uma senha e a cada senha corresponde um único cliente? Resp 3.000 24. Um pacote de dados tramita de um ponto A a um ponto B passando por 2 roteadores R1 e R2, nessa ordem. Sabe-se que existem 3 rotas de A até R1, 3 rotas de R1 a R2 e 4 rotas de R2 a B. Quantos caminhos distintos esse pacote pode percorrer de A até B? Resp 36 25. Pretendo colocar um roteador wireless em cada uma das 4 salas do meu escritório. O site da empresa onde será feita a compra, oferece 8 modelos distintos. De quantas maneiras distintas pode ser feita essa compra? Resp. 70 RESPOSTA DO EXERCÍCIO 7.1 2) a) 109 b) 5x108 c) 59 d) 105 e) 9.98=99 f) 99 g) 109 – 99 4) 20x19x18x17x....x2x1 = 20! 6) 420x 510 8) 523x102 10) 20 12) 1441 14) 902 16) 263 18) 4.53=500 20) a) 263x 103 b) 263x10x9x8 c) 26x25x24x103 d) 26x25x24x10x9x8 22) a) 96 b) 42 c) 24
Compartilhar