4.1 Introducción al modelo de 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.

Arboles Binarios

Arboles Binarios

Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos, y tablas de contenidos. Veremos los recorridos que se pueden hacer en los árboles binarios, también se va a ampliar sobre árboles en los lenguajes de programación funcional. Introducción 

 * Recorrido en amplitud. * Es aquel recorrido que recorre el árbol por niveles del nivel superior a los niveles inferiores, en el ejemplo sería: Recorridos de árbol binario 

* Recorrido en profundidad. * Existen 3: Preorden, Postorden, Inorden. Recorridos 

* Recorrer un árbol en preorden consiste en primer lugar, examinar el dato del nodo raíz, posteriormente se recorre el subárbol izquierdo en preorden y finalmente se recorre el subárbol derecho en preorden. Recorrido Preorden 

 * Recorrer un árbol en Postorden consiste en primer lugar en recorrer el subárbol izquierdo en Postorden, luego se recorre el subárbol derecho en Postorden y finalmente se visita el nodo raíz. Recorrido Postorden 

 * Recorrer un árbol en Inorden consiste en primer lugar en recorrer el subárbol izquierdo en Inorden, luego se examina el dato del nodo raíz, y finalmente se recorre el subárbol derecho en Inorden. Recorrido Inorden 

* Los ordenamientos más importantes son llamados: pre-orden, post-orden e Inorden. Si un árbol T es nulo, entonces, la lista vacía es el listado: pre-orden, post- orden e Inorden del árbol T. Si T consiste de un solo nodo n, entonces, n es el listado: pre-orden, post- orden e Inorden del árbol T. Recorridos en Lenguajes de Programación funcional 

* Los algoritmos de recorrido de un árbol binario presentan tres tipos de actividades comunes: *. Visitar el nodo raíz *. Recorrer el subárbol izquierdo *. Recorrer el subárbol derecho Recorridos en Lenguajes de Programación funcional 

·         Recorrido Preorden. 
·         Recorrido Inorden. 
·         Recorrido Postorden. 

Arboles generales

Un árbol es una estructura no lineal a cíclica utilizada para organizar información de forma eficiente.

La definición es recursiva:

Un ´árbol es una colección de valores {v1, v2,. . . vn} tales que ¦

* Si n = 0 el ´árbol se dice vacío. ¦ En otro caso, existe un valor destacado que se denomina raíz (p.e. v1), y los demás elementos forman parte de colecciones disjuntas que a su vez son ´arboles. Estos ´árboles se llaman subárboles de la raíz.

Las estructuras tipo ´árbol se usan principalmente para representar datos con una relación jerárquica entre sus elementos, como ´arboles genealógicos, tablas, etc. X

La terminología de los ´árboles se realiza con las típicas notaciones de las relaciones familiares en los ´arboles genealógicos: padre, hijo, hermano, ascendente, descendente, etc.

Algunas definiciones

Nodo, son los elementos del ´árbol.

 Raíz del ´árbol: todos los ´árboles que no están vacíos tienen un ´único nodo raíz. Todos los demás elementos o nodos se derivan o descienden de ´el.

Nodo hoja es aquel nodo que no contiene ningún subárbol.

Tamaño de un ´árbol es su número de nodos.

A cada nodo que no es hoja se le asocia uno o varios subárboles llamados descendientes o hijos. X De igual forma, cada nodo tiene asociado un antecesor o ascendiente llamado padre.

Todos los nodos tienen un solo padre excepto la raíz que no tiene padre.

Cada nodo tiene asociado un número de nivel que se determina por la longitud del camino desde la raíz al nodo específico.

La altura o profundidad de un ´árbol es el nivel más profundo más uno.

Examen

Programa-Funciones

2.3. 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

2.2 Funciones

En programación, una función es una sección de un programa que calcula un valor de manera independiente al resto del programa.

Una función tiene tres componentes importantes:

Los  parámetros, que son los valores que recibe la función como entrada.
El  código de la función, que son las operaciones que hace la función.
El  resultado (o valor de retorno), que es el valor final que entrega la función.
En esencia, una función es un mini-programa. Sus tres componentes son análogos a la entrada, el proceso y la salida de un programa.

EJEMPLO

Haskell utiliza evaluación perezosa o mediante paso de parámetros por nombre usando punteros para compartir valores de expresiones.

cuadrado x = x * x unos = 1: unos

cuadrado (2+1) ==> [def. cuadrado]

x*x siendo x = (2+1) ==> [def. (+)]

x*x siendo x = 3 ==> [sustitución]

3*3 ==> [def. (*)]

9

head unos ==> [def. unos]

head (1:unos) ==> [def. head]

Las declaraciones de funciones generalmente son especificadas por: 

Un nombre único en el ámbito: Nombre de la función con el que se identifica y se distingue de otras. No podrá haber otra función ni procedimiento con ese nombre (salvo sobrecarga o polimorfismo en programación orientada a objetos).

Un tipo de dato de retorno: tipo de dato del valor que la función devolverá al terminar su ejecución.
Una lista de parámetros: Especificación del conjunto de argumentos (pueden ser cero, uno o más) que la función debe recibir para realizar su tarea.
El código u órdenes de procesamiento: conjunto de órdenes y sentencias que debe ejecutar la función.

Un problema complejo se puede dividir en pequeños subproblemas más sencillos. Estos subproblemas se conocen como “Módulos” y su complementación en un lenguaje se llama subprograma (procedimientos y funciones).

Un subprograma realiza las mismas acciones que un programa, sin embargo, un subprograma lo utiliza solamente un programa para un propósito específico.

Un subprograma recibe datos de un programa y le devuelve resultados (el programa “llama” o “invoca” al subprograma, este ejecuta una tarea específica y devuelve el “control” al programa que lo llamo).

Función: Una función en matemáticas, es una operación que toma un o más valores (argumentos) y devuelve un resultado (valor de la función para los argumentos dados).

Por ejemplo:

F(X) = X / (1+X2)

Donde:

F………….. Nombre de la función

X…………. Es el argumento (también conocido como parámetro formal)

Definición de funciones: Una definición de función se presenta de la siguiente manera:

Función nombre_funcion (p1, p2,…, pn)

Inicio

Bloque de instrucciones

Fin

Donde:

Función …………… Es la palabra clave que nos indica una definición de función.

Nombre_funcion ….. Es el identificador con el cual se reconoce a la función en el cuerpo del algoritmo principal.

P1,p2,…,pn ……… Es el grupo de parámetros que define a la función.

Llamado a una función

Cuando definimos una función solo le indicamos al algoritmo que esta función existe, pero una definición de función no implica la realización de las instrucciones que la constituyen. Para hacer uso de una función, el algoritmo principal la debe llamar.

Por ejemplo:

Función F(X)

Inicio

F = X /(1 + X^2)

Fin

Inicio

Imprimir “Este es el algoritmo principal”

Leer N

R = F(N) llamado de la función

Imprimir “El resultado de la función es:”, R

Fin

Un problema complejo se puede dividir en pequeños subproblemas más sencillos. Estos subproblemas se conocen como “Módulos” y su complementación en un lenguaje se llama subprograma (procedimientos y funciones).

Un subprograma realiza las mismas acciones que un programa, sin embargo, un subprograma lo utiliza solamente un programa para un propósito específico.

Un subprograma recibe datos de un programa y le devuelve resultados (el programa “llama” o “invoca” al subprograma, este ejecuta una tarea específica y devuelve el “control” al programa que lo llamo).

Función: Una función en matemáticas, es una operación que toma un o más valores (argumentos) y devuelve un resultado (valor de la función para los argumentos dados). Por ejemplo:

F(X) = X / (1+X2)

Donde:

F………….. Nombre de la función

X…………. Es el argumento (también conocido como parámetro formal)

Definición de funciones: Una definición de función se presenta de la siguiente manera:

Función nombre_funcion (p1, p2,…, pn)

Inicio

Bloque de instrucciones

Fin

Donde:

Función…………… Es la palabra clave que nos indica una definición de función.

Nombre_funcion…. Es el identificador con el cual se reconoce a la función en el cuerpo del

Algoritmo principal.

P1, p2,…, pn……… Es el grupo de parámetros que define a la función.

Llamado a una función

Cuando definimos una función solo le indicamos al algoritmo que esta función existe, pero una definición de función no implica la realización de las instrucciones que la constituyen. Para hacer uso de una función, el algoritmo principal la debe llamar. Por ejemplo:

Función F(X)

Inicio

F = X / (1 + X^2)

Fin

Inicio

Imprimir “Este es el algoritmo principal”

Leer N

R = F(N) llamado de la función

Imprimir “El resultado de la función es:”, R

Fin

2.1. El tipo de datos

En lenguajes de programación un tipo de dato es un atributo de una parte de los datos que indica al ordenador (y/o al programador) algo sobre la clase de datos sobre los que se va a procesar.

En un sentido amplio, un tipo de datos define un conjunto de valores y las operaciones sobre estos valores. Casi todos los lenguajes de programación explícitamente incluyen la notación del tipo de datos, aunque lenguajes diferentes pueden usar terminología diferente. La mayor parte de los lenguajes de programación permiten al programador definir tipos de datos adicionales, normalmente combinando múltiples elementos de otros tipos y definiendo las operaciones del nuevo tipo de dato. Por ejemplo, un programador puede crear un nuevo tipo de dato llamado "Persona" que especifica que el dato interpretado como Persona incluirá un nombre y una fecha de nacimiento.

Un tipo de dato entero en computación es un tipo de dato que puede representar un subconjunto finito de los números enteros. El número mayor que puede representar depende del tamaño del espacio usado por el dato y la posibilidad (o no) de representar números negativos. Los tipos de dato entero disponibles y su tamaño dependen del lenguaje de programación usado así como la arquitectura en cuestión. Por ejemplo, si para almacenar un número entero disponemos de 4 bytes de memoria tememos que: 4 Bytes = 4x8 = 32 bits Con 32 bits se pueden representar 232=4294967296 valores: Sólo positivos: del 0 al 4294967295 Positivos y negativos: del -2147483648 al 2147483647

Tipos de datos en coma flotante Se usan para representar números con partes fraccionarias. Hay dos tipos de coma flotante: float y double. El primero reserva almacenamiento para un número de precisión simple de 4 bytes y el segundo lo hace para un numero de precisión doble de 8 bytes.Tipo:float4 Bytes (32 bits) double8 Bytes (64 bits)

Tipo de dato carácter (Char) Es cualquier signo tipográfico, puede ser una letra, un número, un signo de puntuación o un espacio. Este término se usa mucho en computación. Un valor de tipo carácter es cualquier carácter que se encuentre dentro del conjunto ASCII ampliado, el cual está formado por los 128 caracteres del ASCII más los 128 caracteres especiales que presenta, en este caso, IBM.

Los valores ordinales del código ASCII ampliado se encuentran en el rango de 0 a 255. Dichos valores pueden representarse escribiendo el carácter correspondiente encerrado entre comillas simples (apóstrofos).Así, podemos escribir: ‘A' < 'a ‘Que significa: "El valor ordinal de A es menor que el de a" o "A está antes que a “Un valor de tipo carácter (char en inglés) se guarda en un byte de memoria. La única operación (además de las relacionales) que podemos hacer con caracteres es la concatenación concatenando dos caracteres, por ejemplo 'a' y 'X' obtendríamos la cadena "aX".

Tipo de dato lógico El tipo de dato lógico o booleano es en computación aquel que puede representar valores de lógica binaria, esto es, valores que representen falso o verdadero. Se utiliza normalmente en  programación, estadística, electrónica, matemáticas (Álgebra booleana), etc...Para generar un dato o valor lógico a partir de otros tipos de datos, típicamente, se emplean los operadores relacionales (u operadores de relación), por ejemplo: 0 es igual a falso y 1 es igual a verdadero (3>2)= 1 = verdadero (7>9)= 0 = falso

Palabra reservada una palabra reservada es una palabra que tiene un significado Gramatical especial para ese lenguaje y no puede ser utilizada como un identificador en ese lenguaje.

Por ejemplo, en SQL, un usuario no puede ser llamado "group", porque la palabra group es usada para indicar que un identificador se refiere a un grupo, no a un usuario. Al tratarse de una palabra clave su uso queda restringido. Ocasionalmente la especificación de un lenguaje de programación puede tener palabras reservadas que están previstas para un posible uso en futuras versiones. En Java const y goto son palabras reservadas — no tienen significado en Java, pero tampoco pueden ser usadas como identificadores. Al reservar los términos pueden ser implementados en futuras versiones de Java, si se desea, sin que el código fuente más antiguo escrito en Java deje de funcionar.