quarta-feira, 11 de julho de 2018

Pensando Sobre Matemática #75 - Análise Combinatória - 1

Chega um momento das nossas vidas que nós temos que parar e analisar as possbilidades. Felizmente a matemática nos ajuda nisso!



A coisa vai ser tão simples dessa vez que nem vai precisar de MathJax pra comer esses lanches.
Uma vez eu escutei uma frase bastante interessante. Foi um professor meu do ensino médio que disse assim:

"Análise Combinatória é a arte de contar"

Eu acho que é uma frase muito boa porque ela serve basicamente pra isso. Antes que você diga que ela serve pra fazer probabilidade, entenda que ela só é útil porque ela consegue facilmente calcular a quantidade de elementos que tem em espaços amostrais do mundo cotidiano. As ferramentas em geral derivam da teoria dos conjuntos, como quase tudo na matemática, só que geralmente a gente abstraí esse tipo de coisa e trabalha com coisas bem mais palpáveis: Quadradinhos.

É bem simples, a gente coloca caixinhas onde vão os elementos e ao invés de colocarmos os elementos lá, nós colocamos a quantidade de possibilidades que podem caber ali. Isso funciona particularmente bem pra problemas geralmente ligados a organização. Eu honestamente não quero parecer um livro de matemática que fica te dando aquelas questões absurdas que você nunca vai usar na vida, mas saiba que você fica contando as possibilidades a maior parte do tempo.

Mas veja bem, as coisas que você verá nesse artigo não necessáriamente são uma receita de bolo, mas certamente em qualquer problema onde você vai precisar de análise combinatória você tem 2 ingredientes.

  1. Elementos primários, que são usados para montar os grupos/padrões
  2. Tamanho dos padrões
  3. Regras de padrões

Tudo fica mais fácil de entender com exemplos então vamos lá. Exemplos do ingrediente 1:

  • Os jogos de video game que você tem no seu armário/steam
  • Os seus livros
  • Seus pares de sapato
De preferência que você não tenha elementos repetidos. Não que isso seja importante porque você consegue trabalhar com elementos repetidos simplesmente etiquetando-os(e dessa forma tornado-os distintos). Agora vamos a exemplos de 2:

  • O seu armário
  • A sua estante
  • A despensa da cozinha
  • As suas caixas de sapato
Existe uma razão para as caixas de sapato serem destacadas, é porque o funcionamento delas, simula quase que exatamente como usamos a análise combinatória. Elas ficam especialmente úteis se forem distintas e ordenadas, e nada que numerá-las não resolva esse problema. Agora só ficaram faltando as regras de como a gente coloca as coisas no lugar. Então vamos aos exemplos de 3.

  • Eu não posso repetir os elementos primários
  • Eu posso repetir os elementos primários
  • Se o elemento A está nas caixas, então C não pode estar em qualquer outra caixa.
Sim, eu sei, essa última regra ficou meio esdrúxula, mas existem casos assim, então não é nada de outro mundo.

Antes de continuar, há uma primeira intuição que não necessariamente é verdadeira: O tamanho de 2 tem que ser menor do que o tamanho de 1. Isso faz um certo sentido quando nós temos recursos abundantes como os livros e precisamos organizá-los em um outro recurso mais limitado que são as caixas de sapato. Mas isso pode ser facilmente contra-exemplificado quando ainda sobra espaço na estante pra por mais livro.

Mas tem um caso que é particulamente útil que é a maldita questão da senha segura. Eu acho que todo especialista em segurança da informação deveria ler isso antes de sair tentando impor umas políticas de senha que sacrificam 1 virgem. Vamos supor um alfabeto limitado de 3 letras. A graça aqui é que o tamanho dos elementos primários é infinito porque você pode por quantos você quiser, e agora nessa senha você só pode usar "A", "B", ou "C".

Agora lembra do que eu falei de colocar a quantidade de possibilidades ao invés do elemento primário em si dentro da caixa? Suponha que você tem infinitas caixas de sapato numeradas, você vai ter algo mais ou menos assim:

_ _

Pra uma senha de 2 letras. Antes de sair mostrando porque a gente coloca os números deixa eu explicitar todas os arranjos possíveis:

A A
A B
A C
B A
B B
B C
C A
C B
C C

Cacete. 9 aranjos. curiosamente o mesmo que se fizessemos:

3 3

E multiplicassemos. Isso faz sentido porque para cada possibilidade após a escolha da primeira você ainda tem mais 3. Por isso que é 3 x 3.

- Ah mas e se eu colocasse outra letra?
- Então pra cada uma dessas combinações aí que você acabou de ver, você ia ter mais três possíveis: 9 x 3 = 27. Ou como a gente gosta de colocar: 3 x 3 x 3 = 27.

Até então tudo bem. Mas veja que com se você usar 2 letras só, mas usar 5 caixas de sapato. você tem uma quantidade de possibilidades maior: 2 x 2 x 2 x 2 x 2 = 32. - O que isso quer dizer? - Isso quer dizer que, essencialmente a complexidade da senha é a quantidade de caracteres disponíveis elevado a quantidade de vezes que você os usa. Eu vou usar uma notação que geralmente se usa em software de matemática. No caso das 5 caixas com A ou B você tem 2^5. No caso das 3 caixas com A B ou C você tem 3^3, Se você tem n letras e usa m caixas, você tem n^m arranjos.

Agora, qual é a disputa? É melhor você usar mais elementos primários ou mais elementos secundários? Se você for analisar friamente. Você vai ver que existem casos onde realmente é melhor você aumentar a quantidade de elementos primários.

Mas a verdade é: Melhor continuar aumentando elementos secundários. Eu vou partir de 4 letras e 4 caixas de sapato o que me dá 256 combinações, beleza?
  • Se você coloca mais um caracter nas suas quatro caixas você tem 5^4 = 625
  • Se você coloca mais uma caixa: 4^5 = 1024
Isso tem um nome específico pra quem está estudando esse tópico. Chama-se Arranjo com repetição. Quando você tem um arranjo com repetição a quantidade de possibilidade é exponencial porque o que você coloca em cada caixa é completamente independente da outras.

Mas as vezes você não pode repetir os caracteres. Quando isso acontece você tem o Arranjo. Se você tiver agora 7 caracteres pra colocar nas 4 caixas anteriores, o caracter de uma caixa influencia as outras, mas felizmente as caixas estão numeradas, então existe uma ordem na qual você vai preenchê-las. Na primeira então você teria 7 possibilidades:

7 _ _ _

Bom, você não pode usar o caracter anterior, então:

7 6 _ _

E assim sucessivamente

7 6 5 _
7 6 5 4

Repare que é similar ao Arranjo com repetição, no sentido que para cada caracter que você escolhe como o primeiro, você desdobra na quantidade de possibilidades, o que gera multiplicação, logo você teria:

7 x 6 x 5 x 4 = 840

840 possibilidades pra preencher 4 caixas usando 7 caracteres. É alguma coisa. Se você tiver os caracteres certos dá até pra colocar a senha como ABNT.

Só que tem um problema, os caracteres formam a senha do seu cofre, e o inimigo conseguiu descobrir quais são os 4 caracteres que você usou inicialmente, quantas chances ele vai ter?

4 x 3 x 2 x 1

Que na verdade são a quantidade de anagramas da palavra ABNT. Matemáticos não gostam muto de anagramas, eles preferem chamar isso de Permutação. É importante frisar que a Permutação não é nada mais que um Arranjo  metido a besta onde a quantidade de caracteres e caixinhas é igual. Ela tem esse nome porque o conceito por trás desse tipo de coisa é diferente. Você não se imagina colocando os elementos primários nos secundários, e sim trocando a ordem dos elementos secundários. É importante frisar que para que o Arranjo e a Permutação funcionem, os elementos secundários precisam estar ordenados.

Por enquanto é só. Esses dias tem sido difícil pra escrever, mas na segunda parte a gente vai usar o MathJax e vmos ver mais algumas peculiaridades da Análise Combinatória.


Imagens:
https://www.todamateria.com.br/analise-combinatoria/

Nenhum comentário:

Postar um comentário