[Engenharia da Computação #1] Análise Combinatória e Probabilidades
Neste tópico e no próximo, estudaremos probabilidades, o que significa que teremos a capacidade de inferir quais a chances que determinado evento pode assumir um valor, ou um intervalo de valores específicos.
Inicialmente, estudaremos a análise combinatória, que nos ajuda a contar de quantas formas possíveis, determinado grupo de elementos pode se combinar. Nesse contexto, destaca-se que esse conhecimento auxilia o cálculo de probabilidades em algumas situações, que estudaremos nesta parte do projeto.
Em nossos estudos sobre combinatória, veremos a permuta simples, arranjo simples e combinação simples. Aqui o "simples" significasem repetição de elementos. Vamos começar?
1) Permuta simples
Na permuta desejamos saber de quantas maneiras diferentes, determinado conjunto de elementos podem ser ordenados, utilizando todos os esses elementos.
Por exemplo:Quantos anagramas podem ser criados com as letras das palavras CELSO?
Anagramas são combinações de letras, como: CELSO, ECLOS, SELOC, …
Nesse caso, temos 5 elementos e queremos utilizar todos eles. No entanto, aqui aplicamos o conceito de permuta. A notação matemática é:
PN = N!
Em que, N é o número de elementos e o símbolo "!" é um fatorial. Mas, o que é um fatorial?
Vamos parar um pouco a combinatória, para revisar o conceito de fatorial.
Fatorial é a multiplicação de um número (N) pelos seus antecessores, até o chegarmos ao número 1. Vejamos a seguir:
Aplicaremos com mais frequência essas propriedades neste tópico e no próximo. Voltando a resolução do exemplo dos anagramas, a palavra CELSO tem 5 letras. Dessa forma, teremos uma permuta com 5 elementos
P5 = 5! = 5*4*3*2*1 = 120
Ou seja, é possível escrever 120 anagramas diferentes com estas 5 letras.
Vamos imaginar, agora, a seguinte questão:
Qual a probabilidade de um gerador aleatório de anagramas, crie um anagrama começado com "E", utilizando as letras C-E-L-S-O? A probabilidade aqui é a razão do número de anagrama começados com "E" (n), pelo total de anagramas possíveis (N):
p = n/N
O valor de N já sabemos. É P5 = 120. Mas, e o valor de n? Como devemos começar com a letra "E", a primeira posição só tem uma opção. Nos restam 4 posições e 4 letras. Isso também é uma permuta, pois utilizaremos todos os elementos disponíveis.
N = 1*P4 = 1*4*3*2*1 = 24
Mas o que significa o "1" antes da permuta? Ele quer dizer que só há uma opção possível na primeira letra. Como as demais são livres, aplicamos a permuta.
E agora, qual a probabilidade de um gerador aleatório de anagramas, criar um anagrama começado com "E"?
p = 24/120 = 1/5 = 0,2 = 20%
A probabilidade é de 20%. Significa que, a cada 5 anagramas criados, 1 terá com letra inicial o "E".
Mas, como chegamos nos 20%?
Em uma calculadora, basta fazer a divisão direta. No caso, como fizemos sem a calculadora, simplificamos a fração até ela se tornar irredutível, em seguida, dividimos o numerador pelo denominador e multipliquei por 100 (por cento).
Vamos ver mais um exemplo? Qual a probabilidade de números que podem ser criados com os algarismos 1-3-4-5-6-7-9, sendo que o primeiro deve ser 4, o último dever ser 1 ou 9?
Para achar a probabilidade, o total de números formados será:
P7 = 7! = 7*6*5*4*3*2*1 = 5040
Agora, vamos calcular a quantidade dos números que devem ter o primeiro algarismo 4 e o último algarismo 1 ou 9.
Separando em duas fases, vamos determinar a quantidade dos números iniciados por 4 e finalizado por 1 (na). A posição inicial e final só têm 1 possibilidade. Assim, sobre as 5 posições intermediárias, e 5 algarismos. Isso é uma P5. Dessa forma, temos:
na = 1*P5 *1 = 1*5*4*3*2*1*1 = 120
A segunda restrição nos diz que os números devem ser iniciados por 4 e finalizados por 9 (nb). A ideia é a mesma:
nb = 1*P5 *1 = 1*5*4*3*2*1*1 = 120
O total de números que seguem as restrições é na+nb=240. Com este resultado, podemos calcular a probabilidade desejada:
p = 240/5040 = 1/21 = 0,0476 = 4,76%
Sendo assim, esta é essência deste tópico, encontrar o número de combinações possíveis, e calcular a probabilidade de um evento específico.
2) Arranjo simples
No arranjo simples, os elementos não se repetem, aliado a isso, não utilizaremos todos os elementos em nossas combinações. Além disso, é muito importante ressaltar que para o arranjoa ordem em que os elementos aparecem é fundamental.
A fórmula de arranjo é:
AN,p = N!/(N – p )!
Em que, N é o número de elementos e o p, o número elementos utilizados.
Exemplo:A ativação de determinado mecanismo depende da sequência de 4 interruptores, que podem assumir as cores: vermelho (R), azul (B), verde (G), amarelo (Y) ou branca (W). Se a sequência correta de ativação é B-W-G-R, qual a probabilidade de uma pessoa, ao acaso, digitar a sequência correta de ativação deste mecanismo?
Para achar a probabilidade, precisamos saber o número de combinações possíveis. Nesse caso, a ordem das cores importa. Assim, isto é um arranjo com N = 5 e p = 4:
A5,4 = 5!/(5 – 4)! = 5!/1! =5! = 120
O número de combinações necessárias para a ativação é somete uma (B-W-G-R), assim a probabilidade será 1/120 = 0,83%.
Agora, vejamos mais o caso das senhas pessoais: Se determinado sistema aceita como caracteres os algarismos de 0 a 9, as 26 letras do alfabeto, diferenciando maiúsculas e minúsculas, além de 6 caráteres especiais (!,@,#,$,&,*). Qual a probabilidade de um invasor digitar ao acaso uma senha de 8 caracteres e conseguir o acesso? Para calcular a resposta, precisamos saber quantos caracteres (N) se pode utilizar para compor a senha de 8 caracteres (p). Vejamos:
Assim, a probabilidade de alguém acertar a senha ao digitar 8 caracteres ao acaso é 1/40320, ou 0,0025%
O arranjo é utilizado quando a ordem dos elementos importa para a situação, quando isso não acontece, utilizamos a combinação.
3) Combinação simples
Na combinação, assim como no arranjo, temos a disposição N elementos, mas, só utilizamos p elementos. Nenhum deles deve se repetir, para que possamos utilizar a fórmula a seguir:
CN,p = N!/[p!*(N – p)!]
Exemplo: Suponha que você deseja apostar em um tipo de loteria, em que é preciso acertar os 5 números sorteados, retirados de uma urna com números de 1 a 100. Caso a aposta unitária seja R$ 4,00, quantos você deve gastar, para ter total certeza que serás o ganhador do prêmio de R$ 100.000.000,00?
Inicialmente, é importante constatar que, para ter total certeza que será o ganhador, será necessário apostar em todas as combinações possíveis de 5 números. Quantas apostas então serão necessárias?
Isso significa que precisarias de R$ 4* 75.287.520 = R$ 301.150.080,00. Portanto, podemos perceber que, para você ter certeza do ganho, terá que gastar 3 vezes mais que o próprio prêmio.
Vamos praticar a teoria? Veja na sequência um vídeo com exercícios, sobre os conteúdos abordados nesse tópico.