Se debe asistir con el DNI u otro carnet con foto acreditativo de la identidad.

Se permite llevar al examen los apuntes que se desee.

No se permite utilizar ningún dispositivo electrónico (teléfonos, tabletas, lectores electrónicos, portátiles, etc).

Normas de evaluación: http://webdiis.unizar.es/asignaturas/AB/?page_id=36

Indicaciones generales COVID-19: ver aquí.

http://encuestas.unizar.es/

Las encuestas son muy importantes para facilitar la mejora, año a año, de la asignatura. Os rogamos dediquéis unos minutos de vuestro tiempo para responderlas.

El examen escrito tendrá lugar el 9 de junio, a las 8:30 de la mañana, en las aulas 20B y 21 del edificio Torres Quevedo. Duración prevista: 2 horas.

Se debe asistir con el DNI u otro carnet con foto acreditativo de la identidad.

Se permite llevar al examen los apuntes que se desee.

No se permite utilizar ningún dispositivo electrónico (teléfonos, tabletas, lectores electrónicos, portátiles, etc).

Normas de evaluación: http://webdiis.unizar.es/asignaturas/AB/?page_id=36

Indicaciones generales COVID-19: ver aquí.

Toda solución de programación dinámica evita usar una solución top-down recursiva que directamente traduzca a un algoritmo la ecuación recurrente correspondiente al problema. Esto es así porque, normalmente, el coste en tiempo de esa solución es extremadamente alto pues resuelve muchas veces los mismos subproblemas.

Para evitar resolver muchas veces los mismos subproblemas, un algoritmo de programación dinámica utiliza siempre una tabla auxiliar, en la que se almacenan las soluciones de los subproblemas conforme se van resolviendo.

Dicho esto, hay dos formas distintas de implementar la solución de programación dinámica:

• Solución de abajo arriba (bottom-up) iterativa, en la que se van resolviendo todos los subproblemas y rellenando la tabla en un cierto orden, iterativamente, en primer lugar resolviendo los casos base de la recursión y después el resto de los casos aplicando la ecuación recurrente “ordenadamente”, de manera que cuando se necesiten las soluciones de ciertos subproblemas (en cierto sentido, “más pequeños”) para resolver otros, éstas hayan sido resueltas y almacenadas en la tabla con anterioridad en el(los) bucle(s) correspondiente(s) del algoritmo. Ejemplos de estas soluciones son las de los problemas de la mochila 0-1, el camino de coste mínimo en un grafo multietapa o la multiplicación de una secuencia de matrices, vistas ya en clase.
• Solución (recursiva) de arriba abajo (top-down) con memorialización (memoization), en la que se aplica directamente la ecuación recurrente, como en la solución top-down recursiva (mencionada antes y descartada por muy ineficiente), pero cada vez que se resuelve un subproblema, se almacena su solución en la tabla auxiliar para evitar volver a resolverlo de nuevo más adelante. De esta forma, lo primero que hace el algoritmo es averiguar si el subproblema ha sido ya resuelto consultando la tabla, y sólo si no se ha resuelto todavía, se aplica la ecuación recurrente para resolverlo (de forma recursiva). Un ejemplo de este tipo de solución es la del problema del viajante de comercio, vista ya en clase.

El coste asintótico de ambos métodos suele ser el mismo, salvo en algunos casos (poco frecuentes) en los que la solución de arriba abajo no necesita resolver todos los subproblemas de la tabla. En general, la solución de abajo arriba ofrece mejores resultados prácticos al tener constantes multiplicativas más pequeñas, pues se evita el sobrecoste provocado por las llamadas recursivas. Por eso recomendamos, siempre que sea posible, plantear una solución de abajo arriba iterativa.

Lectura adicional (acceso restringido): ejemplo del recorte óptimo de varillas y sus dos soluciones de programación dinámica (arriba abajo con memorialización versus abajo arriba iterativa), del libro [CLRS09].

Los enlaces de:

• la videoconferencia para la primera clase (de presentación) y
• las videoconferencias para el resto de clases del profesor Javier Campos,

así como las instrucciones básicas, se pueden encontrar en el Moodle de la asignatura.

El examen escrito (40% del peso de la nota final) tendrá lugar el 8 de junio de 2020 a las 15:30 horas en salas virtuales de Google Meet que se comunicarán con la suficiente información y antelación en Moodle.

El examen durará dos horas (además del tiempo necesario para completar el protocolo) y constará de problemas relacionados con la primera parte de la asignatura (divide y vencerás, algoritmos voraces y programación dinámica).

Se debe asistir provisto del DNI o carnet de la Universidad de Zaragoza. Más instrucciones para la realización del examen están disponibles en Moodle.

La información sobre entrega de prácticas (30% del peso de la nota final) está disponible también en Moodle.

Igualmente, el 25 de mayo se publicará en Moodle la información sobre el miniproyecto de programación lineal (30% del peso de la nota final).