Site menu Pegadinha de matemática intervalar
e-mail icon
Site menu

Pegadinha de matemática intervalar

e-mail icon

Bem que eu queria ter lido o livro de matemática intervalar daquela série da UFRGS, mas meu filho pegou primeiro e riscou todo, aí foi para o lixo. Achei que não tinha perdido muita coisa, mas hoje vi a importância do assunto.

Todo programador já topou com o problema da superposição de intervalos. Por exemplo, tenho dois intervalos de data, e preciso testar se eles sobrepõem.

Figura 1: Superposição de intervalos

Outro exemplo: comparar intervalos de preços: eu aceito preço A até B, meu fornecedor ofereceu preço C até D. Se existir "terreno comum" entre minha faixa A..B e a faixa C..D dele, temos negócio, senão, nada feito.

Mais um caso: testar igualdade de números de ponto flutuante. Também é outra pegadinha que todo programador já caiu: você faz 0,1 + 0,2 e a comparação com 0,3 resulta Falso — porque o resultado, para o computador, foi 0,29999999999.

Um jeito de evitar este problema é usar inteiros escalonados. Num sistema contábil, o correto é armazenar os valores em centavos, não em reais. O SQL oferece o tipo DECIMAL pelo messmo motivo: representação exata de números decimais.

Mas, quando somos obrigados a usar ponto flutuante, precisamos estipular uma tolerância ("epsilon"). Se os números se sobrepoem nas suas respectivas faixas de tolerância, são considerados "iguais":

x = 0.3
y = 0.1 + 0.2
epsilon = 10**-10  # tolerância
A = x - epsilon
B = x + epsilon
C = x - epsilon
D = x + epsilon
# Se a faixa A..B sobrepõe C..D, então podemos 
# considerar que x e y são "iguais".

Na verdade, podemos usar uma técnica bem mais simples ao comparar números:

abs(valor) < epsilon                  // para verificar se é zero
abs(valor1 - valor2) < epsilon        // para verificar se são iguais 

Mas comparar intervalos dá um pouco mais de trabalho.

A vida inteirinha eu testei superposição da seguinte forma:

(A >= C and A <= D) or (B >= C and B <= D)

A lógica é simples: verifico se o "meu" preço mais baixo (A) está no intervalo do fornecedor (C..D). Se estiver, obviamente há superposição. Se não, verifico então se meu preço mais alto (B) está entre C e D. Se nenhum dos extremos A e B está no intervalo C..D, não pode haver superposição.

Um programador mais naïve e mais paranóico faria também o teste contrário: ver se C ou D estão na faixa A..B, resultando numa expressão muito mais comprida:

[(A >= C and A <= D) or (B >= C and B <= D)] or 
[(C >= A and C <= B) or (D >= A and D <= B)]

Parece óbvio que não é necessário adicionar este contra-teste, afinal se A..B sobrepõe C..D, o contrário é automaticamente verdadeiro, né?

Bem, hoje fui brincar com um código que testava igualdade de ponto flutuante, aí pesquisa daqui, pesquisa dali, e descobri que eu também estava errado a vida inteira. O teste a seguir é suficiente para detectar sobreposição:

A <= D and B >= C 

Vivendo e aprendendo.

Para me redimir um pouco, notei que a fórmula ideal, com 2 comparações, pressupõe intervalos "em ordem" ou seja, A < B e C < D. Se algum intervalo estiver fora de ordem, esta fórmula não funciona; mas a "minha" fórmula com 4 comparações ainda funciona se o intervalo A..B estiver desordenado.

Provavelmente, quando precisei de semelhante fórmula pela primeira vez, tive de lidar com intervalos fora de ordem, e acabei me fixando na versão de 4 comparações.

A fórmula com oito comparações parece imune a intervalos fora de ordem, mas não é. Se os dois intervalos estiverem invertidos, ela falha. Ela ainda funciona se apenas um dos intervalos estiver invertido (não importa qual). Sendo assim, o melhor é ordenar os intervalos e usar a fórmula com duas comparações.

Prova de correção

É fácil constatar intuitivamente que as fórmulas com quatro ou oito comparações estão corretas. Resta agora provar que a fórmula com apenas duas comparações é equivalente às outras, e portanto também correta.

A chave está nas relações de implicância: se A >= C, forçosamente B >= C. Ou na mão contrária: B < C implica em A < C. Isto permite reescrever expressões sem alterar seu resultado. Por exemplo:

A >= C é equivalente a (A >= C and B >= C)
C >= A é equivalente a (C >= A and D >= A)

e assim por diante. Trabalhar a fórmula de 8 comparações foi, curiosamente, mais simples:

# Transforma cada comparação numa letra
(A >= C and A <= D) or (B >= C and B <= D) or
    a          b          c           d 

[(C >= A and C <= B) or (D >= A and D <= B)]
   !a          c           b         !d

[ab + cd] + [!ac + b!d]

# Relações de implicância
a=>ac
!a=>!ab
d=>bd
!d=>!dc

# Usa as regras de implicância
[acb+cbd] + [!abc+bc!d]

# Simplifica
abc+bcd+!abc+bc!d
bc(a+!a)+bc(d+!d)
bc

A expressão com 4 comparações foi osso mais duro de roer, não consegui simplificar diretamente. O caminho que encontrei foi:

Trocar (A,B) por (C,D) evidencia que os dois
lados da fórmula de 8 comparações (com 4 comparações
cada) são equivalentes e redundantes.

ab+cd + !ac+b!d = ab+cd = !ac+b!d = bc
e-mail icon