Cortesia de wikipedia
O algoritmo do jantar de anos.
«Se convidarmos um frupo de amigos para o nosso jantr de anos e quisermos preencher uma mesa de quatro pessoas, podemos ter de escolher os nossos três companheiros de entre cinco amigos. Mas o António está zangado com a Beatriz, sua antiga namorada. E esta e o Carlos são inseparáveis. Ora o Carlos, que é amigo do António, está de relações cortadas com o Daniel. E este, por seu turno, não dá um passo sem trazer consigo a Eduarda, que não pode ver o António à frente.
Como se resolve este quebra-cabeças? O melhor é seguir um algoritmo, isto é um conjunto de regras que estabeleça uma procura sistemática de solução. Os algoritmos são muito caros aos matemáticos e aos cientistas da computação. Alguns são muito complicados. Mas por vezes os mais simples são os mais eficientes. No nosso caso, podemos seguir um processo sistemático de procura e de eliminação, um algoritmo bastante eficaz, apesar de simples.
Cortesia de telendro
Sendo assim, começamos por escolher o nosso amigo A e vemos que não podemos convidar a nossa amiga B; poderíamos convidar C, mas este não vem se não vier B; e assim por diante. Como não há solução contendo A, tentamos de novo, começando desta vez por B, e assim continuamos, até encontrar três amigos para o jantar. Será que isso é possível, neste caso? Ou será que temos de desistir, forçados a reconhecer, tristemente, que as desavenças humanas são mais complicadas que os algoritmos?
Os quebra-cabeças deste tipo são conhecidos como problemas de satisfabilidade, ou de satisfação, para quem não goste de palavras novas desnecessárias. Os matemáticos ultrapassam o dilema chamando-lhes problemas SAT, o que satisfaz toda a gente.
Cortesia de becodonoturnowordpress
O jantar acima é um exemplo dos chamados problemas 2-SAT, pois cada restrição engloba duas variáveis («A ou B», «a e C», etc). Mas o problema pode complicar-se se o António, o Carlos e o Daniel forem inseparáveis, ou seja, se tivermos de considerar três variáveis em cada restrição («A e B e C», ou «A e C ou D», etc.).
Estes outros problemas são conhecidos como problemas 3-SAT. E podem imaginar-se restrições de tipo mais geral, criando os chamados problemas k-SAT». In Nuno Crato, A Matemática das Coisas, Gradiva, Sociedade Portuguesa de Matemática, Abril 2008, ISBN 978-989-616-241-2.
Cortesia de Gradiva/JDACT
