Estruturas Discretas da Computação Combinatória

Prévia do material em texto

Estruturas Discretas da Computação
Combinatória (como contar).
Baseado em “Introduction to probability”, Bertsekas and Tsitsiklis, 2nd
Edition, 2008, e em slides de John N. Tsitsiklis (um dos autores).
Gonçalo Valadão
UAL - Departamento de Ciências e Tecnologias - Autonoma TechLab
Lei uniforme discreta
• Considerem-se os conjuntos Ω e A a seguir ilustrados:
• O conjunto Ω é composto por n elementos igualmente prováveis, e o
conjunto A constitúıdo por k desses elementos.
• Assim temos P(A) = kn
Prinćıpio básico de contagem
• Baseia-se no prinćıpio de divide and conquer mediante o qual a
contagem é dividida em diversas fases.
• Considera-se a experiência que tem como resultado cada um dos
elementos que se pretende contar.
• Divide-se essa experiência em diversas fases: por exemplo
suponha-se que uma experiência tem duas fases consecutivas, a
primeira das quais pode ter um dos resultados a1, a2, . . . , am, tendo
a segunda fase um dos resultados b1, b2, . . . , bn.
Prinćıpio básico de contagem
• Os posśıveis resultados desta experiência de duas fases são todos os
pares ordenados (ai , bj) i = 1, . . . ,m, j = 1, . . . , n.
• O número de resultados da experiência é portanto mn.
• Esta observação pode ser generalizada de acordo com a figura
seguinte:
Prinćıpio básico de contagem
• Prinćıpio básico de contagem:
Prinćıpio básico de contagem
• Exemplo: Com 4 camisas, 3 gravatas e 2 casacos quantos trajes é
posśıvel realizar?
• Em geral tendo a experiência r fases e tendo ni escolhas em cada
fase o número total de escolhas será n1 · n2 · . . . · nr .
• Neste caso temos então 4× 3× 2 escolhas:
Prinćıpio básico de contagem
Prinćıpio básico de contagem: mais exemplos
• Número de matŕıculas com 2 letras seguidas de 4 algarismos:
26× 26× 10× 10× 10× 10. Caso não sejam permitidas repetições:
26× 25× 10× 9× 8× 7.
• Permutações: número de maneiras de ordenar n elementos:
• Número de subconjuntos do conjunto {1, . . . , n}:
2× 2× . . .× 2 = 2n.
Prinćıpio básico de contagem: mais exemplos
• Exemplo: Determinar a probabilidade de seis lançamentos de um
dado (não viciado) darem números diferentes:
• O número de resultados posśıveis: 6 × 6 × 6 × 6 × 6 × 6. Este é o
número de elementos de Ω.
• Número de elementos de A: 6!
• Então P(A) = #A
#Ω
= 6!
66
Prinćıpio básico de contagem: combinações
• Define-se
(
n
k
)
como sendo o número de conjuntos de k elementos,
que são subconjuntos de um conjunto com n elementos.
• Para determinar
(
n
k
)
pode pensar-se em duas maneiras de construir
uma sequência ordenada de k elementos distintos:
• Escolher os k elementos um de cada vez.
• Escolher k elementos, ordená-los em seguida.
Prinćıpio básico de contagem: combinações
•
(
n
k
)
= n!(n−k)!k!
•
(
n
n
)
= n!0!n! = 1, por convenção 0! = 1
•
(
n
0
)
= n!n!0! = 1
•
∑n
k=0
(
n
k
)
=
(
n
0
)
+
(
n
1
)
+ . . . +
(
n
n
)
= número de subconjuntos de
{1, . . . , n} = 2n
Exemplos
• Consideremos n lançamentos independentes de uma moeda, com
P(H) = p. A probabilidade de em n lançamentos serem obtidas k
caras é dada pela, assim chamada, distribuição binomial:
P(k) =
(
n
k
)
pk(1− p)(n−k)
• A probabilidade de uma determinada sequência com k caras é
pk(1− p)n−k . Dado que existem
(
n
k
)
dessas sequências resulta a
fórmula da binomial.
Exemplos
• Dado que em 10 lançamentos ocorreram 3 caras, qual a
probabilidade de os primeiros 2 lançamentos serem caras?
• Acontecimento A: os primeiros dois lançamentos foram caras.
• Acontecimento B: 3 dos 10 lançamentos foram caras.
Prinćıpio básico da contagem: partições
• Consideremos que temos n ≥ 1 elementos distintos e r ≥ 1 pessoas.
São dados ni elementos à i-ésima pessoa.
• Temos que n1, n2, . . . , nr são inteiros não negativos que são dados e
que n1 + n2 + . . . + nr = n.
• O número de ordenações dos n elementos é n!. Esse número de
ordenações pode também ser dado por C · n1!n2! . . . nr !
• Temos então que o número de partições (n1, n2, . . . , nr ) é dado por
C = n!n1!n2!...nr ! (coeficiente multinomial).
Exemplos
• Problema: dado um baralho de 52 cartas distribúıdas (justamente)
por 4 jogadores. Determinar a probabilidade de cada jogador ficar
com um às.
• Considerando que os outcomes são partições igualmente prováveis,
temos que o número desses outcomes é 52!13!13!13!13!
• O número de outcomes com um às por cada pessoa é:
• distribuição dos ases: 4 · 3 · 2 · 1
• distribuição das restantes 48 cartas: 48!
12!12!12!12!
• A resposta ao problema é portanto:
4 · 3 · 2 · 48!
12!12!12!12!
52!
13!13!13!13!