Teoria dos problemas – Wikipédia, a enciclopédia livre

Este artigo carece de reciclagem de acordo com o livro de estilo. Sinta-se livre para editá-lo(a) para que este(a) possa atingir um nível de qualidade superior. (Maio de 2015)

Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. Ajude a melhorar este artigo inserindo citações no corpo do artigo. (Maio de 2015)

Dentre as diversas áreas de estudo encontramos na área de Inteligência Artificial (A.I.) técnicas aplicadas à resolução de problemas.

Podemos enquadrar os problemas em três grandes grupos:^{[carece de fontes?]}

1. Os que não têm solução e portanto não há nada a fazer, que são classificados como problemas indecidíveis (ou impossíveis de serem solucionados).
2. Os que têm solução algorítmica e podemos resolvê-los formalmente passo a passo, codificando os algoritmos para sua resolução.
3. Um terceiro grupo que não pertecem aos dois anteriores. Dentre eles podemos ter:

• Aqueles em que a solução algorítmica têm complexidade NP-Completa;
• Aqueles que o Ser Humano é capaz de resolver;
• Aqueles que os Seres Vivos são capazes de resolver. Ex: Jogar Xadrez, Jogar Futebol, Reconhecer Faces, Fazer Traduções, Procurar Comida, Reconhecer Letras, entre outros.

É difícil de explicar precisamente o que é um problema, mas podemos explicar como sendo uma questão que se propõe para ser resolvida. Note que resolver um problema não necessariamente significa em se ter um método para resolvê-lo. Antes mesmo de se tentar buscar a solução de um problema, deve-se responder as seguintes perguntas:

• Quais são os dados (informações)?
• Quais são as soluções possíveis?
• O que caracteriza uma solução satisfatória?

Também pode-se pensar que problema é algo difícil de resolver, uma dúvida, uma questão, enigma ou mistério. Problema é melhor "entendido" nas diferentes áreas do conhecimento, por exemplo:

• Problema dos canibais e missionários;
• Problema do caixeiro viajante;
• Problema das pontes de Königsberg;
• Problema do carteiro chinês
• Tabuleiro de xadrez mutilado;

Na Teoria dos problemas um problema pode ser representado em linguagem matemática da seguinte forma:

   P = ( I, B, C ) 

P: O problema apresentado;

B: O conjunto de dados do problema, conjunto não vazio, que deve representar a informação apropriada do problema. Alguns elementos podem permanecer iguais e outros em constante dinâmica. É necessário documentar não só o estado inicial do problema mas também todos seus estados de mudanças.

I: O conjunto de operações e transformações, também conjunto não vazio, que podem ocorrer durante o processo da resolução do problema desde a sua fase inicial, as possíveis respostas.

C: Condição, uma relação binária, que deve satisfazer o problema. Esta relação caracteriza uma solução satisfatória, ela associa a cada elemento do conjunto de dados a solução única desejada. Mais precisamente é o conjunto solução do problema.

P

   +---+         +---+    |   |   O     |   |    | B | = = = > | C |    |   |         |   |    +---+         +---+ 

Exemplos

Uma pessoa que enfrenta um problema para satisfazer certos objetivos e não conhece que ações deve tomar para conseguir resolvê-lo.

Então ao se resolver um problema identificamos os seguintes componentes: Um objetivo para ser alcançado, um conjunto de ações pré-pensadas para resolver tal problema e a situação inicial do tal problema.

   Exemplo: Um Puzzle    Existe um tabuleiro de 4x4 casas e 15 peças somente. O problema é que temos    que fazer com que as peças espalhadas no quadrado formem uma configuração    previamente definida. Existe uma regra para isso, o movimento somente ocorre    uma peça por vez e somente para casas adjacentes. 

Neste caso o conjunto de dados do problema poderia ser descrito pela configuração das peças no tabuleiro, as operações de busca da solução como movimentos das peças de acordo com as regras, e a configuração final a solução do problema.

Um problema de diagnóstico médico pode ser modelado da mesma maneira, seja:

   O problema "P" é o diagnóstico.    O conjunto "B" da dados do problema são dados que o médico obteve de exames com seu paciente.    O conjunto "C" da solução é o conjunto de todas as doenças possíveis. 

Neste caso, a busca de uma solução é encontrar um par (d,k), tal que d ${\displaystyle \in }$ B e k ${\displaystyle \in }$ C.

Em casos como o diagnóstico médico estamos buscando uma função que resolva o problema, essa função é denominada função problema.

Um outro exemplo, é o problema da raiz de polinômio.

   A solução do problema da busca das raízes de um polinômio com coeficientes reais consiste em    associar a cada conjunto de coeficientes de um polinômio particular p(x) de grau n, n números    complexos cn de modo a satisfazer a condição de que o valor de p(x) fazendo x = c para todo    n seja nulo. 

A função problema, se existir, pode ser encontrada de diversas formas:

• Enumeração exaustiva: Enumerando todos os pares que ligam dados do problema ao conjunto solução. Evidentemente, este modo de definir uma função, só se aplica no caso que o conjunto de dados é finito.

   Exemplo:    Seja uma agenda de telefones. Ela pode ser considerada como a função que associa a    cada nome de pessoa seu telefone. 

• Declarativamente: Definindo propriedades que definem a solução do problema.

   Exemplo 1:    Dado um número real, associa dois números cuja soma de seus quadrados é igual ao    número real dado. A solução pode ser visualizada como um círculo, centrado na    origem de um plano com coordenadas ortonormais (eixos ortogonais e de mesma escala),    de raio igual ao número dado. 

   Exemplo 2:    Seja a função característica do conjunto das equações diofantinas de quarta ordem    que tem solução. Ora a partir de 3 sabe-se não haver teorema permitindo saber se    o problema tem ou não solução. Logo, o que resta é tentar todas as possibilidades...    e como existem infinitos números inteiros não se pode ter certeza, se calculando o    problema tem solução ou ainda não foi achada ou não tem solução! 

• Por um algoritmo: A correspondência entre dados e resultados é feita através de um programa de computador, e sempre que ele para consegue-se chegar a uma solução. Sendo assim, um programa pode ser considerado como um modo de definir um problema.

   Exemplo:    Formulário de Imposto de Renda 

• Por exemplos: Pode-se reconhecer que, neste caso, a solução não é única: todas as funções que sejam iguais dentro subconjunto em que o problema é definido são válidas e é necessário fazer uma aproximação, neste caso costuma-se usar técnicas de Inteligência artificial como Rede neural, Usam-se os exemplos para treinar a rede e obtém-se valores estimados da solução para os outros valores usando a propriedade de generalização das redes.

   Exemplo:    Costuma-se empregar redes neurais com aprendizado supervisionado. Usam-se os    exemplos para treinar a rede e obtém-se valores estimados da solução para os    outros valores usando a propriedade de generalização das redes 

Os modos de definir uma função levam a questões como Teoria da computabilidade e Complexidade.

• Inteligência artificial
• Sistema especialista
• TRIZ

• J.M. Barreto. Inteligência Artificial, uma abordagem híbrida