Clasificación de Problemas

 

Que es un Problema?

Es una pregunta sobre un conjunto de datos.

 

Que es una Solución?

Es el método general para resolver todas las posibles preguntas.

 

Clasificación de los Problemas.

 

Los problemas matemáticos se pueden dividir en 2 grupos:

a) Problemas indecidibles.

Son aquellos que no se pueden resolver a través de un algoritmo.

›b) Problemas decidibles.

Son aquellos que cuentan al menos con un algoritmo para su cómputo.

 

Tipos de problemas decidibles.

 

a) Tratables.

Aquellos para los que existe al menos un algoritmo capaz de resolverlo en un tiempo razonable. A los problemas tratables se les conoce también como problemas de complejidad P (de orden polinomial).

› Ej: Problema Tratable.

Calcule la rentabilidad económica de las acciones de Codelco en la bolsa internacional de valores del último semestre.

› b) Intratables.

Aquellos para los que no es factible obtener su solución. A los problemas intratables se le conoce también como problemas NP (de orden no determinístico polinomial).

› Ej: Problema Intratable.

Determine las variables de espacio – tiempo que influyeron en la generación del Big Bang que dio origen al sistema solar.

 

Clasificación de Problemas según Complejidad.

 

COMPLEJIDAD              /     CONCEPTOS	P (POLINÓMICO)	NP (NO-DETERMINISTA POLINÓMICO)	NP-COMPLETO (NO-DETERMINISTA POLINÓMICO COMPLETO)
DEFINICIÓN	Son los problemas tratables, es decir que suelen ser abordables en la práctica, pueden contener muchos problemas naturales.	Son los problemas en los cuales se aplica un algoritmo polinómico para comprobar si una posible solución es viable o no.	Son aquellos problemas los cuales están en  la frontera externa  de la clase np, son los peores problemas posibles de la clase np.
DIFERENCIAS	En P están los problemas que se pueden resolver en tiempo polinómico.	Sus mejores algoritmos conocidos son no deterministas.	Imposible encontrar un algoritmo eficiente para una solución óptima.
EJEMPLOS	Búsqueda binaria, secuencial, factorial.	Torres de hanoi, Ordenación Shell.	Vendedor viajero, mochila, camino largo, ciclo hamiltoniano, coloración, etc.

 

Solución a problemas  NP-Completo.

 

 

1) Técnicas Heurísticas.

Se basa en el conocimiento intuitivo del programador sobre un determinado problema.

2) Aproximaciones Polinomiales.

Soluciones q se aproximen a la solución óptima.

 

Problemas de Decisión.

 

 

Son aquellos problemas que están asociados a un problema de optimización y que pueden ser resueltos a través de una respuesta por SI o por NO.

 

Ejemplos de Problemas de Decisión.

 

 

1) Halting Problem.

Dado un problema y su entrada, ¿Parara este alguna vez?.

2) Problema de Satisfactibilidad (SAT).

Dada una formula booleana, ¿Es esta satisfactible?.

3) Problema de circulo Hamiltoniano.

Dado un grafo G ¿Hay un circuito en G que visite todos los nodos exactamente de una vez?.

 

Algoritmos para resolver SAT.

 

 

a) Métodos Exactos.

Si existe una solución siempre va a encontrarla.

 Ej: Algoritmo de Davis y Putman, Algoritmo de 2 Fases.

b) Métodos Incompletos.

Son aquellos que no siempre van a encontrar la solución.

 Ej: Algoritmo de Greedy o GSAT, Algoritmo WalkSat, SA-SAT, MASK, Redes neuronales.

 

Aplicación del Problema SAT.

 

 

• Lógica matemática.

• Inteligencia Artificial.

• Ingeniería VLSI.

• Teoría Computacional.