El problema de la igualdad de los bordes de los árboles binarios (sameFringe)

PorJosé A. Alonso

Dos árboles binarios tienen iguales los bordes si tienen exactamente
las mismas hojas leídas de izquierda a derecha, independientemente de
nodos interiores. Por ejemplo,

Los bordes de los árboles 1 y 2 son iguales, aunque tiene distintas
estructuras internas. El árbol 3 no tiene el mismo borde que el 1 o
el 2, debido al nodo 4. El árbol 4 tampoco tiene el mismo borde que
el 1 debido al orden en que se leen las hojas.

El problema de la igualdad de los bordes de los árboles binarios
(samefringe, en inglés) consiste en decidir si dos árboles tienen los bordes iguales.
Read More “El problema de la igualdad de los bordes de los árboles binarios (sameFringe)”

La función de Ackermann como prueba de rendimiento

PorJosé A. Alonso

En la entrada la función de Takeuchi como banco de prueba para la eficiencia usé la función de Takeuchi para comparar la eficiencia de Haskell (GHC) y Lisp (Clisp y LispWorks). En esta voy a hacer lo mismo con la función de Ackermann.

La función de Ackermann (también llamada función de Ackermann-Péter) es un ejemplo sencillo de función recursiva que no es primitiva recursiva. Definida en 1926 por Wilhelm Ackermann, pero se presenta frecuentemente en la forma propuesta por Rózsa Péter, que es la siguiente
<br /> A(m,n) =<br /> \left\{<br /> \begin{array}{ll}<br /> n+1, & \mbox{si\ } m=0, \\<br /> A(m-1,1), & \mbox{si\ } m>0 \mbox{\ y\ } n=0 \\<br /> A(m-1,A(m,n-1)), & \mbox{si\ } m>0 \mbox{\ y\ } n>0<br /> \end{array}<br /> \right.<br />
Read More “La función de Ackermann como prueba de rendimiento”

TAK como prueba de rendimiento

PorJosé A. Alonso

A partir del artículo La función de Takeuchi como banco de prueba para la eficiencia y sus comentarios he estado investigando sobre su uso. En este artículo resumo el resultado de las indagaciones.

La función de Takeuchi se utiliza en la prueba TAK cuyo creador es Richard P. Gabriel según afirma en su libro Performance and evaluation of LISP systems (MIT Press, 1985). En las páginas 81-91 de su libro describe la prueba TAK. En concreto,  indica su objetivo (p. 81)
Read More “TAK como prueba de rendimiento”