4.1 INTRODUCCIÓN A LA PROGRAMACIÓN LÓGICA
La Programación Lógica estudia el uso de la lógica para el planteamiento de problemas y el control sobre las reglas de inferencia para alcanzar la solución automática.
La Programación Lógica, junto con la funcional, forma parte de lo que se conoce como Programación Declarativa, es decir la programación consiste en indicar como resolver un problema mediante sentencias, en la Programación Lógica, se trabaja en una forma descriptiva, estableciendo relaciones entre entidades, indicando no como, sino que hacer, entonces se dice que la idea esencial de la Programación Lógica es
Programa= lógica + control
Lógica (programador): hechos y reglas para representar conocimiento
Control (interprete): deducción lógica para dar respuestas (soluciones)
La programación lógica intenta resolver lo siguiente:
Dado un problema S, saber si la afirmación A es solución o no del problema o en qué casos lo es. Además queremos que los métodos sean implantados en maquinas de forma que la resolución del problema se haga de forma automática.
La programación lógica: construye base de conocimientos mediante reglas y hechos
* Regla: implicación o inferencia lógica que deduce nuevo conocimiento, la regla permite definir nuevas relaciones a partir de otras ya existentes
Ej.:
Mortal (x): – humano(x)
x es mortal si x es humano
*Hecho: declaración, cláusula o proposición cierta o falsa, el hecho establece una relación entre objetos y es la forma más sencilla de sentencia
Ej.:
Humano (Sócrates); Sócrates es humano
Ama (Juan, María) ; ama Juan a María
*Consulta: se especifica el problema, la proposición a demostrar o el objetivo Partiendo de que los humanos son mortales y de que Sócrates es humano, deducimos que
Sócrates es mortal
Mortal (x): – humano(x);- los humanos son mortales; regla
Humano (Sócrates); Sócrates es humanos; hecho
4.3 SEMÁNTICA DE LOS PROGRAMAS LÓGICOS
Caracteristica:
• Los objetos y las relaciones importantes deben aparecer explícita-mente y de forma conjunta
4.4 Representación clausada
Representación clausada del conocimiento
La representación del conocimiento y el razonamiento es un área de la inteligencia artificial cuyo
objetivo fundamental es representar el conocimiento de una manera que facilite la inferencia (sacar
conclusiones) a partir de dicho conocimiento. Analiza cómo pensar formalmente - cómo usar un
sistema de símbolos para representar un dominio del discurso (aquello de lo que se puede hablar),
junto con funciones que permitan inferir (realizar un razonamiento formal) sobre los objetos.
Generalmente, se usa algún tipo de lógica para proveer una semántica formal de como las
funciones de razonamiento se aplican a los símbolos del dominio del discurso, además de proveer
operadores como cuantificadores, operadores modales, etc. Esto, junto a una teoría de
interpretación, dan significado a las frases en la lógica.
Cuando diseñamos una representación del conocimiento (y un sistema de representación del
conocimiento para interpretar frases en la lógica para poder derivar inferencias de ellas) tenemos
que hacer elecciones a lo largo de un número de ámbitos de diseño. La decisión más importante
que hay que tomar es la expresividad de la representación del conocimiento. Cuanto más
expresiva es, decir algo es más fácil y más compacto. Sin embargo, cuanto más expresivo es un
lenguaje, más difícil es derivar inferencias automáticamente de él. Un ejemplo de una
representación del conocimiento poco expresiva es la lógica proposicional. Un ejemplo de una
representación del conocimiento muy expresiva es la lógica autoepistémica. Las representaciones
del conocimiento poco expresivas pueden ser tanto completas como consistentes (formalmente
menos expresivas que la teoría de conjuntos). Las representaciones del conocimiento más
expresivas pueden ser ni completas ni consistentes.
El principal problema es encontrar una representación del conocimiento y un sistema de
razonamiento que la soporte que pueda hacer las inferencias que necesite tu aplicación dentro de
los límites de recursos del problema a tratar. Los desarrollos recientes en la representación del
conocimiento han sido liderados por la web semántica, y han incorporado el desarrollo de
lenguajes y estándares de representación del conocimiento basados en XML, que
incluyen Resource Description Framework (RDF), RDF Schema, DARPA Agent Markup
Language (DAML), y Web Ontology Language (OWL).
4.5. Espacios de búsqueda.
Cuando se resuelve un problema, se busca la mejor solución entre un conjunto de posibles soluciones. Al conjunto de todas las posibles soluciones a un problema concreto se llama espacio de búsqueda. Cada punto en el espacio de búsqueda representa una posible solución. Cada posible solución se le puede asociar un fitness o un valor que indicará cómo de buena es la solución para el problema. Un algoritmo genético (AG) devolverá la mejor solución de entre todas las posibles que tenga en un momento dado.
Entonces parece que buscar una solución se reduce a buscar un valor extremo (mínimo o máximo) en el espacio de búsqueda. A veces el espacio de búsqueda puede ser bien definido, pero en la mayoría de las ocasiones sólo se conocen algunos puntos en el espacio de búsqueda. Cuando se usa un AG las posibles soluciones generan otras a medida que el genético evoluciona.
La resolución de un problema puede expresarse como la busqueda del extremo de una función Aquí resolvemos ese problema, este es un algorítmo genético que calcula el máximo de una función. La gráfica representa un espacio de busqueda y las líneas verticales son posibles soluciones. La línea roja es el mejor individuo de la población y las verdes el resto.
Pulsa el botón Empezar para que el genético comience, el botón Parar detendrá la ejecución, en el botón Paso a Paso se ejecutará un único paso creando una nueva población y el botón Reiniciar creará una nueva población inicial.
El problema estriba en que la búsqueda puede ser muy compleja por diversas razones, como por ejemplo no saber dónde buscar una solución o dónde empezar a buscarla. Existen muchos métodos que se usan para buscar una solución válida, pero no necesariamente obtienen la mejor solución. Algunos de estos métodos son los algoritmos de escalada, backtracking o vuelta atrás, búsqueda a ciegas y los algoritmos genéticos. Las soluciones que encuentran estos tipos de búsqueda suelen ser buenas soluciones, pero no siempre encuentran la óptima.
4.4 Consulta de una base de datos de clausulas.
SELECT select_list
FROM table_source
[WHERE search_condition]
[GROUP BY group_by_expression]
[HAVING search_condition]
[ORDER BY order_expression [ASC | DESC] ]
FROM
4.5 Espacios de búsqueda
Especifica de dónde queremos obtener los datos, es decir, de que tabla. Se utiliza no sólo en el comando de consulta, SELECT, sino también en los comandos UPDATE y DELETE .Problemas NP Completos
Cuando se plantea un problema concreto, habrá una serie de algoritmos aplicables. Se suele decir que el orden de complejidad de un problema es el del mejor algoritmo que se conozca para resolverlo. Así se clasifican los problemas, y los estudios sobre algoritmos se aplican a la realidad.
Estos estudios han llevado a la constatación de que existen problemas muy difíciles, problemas que desafían la utilización de los ordenadores para resolverlos. En lo que sigue esbozaremos las clases de problemas que hoy por hoy se escapan a un tratamiento informático.
Clase P
Los algoritmos de complejidad polinómica se dice que son tratables en el sentido de que suelen ser abordables en la práctica. Los problemas para los que se conocen algoritmos con esta complejidad se dice que forman la clase P.
Aquellos problemas para los que la mejor solución que se conoce es de complejidad superior a la polinómica, se dice que son problemas intratables. Seria muy interesante encontrar alguna solución polinómica (o mejor) que permitiera abordarlos.
Aquellos problemas para los que la mejor solución que se conoce es de complejidad superior a la polinómica, se dice que son problemas intratables. Seria muy interesante encontrar alguna solución polinómica (o mejor) que permitiera abordarlos.
Clase NP
Algunos de estos problemas intratables pueden caracterizarse por el curioso hecho de que puede aplicarse un algoritmo polinómico para comprobar si una posible solución es válida o no. Esta característica lleva a un método de resolución no determinista consistente en aplicar heurísticos para obtener soluciones hipotéticas que se van desestimando (o aceptando) a ritmo polinómico.
Los problemas de esta clase se denominan NP (la N de no-deterministas y la P de polinómicos).
Los problemas de esta clase se denominan NP (la N de no-deterministas y la P de polinómicos).
Clase NP Completos
Se conoce una amplia variedad de problemas de tipo NP, de los cuales destacan algunos de ellos de extrema complejidad. Gráficamente se puede decir que algunos problemas se hayan en la "frontera externa" de la clase NP. Son problemas NP, y son los peores problemas posibles de clase NP. Estos problemas se caracterizan por ser todos "iguales" en el sentido de que si se descubriera una solución P para alguno de ellos, esta solución sería fácilmente aplicable a todos ellos. Actualmente hay un premio de prestigio equivalente al Nobel reservado para el que descubra semejante solución... ¡y se duda seriamente de que alguien lo consiga!
Es más, si se descubriera una solución para los problemas NP-completos, esta sería aplicable a todos los problemas NP y, por tanto, la clase NP desaparecería del mundo científico al carecerse de problemas de ese tipo. Realmente, tras años de búsqueda exhaustiva de dicha solución, es hecho ampliamente aceptado que no debe existir, aunque nadie ha demostrado, todavía, la imposibilidad de su existencia...
Una alternativa para resolver los problemas NP-completos son los algoritmos genéticos. Ejemplos de problemas NP-completos son el problema del viajante de comercio (TSP), el problema del coloreamiento de un grafo, el problema de la satisfacibilidad...
Clase NP Duros
Esta clase puede ser descrita como conteniendo los problemas de decisión que son al menos tan dificiles como un problema de NP. Esta afirmación se justifica porque si podemos encontrar un algoritmo A que resuleve uno de los problemas H de NP-hard en tiempo polinómico, entonces es posible construir un algotimo que trabaje en tiempo polinómico para cualquier problema de NP ejecutando primero la reducción de este problema en H y luego ejecutando el algoritmo A. La clase NP-completo puede definirse alternativamente como la intersección entre NP y NP-hard
Comentarios
Publicar un comentario