Resolver problemas por moeda ao ar

Ao longo da vida são comuns os casos em que não conseguimos decidir-nos por duas ou mais opções. Nestas situações costuma-se, em jeito de brincadeira, propor resolver o assunto atirando moeda ao ar. Se sair caras ganha a opção A, se for coroas ganha a B. Contudo, esta técnica tem aplicações mais sérias e interessantes no mundo da computação.

Aniversários coincidentes

Um problema típico consiste em determinar a probabilidade de pelo menos 2 pessoas, dum dado conjunto, fazerem anos no mesmo dia. A forma matemática de o resolver não é muito difícil: se existirem N pessoas têm 365^N aniversários possíveis, mas para não haver nenhum repetido, a primeira terá 365 dias, a segunda 364, e por aí fora. Assim temos 1 -

365!/( (365-N)! * 365^N ).

Mas por "moeda ao ar" é mais fácil resolver este problema: simulamos N aniversários e vemos se existe algum coincidente. Depois de repetidas várias vezes esta simulação, o resultado pretendido é o rácio entre o número de casos coincidentes e o total. Eis uma rápida implementação em C:

$ cat x.c

#define K 100000

#define N 20

int main()

{

int a[365], i, j, collisions=0;

srand(time(0));

for (i=0; i<K; i++) {

/* inicio da cada simulação */

memset(a, 0, sizeof(a));

for (j=0; j<N; j++) {

/* simulação dos aniversários */

if (a[rand()%365]++) {

collisions++;

break;

}

}

}

printf("%f\n", (float)collisions/K);

}

$ gcc x.c

$ ./a.out

0.413520

Se calcularmos o valor matemático exacto:

um valor aproximado até a 2ª casa decimal do estimado aleatoriamente. Assim, em 20 pessoas, existem cerca de 41% de hipóteses de duas fazerem anos no mesmo dia.

Esta técnica pode ser alargada a outros campos da matemática. Por exemplo, se emitirmos N coordenadas (x,y) aleatórias, podemos estimar a área de qualquer função dividindo as que caiem "dentro" dessa função pelas que caiem num quadrado de área pré-definida, que a contenha.

Scheduling

Pretendemos que um dada tarefa corra de x em x tempo, mas não queremos associar-lhe qualquer tipo de contadores, ou de modo geral, não queremos manter informação de estado. Mais uma vez a solução aqui passa pela moeda ao ar. Se tivermos um ciclo periódico de 1 segundo, as nossas tarefas podem ser lançadas com a seguinte construção:

while true:

wait 1s

if u() < 0.3: task1() # 1/0.3s = 3.3s

if u() < 0.1: task2() # 1/0.1s = 10 s

Aqui u() retorna um valor aleatório no intervalo [0,1), logo u()<0.3, por exemplo, tem uma probabilidade de acontecer de 30%, ou seja, cada 1/30% vezes que o ciclo corre task1(). Deste modo, a longo prazo, task1() irá correr em média uma vez a cada 3.3s.

Evitar congestão

Sempre que existem muitos acessos ao mesmo recurso, seja processos a competir por CPU num computador, ou carros pelos acessos nas estradas, uma forma de tentar diminuir a congestão consiste em alguém altruísta decidir esperar algum tempo, aleatório, antes de avançar.

Vamos supor N processos que são lançados num dado tempo que não conseguimos controlar. Evitamos problemas de simultaneidade esperando um pouco no início:

proc1_wrapper:

sleep rand()%60 # espero até 60 segundos

exec proc1 # e depois lanço o processo

Desta forma nenhum processo precisa de comunicar com os outros, nem saber sequer que existem. Este modelo é de resto o que existe na ethernet para resolver conflitos de sinal.

Conclusão

Existem muitos mais casos práticos de aplicação de técnicas aleatórias, que, criteriosamente bem usadas, podem salvar o dia. A regra prática é: se for díficil decidir, escolha-se ao acaso.

Carlos Duarte, 15Jul05

cgdarrobasdf-eu.org