Download - Problemas NP
![Page 1: Problemas NP](https://reader036.vdocumento.com/reader036/viewer/2022080901/55b43bcabb61ebda6b8b478e/html5/thumbnails/1.jpg)
Problemas NP Inteligencia Artificial
Por: Guillermo Arturo González
Villagómez y Joel Raúl López Saucedo
![Page 2: Problemas NP](https://reader036.vdocumento.com/reader036/viewer/2022080901/55b43bcabb61ebda6b8b478e/html5/thumbnails/2.jpg)
Según Alan Turing, si durante el intercambio entre una computadora y el usuario, este último cree que está intercambiando con otro humano, se considera que el sistema es inteligente.
Breve Introducción a IA
![Page 3: Problemas NP](https://reader036.vdocumento.com/reader036/viewer/2022080901/55b43bcabb61ebda6b8b478e/html5/thumbnails/3.jpg)
Se considera, que la solución de un problema abarca un razonamiento muy complejo, el cual, requiere generar esfuerzos para llegar al fin de la interrogante.
Breve Introducción a IA
![Page 4: Problemas NP](https://reader036.vdocumento.com/reader036/viewer/2022080901/55b43bcabb61ebda6b8b478e/html5/thumbnails/4.jpg)
Existen 4 diferentes formas de resolución de problemas.
Entrando en materia:
![Page 5: Problemas NP](https://reader036.vdocumento.com/reader036/viewer/2022080901/55b43bcabb61ebda6b8b478e/html5/thumbnails/5.jpg)
1. Aplicación de una fórmula explícita que da la solución
Entrando en materia:
![Page 6: Problemas NP](https://reader036.vdocumento.com/reader036/viewer/2022080901/55b43bcabb61ebda6b8b478e/html5/thumbnails/6.jpg)
2. Uso de una definición recursiva.
Entrando en materia:
![Page 7: Problemas NP](https://reader036.vdocumento.com/reader036/viewer/2022080901/55b43bcabb61ebda6b8b478e/html5/thumbnails/7.jpg)
3. Uso de un algoritmo que converge a la solución
Entrando en materia:
![Page 8: Problemas NP](https://reader036.vdocumento.com/reader036/viewer/2022080901/55b43bcabb61ebda6b8b478e/html5/thumbnails/8.jpg)
4. La aplicación de otros procesos, en particular la prueba y error
Entrando en materia:
![Page 9: Problemas NP](https://reader036.vdocumento.com/reader036/viewer/2022080901/55b43bcabb61ebda6b8b478e/html5/thumbnails/9.jpg)
una manera sencilla de explicar esto es de la siguiente manera:
Problema:comprobar si el número X es la raíz cuadrada del número Z
Una breve aplicación
![Page 10: Problemas NP](https://reader036.vdocumento.com/reader036/viewer/2022080901/55b43bcabb61ebda6b8b478e/html5/thumbnails/10.jpg)
Se puede solucionar de las siguientes maneras:.-Calculando la raíz de Z y comprobando con X (proceso lento y engorroso).-Elevando al cuadrado a X y compararlo con Z (simple multiplicación de X*X
Una breve aplicación
![Page 11: Problemas NP](https://reader036.vdocumento.com/reader036/viewer/2022080901/55b43bcabb61ebda6b8b478e/html5/thumbnails/11.jpg)
Lo que se puede concluir es que en algunos problemas es más fácil comprobarlos que realizarlos
Una breve aplicación
![Page 12: Problemas NP](https://reader036.vdocumento.com/reader036/viewer/2022080901/55b43bcabb61ebda6b8b478e/html5/thumbnails/12.jpg)
Cuando el algoritmo requiere tiempo polinomial para dar un resultado se dice que el problema es de clase P
![Page 13: Problemas NP](https://reader036.vdocumento.com/reader036/viewer/2022080901/55b43bcabb61ebda6b8b478e/html5/thumbnails/13.jpg)
Cuando no se conoce un algoritmo de solución polinomial, aunque sea posible, los problemas son de clase NP
![Page 14: Problemas NP](https://reader036.vdocumento.com/reader036/viewer/2022080901/55b43bcabb61ebda6b8b478e/html5/thumbnails/14.jpg)
Con los problemas de clase NP, dada una solución comprobar en tiempo polinomial si su costo es mejor que un determinado valor
![Page 15: Problemas NP](https://reader036.vdocumento.com/reader036/viewer/2022080901/55b43bcabb61ebda6b8b478e/html5/thumbnails/15.jpg)
De los problemas de clase NP son los que se encargan los métodos de solución de la Inteligencia Artificial.
![Page 16: Problemas NP](https://reader036.vdocumento.com/reader036/viewer/2022080901/55b43bcabb61ebda6b8b478e/html5/thumbnails/16.jpg)
Problemas NP-completo (ó Co-NP):contiene los problemas más difíciles de NP, en el sentido de que cuestan más tiempo polinómico que un problema NP “sencillo”
Tipos de Problemas NP
![Page 17: Problemas NP](https://reader036.vdocumento.com/reader036/viewer/2022080901/55b43bcabb61ebda6b8b478e/html5/thumbnails/17.jpg)
Importancia de Co-NP:se dice que esta clase es importante ya que si se desea conseguir la forma logarítmica de un problema NP, solucionando uno Co-NP se solucionan todos los problemas NP relacionados al problema que se desea resolver.
Tipos de Problemas NP
![Page 18: Problemas NP](https://reader036.vdocumento.com/reader036/viewer/2022080901/55b43bcabb61ebda6b8b478e/html5/thumbnails/18.jpg)
#P es el conjunto de problemas de conteo correspondientes a los problemas de decisión en NP
Tipos de Problemas NP