31
edits
Changes
Jump to navigation
Jump to search
Técnicas Avançadas de Contagem (view source)
Revision as of 10:01, 2 December 2015
, 10:01, 2 December 2015no edit summary
simplify(%);
'''3. Inclusão – Exclusão'''
Nós vamos começar a ver, nesta seção, a segunda das duas principais técnicas de contagem abrangida no Capítulo 5 desse texto – o princípio de inclusão e exclusão. Vamos ver como usar Maple para resolver problemas com essa técnica. No cerne do princípio de inclusão e exclusão está a fórmula
<math> | A \cup B | = | A | + | B | - | A \cap B | </math>
a qual diz que, para dois conjuntos finitos A e B, o número de elementos da união AUB de dois conjuntos devem ser encontrados primeiramente ao adicionar os tamanhos |A| de A e |B| de B, e depois subtrair o numero de elementos comuns a ambos A e B, senão seria contado duas vezes. Esta fórmula pode ser generalizada para contar o número de elementos da união de qualquer número finito de conjuntos finitos.
Para trabalhar com fórmulas como esta em Maple, é necessário aprender primeiro como representar conjuntos em Maple. Já que Maple é especialmente projetada para fazer matemática, isto é feito muito naturalmente: para representar um conjunto de elementos, simplesmente listamos estes elementos, separando-os por vírgulas, e incluindo toda a construção em chaves. Por exemplo, para representar o conjunto {2,3,5} cujos membros são os números 2, 3 e 5, nós podemos usar notação matemática comum.
2, 3, 5;
Em Maple, um conjunto é a estrutura de dados de primeira classe. Você pode atribuir um conjunto a uma variável:
A := 2, 3, 5;
Perceba que a idéia do Maple de um conjunto corresponde precisamente a uma notação matemática. Assim, não existe uma ordem implícita entre os membros de um conjunto, nem existe qualquer noção de multiplicidade para membros do conjunto. Para problemas que requerem este tipo de informação adicional, outras estruturas de dados, como listas e arranjos, devem ser usadas. Podemos ver isso em Maple com os exemplos a seguir:
A := `Alice`, `Bob`, `Eve`;
B := `Bob`, `Alice`, `Eve`;
evalb(A = B);
C := `Alice`, `Bob`, `Eve`, `Eve`;
evalb(A = C);
O procedimento evalbMaple avalia uma expressão booleana, e retorna verdadeiro ou falso, de acordo com a veracidade da falsidade da expressão. Então, Maple considera os três conjuntos A, B e C como o mesmo conjunto. O primeiro exemplo mostra que a ordem em que são listados os membros de um conjunto é irrelevante, enquanto o segundo mostra que, apesar de listar a string ‘Eve’ duas vezes, Maple só a vê uma vez. (Experimento com estes exemplos usando listas, que são delimitadas com colchetes em vez de chaves, para ver a diferença entre conjuntos e listas in Maple).
Para determinar o tamnho de um conjunto (o número de objetos dentro dele) in Maple, usamos o procedimento Maple nops (pense nisso como n operandos)
A := `Alice`, `Bob`, `Eve`;
nops(A);
C := `Alice`, `Bob`, `Eve`, `Eve`;
nops(C);
Os operadores teóricos de conjuntos (união) e (interseção) são representados em Maple pela escrita de seus nomes – union e intersect (em inglês), respectivamente.
A := 1, 2, 3, 4, 5: B := 4, 5, 6, 7, 8:
A union B;
A intersect B;
Além disso, a diferença teórica de conjuntos é denotada pelo operador Maple minus.
A minus B;
Vamos usar as operações para verificar o princípio de inclusão e exclusão em um exemplo particular.
Flintstones := `Fred`, `Wilma`, `Pebbles`;
Rubbles := `Barney`, `Betty`, `Bam Bam`;
Husbands := `Fred`, `Barney`;
Wives := `Wilma`, `Betty`;
Kids := `Pebbles`, `Bam Bam`;
Se este fosse um censo completo, então o número de crianças morando em Bedrock seria
nops(Kids);
enquanto que o número de habitantes de Bedrock que também são Flintstones ou criança é
nops(Flintstones union Kids);
De acordo com o princípio de inclusão e exclusão, este número também deveria ser
nops(Flintstones) + nops(Kids)
- nops(Flintstones intersect Kids);
que, claro, que é!
Como outro exemplo, considere um problema de determinar o número de inteiros positivos menor ou igual a 1000 que não são divisíveis por 2 ou 111 ao mesmo tempo. Primeiro, nós geraremos um conjunto de inteiros positicos menor ou igual a 1000.
hundred := seq(i, i = 1..1000):
Isto mostra como você pode usar o iterador Maple seq para gerar os membros de um conjunto. A seguir, vamos nos livrar dos elementos que são divisíveis por 2.
A := hundred minus seq(2 * i, i = 1..1000):
E daqueles que são divisíveis por 7:
B := hundred minus seq(7 * i, i = 1..1000):
(Perceba o uso combinado dos operadores seq e minus; eles trabalham bem convenientemente juntos aqui) Nós estamos procurando por inteiros que pertencem a um ou ambos de A e B, que é a união deles, então queremos o tamanho de um conjunto , o qual é
nops(A union B);
De acordo com o princípio de inclusão e exclusão, este valor também pode ser computado como
nops(A) + nops(B) - nops(A intersect B);
O mesmo princípio pode ser usado para exemplos maiores. Aqui, descrevemos o que precisa ser feito para determinar o número de inteiros positivos menor que 10.000 que são indivisíveis pelos primos 2, 3, 5 e 7. Para fazer isso, vamos usar o princípio da inclusão e exclusão para contar esses inteiros menor que 10000, que são divisíveis por, ao menos, um destes quatro números primos, e depois subtraí-los de 10000.
Primeiro, criamos um conjunto de inteiros postivos menor ou igual do que um mil.
th := seq(i, i=1..10^3):
Agora, os inteiros menores que 10000 que são divisiveis por um dos 2, 3, 5 e 7 são os da união dos conjuntos
th2 := th intersect seq(2*i, i=1..1000):
th3 := th intersect seq(3*i, i=1..1000):
th5 := th intersect seq(5*i, i=1..1000):
th7 := th intersect seq(7*i, i=1..1000):
(Note que não temos que permitir o índice i para alcançar 10000 em cada um destes, mas é mais simples deste modo, uma vez que irá descartar os valores desnecessários por tomar a interseção.) A seguir, criamos conjunto de inteiros que são divisíveis por estes quatro primos em pares.
th_2_3 := th intersect seq(2*3*i, i=1..1000):
th_2_5 := th intersect seq(2*5*i, i=1..1000):
th_2_7 := th intersect seq(2*7*i, i=1..1000):
th_3_5 := th intersect seq(3*5*i, i=1..1000):
th_3_7 := th intersect seq(3*7*i, i=1..1000):
th_5_7 := th intersect seq(5*7*i, i=1..1000):
Contamos também os inteiros menores que 10000 que são divisíveis pelos números em triplas.
th_2_3_5 := th intersect seq(2*3*5*i, i=1..1000):
th_2_3_7 := th intersect seq(2*3*7*i, i=1..1000):
th_2_5_7 := th intersect seq(2*5*7*i, i=1..1000):
th_3_5_7 := th intersect seq(3*5*7*i, i=1..1000):
Finalmente, contamos os numeros menores que 10000 que sao divisíveis por todos os quarto número 2, 3, 5 e 7.
th_2_3_5_7 := th intersect seq(2*3*5*7*i, i=1..1000):
Agora, para calcular os números inteiros menores que 10000 que são divisíveis por pelo menos um dos 2, 3, 5 e 7, nós calculamos como se segue.
nops(th2) + nops(th3) + nops(th5) + nops(th7);
% - (nops(th_2_3) + nops(th_2_5) + nops(th_2_7));
% - (nops(th_3_5) + nops(th_3_7) + nops(th_5_7));
% + (nops(th_2_3_5) + nops(th_2_3_7) + nops(th_2_5_7));
% + nops(th_3_5_7) - nops(th_2_3_5_7);
Portanto, o número de inteiros menores que 10000 que não são divisíveis por 2, 3, 5 ou 7 é
1000 - %;
