1 PROBLEMAS ALGORITMICOS

2  Los programadores deben ser capaces de diseñar una solución de tal manera que puedan resolver los problemas planteados.  Estos problemas requieren de cierto nivel de abstracción y análisis.  Luego de plantear la solución se debe implementar, y colocar las funciones identificadas en el análisis, y separar en módulos (Modularidad) 2

3 3 Clasificación de los problemas según su naturaleza.

4  Problema que responden si o no a determinada indagación.  Ejemplos: Responder si existe una ruta entre dos lugares o no. Responder si existe una secuencia de pasos para llegar a una solución. 4

5  Los problemas de localización consiste en encontrar determinada solución en caso exista.  Un problema de optimización consiste encontrar en caso exista la mejor soluciono la solución mas optima. 5

6  Son problemas tratables, es decir que tienen solución, ya sea buena o mala.  Podemos resolver problemas como cualquier tipo de transacción como son: un sistema de ventas, sistema de pagos, registro de clientes.  Se puede construir un autómata determinista para la solución.  Pueden ser resueltos en un tiempo polinómico. 6

7  Se necesita construir un autómata No determinista para su solución.  Puede ser transformado polinómicamente en el conjunto de problemas.  Pueden ser resueltos por problemas enumerativos.  No pueden resolverse en un tiempo polinómico.  Los problemas NP intratables se les conoce como NP- Difícil. Ejemplos: Coloración de mapas, selección de proyectos, agentes viajeros. 7

8 8 Relación entre problemas P y NP