Teoria dos problemas

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Ambox rewrite.svg
Esta página precisa ser reciclada de acordo com o livro de estilo (desde maio de 2015).
Sinta-se livre para editá-la para que esta possa atingir um nível de qualidade superior.
Text document with red question mark.svg
Este artigo ou secção contém fontes no fim do texto, mas que não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (desde maio de 2015)
Por favor, melhore este artigo introduzindo notas de rodapé citando as fontes, inserindo-as no corpo do texto quando necessário.

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[editar | editar código-fonte]

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.

Definição de problema[editar | editar código-fonte]

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

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.

Caracterização de um problema[editar | editar código-fonte]

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

A função problema[editar | editar código-fonte]

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.

Ver também[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]