Deixe-me explicar melhor: suponha que voce tenha o conjunto A = {1, 2, 4}. Quantos subconjuntos podemos formar com os elementos de A?
Bem, como A tem 3 elementos, é claro que podemos formar subconjuntos de 0 a 3 elementos.
Para ser mais exato, são eles:
- Nenhum elemento: {} ou ∅ (o conjunto vazio)
- 1 elemento: {1}, {2} e {4}.
- 2 elementos: {1, 2}, {1, 4} e {2, 4}.
- 3 elementos: {1, 2, 4}, o próprio conjunto A.
Total: 8 subconjuntos.
Mas e se A tivesse 4, 10 ou 100 elementos? Há uma maneira de calcular a quantidade de subconjuntos para um n qualquer?
Antes de prosseguirmos, porém, gostaria de dizer que esses conjuntos de todos os subconjuntos de um conjunto qualquer é chamado conjunto das partes (ou power set, em inglês), também denotado por
É possível provar por indução que a quantidade de elementos de
É também possível observar que há uma relação entre a quantidade de subconjuntos com k elementos observando as linhas do Triângulo de Pascal. Cada linha
cuja soma dá exatamente
Uma outra maneira (para mim a mais fácil) de computar a quantidade de possíveis subconjuntos é usando a notação binária. De alguma forma, os elementos precisam ser ordenados, e iremos usar n símbolos, dentro do conjunto {0, 1} para identificar um subconjunto. É fácil perceber que, a cada configuração de subconjunto, ou um elemento está ou não está neste subconjunto.
Por exemplo, no exemplo com A = {1, 2, 4}, temos as seguintes representações:
- Nenhum elemento: {} => 000
- 1 elemento: {1}, {2} e {4} => 100, 010 e 001
- 2 elementos: {1, 2}, {1, 4} e {2, 4} => 110, 101 e 011
- 3 elementos: {1, 2, 4} => 111
Assim, só precisamos calcular quantas combinações de 0's e 1's são possíveis, usando n posições. E a resposta é exatamente 2 x 2 x 2 x ... x 2 (n vezes) =
;-)
 |
| Imagem: http://commons.wikimedia.org/wiki/File:Knapsack.svg |
Vamos ver uma aplicação legal com essa representação de notação binária para representação de conjuntos.
Você conhece o problema da mochila? Resumidamente, nesse problema você deseja colocar alguns objetos dentro de uma mochila que suporta um peso máximo. Cada objeto tem um peso e um valor. O que se pretende é alcançar o valor máximo possível sem ultrapassar o peso máximo suportado pela mochila. Uma das maneiras de representar quais elementos você deseja colocar na mochila é pela representação binária. Suponha que temos 6 objetos, e desejamos levar o 1º, o 3º e o 6º. Assim, a configuração será 101001.
Uma maneira de resolver o problema da mochila é usando algoritmos genéticos, e para esse tipo de algoritmo, precisa-se representar uma configuração/estado do problema formando palavras com caracteres de um dado alfabeto. Nesse caso, a notação binária funciona perfeitamente!
Só pra matar a curiosidade de quem ainda não conhece algoritmos genéticos, vou mostrar algumas operações simples desse tipo de algoritmo.
 |
| Imagem: http://www.genomenewsnetwork.org/gnn_images/whats_a_genome/crossing_over.jpg |
Por exemplo, o crossing-over, feita com a combinação de 2 estados:
101001 (significa colocar na mochila os elementos 1, 3 e 6) e
110111 (os elementos 1, 2, 4, 5 e 6 na mochila),
que se quebram (depois da 3ª posição, p. ex.) e se rearranjam:
101111 (a primeira parte do estado 1 e a segunda parte do estado 2, que são os elementos 1, 3, 4, 5 e 6 na mochila)
110001 (a primeira parte do estado 2 e a segunda parte do estado 1, que são os elementos 1, 2 e 6 na mochila)
Recombinando os estados dessa forma, espera-se encontrar combinações que sejam bons subconjuntos de elementos a serem postos na mochila.
Em um próximo post, falarei mais sobre esse tipo de algoritmo.
