Teoria dos Grafos: Exercícios de Algoritmos Aleatorizados / ensinoeinformacao

PESQUISA OPERACIONAL

Disciplina: Teoria dos Grafos

Exercícios sobre Algoritmos Aleatorizados

Exercícios sobre Algoritmos Aleatorizados:

Exercício 1:

Sortear as cores aleatoriamente e randomizar

Exercício 2:

E[X]=E[X1]+E[X2]+…+[X100000]

E[Xi]=0.99, para i=1,…,80000

E[Xi]=0.01, para i=80001,…,100000

→

E[X]=79400

Exercício 3:

A) 1/j + 1/ (j+1) + … + 1/ (n-1)=H(n-1)-H(j-1)

B) Xi=1 se o nó vi não recebe arco e 0 caso contrário.

Probabilidade de vi terminar vazio é (i-1)/i . (i)/(i+1) … x (n-2)/(n-1)=(i-1)/(n-1)

Somando para todo i, temos n /2.

Exercício 4:

Sorteie uma ordem aleatória.

A probabilidade de uma dada restrição ser satisfeita é 1/3.

Portanto, o número esperado de restrições satisfeitas é k/3.

Exercício 5:

A) xi e not xi

B) Se existe a clausula xi então sorteie xi=1 com probabilidade 0.6. Se existe a clausula not xi sorteie xi=0 com probabilidade 0.6. As demais variáveis sorteie com prob 0.5.

Probabilidade de uma clausula falhar é maior ou igual a 1-(0.6)².

Exercício 6:

Estratégia:

Observe os n/2 primeiros bids e memorize o maior deles, b*.
Ao examinar os n/2 últimos bids pare se encontrar um bid maior que b*.

Caso contrário, pare no último bid.

Análise:

A probabilidade do segundo maior bid ser um dos n/2 primeiros e o maior bid ser um dos n/2 últimos é (n/2)²/n(n-1) > ¼. Caso isso aconteça o algoritmo retorna o maior bid.

Exercício 7:

x=X1+…Xn

Xi=1 se o i-ésimo bid apresentado é atualizado e 0, caso contrario.

Probabilidade de Xi ser atualizado é a probabilidade de Xi ser maior que todos os anteriores, ou seja, 1/i.

Somando a série temos ln(n).

Exercício 9:

B) O número de jobs rejeitados é igual ao número de máquinas que não recebem jobs.

Exercício 10:

Probabilidade de não ser o corte mínimo é a probabilidade de sortear a,d ou d,a=1/6.
Fazendo n cópias, a probabilidade de obter o corte mínimo é a probabilidade de conseguir em todos= .