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 [...]

Se ha publicado una hoja de problemas (algoritmos de programación dinámica).

La prueba escrita intermedia (prevista en la guía docente) será el miércoles 29 de marzo a las 15:00 (duración: 2 horas) en el aula 12 del edificio Ada Byron. Consistirá en un par de problemas de los temas de algoritmos voraces y divide y vencerás. Se permitirá utilizar material impreso (transparencias, libros…) pero no se [...]

Existe un algoritmo de coste asintótico lineal, en el caso peor, para el problema de selección, es decir, para el cálculo del k-ésimo menor elemento (o estadístico de orden k) de un vector de tamaño n. Por tanto, en particular, puede usarse para el cálculo de la mediana (haciendo k = techo(n/2) ). Os lo incluyo debajo, extraído del [...]

. 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 [...]

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 [...]

Se ha publicado una hoja de problemas (algoritmos de divide y vencerás).

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