Algoritmia básica (AB)
El reto de diseñar algoritmos eficientes para resolver problemas puede resultar apasionante

sguenos en twitter

El examen escrito tendrá lugar el 13 de septiembre, a las 15:30 horas, en el aula 10 del edificio Torres Quevedo. Duración prevista: 2.5 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í.

 

Resultados primera convocatoria
28 junio 2021 por Javier Campos en Anuncios,Examen Comentarios

Se han publicado en la plataforma Moodle los resultados de la primera convocatoria del curso 2020-21.

Encuestas de docencia
25 mayo 2021 por Javier Campos en Anuncios,encuestas Comentarios

Hasta este viernes, 28 de mayo, está abierto el periodo de realización de encuestas sobre la docencia de la asignatura:

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

 

Inicio del curso 2020-21
25 enero 2021 por admin en Anuncios Comentarios

Inicio de clases de Algoritmia Básica (curso 2020-21): el 9 de febrero, martes, a las 15:10 horas, mediante videoconferencia.

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.

Se ha publicado en el Moodle de la asignatura (sección Convocatorias) toda la información sobre la convocatoria de septiembre.

Se han publicado en la plataforma Moodle los resultados de la primera convocatoria del curso 2019-20.

Se ha publicado en el tablón oficial la convocatoria de examen de junio:

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

La siguiente adenda a la guía docente, motivada por el estado de alarma, ha sido informada favorablemente por la Comisión de Garantía de la Calidad de los Grados de la EINA:

  1. Adaptaciones en el programa (revisión y adaptación de los contenidos de la asignatura): No se han producido cambios en los contenidos de la asignatura respecto a lo indicado en la guía docente.
  2. Adaptaciones en la metodología docente (clases online, videos grabados, …): Las actividades docentes señaladas en la guía docente de la asignatura se desarrollan mediante el uso de las herramientas telemáticas docentes disponibles (Moodle y G-Suite), asegurando la protección de los datos personales de los estudiantes.
  3. Adaptaciones en la evaluación:
  • La “prueba escrita intermedia” que estaba previsto realizar día 15 de abril fue suspendida debido a la imposibilidad de realizarla. Por tanto se elimina de los criterios de evaluación. Al ser una prueba voluntaria, no afecta al resto de criterios.
  • La evaluación global se modifica de la siguiente forma con objeto de facilitar a los estudiantes su adaptación a las circunstancias excepcionales actuales:
    • Parte práctica. Presentación de trabajos prácticos de programación en los que se obtendrá una calificación de prácticas que ponderará un 30% de la nota final de la asignatura.
    • Miniproyecto. Entrega de un trabajo conceptual y práctico cuya evaluación ponderará un 30% de la nota final de la asignatura.
    • Examen escrito en el que se deberán resolver problemas de naturaleza similar a los planteados en clase sobre la primera mitad de los temas de la asignatura. La calificación obtenida ponderará un 40% de la nota final de la asignatura.
  • Estas actividades de evaluación se realizarán mediante el uso de las herramientas de evaluación telemática disponibles en la Universidad de Zaragoza (Moodle y G-Suite), asegurando la protección de los datos personales y garantizando los derechos de los estudiantes establecidos en el Acuerdo de 22 de diciembre de 2010, del Consejo de Gobierno de la Universidad, por el que se aprueba el Reglamento de Normas de Evaluación del Aprendizaje.