Repositorio de Antonio Sánchez

Para identificar una dirección MAC multicast tenemos que fijarnos en el primer byte (octeto) de los 6 byte que forman la dirección MAC. Si el bit menos significativo está fijado a 1 se trata de una MAC multicast.

Ejemplo MAC:

01:80:c2:00:00:00 en decimal el primer octeto equivale a 00000001, por lo que se trata de una MAC multicast.

:wq

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,

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

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

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

Se trata de un algoritmo que se usa para compresión o encriptación de datos desarrollado por David A. Huffman en 1952.

Se basa en el concepto de asignar códigos de distinta longitud de bits a cada uno de los caracteres de un fichero. Si se asignan códigos más cortos a los caracteres que aparecen más a menudo se consigue una compresión de ficheros.

El algoritmo consiste en la creación de un árbol binario que tiene cada uno de los símbolos por hoja, y construido de tal forma que siguiéndolo desde la raíz a cada una de sus hojas se obtiene el código Huffman asociado.

1. Se crean varios árboles, uno por cada uno de los símbolos del alfabeto, consistiendo cada uno de los árboles en un nodo sin hijos, y etiquetado cada uno con su símbolo asociado y su frecuencia de aparición.
2. Se toman los dos árboles de menor frecuencia, y se unen creando un nuevo árbol. La etiqueta de la raíz será la suma de las frecuencias de las raíces de los dos árboles que se unen, y cada uno de estos árboles será un hijo del nuevo árbol. También se etiquetan las dos ramas del nuevo árbol: con un 0 la de la izquierda, y con un 1 la de la derecha.
3. Se repite el paso 2 hasta que sólo quede un árbol.

Con este árbol se puede conocer el código asociado a un símbolo, así como obtener el símbolo asociado a un determinado código. Lo normal es pasar la asociación de código y símbolos a una tabla para trabajar con ella y desechar el árbol.

Como ejemplo vamos a aplicarlo a la cadena “tres_tristes_tigres”. Hay que tener en cuenta los espacios en blanco para codificar la cadena completa.

Primero. Asignamos la frecuencia de aparición (absoluta o relativa) a cada carácter de la cadena.

t (4) r (3) e (3) s (4) _ (2) i (2) g (1)

Segundo. Ordenamos de menor a mayor los caracteres según su frecuencia. Si se repiten las frecuencias no importa.

g (1) _ (2) i (2) r (3) e (3) t (4) s (4)

Tercero. Creamos un árbol con un único nodo por cada carácter (con su respectiva frecuencia).
Cuarto. Cogemos los 2 arboles con menos frecuencia y los unimos compartiendo un nuevo nodo raíz que contiene la suma de las frecuencias. Además etiquetamos la arista del nodo derecho con un 1 y del nodo izquierdo con un 0.
Quinto. Repetimos el paso anterior hasta que sólo quede un árbol.

Ahora recorremos las ramas desde las hojas hasta el nodo raíz apuntando las etiquetas de cada rama. El código de cada hoja será el inverso de cada una de las secuencias obtenidas. En el ejemplo, para el carácter “r” recorremos desde su hoja hasta la raíz obteniendo la secuencia 110 por lo que el código de Huffman asociado al carácter “r” es el inverso 011.

Para el resto de los caracteres tenemos la siguiente asociación:

s 10
t 11
e 001
r 011
i 010
_ 0001
g 0000

Vemos que los caracteres que más se repiten tienen códigos más cortos para que sea efectiva la compresión.

Fuente: Wikipedia y apuntes de Estructuras de Datos y Algoritmos del LSI.

:wq

La gente de la la asociación Sugus GNU/Linux (grupo de usuarios y usuarias de GNU/Linux de la Escuela Técnica Superior de Ingeniería Informática de la Universidad de Sevilla) ha abierto un espacio para alojar los apuntes o prácticas de las asignaturas de las carreras que se cursan en dicha escuela.

El único requisito es que el material esté publicado con una visible versión de una licencia libre (GNU Free Documentation License, por ejemplo).

Me parece una buena iniciativa en la que intentaré participar si consigo un buen nivel en los trabajos de este cuatrimestre. Animo a cualquiera que tenga unos buenos apuntes o prácticas a que los licencien correctamente y los cuelguen para el bien de la comunidad universitaria.

:wq

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

Bueno, este era uno de los dispositivos que se me resistian en GNU/Linux por ser vago pero esta tarde las décimas de fiebre del constipao que tengo me han hecho ponerme manos a la obra.

Después de un par de búsquedas en google me he topado con que existe un driver para el chip Sunplus que lleva mi camara. Podeis encontrar información aqui.

Lo primero que he hecho ha sido descargar la última versión de los controladores.

agoia:/home/antonio/descargas/# tar -xvzf spca5xx-20050419.tar.gz
agoia:/home/antonio/descargas/# cd spca5xx-20050419


Le echamos un vistazo a las instrucciones de instalación (less INSTALL) y nos damos cuenta de que nos hacen falta las fuentes del kernel para poder compilar el módulo de la cámara. Pues de camino actualizo al kernel 2.6.10 mi máquina:

agoia:~# apt-get install kernel-image-2.6.10-1-386 kernel-headers-2.6.10-1-386
agoia:~# lilo -v
agoia:~# sync
agoia:~# reboot


Ahora que hemos arrancado con el nuevo kernel ya estamos en disposicion de compilar el módulo.

agoia:/home/antonio/descargas/# cd spca5xx-20050419
agoia:/home/antonio/descargas/spcaview-20050419# make clean
agoia:/home/antonio/descargas/spcaview-20050419# make
agoia:/home/antonio/descargas/spcaview-20050419# make install


A mi me dio un error al hacer el make porque se me había olvidado instalar las librerias libsdl como bien dicen las instrucciones, cosa que resolví haciendo

agoia:/home/antonio/descargas/spcaview-20050419# apt-get install libsdl1.2-dev


y repitiendo los 3 pasos anteriores.

Bueno, ahora que ya tenemos compilado e instalado el modulo enchufamos la cámara en modo webcam al puerto usb y hacemos

agoia:~# lsmod | grep spca
spca5xx 277912 0
usbcore 107256 4 spca5xx,usbnet,uhci_hcd


y comprobamos que lo tenemos cargado.

Nos hace falta el programita spcaview que instalamos siquiendo las instrucciones que incluye sin problemas.

Para probar el funcionamiento hacemos

agoia:~# spcaview -t


si se nos abre una ventanita con la imagen de nuestra cámara de lujo, ya la tenemos lista para usarla con cualquier programita de videoconferencia como gnomemeeting.

A mi me dio un error que me decía que no se encontraba el dispositivo /dev/video0 que solucioné creando el dispositivo y cargando el modulo videodev.

agoia:~# modprobe videodev
agoia:~# mknod /dev/video0 c 81 0
agoia:~# chmod 666 /dev/video0
agoia:~# lsmod | grep spca
spca5xx 277912 0
videodev 9728 1 spca5xx
usbcore 107256 4 spca5xx,usbnet,uhci_hcd


Espero que le sirva de ayuda a los propietarios de una de estas camaritas.

Actualización

Hoy me ha dado por configurar la webcam en el portatil para ver si pruebo el futuro soporte de videoconferencia de gaim y vaya si ha cambiado el panorama desde la última vez que la instalé, ahora en mi debian sid sólo hay que hacer:

apt-get install spca5xx-source
m-a prepare
m-a a-i spca5xx
cd /usr/src
dpkg -i spca5xx-modules-2.6.12.6-05.deb

y al ejecutar el gnomemeeting veremos que la detecta a la primera. ¿Quien dijo que linux era complicado?

:wq

Lineak es un software que nos permite darle uso a esas teclas multimedia que traen los modernos teclados bajo GNU/Linux.

La instalación bajo Debian GNU/Linux es muy sencilla y basta con hacer

apt-get install lineakd

para ver la lista de teclados que están soportados ejecutamos

lineakd -l

en mi caso quiero configurar un teclado Logitech Cordless Desktop Pro con lo que veo en la lista anterior que el tipo es LTCDP.

Ahora vamos a generar un archivo de configuración para nuestro teclado que se situara en $HOME/.lineakd/lineakd.conf

lineakd -c LTCDP

Existen herramientas gráficas para configurar las funciones de las teclas pero yo he preferido editar el fichero de configuración a mano y asociar una función a cada tecla de la siguiente manera.

vim /home/antonio/.lineakd/lineakd.conf

CdromDevice = /dev/cdrom
Display_align = center
Display_color = 0aff00
Display_font = -adobe-helvetica-bold-r-normal-*-*-240-*-*-p-*-*-*
Display_hoffset = 0
Display_plugin = internal
Display_pos = bottom
Display_soffset = 1
Display_timeout = 3
Display_voffset = 50
KeyboardType = LTCDP
MixerDevice = /dev/mixer
RAWCommands =
Screensaver =
conffilename = /home/antonio/.lineak/lineakd.conf
keystate_capslock =
keystate_numlock =
keystate_scrolllock = 

Go = mozilla-firefox http://antoniosanchez.wpblogs.com
Internet = mozilla-firefox
Mail = mozilla-firefox http://www.gmail.com
Mute = EAK_MUTE
Next = xmms -f
Play|Pause = xmms --play-pause
Previous = xmms -r
Search = mozilla-firefox http://www.google.es
Sleep =
Stop = xmms -s
VendorHome =
VolumeDown = EAK_VOLDOWN
VolumeUp = EAK_VOLUP

Para lanzar el programa podemos incluirlo en algún archivo que se carge al inicio de sesión del entorno gráfico o bien como hago yo lanzarlo en segundo plano cada vez que lo necesito con

lineakd &

:wq