. 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/ (acceso restringido, con la clave facilitada en clase).

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

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