Programación

Un grupo de científicos del Instituto de Ciencias de la Construcción Eduardo Torroja perteneciente al CSIC (Consejo Superior de Investigaciones Científicas), acaba de desarrollar un nuevo material resultante de la combustión del carbón, muy similar al cemento que además supera varias de las prestaciones del cemento convencional.

Gracias a este nuevo material, se obtendría hasta una reducción del 50% de las emisiones que se realizan de dióxido de carbono a la atmósfera como consecuencia de la elaboración, ya que se necesita menos temperatura para su fabricación, con lo que la industria cementera podría contribuir al mantenimiento del medio ambiente.

Leer más

Las computadoras actuales son capaces de realizar varias actividades a la vez. Mientras se ejecuta una tarea de un usuario, el sistema puede estar leyendo una unidad de disco o escribiendo en una impresora, gracias a las posibilidades que ofrecen los circuitos de acceso directo a memoria (DMA) y las interrupciones generadas por los órganos de L/E (Lectura/Escritura). Además, siempre que existan esas interrupciones, se pueden ejecutar varios procesos de usuario de forma alternada, solapándose con las operaciones de L/E.

Leer más

El crecimiento de la red es realmente vertiginoso, tan sólo en España la mitad de la población ya son usuarios. La red influye en la información, en las compras, en la relación, es un punto de encuentro para millones de persona. Por todo esto, se ha presentado un nuevo proyecto de la mano del Instituto de Tecnología de Massachussets y la Universidad Británica de Southampton para la creación de un nuevo título de estudios superiores, Ciencias de la Web.

Tim Berners-Lee, el artífice del World Wide Web y uno de los responsables de esta nueva iniciativa, indica la necesidad de elaborar una ciencia específica para entender lo que representa la red y los escollos que en ella se pueden encontrar. En la nueva ciencia se conjugarán todos los aspectos contenidos en la red, sea sociología, consumo, derechos de autor, cualquier aspecto que se relacione y que haya ganado presencia gracias a la red.

Leer más

Seguimos con el post de ayer, donde estábamos implementando en Java una aplicación que leyese un documento XML usando SAX. La aplicación de ejemplo la he dividido en 5 clases: Index, Acciones, Parseador, Interfaz y Conclusión.

Leer más

XML es el acrónimo de eXtensible Markup Language (lenguaje de marcado ampliable o extensible). Es un lenguaje de etiquetas que se basa en documentos de texto plano en los que se utilizan etiquetas para delimitar los elementos de un documento. Es una versión simplificada de SGML, capaz de describir diversos tipos de datos. Su principal propósito es facilitar el intercambio de información. Son muchos los lenguajes basados en XML (por ejemplo, SVG, RDF, MathML, XSIL, ...). XML permite a las aplicaciones parsear el contenido del documento, pudiendo modificar y leer su contenido.

Podemos parsear un documento XML de dos modos: usando SAX o DOM. Podemos distinguir a grandes rasgos el funcionamiento de cada modo de parseo de la siguiente forma:

• DOM: DOM crea un árbol jerárquico en memoria que contiene el todo documento XML, y con él en memoria podemos hacer realizar cualquier tipo de recorrido, movimiento o acción con los elementos que deseemos.


• SAX: SAX significa Simple API for XML. Se usa para realizar un recorrido secuencial de los elementos del documento XML, es decir, vamos tratando la información a la vez que la vamos leyendo.

SAX es menos potente que DOM, pero aún así es más rápido y útil para los casos donde por ejemplo interesa hacer una lectura secuencial o buscar algún fragmento en un documento.

Leer más

El algoritmo de Huffman se usa para la compresión o encriptación de datos mediante el estudio de la frecuencia de aparición de caracteres. Fue desarrollado por el norteamericano David Albert Huffman en 1952 mientras hacía el doctorado en el MIT. El método fue publicado en una revista como A Method for the Construction of Minimum-Redundancy Codes (el artículo original). El algoritmo funciona a partir de un conjunto dado de símbolos con sus respectivos pesos. Los pesos son la frecuencia de aparición en una cadena. Por ejemplo en la cadena Genciencia el peso del símbolo i es 2, ya que aparece en dos ocasiones. La salida del algoritmo es el mismo conjunto de símbolos de entrada codificado mediante un código binario con un tamaño menor. La descripción matemática del algoritmo de Huffman es la siguiente:

Entrada

• Conjunto de Símbolos:


• Pesos asociados:

Donde n es la cantidad de símbolos diferentes que existe en la cadena de entrada. Así pues los pesos asociados a los símbolos pertenecientes al conjunto A se encuentran en un rango comprendido entre 1 y n (entendiendo que la entrada no va a ser una cadena vacía), es decir:

Salida

• Conjunto de código binarios:

Meta

• Conseguir que el peso de C sea menor que el de A:

Leer más

“Al crear el mundo, Dios situó sobre la Tierra tres varillas de diamante y 64 discos de oro. Los discos son todos de diferente tamaño e inicialmente fueron colocados en orden decreciente de diámetros sobre la primera de las varillas. También creó Dios un monasterio cuyos monjes tienen la tarea de trasladar todos los discos desde la primera varilla a la tercera. La única operación permitida es mover un disco de una varilla a otra cualquiera, pero con la condición de que no se puede situar encima de un disco otro de diámetro mayor. La leyenda dice también que cuando los monjes terminen su tarea, el mundo se acabará”.

El otro día alguien preguntó para qué servían los números de Mersenne. El número mínimo de movimientos para resolver el juego de las Torres de Hanoi viene dado por los números de Mersenne (M=2ⁿ-1 con n primo), siendo el n el número de discos a trasladar. Por lo tanto, los monjes hubiesen necesitado 2⁶⁴-1 = 18446744073709551615 movimientos para resolver el juego con 64 discos. Si suponemos que los monjes realizan un movimiento por segundo tardarían 58454204609 siglos y 6 años en completar el traslado, contando con que no descansen ni un solo segundo en ese tiempo ni que cometan ningún fallo, pues el tiempo que hemos calculado ha sido el mínimo número de movimientos, es decir, hemos excluido los posibles fallos. Lógicamente si resolvemos este problema para 64 discos el mundo no se acaba Existe un algoritmo recursivo donde podemos ver una sencilla solución al problema:

hanoi(n, Orig, Aux, Dst)
si (N>0) hacer
hanoi(n-1, Orig, Dst, Aux)
escribir(Movemos Orig a Dst)
hanoi(n-1, Aux, Orig, Dst)

Leer más

Seguimos con problemas que se pueden resolver mediante algoritmos voraces. Vamos imaginar que tenemos a una persona que desea viajar en coche desde un punto A hasta otro punto B (n kilómetros). El viajante dispone de un mapa de carretera que indica la distancia entre las gasolineras que están situadas en el trayecto que va a realizar. En el punto de origen, el tanque del coche se encuentra lleno. Conocemos un máximo de kilómetros que el coche puede realizar sin la necesidad de repostar (x kilómetros / xsu objetivo es pararse a repostar el menor número de veces posibles. El algoritmo voraz nos determinará en qué gasolineras el viajante tiene que parar a repostar.

Leer más

Los algoritmos voraces (greedy algorithms en inglés) son unas rutinas muy eficientes (O(n), O(n²)) aunque no suelen proporcionar la mejor solución a un problema. Existen algoritmos voraces muy conocidos, como el Algoritmo de Dijkstra o el Algoritmo de Kruskal. Vamos a resolver mediante un algoritmo voraz el conocido Problema del cambio de monedas. El problema se presenta de la siguiente forma: Dado un sistema monetario S de longitud K y una cantidad de cambio C, devolver una solución (si existe) que nos indique el número de monedas de S equivalente a C, es decir, que nos muestre el cambio para C a partir de monedas de S. Veamos un ejemplo:

En este ejemplo nos proporcionan un sistema monetario que contiene monedas de valor 10, 6, 5 y 1. La cantidad que debemos cambiar es C=12. El algoritmo voraz siempre intentará realizar el cambio mediante monedas del mayor valor posible. Si en algún paso C es menor estricto que S[t] (t≤K), se incrementará t y repetiremos el mismo paso para la siguiente moneda de S. Al finalizar, el algoritmo voraz nos indica que el cambio resultante para 12 son dos monedas de 1 y una de 10. Cómo he comentado al principio los algoritmos voraces en muchas ocasiones no presentan la mejor solución, pues en éste ejemplo sería mejor cambiar 12 por dos monedas de 6, entendiendo por mejor solución devolver el menor número de monedas posibles.

Leer más