UNIVERSIDAD DE LOS ANDES
COORDINACION GENERAL DE ESTUDIOS INTERACTIVOS A DISTANCIA
MERIDA - VENEZUELA
Curso de Lógica y Matemática
Postgrado en Modelado y Simulación de Sistemas
MANUAL de PROLOG - BRATKO
EJECUCIÓN DE ARRIBA HACIA ABAJO (Top Down) VS. EJECUCIÓN DE ABAJO HACIA ARRIBA (Bottom Up)
En el capítulo anterior, estudiamos la recursión, un poderoso método para resolver problemas usando la descomposición a problemas más pequeños del mismo tipo. La recursión en PROLOG usa el método de ejecución de arriba hacia abajo (top down) típicamente.
EJECUCIÓN DE ARRIBA HACIA ABAJO (Top Down)
El cálculo de arriba hacia abajo (Top Down), típicamente usado en PROLOG, comienza con el problema original y lo descompone en problemas más y más simples hasta alcanzar un problema trivial, es decir, el hecho en la base de datos PROLOG es alcanzado. Entonces, la solución de los problemas más grandes está compuesta de las soluciones de los problemas más simples, etc. Hasta que la solución del problema original es obtenida. Los siguientes dos ejemplos presentan programas que usan el cálculo de arriba hacia abajo (Top Down).
FACTORIAL
Para obtener el factorial de N primero calculamos el factorial de N-1 usando el mismo procedimiento (recursión) y entonces, usando el resultado del subproblema, calculamos el factorial de N. La recursión para cuando un problema trivial es alcanzado, es decir, cuando el factorial de 0 es alcanzado, es decir, cuando el factorial de 0 es computado.
fact_td(0,1).
fact_td(N,F) :- N>0, N1 is N-1, fact_td(N1,F1), F is N*F1.
Notar, que la complejidad de procedimiento de arriba es lineal, es decir, necesitamos N+1 llamadas del procedimiento fact_td.
FIBONACCI
El siguiente programa calcula los números de Fibonacci usando el método de arriba hacia abajo (Top Down), es decir, si estamos buscando el número de Fibonacci de N>1, primero calculamos los números de Fibonacci de N-1 y N-2 (usando el mismo procedimiento) y, entonces, componemos el número de Fibonacci de N partiendo de los subresultados. En este caso, la recursión para tan pronto como el número de Fibonacci de 0 o 1 es computado.
fibo_td(0,0).
fibo_td(1,1).
fibo_td(N,F) :-
N>1, N1 is N-1, N2 is N-2,
fibo_td(N1,F1), fibo_td(N2,F2),
F is F1+F2.
Notar, que el procedimiento de arriba es muy ineficiente si la regla de ejecución de PROLOG estándar es usada porque calculamos la misma cosa muchas veces. Por ejemplo, para calcular F(N-1) necesitamos calcular F(N-2) lo cual también es requerido para calcular F(N) que fue descompuesto en F(N-1) y F(N-2). De hecho, la complejidad del procedimiento de arriba es exponencial eso es "no muy eficiente".
EJECUCIÓN DE ABAJO HACIA ARRIBA (Bottom Up)
Aún si el cálculo de arriba hacia abajo es típica para PROLOG, podemos aún simular el cálculo de abajo hacia arriba (Bottom Up) también sin hacer cambios al interpretador de PROLOG. El cálculo de abajo hacia arriba (Bottom Up) comienza con conocer los hechos y extender el conjunto de verdades conocidas usando reglas, es decir, derivar nuevos hechos de reglas y hechos viejos. Esta extensión continúa hasta que el problema resuelto es presentado en el conjunto computado de hechos. En general, el método de abajo hacia arriba (Bottom Up) puro es menos eficiente que el método de arriba hacia abajo (top down)porque muchos hechos son derivados y no tienen nada en común con el problema original. Por lo tanto, PROLOG usa la evaluación de arriba hacia abajo (top down) como un método estándar de ejecución. Sin embargo, en los mismos casos, es posible guiar la evaluación de abajo hacia arriba (Bottom Up) hacia la solución del problema original. Los siguientes dos ejemplos presentan versiones de abajo hacia arriba (Bottom Up) de los dos procedimientos de arriba para calcular factorial y números de Fibonacci. La ventaja de la evaluación de abajo hacia arriba (Bottom Up) es visible principalmente en el procedimiento fibo_bu que es más rápido que fibo_td.
FACTORIAL
Ahora, calculamos el factorial usando el método de abajo hacia arriba (Bottom Up) comenzando con el problema trivial de calcular el factorial de 0 y continuar con el factorial de 1,2 y así sucesivamente hasta que el factorial de N es conocido. Ya que no queremos cambiar la conducta estándar de PROLOG, que es por naturaleza top down, necesitamos simular el cálculo de abajo hacia arriba (Bottom Up), es decir, tenemos que almacenar los hechos calculados usando parámetros adicionales. En este caso, recordamos sólo el último "hecho" calculado a saber el factorial de M en el paso M-th.
fact_bu(N,F) :- fact_bu1(0,1,N,F).
fact_bu1(N,F,N,F).
fact_bu1(N1,F1,N,F) :-
N1<N, N2 is N1+1, F2 is N2*F1, fact_bu1(N2,F2,N,F).
Notar, que la complejidad del procedimiento de arriba es lineal otra vez, es decir, necesitamos N+1 llamadas del procedimiento fact_bu1. Sin embargo, el procedimiento fact_bu1 es más eficiente que fact_td porque puede ser traducido usando iteración, es decir, sin una pila la cual es requerida para la recursión en fact_td.
FIBONACCI
Podemos usar el mismo principio como en " factorial bottom-up" para calcular los números Fibonacci usando el método de abajo hacia arriba (Bottom Up). Ahora, necesitamos recordar los últimos dos números de Fibonacci para ser capaz de calcular el próximo número de Fibonacci.
fibo_bu(N,F) :- fibo_bu1(0,0,1,N,F).
fibo_bu1(N,F,_,N,F)
fibo_bu1(N1,F1,F2,N,F) :-
N1<N, N2 is N1+1, F3 is F1+F2,
fibo_bu1(N2,F2,F3,N,F).
Notar, que la complejidad de fibo_bu es lineal y por lo tanto el procedimiento fibo_bu es más eficiente que fibo_td el cual es exponencial.
-
El número
de Fibonacci de 0 es F(0)=0
El número de Fibonacci de 1 es F(1)=1
El número de Fibonacci de N>1 es F(N)=F(N-1)+F(N-2)