INTELIGENCIA ARTIFICIAL - CICLO 2012-I - GRUPO 6

INTELIGENCIA ARTIFICIAL - CICLO 2012-I - GRUPO 6

• La complejidad computacional estudia el coste de la resolución de un problema.

• Los recursos mas estudiados son: el tiempo y espacio de memoria que necesitan los algoritmos para resolver los problemas dados.

2 de 7

INTELIGENCIA ARTIFICIAL - CICLO 2012-I - GRUPO 6

• Los problemas de decisión son aquellos problemas que pueden dar una respuesta positiva o negativa.

• Un problema de decisión también se puede formalizar como el problema de decidir si una cierta frase pertenece a un conjunto dado de frases, también llamado lenguaje formal.

• En este tipo de problemas destacan los problemas P y NP. 3 de 7

INTELIGENCIA ARTIFICIAL - CICLO 2012-I - GRUPO 6

• Los problemas de localización son aquellos en donde se trata de encontrar la mejor ubicación de una instalación dentro de un espacio geográfico.

• Los problemas de optimización son aquellos que intentan dar respuesta a un tipo general de problemas donde se desea elegir el mejor entre un conjunto de opciones.

4 de 7

INTELIGENCIA ARTIFICIAL - CICLO 2012-I - GRUPO 6

• Los problemas P son aquellos problemas de decisión que pueden ser resueltos por una maquina determinista en tiempo polinomio.

• Los problemas NP son problemas de decisión que pueden ser resueltos en tiempo polinomio por una maquina no determinista.

5 de 7

INTELIGENCIA ARTIFICIAL - CICLO 2012-I - GRUPO 6

• Problemas de suma de subconjuntos.- dado un conjunto S de enteros, ¿existe algún subconjunto cuya suma sea exactamente cero?

• Problema de parada.- Este problema consiste en tomar un programa y sus datos y decidir si va a terminar o si se ejecutará indefinidamente.

6 de 7

INTELIGENCIA ARTIFICIAL - CICLO 2012-I - GRUPO 6

• Problema de satisfactibilidad booleana (SAT).- donde interesa saber si una expresión booleana con variables y sin cuantificadores tiene asociada una asignación de valores para sus variables que hace que la expresión sea verdadera

7 de 7