Gobby

22 noviembre 2007

Gooby es un editor colaborativo en tiempo real. Es decir, es un editor de texto donde varios usuarios pueden editar a la vez un mismo fichero.

Gobby in action

En el trabajo llevamos bastante tiempo usando este editor para redactar documentos de forma ágil entre varias personas y nos viene muy bien para realizar el proyecto de Ingeniería del Software de la carrera entre mi compañero de proyecto y yo.

Esta aplicación es multiplataforma y puede usarse en Linux, Windows y MacOS usando las librerías GTK+.  Además la comunicación va encriptada y se pueden editar varios documentos a la vez.

Los que no la conozcáis probadla y se convertirá en una herramienta indispensable.

:wq

Anuncios

“El examen está temporizado, el hueco de las preguntas está controlado para que no os enrolléis, el que la tenga más grande que yo… que escriba por detrás… la letra, la letra”.

Profesor de Sistemas Operativos.

Da gusto empezar un examen con una carcajada.

:wq

Comienzo PFC

26 agosto 2007

Me ha costado bastante coger el ritmo de trabajo después de volver de vacaciones. He decidido no prepararme la única asignatura que me ha quedado para septiembre este año e intentar ir a clase aunque me pise 1 hora semanal con otra asignatura.

Los motivos que me han llevado a tomar esta decisión han sido que no creía poder afrontar con garantías ese examen y que puedo aprovechar el tiempo hasta el comienzo de las clases para sentar las bases del PFC y tener planificado el trabajo para empezar en serio con el proyecto en el segundo cuatrimestre.

No descarto realizar a partir de ahora algunas entradas del blog en inglés para dar más alcance al PFC.

Espero haber tomado la decisión acertada.

:wq

Algoritmos Voraces

9 agosto 2007

Los algoritmos voraces son algoritmos genéricos que se usan normalmente para intentar resolver problemas de optimización. Esto es, problemas en los que hay que maximizar o minimizar una función objetivo.

Se parte de un número de elementos de entrada y se van seleccionando o descartando formando el conjunto final de seleccionados que cumplen las restricciones del problema inicial.

No se tiene la posibilidad de dar marcha atrás y rehacer la selección. La solución no tiene porque ser óptima siempre.

Podemos utilizar el siguiente esquema para resolver problemas mediante algoritmos voraces:

alg
   inicializa()
   mientras (No fin() )
      seleccionaYElimina()
      si prometedor():
         anotaEnSolucion()
      fsi
   fmientras
fin

Con la función inicializa() pretendemos establecer las variables necesarias para resolver el problema y asociarles un valor. La función fin() establece el final de las iteraciones sobre el conjunto de elementos de entrada. seleccionaYElimina() es la encargada de elegir el elemento de entrada que se va a procesar y lo elimina del conjunto. prometedor() se encarga de determinar si el elemento elegido añadido al conjunto de salida hace que este mantenga las restricciones del problema. En ese caso se anotaEnSolucion().

Partiendo de este esquema podemos intentar solucionar algunos problemas mediante algoritmos voraces que suelen tener unos ordenes de complejidad bajos.

:wq

En otro ejercicio de clase se nos pide que diseñemos una función que, dado un natural h, devuelva un árbol binario que cumpla que es el árbol equilibrado de altura h con el menor número de nodos posible. El contenido de los nodos de dicho árbol será un natural en el rango de 1 hasta el número de nodos del árbol, de forma que todos los nodos tengan información diferente y el árbol esté ordenado.

Recordemos los conceptos de,

Árbol equilibrado: es un árbol binario de búsqueda en el que para cada nodo el número de niveles de sus subárboles izquierdo y derecho no debe diferir en más de una unidad.

Árbol binario de búsqueda: es un árbol binario que tiene la propiedad que hace que todos los elementos almacenados en el subárbol izquierdo son menores que la raíz y ésta es menor que todos los elementos del subárbol derecho.

Veamos algunos ejemplos de árboles equilibrados,

Árboles equilibrados para una altura dada

Podemos ver que el número de nodos para una altura dada coincide con la expresión 2^(altura – 1). Mi implementación se basa en una función auxiliar recursiva que vaya construyendo los árboles binarios desde las hojas a la raíz sabiendo que los nodos que compondrán el árbol irán ordenados desde 2 hasta el número de nodos además de la primera hoja etiquetada con 1 que hace que se alcance la altura pedida con el mínimo número de nodos.

Esta es mi implementación:

func generaAVL (h: natural) dev (a: BinaryTree)
alg
	// Funcion recursiva auxiliar que genera el arbol binario de búsqueda
	// a partir del número de nodos del árbol que viene dado por 2^(altura -1)
	a := generaAVLaux(2, 2^(h-1)) 
fin

func generaAVLaux (ini, fin) dev (a: BinaryTree)
var
	raiz: Entero
	izq, der: BinaryTree
alg
	raiz := (ini + fin) / 2
	
	si ((raiz - ini) = 1):		// Caso base
		si (ini = 2)
			izq := BinaryTree(BinaryTree(null,1,null), ini, null )
		| otras:
			izq := BinaryTree(null, ini, null)
		fsi
		der := BinaryTree(null, fin, null)
		a := BinaryTree(izq, raiz, der)
	| otras:			// Caso recursivo
		a := BinaryTree( generaAVLaux(ini, raiz-1), raiz, generaAVLaux(raiz+1, fin) )
	fsi
fin

Creo que se trata de una implementación un poco sucia en cuanto al código pero creo que es bastante eficiente. Se trata del ejercicio 4 del boletín de árboles de EDA.

:wq

Código de Huffman

20 abril 2007

Hace poco intenté explicar cómo se utiliza el algoritmo de Huffman para codificar e incluso encriptar una cadena de caracteres.

Llegamos a un punto en el que tenemos un árbol de Huffman y tenemos que recorrerlo para obtener la codificación asociada a cada carácter.

Arbol binario algoritmo Huffman

Esto es precisamente lo que se nos pide en clase: realizar un algoritmo que recibe un árbol binario de Huffman y devuelve dos listas, una con los caracteres y otra con las cadenas que representan el código que se le asigna al carácter. Carácter y código en las listas están relacionadas por la posición que ocupan.

Mi solución en pseudo-código sería la siguiente:

alg codigoHuffman
var
	lcar: Lista de Cadena 	// Lista de caracteres
	lcod: Lista de Cadena 	// Lista de codigos asociados a los caracteres
	a: BinaryTree		// Arbol binario de Huffman
	aux: Cadena		// Cadena auxiliar para ir almacenando los codigos
prin
	recorridoArbolHuffman (a, aux, lcar, lcod) 	//Funcion recursiva
fin

proc recorridoArbolHuffman (a: BinaryTree, aux: Cadena, ent/sal lcar, lcod: Lista de Cadena)
var
	numcar: Entero		// Número de caracteres que tiene el árbol
alg
	si a.isLeaf():		// Caso base
		numcar:= numcar + 1
		lcar.add(numcar, a.getRoot())
		lcod.add(numcar, aux)
	| otras:
		recorridoArbolHuffman( a.Left(), aux.addCaracter("0"), lcar, lcod )
		aux.removeLast()	// Borramos el último elemento de la cadena auxiliar
		recorridoArbolHuffman( a.Right(), aux.addCaracter("1"), lcar, lcod )
		aux.removeLast()
	fsi
fin

Se trata del ejercicio 3 del boletín de árboles de EDA.

:wq

Árbol monodistante

17 abril 2007

Un árbol monodistante de orden N es un árbol binario de números enteros en el que la suma de los valores de los nodos de cada camino que va desde la raíz a un nodo hoja es igual a N.

Ejemplo de árbol monodistante de orden 15:

arbol monodistante de orden 15

En un ejercicio de clase se nos pide que diseñemos una función que compruebe si un árbol es monodistante o no.

El prototipo de la función puede ser el siguiente:

func esMonodistante(a:BinaryTree; n: Natural) dev b:Boolean

La función tiene como entrada un arbol binario (BinaryTree) y un natural que indica el orden y devuelve cierto si el árbol es monodistante o falso en cualquier otro caso.

Siempre que vayamos a trabajar con árboles conviene pensar en una solución recursiva. El caso base de esta función recursiva podría ser que el árbol estuviera vacio o que el árbol sólo tuviera una hoja. En el resto de casos sólo tendríamos que comprobar que el subarbol derecho y el subarbol izquierdo son monodistantes haciendo una llamada recursiva y decrementando el orden del árbol.

Mi solución recursiva es esta:

func esMonodistante (a:BinaryTree, n:Natural) dev (b:Logico)
alg
	si a.isEmpty():   //el árbol está vacio
		b := cierto
	| a.isLeaf():     //el árbol es una hoja
		b := ( a.getRoot() = n )
	otras
		b := (esMonodistante(a.left() , n-a.getRoot())
		    Y esMonodistante(a.right(), n-a.getRoot()) )
	fsi
fin

Por si os sirve de algo se trata del Ejercicio 19 del Boletín de Árboles de la asignatura Estructuras de Datos y Algoritmos

:wq