Maxima – Página 4

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

PorJosé A. Alonso 29 agosto 20108 marzo 2013

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,

   árbol1          árbol2       árbol3     árbol4 
      o              o           o	        o    
     / \            / \         / \	       / \   
    1   o          o   3       o   3	      o   1  
       / \        / \         / \	     / \     
      2   3      1   2       1   4	    2   3

árbol1 árbol2 árbol3 árbol4

o o o o

/ \ / \ / \ / \

1 o o 3 o 3 o 1

/ \ / \ / \ / \

2 3 1 2 1 4 2 3

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)”

Relación entre el número e y los números primos en Maxima

PorJosé A. Alonso 26 agosto 20108 marzo 2013

En el artículo anterior comenté la relación entre los números primos y el número $e$ expresada mediante la fórmula

$e = \displaystyle\lim_{n \to{+}\infty}\displaystyle\sqrt[p_n]{\displaystyle\prod_{i=1}^n p_i}$

donde $p_i$ es el $i$ -ésimo número primo. Así mismo mostré un ejercicio en Haskell para comprobarla.

En el artículo de hoy presento un ejercicio para comprobar la fórmula anterior en Maxima, pensado para el curso de Informática (del Grado de Matemáticas) y el libro Introducción al cálculo simbólico con Maxima.

El ejercicio es el siguiente

Ventajas de la pereza en el problema de los k menores elementos

PorJosé A. Alonso 24 agosto 20108 marzo 2013

Una característica singular de Haskell es su carácter perezoso, frente al impaciente de la mayoría de los restantes lenguajes.

Los lenguajes perezosos usan evaluación perezosa; es decir, al evaluar una expresión evalúan sus argumentos sólo cuando los necesita. De manera opuesta, en la evaluación impaciente los argumentos de las expresiones se evalúan antes que las expresiones.

En esta entrada presento un ejercicio para Informática (del Grado de Matemáticas) con objeto de resaltar la ventaja de la evaluación perezosa de Haskell frente a la evaluación impaciente de Maxima. Para ello compararé sus rendimientos al calcular los k primeros elementos de una lista con definiciones semejantes en Haskell y Maxima.
Read More “Ventajas de la pereza en el problema de los k menores elementos”

La función de Takeuchi como banco de prueba para la eficiencia

PorJosé A. Alonso 11 agosto 20109 abril 2014

La función de Takeuchi está definida por
$tak(x,y,z) = \newline \left\{ \begin{array}{ll} y, & si \ x \leq y \\ tak(tak(x-1,y,z), tak(y-1,z,x), tak(z-1,x,y)) & en\ caso\ contrario \end{array} \right.$

En este artículo voy a comparar la la eficiencia de Haskell, Maxima y Lisp escribiendo en los tres la definición recursiva de la función de Takeuchi y calculando $tak(16,6,1)$ .
Read More “La función de Takeuchi como banco de prueba para la eficiencia”

Cruce de listas

PorJosé A. Alonso 5 agosto 20108 marzo 2013

En esta entrada comento las soluciones en Haskell y Maxima de un problema planteado por Adam Majewski en la lista de Maxima en forma de ejercicio para I1M y PD. Además, añadiré soluciones en otros lenguajes conforme las vaya recibiendo.

1. Solución en Haskell

En este ejercico se usarán las siguientes librerías

import Data.List
import Test.QuickCheck

1 2	import Data.List import Test.QuickCheck

Ejercicio 1. Definir la función

cruce :: Eq a => [a] -> [a] -> [[a]]

1	cruce :: Eq a => [a] -> [a] -> [[a]]

tal que (cruce xs ys) es la lista de las listas obtenidas con uniendo las listas de xs sin un elemento con las de ys sin un elemento. Por ejemplo,

*Main> cruce [1,5,3] [2,4]
[[5,3,4],[5,3,2],[1,3,4],[1,3,2],[1,5,4],[1,5,2]]
*Main> cruce [1,5,3] [2,4,6]
[[5,3,4,6],[5,3,2,6],[5,3,2,4],[1,3,4,6],[1,3,2,6],
 [1,3,2,4],[1,5,4,6],[1,5,2,6],[1,5,2,4]]

*Main> cruce [1,5,3] [2,4]

[[5,3,4],[5,3,2],[1,3,4],[1,3,2],[1,5,4],[1,5,2]]

*Main> cruce [1,5,3] [2,4,6]

[[5,3,4,6],[5,3,2,6],[5,3,2,4],[1,3,4,6],[1,3,2,6],

[1,3,2,4],[1,5,4,6],[1,5,2,6],[1,5,2,4]]