Algoritmia básica (AB) » voraces

Hoja de problemas de algoritmos voraces

Javier Campos — Tue, 18 Feb 2020 11:16:51 +0000

Se ha publicado en la web (sección problemas) una hoja de problemas sobre algoritmos voraces (usuario y contraseña, los dados el primer día de clase).

Son para trabajarlos en casa, antes del miércoles próximo.

Hoja de problemas de algoritmos voraces

admin — Wed, 20 Feb 2019 16:25:47 +0000

Se ha publicado en la web (sección problemas) una hoja de problemas sobre algoritmos voraces (usuario y contraseña, los dados el primer día de clase).

Son para trabajarlos en casa, especialmente del 1º al 5º, antes del miércoles próximo.

Publicada hoja de problemas (voraces)

Javier Campos — Mon, 19 Feb 2018 11:49:27 +0000

Se ha publicado una hoja de problemas sobre algoritmos voraces.

Dos enlaces relacionados con matroides

Javier Campos — Wed, 01 Mar 2017 15:00:23 +0000

La anotación en el blog de Jeremy Kun: When Greedy Algorithms are Perfect: the Matroid.
Más allá de los matroides: los gridoides.

Curiosidades sobre el problema del árbol de recubrimiento de coste mínimo

Javier Campos — Tue, 21 Feb 2017 15:28:28 +0000

Leer esta anotación: http://webdiis.unizar.es/asignaturas/AB/?p=1009

Publicada hoja de problemas (voraces)

Javier Campos — Thu, 16 Feb 2017 10:55:18 +0000

Se ha publicado una hoja de problemas (algoritmos voraces).

Un par de anotaciones sobre el problema del cambio en monedas

Javier Campos — Tue, 14 Feb 2017 14:57:28 +0000

Aquí y aquí.

Una curiosa aplicación del código Huffman

Javier Campos — Mon, 11 Apr 2016 10:34:39 +0000

Se puede leer aquí el artículo de divulgación:

Researchers store images in DNA, search for and perfectly retrieve them.

Y aquí puede encontrarse el artículo de investigación:

A DNA-Based Archival Storage System (por James Bornholt, Randolph Lopez, Douglas M. Carmean, Luis Ceze, Georg Seelig y Karin Strauss).

Sobre la corrección del algoritmo voraz para el problema del cambio en monedas

Javier Campos — Thu, 11 Feb 2016 12:18:20 +0000

Como vimos ayer en clase, el algoritmo voraz para devolver una cantidad de dinero con el menor número posible de monedas es correcto (es decir, calcula el número mínimo de monedas) para los sistemas de monedas “habituales”, como el del Euro o el Dólar, que suelen denominarse sistemas canónicos de monedas.

Sin embargo, en general, el voraz no es un algoritmo correcto, no calcula el valor mínimo (ejemplo de monedas marcianas).

Aquí podéis acceder (sólo desde la red de Unizar, o desde vuestra casa usando https://vpn.unizar.es) a un artículo reciente que estudia el sistema de monedas que se requiere para que el algoritmo voraz sea correcto (ojo, no es fácil de leer porque, como ocurre con la mayoría de trabajos de investigación, requiere cierta experiencia en el tema):

Xuan Cai: “Canonical Coin Systems for CHANGE-MAKING Problems“. Proceedings of the Ninth International Conference on Hybrid Intelligent Systems, pp. 499–504. Shenyang, China, August 12-14, 2009.