Algoritmia básica (AB)
El reto de diseñar algoritmos eficientes para resolver problemas puede resultar apasionante

sguenos en twitter

  Toda solución de programación dinámica evita usar una solución top-down recursiva que directamente traduzca a un algoritmo la ecuación recurrente correspondiente al problema. Esto es así porque, normalmente, el coste en tiempo de esa solución es extremadamente alto pues resuelve muchas veces los mismos subproblemas. Para evitar resolver muchas veces los mismos subproblemas, un algoritmo de [...]

Material adicional de divide y vencerás
3 marzo 2020 por Javier Campos en cosas de clase,divide y vencerás Comentarios desactivados

En la página de material adicional de esta web puede encontrarse: Un artículo que describe un par de métodos de ordenación por fusión (o mezcla) “in situ” y analiza su coste (acceso con clave aquí). Un par de capítulos de libros sobre métodos de ordenación en memoria externa basados en la idea de la ordenación por [...]

Floyd-Warshall: cálculo del camino
18 abril 2017 por Javier Campos en cosas de clase,programación dinámica Comentarios desactivados

En la transparencia 55 de programación dinámica quedó como ejercicio el cálculo de los nodos de las secuencias que componen los caminos mínimos desde cualquier nodo i a cualquier nodo j. Hay varias formas de resolverlo. Una muy sencilla consiste en guardar una matriz adicional C[v,w] en la que se almacene un nodo u que [...]

. Las soluciones de programación dinámica aparecen en prácticamente todos los dominios de aplicación. Seleccionamos aquí algunos ejemplos en Visión, Juegos, Robótica y Bioinformática: Dynamic Programming and Graph Algorithms in Computer Vision: A Survey. Dynamic programming and board games: A survey (acceso restringido con usurio/clave). Some dynamic programming problems useful to solve the mobile robot [...]

Fibonacci y programación dinámica
31 marzo 2017 por Javier Campos en cosas de clase,Fibonacci,programación dinámica Comentarios desactivados

Uno de los ejemplos más sencillos (más que los vistos en clase) de aplicación de la programación dinámica es el cálculo del término n-ésimo de la sucesión de Fibonacci. La definición de la sucesión o función de Fibonacci es: Fib(n) = 1, si n = 0,1 Fib(n) = Fib(n-1) + Fib(n-2), si n > 1 [...]

. El algoritmo conocido como “de Karatsuba y Ofman” para multiplicar enteros de n cifras con un coste asintótico en O(nlog 3)  ( ≈ O(n1,59) )  aparece publicado en el artículo ”Multiplication of multidigit numbers on automata”, A. Karatsuba, Y. Ofman, en el nº 145, pp. 293-294, de las actas de la Academia de Ciencias de [...]

Material adicional de divide y vencerás
7 marzo 2017 por Javier Campos en cosas de clase,divide y vencerás Comentarios desactivados

En la página de material adicional de esta web puede encontrarse: Un artículo que describe un par de métodos de ordenación por fusión (o mezcla) “in situ” y analiza su coste (acceso con clave aquí). Un par de capítulos de libros sobre métodos de ordenación en memoria externa basados en la idea de la ordenación por [...]

Dos enlaces relacionados con matroides
1 marzo 2017 por Javier Campos en cosas de clase,voraces Comentarios desactivados

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

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

Un par de anotaciones sobre el problema del cambio en monedas
14 febrero 2017 por Javier Campos en cosas de clase,curiosidades,monedas,voraces Comentarios desactivados

. Aquí y aquí.