Contagem Matemática Aplicada a Computação

Prévia do material em texto

CCT0350 – MATEMÁTICA APLICADA A COMPUTAÇÃO 
Aula 3: Contagem 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 3: Contagem 
Matemática 
Combinatória 
Contagem 
Programação 
Recursos finitos 
Exemplo: Problema de espaço de armazenamento em um banco de dados ou quando precisamos 
determinar quantos usuários uma determinada configuração de servidor pode suportar. 
Exemplo: 
… … 
Contagem 
| 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 3: Contagem 
Ideia: 
 
Se existirem pelo menos K+1 pombos, e somente K casas, 
pelo menos uma casa vai ter mais do que um pombo. 
 
Prova por contradição: 
 
Suponha que mais do que k pombos pousaram em k casas 
de pombos. Se cada casa contiver no máximo um pombo 
teríamos, ao todo, no máximo k pombos, uma contradição. 
wikipedia 
Princípio da casa dos Pombos 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 3: Contagem 
 
 
 
Exemplo: Se mais do que k itens são distribuídos em k caixas, 
então pelo menos uma caixa conterá mais de um item. 
 
 
 
Exemplo: Quantas vezes um único dado precisa ser lançado para 
termos certeza de que obtivemos algum valor duas vezes? 
Itens 
Princípio da casa dos Pombos 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 3: Contagem 
 
Exemplo: Quantas pessoas precisam estar no mesmo quarto para se garantir que pelo 
menos duas pessoas têm o sobrenome iniciado pela mesma letra? 
 
Resposta: Existem 26 letras no alfabeto (caixas). Se tiver 27 pessoas então haverá 27 
letras iniciais (itens), que devem ser distribuídas entre as 26 caixas; por isso, pelo 
menos uma caixa conterá mais de um item. 
 
Exemplo: Quantas pessoas são necessárias para se ter certeza que haverá pelo menos 
duas delas fazendo aniversário no mesmo mês? 
 
Resposta: 13 pessoas. Pelo princípio da casa dos pombos se houver mais pessoas (13) 
do que meses (12) é certo que pelos menos duas pessoas terão nascido no mesmo 
mês. 
pixabay.com 
Princípio da casa dos Pombos 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 3: Contagem 
 
Árvore de possibilidades: 
 
 
 
 
 
 
 
Exemplo: Na programação. 
 
Exemplo: Uma criança pode escolher uma entre duas balas, uma rosa e outra preta, e um 
entre três chicletes, um amarelo, outro verde e outro branco. Quantos conjuntos diferentes 
a criança pode ter? 
Princípio da Multiplicação 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 3: Contagem 
 
 
Exemplo: Uma criança pode escolher uma entre duas balas, uma rosa e outra preta, e um 
entre três chicletes, um amarelo, outro verde e outro branco. Quantos conjuntos diferentes 
a criança pode ter? 
 
 
 
 
 
 
 
 
 
Pela árvore: 2 x 3=6 possibilidades: 
{R,A}, {R,V},{R,B}, {P,A}, {P,V} e {P,B}. 
 
O número de possibilidades: (3 X 2=6). 
Princípio da Multiplicação 
| 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 3: Contagem 
 
Princípio da Multiplicação: Se existem n1 resultados possíveis para um 
primeiro evento e n2 para o segundo, então existem n1.n 2 resultados 
possíveis para a sequência dos dois eventos. 
 
Exemplo: A última parte do seu número de telefone possui 04 dígitos. 
Quanto desses números de 04 dígitos existem? 
 
• O primeiro pode ser escolhido entre 0 a 9 (10 dígitos), 10 
possibilidades para a primeira opção. 
• As seguintes também terão, cada uma, 10 opções. 
 
Usando o princípio da multiplicação: 10 . 10 . 10 . 10 = 10.000 números 
diferentes. 
longah 
Princípio da Multiplicação 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 3: Contagem 
 
Exemplo: Para montar um computador, temos 3 diferentes tipos de monitores, 4 tipos de 
teclados, 2 tipos de impressoras e 3 tipos de "CPUs". Para saber o número de diferentes 
possibilidades de computadores que podem ser montados com essas peças, podemos usar 
o princípio da multiplicação. 
 
Solução: 3 x 4 x 2 x 3 = 72. Então, têm-se 72 possibilidades de configurações diferentes. 
 
http://galeria.colorir.com 
Princípio da Multiplicação 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 3: Contagem 
 
Exemplo: No sistema brasileiro de placas de carro, cada placa é formada por três letras e quatro 
algarismos. Quantas placas em que o número formado pelos algarismos seja par, podem ser 
formadas? 
 
Solução: 
(0 , 2 , 4 , 6 , 8). 
26 26 26 10 10 10 5 
Princípio da Multiplicação 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 3: Contagem 
26 x 26 x 26 = 17.576 -> parte das letras 
10 x 10 x 10 x 5 = 5.000 
Agora é só multiplicar as partes: 17.576 x 5.000 = 87.880.000 
Existem 87.880.000 placas em que a parte dos algarismos formam um número par. 
Princípio da Multiplicação 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 3: Contagem 
Exemplo: Suponha que queremos selecionar uma sobremesa entre três tortas e quatro bolos. 
De quantas maneiras isso pode ser feito? 
 
Temos: 02 eventos, um com 03 resultados possíveis e outro com 04. 
 
No entanto, não temos uma sequência de dois eventos possíveis, já que somente uma 
sobremesa será escolhida. 
 
O número de escolhas possíveis será o número total de possibilidades que temos, 3+4=7. 
Princípio da Adição 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 3: Contagem 
Princípio da Adição: Se A e B são eventos disjuntos, com n 1 e n2 resultados possíveis, 
respectivamente, então o número total de possibilidades para o evento A ou B é 
n 1 + n 2. 
 
Este princípio pode ser usado sempre para contar o número total de possibilidades em 
casos disjuntos. 
 
Exemplo: Um pai deseja presentear seu filho com apenas um presente, bola ou carrinho. 
Chegando à loja ele encontra 9 tipos de bolas diferentes e 10 tipos de carrinho diferentes. 
Quantas são as possibilidades de escolha do presente. 
Princípio da Adição 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 3: Contagem 
Exemplo: Um pai deseja presentear seu filho com apenas um presente, bola ou carrinho. 
Chegando à loja ele encontra 9 tipos de bolas diferentes e 10 tipos de carrinho diferentes. 
Quantas são as possibilidades de escolha do presente. 
 
Solução: Os eventos são disjuntos com n1= 9 e n2= 10 então existem n1+ n2 = 19 possibilidades de 
escolha. 
 
Exemplo: Uma pessoa deseja comprar um veículo de uma concessionária que tem 23 automóveis 
e 14 caminhões em estoque. Quantas escolhas possíveis a pessoa tem? 
 
Solução: O consumidor pode escolher um carro ou um caminhão (conjuntos disjuntos). A escolha 
de um automóvel tem 23 possibilidades, e a de caminhão, 14. Pelo princípio da adição, a escolha 
do veículo tem 23 + 14 = 37 possibilidades. 
Princípio da Adição 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 3: Contagem 
Sugestão de resolução dos exercícios propostos. 
 
Princípio da Multiplicação 
 
a) Na escolha do primeiro livro a ser colocado na carteira temos 4 possibilidades, pois ainda não colocamos 
nenhum livro nela, temos, então, quatro livros a escolher: Português, matemática, história e geografia. 
 
• Se começarmos a pilha com o livro de português, na escolha do próximo livro a ser colocado sobre 
ele, temos 3 possibilidades: matemática, história e geografia. 
• Se escolhermos o livro de história como o segundo livro da pilha, para o terceiro livro temos 2 
possibilidades apenas: matemática e geografia. 
• Se colocarmos na pilha o livro de geografia, para o último livro temos obviamente 1 possibilidade: 
matemática. 
 
Temos 4 possibilidades do primeiro livro podem ser combinadas com cada uma das 3 possibilidades do 
segundo livro, que podem ser combinadas com cada uma das 2 possibilidades do terceiro livro, que 
podem finalmente ser combinadas com 1 possibilidade do quarto livro. Matematicamente o número 
total de possibilidades seria: 4 . 3 . 2 . 1 = 24 
Exercícios Propostos 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 3: Contagem 
Sugestão de resolução dos exercícios propostos. 
 
Principio da Multiplicação 
 
b)Quantos são os números naturais de dois algarismos que são múltiplos de 5? 
10 2o 
1 a 9 
9 possibilidades 
Múltiplo de 5 
Terminar em 0 ou 5 
2 possibilidades 
Solução: 9 x 2 = 18 os números naturais de dois algarismos que são múltiplos de 5. 
Exercícios Propostos 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 3: Contagem 
Sugestão de resolução dos exercícios propostos. 
 
Principio da Adição 
 
a) Bruno tem 8 livros de Ecologia, 10 de Genética e 2 de Bioquímica. De quantas maneiras ele pode 
 escolher um desses livros para presentear um aluno? 
 
Conjuntos dos livros de cada área = conjuntos disjuntos. Portanto 8 + 10 + 2 = 20 maneiras diferentes. 
 
b) Uma senha de usuário de um sistema computacional pode ser formada por sequências de uma a 
 três letras maiúsculas, sendo que repetições são permitidas. Quantas senhas diferentes existem? 
 
Observe que: 
Uma letra: 26 possibilidades 
Duas letras: 26 . 26 = 676 
Três letras: 26 . 26. 26 = 17576 
Assim, pelo princípio da adição temos 26 + 676 + 17576 = 18278 senhas de usuário diferentes. 
Exercícios Propostos 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 3: Contagem 
Indicação de Leitura Específica 
 
• Recomendamos a leitura do capítulo referente Teoria de Conjuntos no material didático. 
• Acesse a Biblioteca Virtual da Estácio e pesquise mais exercícios nos livros de Teoria de 
Conjuntos disponíveis. 
 
Recomendação de leitura no material didático: 
MINELLI, Juliano. Matemática Discreta. 1. ed. Rio de Janeiro: SESES, 2015, p. 11-19. 
 
Sugestão de material: 
 
http://www.univasf.edu.br/~jorge.cavalcanti/Mat_Disc_Parte08.pdf 
http://www.univasf.edu.br/~jorge.cavalcanti/Mat_Disc_Parte08.pdf 
http://www.matematicadidatica.com.br/PrincipioFundamentalContagem.aspx 
 
Indicação de Leitura 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
Indicação de Leitura 
AULA 3: Contagem 
Indicação de Leitura Específica 
 
Sugestão de leitura: Contagem 
 
http://educacao.globo.com/matematica/assunto/matematica-basica/conjuntos.html 
 
http://www.somatematica.com.br/emedio/conjuntos.php 
 
http://pessoal.sercomtel.com.br/matematica/medio/conjuntos/conjunto.htm 
 
 
VAMOS AOS PRÓXIMOS PASSOS? 
 
 
Unidade 2 – Contagem 
 
- Arranjo; 
- Permutação; 
- Combinação.