Three seemingly unrelated problems (matrix chain multiplication, optimal BST, and optimal polygons triangulation). Dynamic Programming and Graph Algorithms in Computer Vision: A Survey. Dynamic programming and board games: A survey (acceso para alumnos de AB). Some dynamic programming problems useful to solve the mobile robot localization problem. Systematic Dynamic Programming in Bioinformatics.

. . “A new kind of cipher that would take millions of years to break.” Ese era el título del artículo publicado por Martin Gardner (conocidísimo divulgador científico norteamericano) en la sección Mathematical Games de la revista Scientific American, vol. 237(2), pp. 120-124, en agosto de 1977 (puede descargarse aquí). En él, Gardner describía el método de [...]

. Existe un algoritmo de coste asintótico lineal, en el caso peor, para el cálculo del 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) ). Puede verse aquí.

. Hemos visto en clase que algunos problemas poseen la estructura algebraica subyacente de matroide y en ese caso pueden resolverse correctamente con un algoritmo voraz. Existe una extensión del concepto de matroide que permite llegar un poco más lejos, para resolver más problemas con algoritmos voraces: se trata de los gridoides. En Wikipedia o en [...]

Hoy, para ver una implementación eficiente del algoritmo de Kruskal, hemos hablado de la función α como inversa de la función de Ackerman. Si alguien anda buscando crecimientos grandes para perder un poco el tiempo, puede echar un vistazo a la notación sagital de Knuth, a la notación sagital encadenada de Conway, a la notación de Steinhaus–Moser, a los números [...]

. Sobre el algoritmo RSA que veremos en clase, recordamos esta anotación anterior con algunas curiosidades: http://webdiis.unizar.es/asignaturas/AB/?p=1078

En el episodio 74 (código de producción 413) de la serie Numb3rs, Colby muestra un mapa sobre la mesa de Charlie: la ciudad de Los Ángeles con 11 posiciones marcadas con chinchetas. Colby.— It’s a pretty basic GPS, no data on the times or the routes. Charlie.—Just the ten most recent destinations he typed in. Colby.— Gives us eleven points, [...]

. Hoy veremos en clase un problema de comparación de secuencias de caracteres (transparencias 41 a 47 de programación dinámica), concretamente el problema de la distancia de edición entre dos secuencias. La solución de este problema (y de otros similares) tiene aplicaciones en diversos ámbitos, entre ellos la biología computacional, así como, de forma mucho [...]

Algo de información: en este enlace.

En la numeración romana no todo vale. En este enlace están las reglas.