1 INTELIGENCIA ARTIFICIALFISI – UNMSM II

2 Clasificación de Problemas AlgorítmicosPresentación del curso. Clasificación de problemas algorítmicos, problemas P y NP. Problemas de decisión, localización y optimización. Descripción de algunos problemas NP-difícil.

3 Presentación La I.A. es el estudio de los sistemas de computación que permiten realizar actividades consideradas inteligentes por el ser humano. Tiene por objetivo resolver problemas a través de ideas del conocimiento, su representación y del ensamblaje de sistemas.

4 Clasificación de Problemas AlgorítmicosPor el tipo de respuesta. (problemas de decisión, localización y optimización) Por su naturaleza. Por su tratabilidad.

5 Problemas de decisión, localización y optimizaciónProblemas de decisión. Consisten en responder SI o NO a determinada indagación. Problemas de localización. Consisten en encontrar, en caso exista, una determinada estructura satisfaciendo requisitos especificados por el problema. Problemas de Optimización. Consiste en un problema de localización y por lo menos un criterio de optimización. Grado de dificultad: Optimización > Localización > Decisión

6 Problemas Algorítmicos por su Naturaleza- Problemas de naturaleza algorítmica que no admiten solución por algoritmo son llamados no-computables. - Problemas de decisión y no-computables son llamados indecidibles. - Problemas para los cuales existen algoritmos de complejidad polinomial son llamados tratables. - Problemas para los cuales comprobadamente no pueden ser resueltos por algoritmos de complejidad polinomial son rotulados intratables. Ejemplo: Problema del agente viajero, Problema de la selección de proyectos

7 Descripción de algunos problemas NP-difícilUn problema P se dice que es NP-difícil, si todo problema de NP es polinómicamente reducible a él. P se dice que es NP-completo, si P es NP-difícil y además, está en NP . Ejemplos: - Problema de la satisfactibilidad. - Problema de la mochila.