# Teoria dos problemas

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

## Tipos de problemas

Podemos enquadrar os problemas em três grandes grupos:$^[$
* 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).
* Os que têm solução algorítmica e podemos resolvê-los formalmente passo a passo, codificando os algoritmos para sua resolução.
* 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.

## Definição de problema

É 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: 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.

## Caracterização de um problema

P

### 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.
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:
Neste caso, a busca de uma solução é encontrar um par (d,k), tal que d $\in$ B e k $\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 função problema

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.
* Declarativamente: Definindo propriedades que definem a solução do problema.
* 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.
* 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.
Os modos de definir uma função levam a questões como Teoria da computabilidade e Complexidade.