Tipos de problemas

Material de tipos de problemas para la clase de análisis de algoritmos - Inacap

1. Tipos de problemas Luis Guzmán Docente: Pilar Pardo Análisis de algoritmo - Inacap

2. Complejidad computacional. La complejidad computacional considera todos los posibles algoritmos para resolver un problema dado. Existen problemas denominados PROBLEMA TRATABLES y PROBLEMAS INTRATABLES,

3. Clasificación. Problemas Indecibles (no se pueden resolver con un algoritmo). Problemas Decidibles (cuentan con al menos un algoritmo para su cómputo).

4. “No todo problema decidible tiene una solución.” Característica que permite dividir los problemas decidibles en 2 tipos: Intratables (no poseen solución) No admite algoritmos razonables. Tratables (existe al menos un algoritmo capaz de resolverlo) Admite algoritmos razonables.

5. Clasificación de problemas por complejidad. - Problemas de Clase P. Problemas de Clase NP. Problemas de Clase NP Completos.

6. La clase P. En esta categoría están los problemas que son tratables (suelen ser abordables en la práctica). Es decir, problemas que pueden ser resueltos por algoritmos de complejidad polinominal . Problemas que pueden ser resueltos en un tiempo polinómico.

7. La clase NP. A algunos de estos problemas se les puede aplicar un algoritmo polinómico para ver si una posible solución es válida o no. Problemas que no pueden ser resueltos en un tiempo polinómico.

8. La clase NP-Completos. La característica de estos problemas es que si existiera al menos una solución para uno de ellos podría aplicarse para todos los demás.