O uso da abstração para a resolução de problemas – Redutibilidade

Imagine-se acordando assustado e percebendo que está nos Backs, em Cambridge, dentro de um barco junto à um graduando fazendo Puntting.
A primeira coisa que você pensa é: “malditos cangurus sequestradores”. A segunda é “Minha mãe vai ficar furiosa por eu ter perdido o almoço na casa da vóvó”. Então, finalmente, num lampejo de sabedoria milenar, você entende que precisa chegar até Heathrow para conseguir voltar para o Brasil.

Infelizmente, logo em seguida, toda a sabedoria e compreensão do universo que se fizeram presentes e colaboraram para o seu entendimento da situação se esvaíram, fazendo com que, novamente, você seja um pobre mortal perdido no Reino Unido. O que fazer agora?

Bom, você pode começar a mapear todo o território das Ilhas Britânicas (sem link para a Wikipédia. Você sabe onde elas ficam!) até encontrar Londres. Outra possibilidade é perguntar para alguém como chegar ao aeroporto.

Parando para pensar um pouco, podemos concluir que a alternativa B (perguntar como fazer para chegar em Londres) não é mais difícil que a alternativa A (mapear todo o território das Ilhas Britânicas). Para aqueles que ainda estão em dúvida, vou dar mais uma chance: volte ao primeiro parágrafo, releia o texto e depois continue a leitura se estiver convencido.

Para aqueles que conseguiram escapar do looping acima (ler, ficar em dúvida, ler, ficar em dúvida…), vamos continuar: A redutibilidade é uma propriedade que envolve dois (ou mais) problemas, digamos, A e B, onde um problema pode ser convertido em outro, de forma que a solução para o problema A possa ser utilizada para responder B.

Agora, vamos fazer de conta que você tenha conseguido chegar em Heathrow com sucesso graças à sua perspicácia. Para aqueles que não conseguiram, ainda, sair desta prisão hipotética, visitem o site da National Rail Enquires.

Prestes à embarcar na primeira classe da British Airlines, vôo direto para o Brasil, a bela atendente da companhia diz que, devido às novas regras anti terrorismo da União Européia, todos os passageiros têm de resolver um dado problema matemático antes de embarcar.

Você, obviamente, fica muito feliz, visto que é um nerd e ainda não desistiu de ler este texto, e pede para que ela diga logo qual é o problema, que você tem pressa de embarcar. Ela, muito atenciosa e educada, como toda balconista nos aeroportos, lhe conta:

O problema conta com cinco filósofos sentados à mesa para se alimentarem. A mesa possui cinco garfos e cinco pratos de comida. Dado os filósofos e os garfos, cada filósofo precisa de dois garfos para comer (macarronada, talvez?). Os filósofos podem estar em um destes três estados: PENSANDO, FAMINTO ou COMENDO. Se um filósofo está pensando não precisa comer. Se quiser passar para o estado comendo ele tenta pegar dois garfos. Se não consegue passa para o estado FAMINTO.

Se conseguir pegar os dois garfos ele passa para o estado COMENDO.

Enquanto no estado FAMINTO, o filósofo permanece tentando pegar os garfos, ou seja, fica esperando a liberação dos garfos. (notem que este é um problema bastante anti higiênico!).

A pergunta  é: Como garantir que nenhum filósofo morra de fome?

Como leitor assíduo do Brainstorm de TI e já adepto das técnicas de redução e abstração de problemas, automaticamente você se lembra da Busca Tabu e rapidamente explica para a graciosa atendente como adaptar esta tecnica à este problema.

Ela sorri e o deixa entrar.  Você se sente mais tranquilo e entende a importância da redutibilidade e suas aplicações na vida real. Afinal, Nunca se sabe quando podemos ficar presos no Reino Mágico de Nárnia.

A redutibilidade é especialmente útil em diversos campos da computação e matemática. A classificação do tempo de execução de algoritmos, a computabilidade de certos problemas, escalonamento e muitos outros, utilizam fortemente a redução de problemas complexos em problemas para os quais já se conhecem a resposta.

A utilização de máquinas de turing e grafos também é um ótimo exemplo do que abstrações e reduções podem fazer para facilitar ou mesmo viabilizar a resolução de problemas.

Fora do âmbito teórico, a redutibilidade é uma propriedade útil para evitar que a roda seja reinventada várias e várias vezes.

3 comments

  1. Pingback: Brainstorm de TI

Deixe sua opinião!

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s