Puede consultarse una solución del test en este enlace (usuario y clave habituales).

Recordamos que el test intermedio será el martes 30 de abril, a las 16:00 horas, en el aula 12 del edificio Ada Byron, sobre los temas: “algoritmos voraces”, “divide y vencerás” y “programación dinámica”; y se permitirá usar apuntes pero no dispositivos electrónicos.

En relación con el problema de fiabilidad de sistemas visto ayer en clase (transparencias 65 a 69 de programación dinámica), tal como discutimos, es necesario garantizar que haya al menos un dispositivo en cada fase (mi ≥ 1,  i = 1…n). Nótese que la ecuación en recurrencias es “hacia atrás”, y por lo tanto el [...]

. Tras detectar hoy en clase que conocíais el concepto de orden de crecimiento inferior (O(-)), pero que no conocíais los de orden de crecimiento superior (Ω(-)) y orden de crecimiento exacto (Θ(-)) de una función, incluyo aquí unas transparencias y este enlace a unos apuntes breves del profesor J.L. Balcázar. (estas dos transparencias y [...]

Hoy estudiaremos en clase el problema del viajante de comercio (TSP, Travelling Salesman Problem), un conocidísimo problema NP-difícil, y veremos una solución de programación dinámica. Hay una página web del Georgia Tech (Georgia Institute of Technology) dedicada a este problema (ver este enlace) que contiene mucho material útil e interesante. Aunque también contiene cosas inútiles… por [...]

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

Ya tenéis disponible el guión de la práctica 2. Se trata de resolver el problema del viajante de comercio mediante dos estrategias: fuerza bruta y programación dinámica. Una vez implementadas las estrategias, hay que comparar sus tiempos de ejecución para distintos tamaños del problema.    

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

. En la técnica de divide y vencerás, un ejemplar del problema se divide en ejemplares más sencillos del mismo problema que se resuelven separadamente (son ejemplares, de alguna manera, independientes) y sus soluciones se combinan para crear una solución del ejemplar del problema original. En programación dinámica, los subproblemas en que se divide el [...]

Algo de información: en este enlace.