Tipos de ProblemasTipos de ProblemasTipos de ProblemasTipos de ProblemasPablo Rojas V.

Complejidad Computacional

• La complejidad computacional considera globalmente todos los• La complejidad computacional considera globalmente todos los

posibles algoritmos para resolver un problema cualquiera.

• Se quiere establecer la diferencia entre problemas que pueden ser

resueltos en tiempo polinómico y los problemas para los cuales no se

conoce algún algoritmo polinómico.

• Se presentarán definiciones que pretenden hacer diferencia entre los

problemas tratables y los intratables.

Clasificación de Problemas

Los problemas matemáticos se pueden segmentar en dosLos problemas matemáticos se pueden segmentar en dos

grupos:

• Problemas indecidibles: Que no se pueden resolver

mediante un algoritmo.

• Problemas decidibles: Que cuentan al menos con un

algoritmo para su cómputo.

Problemas

Clasificación de Problemas

Problemas Problemas

Intratables

No admite algoritmos

razonables.

Problemas

Tratables

Admite algoritmos

razonables.

Clasificación por su complejidad

La Clase P

Problemas de la Está construida por todos

los problemas

comprobadamente

tratables, o sea, problemas

que pueden ser resueltos

por algoritmos de

complejidad polinomial.

Problemas de la

Clase P

• Resolución de sistemas

de ecuaciones lineales.

• Ordenar números.

• Juntar archivos

• Sistema de

transacciones

bancarias.

Clasificación por su complejidad

La Clase NP

Está construido por todos los problemas que pueden ser resueltos por algoritmos

enumerativos, cuya búsqueda en el espacio de soluciones es realizada en un árbol

con profundidad limitada por una función polinomial respecto al tamaño de la

instancia del problema y con ancho eventualmente exponencial.

Problemas de la Clase NP• Torres de Hanoi.

• ShellSort

Clasificación por su complejidad

Clase NP Problemas Clase

Clase NP

Completos

Estos problemas se caracterizan por ser

todos iguales en el sentido de que si se

descubriera una solución P para alguno

de ellos, esta solución sería fácilmente

aplicable a todos ellos.

Problemas Clase

NP Completos

• Mochila: Con un peso W y n

objetos, cada uno con un peso

específico y una ganancia

asociada. La idea es maximizar el

uso de la mochila. Los objetos se

pueden dividir para alcanzar el

peso total.

FinFin