Resolução de Problemas

Esta seção contém uma descrição da abordagem para resolver problemas matemáticos descrita por G. Polya em seu importante livro How to Solve it. Analisaremos também cada passo dessa abordagem sob o ponto de vista da computação.

Compreensão do Problema

É preciso compreender o problema."

— Polya

Considere as seguintes perguntas para ajudar na compreensão do problema:

  1. Qual é a resposta desejada?
  2. Quais são os dados de entrada? Como estes dados estão organizados?
  3. Quais são as restrições?

Aplicação à Computação

No projeto de um algoritmo, e etapa de compreensão do problema é bem parecida com a versão matemática. Nela, é importante considerar as seguintes perguntas:

  1. Qual é a saída do algoritmo?
  2. Qual é a entrada do algoritmo? Qual o formato dos dados de entrada (um registro por linha, registros separados por vírgula, etc.)?
  3. Quais são as restrições na entrada do algoritmo? A entrada é composta somente de números inteiros positivos? Ou somente de palavras escritas em letras minúsculas? Quais são as especificidades da entrada?

Estabelecimento de um Plano

Encontre a conexão entre os dados e a resposta. É possível que você seja obrigado a considerar problemas auxiliares se não puder encontrar uma conexão imediata. É preciso chegar afinal a um plano para encontrar a resposta."

— Polya

Considere as seguintes perguntas para ajudar no estabelecimento de um plano:

  1. Você já viu este problema antes? Ou já viu o mesmo problema apresentado de forma ligeiramente diferente? Você conhece algum problema relacionado? Conhece algum problema que lhe poderia ser útil?
  2. Pense na resposta! E procure encontrar um problema conhecido que tenha a mesma solução ou uma solução semelhante.
  3. Tente encontrar um problema correlato que já foi resolvido antes. É possível utilizá-lo? É possível utilizar seu resultado? É possível utilizar seu método? É possível reformular o problema?

Aplicação à Computação

O equivalente do estabelecimento do plano no cenário de computação é o projeto do algoritmo em si. As perguntas acima podem ser modificadas para o cenário da computação da seguinte forma:

  1. Você já viu esse problema (ou alguma variação dele) antes? O problema que você precisa resolver é uma variação de um problema já conhecido (e para o qual já existe um algoritmo)?
  2. Pense na resposta! O problema que você precisa resolver possui a mesma saída de algum outro problema já conhecido? Seria ele uma versão “disfarçada” desse problema conhecido? É possível modificar a entrada para que o problema se torne um problema já conhecido?
  3. É possível utilizar a saída de um algoritmo já conhecido para resolver o problema? É possível utilizar um algoritmo já conhecido para resolver uma parte (talvez a parte mais importante) do problema?

Execução do Plano

Execute o plano."

— Polya

Ao executar seu plano de resolução, verifique cada passo. É possível verificar claramente que o passo está correto? É possível demonstrar que ele está correto?


Aplicação à Computação

A execução do plano no contexto matemático equivale à implementação do algoritmo para resolver o problema. Considere os seguintes pontos durante a implementação de um algoritmo:

  1. Teste cada parte do algoritmo. Escolha algumas entradas comuns e simule cada passo do algoritmo nessas entradas. O algoritmo funciona para as entradas escolhidas? Repida o mesmo processo para entradas incomuns (mas possíveis) do algoritmo.
  2. É possível verificar claramente que o algoritmo está correto? Você consegue encontrar um invariante que mostre que o algoritmo faz o que ele deveria fazer? Se você não sabe bem o que é um invariante, não se preocupe: veremos em mais detalhes o que é um invariante em breve.
  3. Você consegue demonstrar (usando indução matemática, invariantes, ou alguma outra técnica) que o algoritmo está correto? Esta etapa é muito difícil e trabalhosa na maioria das vezes, por isso ela só é usada em casos críticos.

Verificação

Examine a solução obtida."

— Polya

Considere as seguintes perguntas para ajudar na verificação da solução obtida:

  1. É possível verificar o resultado? É possível verificar o argumento (raciocínio)?
  2. É possível chegar ao resultado por um caminho diferente?
  3. É possível utilizar o resultado, ou o método, em algum outro problema?

Aplicação à Computação

Na etapa de verificação, precisamos considerar alguns aspectos, dentre os quais destacamos:

  1. O funcionamento do algoritmo é claro, ou seja, dada uma entrada e o algoritmo, é possível ver claramente por que ele chega ao resultado esperado?
  2. É possível chegar ao resultado usando um algoritmo diferente? O algoritmo encontrado é assintoticamente ótimo? Um algoritmo é considerado assintoticamente ótimo se, para entradas grandes, a performance dele é mais ou menos a mesma (exceto por um fator constante) que o melhor algoritmo possível. O tópico de análise assintótica de algoritmos será visto em breve e durante sua exposição esses conceitos ficarão mais claros.
  3. É possível usar o algoritmo proposto (ou modificá-lo) para resolver um problema mais genérico?