UNIDAD 4:INTRODUCCION A LA PROGRAMACION LOGICA 4.1 Introducción a la programación lógica En los comienzos de los años 70 el francés Alain Colmenuer desarrolló el lenguaje PROLOG que también permite el desarrollo de aplicaciones en forma declarativa. En general el PROLOG es un demostrador automático de problema, el cual utiliza una Base de Conocimientos en forma de reglas de inferencia deductivas (cláusulas de Horn), es decir sus reglas tienen como consecuente una única acción y las inferencias obte¬nidas son estrictamente lógicas (verdaderas o falsas), aunque puede parecer una limitación, esto no es totalmente justo, ya que PROLOG permite programar mecanismos inferenciales con lógica probabilisticas, dado que se trata de búsquedas en árboles con acumulación de evidencias. El PROLOG como lenguaje surgido del cálculo de predicados, tomó las siguientes ideas de la lógica para su ejecución. 1) Un conjunto de axiomas o hechos. 2) Reglas de inferencias las cuales se resuelven por resolución y unificación. 3) El objetivo a demostrar, que serán las condiciones a unificar con las reglas. También tomó del LISP el tratamiento de las listas para la repre¬sentación de estructuras complejas. Aunque el PROLOG tuvo su origen en la lógica matemática no fue una transposición exacta, y esta ligada a las discusiones que sostienen desde hace años los principales investigadores de la Inteligencia Artificial, los cuales están divididos en dos grandes grupos, de una parte Minsky quien propone estudiar los mecanismos del pensamiento humano y luego simularlo en la computadora. Lo más importante para Minsky son los conceptos, o sea la inter¬pretación que se le puede dar a cada palabra en dependencia de un contexto dado. El otro grupo encabezado por Mac Carthy (autor del LISP), afirma que la lógica matemática es el elemento característico para la representación del razonamiento y su implantación en la computadora, este grupo centra su atención en la formalización y en la estructura de los conocimientos más que en el sentido de los mismos. La lógica desde la antigüedad se concibió como el método de descubrir las leyes del pensamiento, pero estas leyes siempre han estado restringidas al pensamiento científico y muy especialmente el matemático, quedando fuera el sentido común. Esta deficiencia es admitida por los defensores de la lógica, pero ellos consideran que la lógica es la única senda posible para desarrollar programas capaces de mostrar inteligencia. 4.2 Mecanismos básicos matching) de patrones,árboles y backtracking automático. 4.3 Estructura de un programa Sinopsis Desde el punto de vista lógico, puede considerarse que los programas comprenden dos tipos de elementos diferentes: estructuras de datos y algoritmos. O dicho en otras palabras: datos, e instrucciones para su manipulación. Su representación dificada adopta dos formas: una entendible por la máquina (ejecutable y ficheros de datos) y otra entendible por el humano (fuente). Para el conjunto de ambas puede considerarse una escala conceptual que, si vamos de lo general a lo particular, podemos representarla como sigue: Nota: clasificaciones como la que aquí proponemos solo tiene una finalidad didáctica; son un vehículo para introducir al lector en la comprensión global del concepto y no un asunto dogmático e inamovible, ya que este tipo de asuntos depende grandemente del punto de vista que se adopte. Como botón de muestra, vaya por delante la definición de lo que es un programa en palabras de Ellis y Stroustrup , que por lo demás ofrece un punto de vista muy interesante: "Un programa consiste en uno o más ficheros enlazados juntos. Un fichero consiste en una secuencia de declaraciones" (ver Declaraciones y definiciones en. A continuación admiten que esta afirmación puede parecer extraña a aquellos acostumbrados a pensar en un programa como una serie de sentencias ejecutables acompañadas de las declaraciones de las variables correspondientes. Pero recuerdan que en C++, las sentencias están contenidas en funciones, y que en realidad, el cuerpo de una función es en sí mismo una declaración (de la propia función). En consecuencia, puesto que las declaraciones pueden contener inicializadores, también deben ser consideradas como "ejecutable" (lo que hemos denominado algoritmo). AplicaciónComprende ejecutables y datos. Puede haber múltiples ficheros de ambos tipos (ficheros de datos y ejecutables).Programa Parte de una aplicación (código) que puede cargarse y ejecutarse independientemente. Fichero fuente: Se llaman así (abreviadamente) los ficheros que contienen el código fuente (ficheros .C / .CPP) escrito por el programador. Un "fuente" se compila de una vez, cuando recibe la acción del preprocesador, dando lugar a lo que técnicamente se denomina unidad de compilación. Un solo fuente puede ser dividido en múltiples ficheros, cada uno de los cuales puede contener varias funciones, aunque la inversa no es cierta: una función no puede ser dividida entre varios fuentes. La mayoría de las aplicaciones de cierto porte ocupan más de un fuente. Los diversos ficheros son creados y mantenidos por distintos programadores. Después, los ficheros son compilados y enlazados para producir una aplicación final. Es conveniente recordar que C y C++ se desarrollaron en ambientes UNIX, por lo que desde su cuna son lenguajes sensibles a las mayúsculas/minúsculas ("case sensitive") [3]. Esto no representa inconveniente para los programadores acostumbrados a entornos Unix/Linux, pero suele ser fuente de errores para los que han desarrollado en Sistemas MS-DOS y Windows donde esta distinción no es tan importante. Por ejemplo, en C++ la declaración int X, x; declara dos variables distintas.Función:Una parte de un programa (subrutina) con un nombre, que puede ser invocada (llamada a ejecución) desde otras partes tantas veces como se desee. Opcionalmente puede recibir valores (argumentos); se ejecuta y puede devolver un valormain es la primera función en cualquier programa C++; es llamada desde unas rutinas especiales "de inicio" que se incluyen automáticamente en todo programa C++. Esta función es el punto de inicio del programa desde el punto de vista del programador (donde este toma el control). BloqueLista, que puede estar vacía, de sentencias delimitadas por corchetes { }. Desde el punto de vista sintáctico, un bloque puede ser considerado como una sola sentencia (sentencia compuesta 4.10). Dentro de las posibilidades de memoria, los bloques pueden ser anidados a cualquier nivel (los bloques pueden contener otros bloques). El aspecto de los bloques "anidados" es como sigue:... // espacio global del fichero main { // comienzo del bloque main .... // espacio del bloque main { // bloque anidado ... // espacio del bloque anidado } // fin de bloque .... } // fin del bloque main SentenciaSi establecemos una analogía entre un lenguaje natural y un lenguaje computacional como C++, podemos afirmar que las sentencias ("Statements") juegan en C++ el mismo papel que las oraciones en el lenguaje natural, y del mismo modo que una oración gramatical es una palabra o conjunto de ellas, con que se expresa un sentido gramatical completo, las sentencias se componen de una o varias expresiones y tienen sentido computacional completo. La sentencia es la unidad lógica completa más simple en un programa; en C/C++ terminan en punto y coma ;. Un caso especial es la expresión nula ( ; aislado). En el apartado se describe su sintaxis y en el capítulo 4.10 se ofrece su definición formal y una clasificación de los distintos tipos que existen en C++. Un caso especial lo componen las directivas de preprocesado, que suponen transformaciones en el fuente por parte del preprocesadorExpresiónSiguiendo en sentido ascendente de simplicidad en el lenguaje natural, después de las oraciones están las frases, Conjunto de palabras que basta para formar sentido, especialmente cuando no llega a constituir una oración cabal. Su equivalente en el lenguaje C++ serán las expresiones.Las expresiones son secuencias de tokens (operadores, operandos y elementos de puntuación) que especifican una computación; tienen sentido computacional en sí mismas. Son los bloques de computación más simples con los que se construye un programa aunque no pueden ejecutarse separadamente sino cuando forman una sentencia. Como verá el lector, la diferencia entre sentencia y expresión es algo arbitraria. Una o varias expresiones terminadas en punto y coma constituyen una sentencia. Desde el punto de vista lógico, cada sentencia se ejecuta de una vez (aunque sus expresiones sean evaluadas individualmente siguiendo ciertas reglas). En el programa suele estar muy claro cual es el orden de ejecución de sus sentencias, no así de sus expresiones dentro de ellas, toda vez que el Estándar es permisivo en algunos aspectos de detalle. Es importante señalar que, en contra de lo que ocurre en otros lenguajes, en C/C++, el final de línea no significa necesariamente el fin de la expresión, de forma que esta puede ocupar más de una línea (en realidad el compilador ignora los pares de caracteres CR/LF que añaden los editores al final de línea). Por ejemplo: la expresión int x = 5*(4+(3/2-1)) puede ser escrita como: int x = 5* (4+(3/2-1) ); Los conocedores de otros lenguajes advertirán que en C++ no tiene sentido la barra inclinadas \ con que otros lenguajes indican que la siguiente línea de código es en realidad una continuación de la anterior. Se exceptúa naturalmente el caso de constantes de cadena, donde si es preciso indicar al compilador que, en su caso, la cadena continúa en la línea siguiente. Ejemplo, aunque es correcto escribir: int x = 5; En cambio es incorrecto poner char* string = "Las constantes de cadena pueden tener cualquier longitud"; En este caso es necesario indicar al compilador que la cadena continúa en la línea siguiente: char* string = "Las constantes de cadena pueden tener \cualquier longitud"; Del mismo modo que los gramáticos distinguen varios tipos de frases (hecha, musical, proverbial, etc), los informáticos distinguen también varios tipos de expresiones. Los ejemplos que siguen son meramente ilustrativos y no pretenden ser una relación completa:
int x; // no produce ningún valor x = 2; // produce un valor (resultado) Además de producir un valor, las expresiones pueden tener efectos laterales (tanto si producen un valor como si no lo producen). Ejemplo:x = ++a; Además de producir un valor (un resultado, esta expresión tendría dos efectos laterales:1º: Incrementar en 1 el valor de a, 2º: Asignar el valor modificado de a a la variable x. El "resultado" de la expresión coincide precisamente con el valor de x. Las expresiones se evalúan siguiendo ciertas reglas de conversión, agrupamiento, asociatividad y precedencia. Estas reglas dependen de varios factores: el operador; la naturaleza de los operandos utilizados en cada caso, y de la presencia de paréntesis en la expresión. En el apartado se describe completamente su sintaxis formal así como su precedencia y asociatividad. Su sintaxis muestra que las expresiones son definidas recursivamente, y que las subexpresiones pueden ser anidadas sin ningún límite formal. TokenLos tokens son los elementos en que el preprocesador desmenuza el código fuente. En un lenguaje de programación, los tokens son el equivalentes al conjunto de las palabras y signos de puntuación en el lenguaje natural escrito.En el lenguaje C++ estas "palabras" pueden ser de varios tipos: palabras clave, identificadores, constantes, operadores, signos de puntuación (puntuadores) y comentarios (son eliminados). Los tokens están separados por elementos de separación que reciben el nombre genérico de separadores ("Whitespaces"). 4.4 Objetos compuestos Los objetos compuestos, tal como sucede con los objetos simples, han de crearse en la RAM mediante la instrucción de instanciación. Significa que debe conocerse la existencia de un modelo para tal tipo de objetos. En el argot se dice que debe estar ya programada su clase, es decir que alguien ya debe haber programado una descripción detallada del modelo o clase de objetos donde se definen todos los miembros que tendrán los objetos que se construyan con ella. Los objetos entonces tendrán exactamente la composición y los comportamientos definidos en la clase utilizada para definirlos. Por ejemplo, si ya existe definida una clase de objetos llamada Móvil, podrían crearse los siguientes dos objetos que denominamos robot y alvaro 4.5 Recursividad La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una función desde la misma función. Como ejemplo útil se puede presentar el cálculo de números factoriales. Él factorial de 0 es, por definición, 1. Los factoriales de números mayores se calculan mediante la multiplicación de 1 * 2 * …, incrementando el número de 1 en 1 hasta llegar al número para el que se está calculando el factorial. 4.6Juegos mini-max Se poseen 2 jugadores: MAX y MIN, primero jugará MAX y así seguirá el flujo hasta acabar el juego. Existe un árbol de juegos que los programas utilizan para calcular los Movimientos Legales (Permitidos). El valor MINIMAX será un valor que determine el estado final del juego (En le ajedrez: −1, 0, 1; que son triunfo, derrota o empate). En algunos juegos este valor MINIMAX puede ser muy alto (Como en el Backgamon, se estima algo de −192 a 192 valores). Incluso el TicTacToe (3 en Raya), es complejo para armar el árbol de juegos. A los niveles del árbol se les llama capas. Para determinar la estrategia óptima a seguir se usan valores MINIMAX. MAX adoptará el valor máximo y MIN el mínimo. La decisión MINIMAX supone que los 2 jugadores son óptimos, si uno es un novato será fácilmente derrotado por esta decisión. El Algoritmo MINIMAX es la forma computacional en la que se calcula el valor MINIMAX de cada estado |
4.7 Poda alfa-beta es una técnica de búsqueda que reduce el número de nodos evaluados en un árbol de juego por el algoritmo Minimax. Se trata de una técnica muy utilizada en programas de juegos entre adversarios como el ajedrez, el tres en raya o el Go . A continuación se presenta un ejemplo de aplicación del algoritmo para el árbol de la figura. En ella los nodos podados al aplicar el algoritmo se presentan sombreados en gris. Comenzamos con la búsqueda de primero en profundidad. El padre de los nodos hoja más a la izquierda, etiquetados con 5 y 6 respectivamente, deberá escoger un valor β al tratarse de un nivel MIN, esto implica que deberá escoger el valor mínimo entre dichos nodos, es decir 5. siguiendo el desarrollo, se expandirán el resto de sucesores del padre. En este caso se expande el camino que conduce a los nodos hoja 7 y, buscando un valor β menor, el nodo etiquetado con 4. En este momento el valor momentáneo de β en ese nivel es 4 (el mínimo entre 7 y 4). Esto implica que en este momento en el nivel superior, el padre del nodo que etiquetamos anteriormente con β igual a 5, y de este β igual a 4 momentáneo, debe decidir el mejor valor, el más alto al encontrarse en un nivel MAX), si siguiéramos expandiendo hijos del nodo MIN padre de 7 y 4, sólo podríamos conseguir valores menores a 4, lo que seguiría implicando una elección de la jugada izquierda en el nivel MAX, por lo tanto, podemos podar el resto de hijos, tal y como se muestra en la Figura. El resto del desarrollo del árbol se seguiría utilizando los criterios mencionados con anterioridad.  La figura muestra un ejemplo de la poda alfa-beta. Cada nivel representa la jugada de los jugadores MAX y MIN, que tendrán que definir un valor α o β respectivamente. |
miércoles, 30 de marzo de 2011
UNIDAD 4:INTRODUCCION A LA PROGRAMACION LOGICA
domingo, 27 de marzo de 2011
Suscribirse a:
Entradas (Atom)