Teoria dos problemas
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. (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.
Tipos de problemas editar
Podemos enquadrar os problemas em três grandes grupos:[carece de fontes]
- 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 editar
É 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.
Caracterização de um problema editar
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 B e k 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
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.