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).

En este enlace.

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 (m_i ≥ 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  f₀(x), luego los f₁(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,

f_i—1(x) = 0   si   x > c — ∑_i≤j≤n c_j

o, lo que es lo mismo, si  c — x < ∑_i≤j≤n c_j.

En la próxima clase veremos el problema de la triangulación óptima de polígonos (óptima en el sentido de incluir un conjunto de cuerdas de longitud total mínima).

El problema tiene muchas aplicaciones:

• en robótica se utiliza para la generación del plan de movimientos de un robot;
• algo parecido se precisa en informática gráfica para el cálculo de la visibilidad (eliminación de superficies ocultas en una imagen);
• para el cálculo de campos magnéticos en determinados dominios;
• los métodos de análisis de elementos finitos también utilizan la triangulación para hacer tratable el problema;
• los meteorólogos triangularizan para calcular las predicciones del tiempo;
• en algunos algoritmos de teoría del caos también aparecen triangulaciones para resolver ecuaciones diferenciales;
• se usa también en el renderizado de imágenes (generación de imágenes virtuales mediante el cálculo de la iluminación, a partir de un modelo 3D);
• …

En relación con la última aplicación mencionada, puede verse una publicación reciente sobre generación de personajes en videojuegos en la web de la Especialidad en Computación (hacer clic en la imagen siguiente).

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 unas cuantas más en un pdf)

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.