Teoria dos problemas

Origem: Wikipédia, a enciclopédia livre.

Índice

1 Introdução
2 Tipos de problemas
3 O que é um problema?
4 Definição de Problema
5 Caracterização de Problema
6 Exemplos
7 A Função Problema
8 Referências

[editar] Introdução

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

[editar] Tipos de problemas

Podemos enquadrar os problemas em três grandes grupos:

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 passao 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.

[editar] O que é um 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 siginifica 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?
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;
O tabuleiro de xadrez mutilado;
Entre outros.

[editar] Definição de Problema

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.

[editar] Caracterização de Problema

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

[editar] 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 $\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 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.

[editar] 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.

   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 órdem
   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 obtem-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 obtem-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.