.
Los resultados del test intermedio se encuentran en este enlace.
Puede consultarse una solución aquà (acceso restringido, usuario y clave habitual).
Quien desee ver su examen, puede hacerlo en el despacho del profesor.
.
Puede encontrarse una solución del test intermedio aquà (acceso restringido, clave habitual).
.
Las transparencias sobre la solución del problema del viajante de comercio con programación dinámica están basadas en el material del libro: Algorithmics. Theory and Practice, de Gilles Brassard y Paul Bratley (ed. Prentice Hall, 1988). En este enlace (acceso restringido) pueden encontrarse las páginas correspondientes.
.
Hablaremos en clase de la distancia de edición entre secuencias de caracteres.
El problema tiene aplicaciones, entre otras muchas, en los dominios de
- la bioinformática (ver el enlace
http://webdiis.unizar.es/asignaturas/AB/?p=93) y de - la robótica (ver
http://webdiis.unizar.es/asignaturas/AB/?p=1144).
El test intermedio será el miércoles 9 de abril, a las 17:00 horas, en el aula 12 del edificio Ada Byron, sobre los temas: algoritmos voraces y divide y vencerás. Se permitirá usar apuntes pero no dispositivos electrónicos.
Dado que el servidor moodle no está disponible este fin de semana, hemos dejado copia de los enunciados de las hojas 3 y 4 de ejercicios en:
http://webdiis.unizar.es/asignaturas/AB/restringido/ejercicios/
.
En la técnica de divide y vencerás, un ejemplar del problema se divide en ejemplares más sencillos del mismo problema que se resuelven separadamente (son ejemplares, de alguna manera, independientes) y sus soluciones se combinan para crear una solución del ejemplar del problema original.
En el próximo esquema algorÃtmico que veremos en clase, programación dinámica, los subproblemas en que se divide el problema original no son independientes, en el sentido siguiente: los subproblemas comparten subproblemas entre ellos. Por tanto, una solución de divide y vencerás resolverÃa repetidas veces esos subproblemas compartidos, haciendo más trabajo del necesario. En programación dinámica se utiliza la técnica de la memorialización (memoization) para almacenar y reutilizar las soluciones de los subproblemas comunes, evitando resolverlos más de una vez.
.
Sobre el algoritmo RSA que veremos en clase, recordamos esta anotación anterior con algunas curiosidades:
http://webdiis.unizar.es/asignaturas/AB/?p=1078
.
Además de los ejercicios de la hoja 3, se ha planteado en clase el ejercicio que aparece en la transparencia nº 87 de algoritmos voraces. Se trata de plantear un algoritmo de coste lineal para decidir si un conjunto de tareas es independiente (usando la equivalencia 2 del Lema de la transparencia nº 87).
Sólo se admitirá la primera solución recibida de uno de vosotros. Tan pronto como se reciba, se avisará mediante el tablón de moodle de la asignatura.
[Editado a las 20:29 del 10/03/2014] Ya se ha recibido una solución del ejercicio planteado en clase. No se admiten más soluciones. Lo veremos en clase…