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

s韌uenos en twitter

 

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

 

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.

Informaci贸n sobre protecci贸n de datos de car谩cter personal en el tratamiento de gesti贸n de grabaciones de docencia

Tratamiento: Gesti贸n de grabaciones de docencia.

Finalidad: Grabaci贸n y tratamiento audiovisual de docencia y su evaluaci贸n.

Base Jur铆dica: Art. 6.1.b), c) y d) Reglamento General de Protecci贸n de Datos.

Responsable: Universidad de Zaragoza.

Ejercicio de Derechos de acceso, rectificaci贸n, supresi贸n, portabilidad, limitaci贸n u oposici贸n al tratamiento ante el gerente de la Universidad conforme a https://protecciondatos.unizar.es/procedimiento-seguir.

Informaci贸n completa en: https://protecciondatos.unizar.es/sites/protecciondatos.unizar.es/files/users/lopd/gdocencia_extensa.pdf

Propiedad intelectual: Queda prohibida la difusi贸n, distribuci贸n o divulgaci贸n de la grabaci贸n y particularmente su compartici贸n en redes sociales o servicios dedicados a compartir apuntes. La infracci贸n de esta prohibici贸n puede generar responsabilidad disciplinaria, administrativa y de 铆ndole civil o penal.

Se ha publicado en el Moodle de la asignatura la primera convocatoria de evaluaci贸n del curso 2019-20 as铆 como instrucciones para la realizaci贸n del examen telem谩tico.

Se ha publicado en la web (secci贸n problemas) una hoja de problemas sobre algoritmos de programaci贸n din谩mica (usuario y contrase帽a, los dados el primer d铆a de clase).

Son para trabajarlos en casa antes del 31 de marzo.

Se ha聽publicado en la web (secci贸n problemas) una聽hoja de problemas sobre algoritmos de divide y vencer谩s (usuario y contrase帽a, los dados el primer d铆a de clase).

Son para trabajarlos en casa, antes del mi茅rcoles pr贸ximo.