Introducción al modelo de programación lógica

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

Sócrates es mortal ; consulta

4.2 Semántica de los programas lógicos

El orden en que aparecen los literales dentro de una sentencia (dentro del cuerpo) o el orden en que se introducen las sentencias en el programa son importantes en PROLOG. El orden afecta tanto al correcto funcionamiento del programa, como al recorrido del árbol de llamadas, determinando, entre otras cosas, el orden en que PROLOG devuelve las soluciones a una pregunta dada.

Está definida por el proceso de inferencia utilizado para probar que un objetivo puede ser derivado del programa.

Una clausula es una disyunción finita de cero o más literales.

Una literal es un átomo o la negación de un átomo. Una literal positiva es un átomo. Una literal negativa es la negación de un átomo.

Cada línea -- sentencia -- de un programa Prolog se denomina cláusula. Las cláusulas son los hechos, reglas y consultas.

La semántica da significado a los programas y nos permite describir formalmente lo que calculan. Hay tres maneras bien conocidas de dar significado o semántica a los programas lógicos: la semántica declarativa, la semántica operacional y la semántica.

 

Representación del conocimiento es un término para referirse a representaciones pensadas para el procesamiento por ordenadores modernos, en particular, para representaciones compuestas por objetos explícitos y de afirmaciones sobre ellos.

Representar el conocimiento mediante cláusulas permite a los ordenadores sacar conclusiones de conocimiento previamente almacenados.

Esta semántica asigna significado a un programa asociándola una función sobre el dominio calculado por el programa. El significado viene dado entonces por el punto fijo de la función, si existe.

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 que tan buena es la solución para el problema.

4.4 consulta de base de clausulas.

4.5 Espacios de búsqueda.

4.6 Programación lógica con números, listas y arboles

La programación funcional se basa en el concepto de función (que no es más que una evolución de los predicados), de corte más matemático. La programación lógica gira en torno al concepto de predicado, o relación entre elementos.

Desde el punto de vista lógico, un programa P puede verse como una teoría lógica formada por las cláusulas del programa. Los modelos de Herbrand de esta teoría son considerados los modelos del programa P.

4.7 control de búsqueda en programas lógicos

4.8 Manipulación de términos

En PROLOG los objetos numéricos pueden corresponder a tipos integer o float de C. Para realizar operaciones numéricas, se tiene el predicado is, que se comporta como una asignación en un lenguaje imperativo. Así, el objetivo X is <expresión> será verdadero cuando X unifique con el resultado numérico de evaluar <expresión>.

Listas

La representación de hechos simples no es lo común en la clasificación de elementos, sino que se agrupan los elementos de un mismo tipo en una lista.

Las listas son colecciones de elementos en PROLOG. Una lista se divide en dos partes:

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

4.9 predicados mitológicos.

ARBOLES BINARIOS

Introducción

En general los árboles se utilizan para construir árboles genealógicos, pero en informática tienen gran aplicación para la creación de los directorios (carpetas) en los discos de las computadoras, para mostrar las relaciones lógicas entre los registros de una base de datos (colección de registros controlados por una computadora) y las búsquedas en los compiladores de los lenguajes de programación (véase árboles binarios).

 Concepto de árbol

Un árbol T es un grafo simple que cumple que entre los vértices v, wT existe un único camino simple.

Observe que para ir de un vértice cualquiera a otro siempre se tiene un camino simple; por ejemplo, para ir del vértice d al vértice n, basta con recorrer el camino d — z — i — n.

Conceptos básicos de árboles

Vértice. También llamado nodo y, corresponde a cada uno de los elementos del árbol.
Ejemplo 12.1: según la figura 12.1, los vértices son: i, z, n, m, x, c, d, e, w.
Raíz. Es el vértice principal del árbol
Ejemplo 12.2: según la figura 12.1, la raíz es i.
Padre. Es el vértice que puede o no tener ramificaciones (subárboles).
Ejemplo 12.3: según la figura 12.1, z es padre de los nodos x, c, d.
Hijo. Es el vértice descendiente de un vértice raíz o padre.
Ejemplo 12.4: según la figura 12.1, los nodos x, c, d son hijos de z.
Hermanos. Son los vértices descendientes de un mismo vértice padre
Ejemplo 12.5: según la figura 12.1, los nodos x, c, d son hermanos.

Descendiente. Siempre que exista camino para ir de un vértice v a otro w, se dice que, v es descendiente de w.
Ejemplo 12.6: según la figura 12.1, los nodos descendientes de i son entre otros z, x.
Ancestro. Si hay camino para ir de un vértice v a otro vértice w (máximo hasta la raíz) se dice que, w es ancestro de v.
Ejemplo 12.7: según la figura 12.1, los nodos x, c, d son i, z.
Hoja. Es un vértice que no tiene ramificaciones (uno o más hijos). También se llama nodo terminal.
Ejemplo 12.8: según la figura 12.1, los nodos del árbol x, c, d, e w son hojas
Nodo no Terminal. Es aquel que tiene por lo menos una ramificación.
Ejemplo 12.9: según la figura 12.1, los nodos no terminales son: i, z, m, n.
Camino. Es el conjunto de vértices por los que se pasa para ir de un vértice a otro.
Ejemplo 12.10: según la figura 12.1, el camino para ir del nodo x al nodo n es x, z, i, n.
Longitud de un camino. Es el número de vértices por los que se deben pasar o recorrer para ir de un vértice a otro.
Ejemplo 12.11: La longitud del camino para ir del nodo x al nodo n de la figura 12.1 es 4.
Nivel: es la longitud del camino simple de la raíz al vértice. Cada nodo tiene un nivel dentro de un árbol.
Ejemplo 12.12: según la figura 12.1, el nodo raíz i tiene el nivel 0, sus hijos ocupan el nivel 1; sus nietos ocupan el nivel 2 y, así sucesivamente
Altura de un árbol. Es el nivel de la hoja u hojas más distantes de la raíz.
Ejemplo 12.13: según la figura 12.1, la altura del árbol es 2.

 Concepto de árbol binario

Un árbol binario es un tipo de árbol en que cada vértice máximo puede tener dos hijos; su nodo raíz está enlazado a dos subárboles binarios disjuntos denominados subárbol izquierdo y subárbol derecho. Los árboles binarios no son vacíos ya que como mínimo tienen el nodo raíz.

Árbol binario lleno

Es aquel árbol en el que los nodos de cada nivel tienen sus dos hijos o ninguno (si es hoja). Ejemplo 12.15: el árbol de la figura 12.2 es lleno.

 Árbol binario completo

Es aquel árbol binario lleno en que todas sus hojas están en el nivel n o n-1 considerando que para un hijo derecho hay siempre un hijo izquierdo. Estos árboles ocupan todas las posiciones del vector. Por lo tanto, todo árbol binario lleno es completo, pero no la viceversa.

Ejemplo 12.16: el árbol de la figura 12.3 es completo.

Propiedades de los árboles binarios

 Representación de árboles binarios

Los árboles binarios pueden representarse en un vector o en una lista ligada. Nuestro interés se centrará en los vectores.
Para representar a un árbol binario en un vector se escriben por niveles los nodos del árbol de manera ordenada, de izquierda a derecha (hijo izquierdo — hijo derecho).
Esta representación es poco eficiente cuando el árbol no es completo, en vista del gran desperdicio de memoria que podría haber por las posiciones libres que quedarían en el vector.
Si k es la posición en un vector de un nodo de un árbol con n niveles, se tiene:

.El vector tendrá 2n+1 -1 posiciones.

. El padre estará en la posición k/2 (con k>1)

.El hijo izquierdo estará en la posición 2*I (con 2*k<n) y el hijo derecho en la posición 2*k+1.

Ejemplo 12.18: represente en un vector el árbol de la figura 12.4
El árbol de la figura 12.4 representado en un vector queda como sigue:

¿En qué posiciones están: el hijo izquierdo de b, el hijo derecho de c. ¿Cómo podría verificarse que f y e son hojas?

 Recorridos en un árbol binario

Un recorrido en un árbol binario es Una operación que consiste en visitar todos sus vértices o nodos, de tal manera que cada vértice se visite una sola vez.
Se distinguen tres tipos de recorrido: INORDEN, POSORDEN Y PREORDEN.
En cada recorrido se tiene en cuenta la posición de la raíz (de ahí su nombre) y que siempre se debe ejecutar primero el hijo izquierdo y luego el derecho.

Recorrido INORDEN. Este recorrido se realiza así: primero recorre el subárbol izquierdo, segundo visita la raíz y por último, va al subárbol derecho. En síntesis:
hijo izquierdo — raíz — hijo derecho

Recorrido PREORDEN. Este recorrido se realiza así: primero visita la raíz; segundo recorre el subárbol izquierdo y por último va a subárbol derecho. En síntesis:
raíz — hijo izquierdo — hijo derecho

Recorrido POSORDEN. Primero recorre el subárbol izquierdo; segundo, recorre el subárbol derecho y por último, visita la raíz. En síntesis:
hijo izquierdo– hijo derecho — raíz
Ejemplo 12.19: realice los diferentes recorridos sobre árboles de las figuras 12.5a, 12.5b y 12.5c.

 Tipos de árboles binarios

 Árboles de expresión

Son árboles binarios que se utilizan para almacenar en la memoria de una computadora expresiones lógicas, aritméticas o algebraicas. Este proceso lo realizan los compiladores de los lenguajes de programación. Los PC y las calculadoras comunes utilizan el recorrido INORDEN usando la notación infija para evaluar las expresiones, al igual que los seres humanos. El recorrido PREORDEN utiliza la notación infija o polaca.
Algunos compiladores y algunas calculadoras como por ejemplo, la Hewlet Packard evalúan las expresiones en POSORDEN usando la notación posfija (o notación polaca inversa) donde el operador aparece después de sus operandos; por ejemplo, AB/ indican que A debe dividirse por B. Observe que la notación posfija tiene ventajas sobre la notación infija debido a que la notación posfija no necesita paréntesis ni tiene que predeterminar un orden de prioridad para sus operadores (lógicos o aritméticos); es por tal razón que una expresión se evaluará sin ambigüedad.
Para evaluar una expresión con recorrido INORDEN pueden seguirse los siguientes pasos:

1. Trascriba la expresión con recorrido INORDEN a POSORDEN (o a PREORDEN). Para tal fin, debe parentizar completamente la expresión y luego, cambie el paréntesis derecho (o izquierdo) por el operador más próximo no utilizado.
   2. Forme el árbol de expresión con recorrido POSORDEN (o PREORDEN) a partir de la expresión dada. En efecto, el árbol se forma escribiendo como raíz el operador principal de la expresión y se escriben los operandos como subárboles izquierdo y derecho. Observe que las hojas del árbol corresponderán a los operandos.
   3. Evalúe la expresión utilizando el árbol, dándole valores aritméticos o lógicos a los operandos.

Ejemplo 12.20: la representación en un árbol binario de la expresión algebraica

 Árbol binario de búsqueda

Un árbol binario de búsqueda es aquel que tiene sus nodos con un orden definido, de tal manera que los datos del subárbol izquierdo son menores y los del subárbol derecho son mayores. Estos árboles tienen como particularidad la permisión de que se puedan realizar búsquedas de nodos o datos determinados, utilizando el método de búsqueda binaria de manera similar al usado en arreglos.
Para crear un árbol binario de búsqueda a partir un listado de datos, asuma que el primer dato es la raíz del árbol; los demás se ubican en el árbol así: los menores como hijos izquierdos y los mayores como hijos derechos.

Ejemplo 12.21: el grafico del árbol, según la siguiente lista: 43, 10, 8, 54, 15, 50, 53 está en la figura 12.7.

PROBLEMAS RESUELTOS

Distribuya los nodos -5,2,-11,4,-13,5,3,-14,1,6,10,-12,8 en el árbol binario de la figura 12.8 y determine ¿Cuáles son los nodos hoja? ¿Cuáles son nodos de 2 hijos?

Solución: Según la figura 12.9, los nodos hoja son:-14,-12, 1, 3, 8 y los nodos de grado 2 son: -13,-5, 2, 4.

captura código de áreas

Intervalos

INTERVALO

Un intervalo es un espacio métrico comprendido entre dos valores. Los intervalos pueden referirse al intervalo de una variable o al intervalo de un array.

El intervalo de una variable está definido como la diferencia entre el valor más alto y el valor más bajo que esa variable puede guardar.

En el caso de una variable entera, la definición está restringida a números enteros, y el intervalo cubrirá todos los números dentro de su intervalo (incluyendo el máximo y el mínimo).El intervalo de un array son los límites superior e inferior del mismo.

Intervalos

 Funciones devuelven siempre el mismo valor

  Los lenguajes funcionales puros tienen la propiedad de transparencia referencial 

 Como consecuencia, en programación funcional, una función siempre devuelve el mismo valor cuando se le llama con los mismos parámetros 

 Las funciones no modifican ningún estado, no acceden a ninguna variable ni objeto global y modifican su valor Diferencia entre declaración y modificación de variables 

 En programación funcional pura una vez declarada una variable no se puede modificar su valor 

 En algunos lenguajes de programación (como Scala) este concepto se refuerza definiendo la variable como inmutable (con la directiva val). 

 En programación imperativa es habitual modificar el valor de una variable en distintos pasos de ejecución 

ejemplos de como utilizar los intervalos:

Funciones

Funciones de primera clase

Se dice que en un lenguaje las funciones son de primera clase (o que son "objetos de primera clase") cuando se pueden tratar como cualquier otro valor del lenguaje, es decir, cuando se pueden almacenar en variables, pasar como parámetro y devolver desde funciones, sin ningún tratamiento especial. El ejemplo más claro en un lenguaje popular lo encontramos en JavaScript, donde estas operaciones con funciones son muy comunes:

// Asignación a variable
var get_post = function(post_number) {
  return fetch(`https://example.org/posts/${post_number}`)
    // Paso como parámetro
    .then(response => response.json())
    .then(function(data) {
      console.log(data);
    });
};

var custom_exp = function(base) {
  // Valor de retorno
  return function(exponent) {
    return Math.pow(base, exponent);
  };
};

En este ejemplo he usado algunas características modernas de JavaScript: template strings y funciones flecha. Si tienes interés en aprender más tal vez quieras consultar el curso sobre Programacion avanzada en JavaScript y ECMAScript .

Como podemos ver, en JavaScript es natural utilizar funciones como parámetros, valores de retorno y en variables. Esto también es así en otros lenguajes como R o Scala. Muchos otros introducen un tipo de funciones denominadas lambdas (o funciones anónimas), que en ocasiones se comportan de forma distinta a las funciones usuales para permitir esas operaciones. Por ejemplo, en Ruby las lambdas son objetos pero no así el resto de funciones:

def greet who = "Mundo"
  "¡Hola #{who}!"
end

greet2 = -> who { "¡Hola #{who}!" }

greet  # => "¡Hola Mundo!"
greet2 # => #<Proc:... (lambda)>

En el ejemplo anterior, greet no hace referencia a la función sino que la ejecuta, devolviendo el mensaje "¡Hola Mundo!", mientras que greet2 sí nos indica que es un objeto de tipo Proc, el cual se puede pasar como argumento, devolver, etc.

Una aplicación interesante de la propiedad de funciones de primera clase es escribir versiones parcialmente aplicadas de otras funciones. Por ejemplo, supongamos que queremos evaluar la función de densidad de una distribución normal para una media y desviación dadas. Podríamos escribir nuestra función de la siguiente manera:

function gaussian(mean, variance, x) {
  return 1 / Math.sqrt(2 * Math.PI * variance) *
    Math.exp((x - mean)**2 / (-2 * variance));
}

Esta implementación nos impide reutilizar la media y la varianza de la distribución para evaluar en varios puntos sin escribir de nuevo los parámetros. En su lugar, consideremos la siguiente versión:

function gaussian_alt(mean, variance) {
  return function(x) {
    return 1 / Math.sqrt(2 * Math.PI * variance) *
      Math.exp((x - mean)**2 / (-2 * variance));
  };
}

var standard_normal = gaussian_alt(0, 1);
console.log(`N(3 | 0, 1) = ${standard_normal(3)}`);

Ahora podemos reutilizar la standard_normal tanto como queramos. Esto es aplicable a muchas otras situaciones donde conviene que nuestras funciones estén parametrizadas a varios niveles y podamos proporcionar los argumentos poco a poco. En ocasiones, el lenguaje proporciona la funcionalidad necesaria para obtener dichas versiones parcialmente aplicadas sin necesidad de reescribir la función:

// Aplicamos la media y varianza
standard_normal = gaussian.bind(null, 2, 1);
console.log(`N(3 | 0, 1) = ${standard_normal(3)}`);

La sintaxis para la aplicación parcial de funciones suele diferir entre lenguajes: en JavaScript usamos bindcomo en el ejemplo, en C++ está disponible std::bind, en Python functools.partial...

Funciones de orden superior

Cuando una función no recibe otras funciones como parámetro, se la denomina de primer orden. En el caso en el que sí las reciba, se llama de orden superior.

Muchos lenguajes nos proveen con una serie de funciones de orden superior para trabajar con estructuras de datos. De entre ellas, las más conocidas son map y reduce: la primera aplica la misma función sobre cada elemento de una colección, y la segunda acumula los elementos en un único valor según una función dada. Veamos un ejemplo:

const list = [1, 2, 3, 4, 5];

const squared = list.map(x => x ** 2);
// => [1, 4, 9, 16, 25]

const product = list.reduce((acc, item) => acc * item, 1);
// => 120

Es importante notar que map no modifica la colección original sino que devuelve una nueva, esto se verifica también en la mayoría de lenguajes que la proporcionan. También es de uso común una función filter, que seleccione elementos mediante un predicado booleano:

const even = list.filter(x => x % 2 == 0);
// => [2, 4]

Casos interesantes de uso de funciones de orden superior son el módulo Enumerable de Ruby, los métodos de la interfaz Stream de Java y los decoradores de Python.

Una última función de orden superior que resulta muy obvia pero no siempre viene integrada en los lenguajes es la composición de funciones. En JavaScript, por ejemplo, podríamos implementar la composición de dos funciones como sigue:

const comp2 = (f, g) => ((...arg) => g(f(...arg)));
const abs = comp2(x => x * x, Math.sqrt);
abs(-4); // => 4

Para componer más de dos funciones, podemos componerlas dos a dos aprovechando el ejemplo anterior y una variante de la función reduce que acabamos de aprender:

const compose = function(...functions) {
  return functions.reduceRight(comp2);
};

// Las funciones se aplican de derecha a izquierda
const f = compose(Math.floor, Math.log, Math.max)
f(10, 20) // => 2