Explique la definición formal de un problema
El primer paso para diseñar un programa que resuelva un problema es crear una descripción formal y manejable del propio problema. Sería adecuado contar con programas que produzcan descripciones formales a partir de descripciones informales, proceso denominado operacionalización. Dado que por ahora no se conoce la forma de construir estos programas este proceso debe hacerse manualmente.
Hay problemas que por ser artificiales y estructurados son fáciles de especificar (por ej. el ajedrez, el problema de las jarras de agua, etc.). Otros problemas naturales, como por ej. la comprensión del lenguaje, no son tan sencillos de especificar.
Para producir una especificación formal de un problema se deben definir:
Espacio de estados válidos;
Estado inicial del problema;
Estado objetivo o final;
Reglas que se pueden aplicar para pasar de un estado a otro.
Un estado es la representación de un problema en un instante dado. Para definir el espacio de estados no es necesario hacer una enumeración exhaustiva de todo el estado válido, sino que es posible definirlo de manera más general.
El estado inicial consiste en uno o varios estados en los que puede comenzar el problema. El estado objetivo consiste en uno o varios estados finales que se consideran solución aceptable.
Las reglas describen las acciones u operadores que posibilitan un pasaje de estados. Una regla tiene una parte izquierda y una parte derecha. La parte izquierda determina la aplicabilidad de la regla, es decir, describe los estados a los que puede aplicarse la regla. La parte derecha describe la operación que se lleva a cabo si se aplica la regla, es decir, como obtener el estado sucesor.
Por ejemplo, en el problema de jugar al ajedrez:
- El espacio de estados son la totalidad de tableros que se puede generar en un juego de ajedrez;
- El estado inicial es el tablero de 8 x 8 donde cada celda contiene un símbolo de acuerdo a las piezas situadas;
- El objetivo o estado final se define como cualquier posición de tablero en la que el contrario no puede realizar ningún movimiento legal y su rey esté amenazado;
- Las reglas son los movimientos legales, que pueden describirse mediante una parte patrón para ser contrastado con la posición actual de tablero y otra parte que describe el cambio que debe producirse en el tablero.
Dado que escribir exhaustivamente todas las reglas es imposible prácticamente, (en el ejemplo, escribir todas las posiciones de tablero), las reglas deben escribirse de la manera más general posible.
La representación como espacio de estados forma parte de la mayoría de los métodos de IA. Su estructura se corresponde con la resolución de problemas porque:
Permite definir formalmente el problema, mediante la necesidad de convertir una situación dada en una situación deseada mediante un conjunto de operaciones permitidas;
Permite definir el proceso de resolución de un problema como una combinación de técnicas conocidas y búsqueda (la técnica general de exploración del espacio intenta encontrar alguna ruta desde el estado actual hasta un estado objetivo).
Mediante una presentación explique en qué consiste y de ejemplos de las clases P, NP y NP completo.
Clase P
Contiene aquellos problemas de decisión que pueden ser resueltos en tiempo polinomico por una MT determinista, esto es, aquellas en las que para cada par estado y símbolo exista a lo sumo una posibilidad de ejecución. Los problemas de complejidad polinomica son tratables, es decir, en la práctica se pueden resolver en un tiempo razonable.
El primer paso para diseñar un programa que resuelva un problema es crear una descripción formal y manejable del propio problema. Sería adecuado contar con programas que produzcan descripciones formales a partir de descripciones informales, proceso denominado operacionalización. Dado que por ahora no se conoce la forma de construir estos programas este proceso debe hacerse manualmente.
Hay problemas que por ser artificiales y estructurados son fáciles de especificar (por ej. el ajedrez, el problema de las jarras de agua, etc.). Otros problemas naturales, como por ej. la comprensión del lenguaje, no son tan sencillos de especificar.
Para producir una especificación formal de un problema se deben definir:
Espacio de estados válidos;
Estado inicial del problema;
Estado objetivo o final;
Reglas que se pueden aplicar para pasar de un estado a otro.
Un estado es la representación de un problema en un instante dado. Para definir el espacio de estados no es necesario hacer una enumeración exhaustiva de todo el estado válido, sino que es posible definirlo de manera más general.
El estado inicial consiste en uno o varios estados en los que puede comenzar el problema. El estado objetivo consiste en uno o varios estados finales que se consideran solución aceptable.
Las reglas describen las acciones u operadores que posibilitan un pasaje de estados. Una regla tiene una parte izquierda y una parte derecha. La parte izquierda determina la aplicabilidad de la regla, es decir, describe los estados a los que puede aplicarse la regla. La parte derecha describe la operación que se lleva a cabo si se aplica la regla, es decir, como obtener el estado sucesor.
Por ejemplo, en el problema de jugar al ajedrez:
- El espacio de estados son la totalidad de tableros que se puede generar en un juego de ajedrez;
- El estado inicial es el tablero de 8 x 8 donde cada celda contiene un símbolo de acuerdo a las piezas situadas;
- El objetivo o estado final se define como cualquier posición de tablero en la que el contrario no puede realizar ningún movimiento legal y su rey esté amenazado;
- Las reglas son los movimientos legales, que pueden describirse mediante una parte patrón para ser contrastado con la posición actual de tablero y otra parte que describe el cambio que debe producirse en el tablero.
Dado que escribir exhaustivamente todas las reglas es imposible prácticamente, (en el ejemplo, escribir todas las posiciones de tablero), las reglas deben escribirse de la manera más general posible.
La representación como espacio de estados forma parte de la mayoría de los métodos de IA. Su estructura se corresponde con la resolución de problemas porque:
Permite definir formalmente el problema, mediante la necesidad de convertir una situación dada en una situación deseada mediante un conjunto de operaciones permitidas;
Permite definir el proceso de resolución de un problema como una combinación de técnicas conocidas y búsqueda (la técnica general de exploración del espacio intenta encontrar alguna ruta desde el estado actual hasta un estado objetivo).
Mediante una presentación explique en qué consiste y de ejemplos de las clases P, NP y NP completo.
Clase P
Contiene aquellos problemas de decisión que pueden ser resueltos en tiempo polinomico por una MT determinista, esto es, aquellas en las que para cada par estado y símbolo exista a lo sumo una posibilidad de ejecución. Los problemas de complejidad polinomica son tratables, es decir, en la práctica se pueden resolver en un tiempo razonable.
Clase NP
Es aquella cuyos problemas son verificables en tiempo polinomial. Lo que se quiere decir es que si se tuviera alguna clase de “certificado” de una solución, entonces, es posible verificar en tiempo polinomial que el certificado es correcto, respecto al tamaño de la entrada.
Es aquella cuyos problemas son verificables en tiempo polinomial. Lo que se quiere decir es que si se tuviera alguna clase de “certificado” de una solución, entonces, es posible verificar en tiempo polinomial que el certificado es correcto, respecto al tamaño de la entrada.
Clase NP Completo
Se compone de todos los problemas que son tan “faciles” (o difíciles) como todos los demás que pertenecen a esta misma clase. Si es posible solucionar algún problema que sea NPC en tiempo polinomial, entonces se podrá solucionar cualquier otro problema de esta clase en tiempo polinomial.
Se compone de todos los problemas que son tan “faciles” (o difíciles) como todos los demás que pertenecen a esta misma clase. Si es posible solucionar algún problema que sea NPC en tiempo polinomial, entonces se podrá solucionar cualquier otro problema de esta clase en tiempo polinomial.
Señale y explique 3 problemas NP. ¿Por qué se consideran problemas NP?
Ejemplo 1:
Bin Packing, que consiste en dada una secuencia de números, empaquetarlos en el mínimo número de latas posible, teniendo en cuenta que cada lata tiene capacidad M y la suma de los números introducidos en la lata no puede exceder el Valor M.
Ejemplo 2
Problemas de satisfactibilidad (SAT) de los que hablaremos a continuacion es un problema de lógica matemática y la teoría de la computación.
Ø La satisfactibilidad proposicional es el problema de decidir si existe una asignación de 0´s y 1´s a los átomos de una formula proposicional que la hacen Verdadera.
Ø Se puede asumir que las instancias SAT están expresadas en FNC sin pérdida de generalidad. Ejemplo: La asignación de valores de verdad que satisfacen la fórmula (P ۷ ¬ Q) ۸(Q ۷ R) ۸(¬ R ۷ ¬P) es P = Q = 1 y R = 0, por lo que la fórmula es satisfactible.
Ejemplo 3
En el mapa tienes marcado n lugares diferentes de la ciudad y quieres saber si existe un camino que pase por todos esos lugares exactamente una vez (sin repetición). Este problema es muy fácil de comprobar, si yo te propongo una solución tu rápidamente puedes comprobar en tan solo O(n) operaciones que el camino que yo propuse efectivamente pasa una sola vez por los n sitios. A pesar de que es fácil de comprobar, nadie sabe cómo resolverlo fácilmente. Todos los algoritmos que se han descubierto para este problema no son esencialmente mejores que una búsqueda por fuerza bruta (pero nadie ha comprobado que no exista un algoritmo polinomial para resolverlo). Este problema se conoce como el problema de Camino Hamiltoniano
Ejemplo 1:
Bin Packing, que consiste en dada una secuencia de números, empaquetarlos en el mínimo número de latas posible, teniendo en cuenta que cada lata tiene capacidad M y la suma de los números introducidos en la lata no puede exceder el Valor M.
Ejemplo 2
Problemas de satisfactibilidad (SAT) de los que hablaremos a continuacion es un problema de lógica matemática y la teoría de la computación.
Ø La satisfactibilidad proposicional es el problema de decidir si existe una asignación de 0´s y 1´s a los átomos de una formula proposicional que la hacen Verdadera.
Ø Se puede asumir que las instancias SAT están expresadas en FNC sin pérdida de generalidad. Ejemplo: La asignación de valores de verdad que satisfacen la fórmula (P ۷ ¬ Q) ۸(Q ۷ R) ۸(¬ R ۷ ¬P) es P = Q = 1 y R = 0, por lo que la fórmula es satisfactible.
Ejemplo 3
En el mapa tienes marcado n lugares diferentes de la ciudad y quieres saber si existe un camino que pase por todos esos lugares exactamente una vez (sin repetición). Este problema es muy fácil de comprobar, si yo te propongo una solución tu rápidamente puedes comprobar en tan solo O(n) operaciones que el camino que yo propuse efectivamente pasa una sola vez por los n sitios. A pesar de que es fácil de comprobar, nadie sabe cómo resolverlo fácilmente. Todos los algoritmos que se han descubierto para este problema no son esencialmente mejores que una búsqueda por fuerza bruta (pero nadie ha comprobado que no exista un algoritmo polinomial para resolverlo). Este problema se conoce como el problema de Camino Hamiltoniano