Algoritmos Voraces

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

Árbol equilibrado de altura dada

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,

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

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.

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

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:

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

camrename

No me gustan nada los nombres que le ponen automáticamente las cámaras de fotos digitales a los archivos, además este nombre depende de la marca de la cámara.

Mi actual Sony Cibershot DSC-W50 nombra las fotografías con el patrón dscXXXXXX y mi difunta Canon Powershot A85 lo hacía de la siguiente forma img_XXXX. La Canon venía con un software de importación de fotografías para Windows bastante útil que comparaba las fotos que ibas a importar de la cámara con el directorio de tu equipo donde tuvieras todas tus fotos de forma que te avisaba cuando importabas algo que ya tenias y además te permitía organizar las fotografías en directorios descriptivos con la fecha en que tomaste la foto siguiendo el patrón AAAA_MM_DD.

Hasta ahora bajo GNU/Linux no conocía ningún software que te permitiera ordenar las fotografías a nivel de directorios. Por ejemplo F-Spot te permite categorizar y ver las fotografías por fechas pero de forma virtual, ya que en el disco siguen desordenadas.

Hoy he encontrado un script para shell llamado camrename que me ha hecho la vida más fácil. Este sencillo script te permite renombrar tus fotografías con el siguiente formato a partir de los datos EXIF de las mismas:

	Pyyyy.mm.dd-hh.mm.ss-seqn.jpg
	 ^^^^ ^^ ^^ ^^ ^^ ^^ ^^^^
	  |   |  |  |  |  |   |
	  |   |  |  |  |  |   +--- Image sequence number
	  |   |  |  |  |  |
	  |   |  |  |  |  +------- Seconds of image creation date/time
	  |   |  |  |  |
	  |   |  |  |  +---------- Minutes of image creation date/time
	  |   |  |  |
	  |   |  |  +------------- Hours of image creation date/time
	  |   |  |
	  |   |  +---------------- Day of month image created
	  |   |
	  |   +------------------- Month image created
	  |
	  +----------------------- Year image created

Con esto ya tengo todos los archivos bien renombrados. Cuando tenga ganas me pondré a retocar dicho script para que además me cree directorios con los días en los que tome las fotografías e incluya las correspondientes dentro.

Gracias a Geoff Kuenning por su conjunto de herramientas para manejar fotografías en GNU/Linux.

:wq

Fibonacci

En muchas asignaturas de algoritmia utilizan la sucesión de Fibonacci como ejemplo de algoritmo recursivo.

La peor forma de darnos la sucesión de Fibonacci es así: 1,1,2,3,5,8…
Otra forma con la que queda totalmente definida es a través de su término general:

fib(n) = n                            si         n < = 1
fib(n) = fib(n-1) + fib(n-2)          si         n > 1

A la vista de la segunda definición de la sucesión de Fibonacci es muy fácil darse cuenta del algoritmo recursivo múltiple que hay que hacer para resolver el problema de hallar el n-ésimo término de la sucesión.

func fib (n:entero) dev (res:entero)
alg
   si (n< =1):
      res := n
   otras:
      res := fib(n-1) + fib(n-2)
   fsi
fin

Según la posición de la llamada a la misma función en un algoritmo recursivo podemos distinguir entre recursividad no final y final, a ésta última nos referimos cuando no hay que realizar más procesamiento después de la llamada recursiva.

Ahora veremos como conseguir un algoritmo recursivo final que nos devuelva el valor de la n-ésimo termino de la sucesión de Fibonacci mediante el uso de acumuladores.

func fibFinal (n:entero) dev (res:entero)
alg
   res := 0
   si (n < 2):
      res := 1
   otras:
      res := fibFinalAux(n,1,0,1)
   fsi
fin

func fibFinalAux (n,i,f0,f1:entero) dev (res:entero)
alg
   res := 0
   si (i = n):
      res := f1
   otras:
      res := fibFinalAux(n,i+1,f1,f0+f1)
   fsi
fin

Lo que hemos hecho ha sido utilizar 2 acumuladores, f0 que almacena en todo momento el valor de fib(n-2) y f1 que almacena el valor de fib(n-1).

Por último, debemos saber que cualquier algoritmo recursivo final puede transformarse en un algoritmo iterativo con un bucle. Si el algoritmo fuese no final tendríamos que usar 2 bucles.

Vamos a ver como pasamos de un algoritmo recursivo final (anterior) a uno iterativo.

func fibIter (n:entero) dev (res:entero)
var
   i,f0,f1,faux: entero
alg
   i := 1
   f0 := 0
   f1 := 1
   faux := 0
   res := 0

   si (n < 2):
      res := 1
   otras:
      mientras (i < n)
         i := i+1
         faux := f0
         f0 := f1
         f1 := faux + f1
      fmientras
      res := f1
   fsi
fin

He hecho la traza de los algoritmos y todos cumplen con su labor. He estado buscando un poco en internet para ver si mi solución era la más eficiente y no he encontrado ninguna para los 2 últimos algoritmos asi que si veis alguna mejora debeis comentadmela

Si os han mandado estos pequeños ejercicios para una práctica pensadlos un poquito y no los copieis porque sino no sirve de nada y yo no me fiaría de un algoritmo de alguien que no conozco.

:wq

Dive into Python

Justo cuando no puedo leer me entero que acaba de ser traducido el libro Dive into Python al español. Ya lo tengo en pdf y no puedo seguir leyendo…

… y no es porque se me haya acabado el texto de la tarjeta como en el Un, Dos, Tres sino porque tengo examen dentro de poco y las pocas horas que tengo libres al día las tengo que invertir en ello. Que coraje. Seguro que cuando termine los examenes ya no tengo ganas de leer, que le vamos a hacer, lo dejo en el escritorio para acordarme.

:wq