Esta es la información correspondiente al examen escrito de la primera convocatoria:
Fecha: Martes 18 de junio de 2013
Hora: 15:00
Lugar: Aula A.07 del edificio Ada Byron
Para los que opten a la evaluación global, el examen práctico será el mismo día a las 18:00 en el laboratorio 1.02 del edificio Ada Byron.
La convocatoria completa está disponible aquí.
Está disponible en la página de ejercicios una hoja de ejercicios sobre algoritmos de ramificación y poda (en caso de entregar alguno de ellos, debe hacerse no más tarde del 29/05/2013).
Tras esta hoja, habrá una más.
Quienes entregaron ejercicios de la hoja de programación dinámica pueden pasar a recogerlos por el despacho del profesor (a partir de mañana por la mañana).
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 cálculo se haría “hacia adelante” (empezando por calcular todos los f0(x), luego los f1(x), etc.).
El requisito de tener al menos un dispositivo en cada fase puede garantizarse descartando las decisiones en las que ya no quedaría remanente para pagar el coste de al menos un dispositivo para todas las fases restantes. Es decir, haciendo, para i = 2…n,
fi—1(x) = 0 si x > c — ∑i≤j≤n cj
o, lo que es lo mismo, si c — x < ∑i≤j≤n cj.
.
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.
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 ejemplo, podéis encontrar una aplicación para iPhone/iPad que sirve para generar un recorrido del viajante de comercio a partir de una foto (generando primero un conjunto de puntos en la foto que servirán como vértices del grafo a visitar por el viajante). La foto de arriba es un ejemplo del resultado.
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, including the meth lab. I see a map with a bunch of dots on it. I figure you can tell me something; maybe even find his stash house.
Charlie.— It’s not really enough data for any kind of inference… maybe some application of Floyd-Warshall…
Hoy veremos en clase el algoritmo de Floyd-Warshall, como ejemplo de algoritmo de programación dinámica.
