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

sguenos en twitter

La semana próxima empezamos con la técnica de ramificación y poda, una estrategia de búsqueda informada especialmente adecuada para problemas de optimización para los que las técnicas anteriores (dividir para vencer, voraz, programación dinámica, u otras) no dan una solución satisfactoria. Un ejemplo reciente de aplicación es el planteado en este artículo, en el que [...]

. Probablemente este miércoles podamos empezar a trabajar en clase con los problemas de la hoja de programación dinámica. Pero únicamente lo haremos si los habéis trabajado antes vosotros… Para plantear una solución de programación dinámica, normalmente, deben seguirse los pasos siguientes: Definir de manera precisa una función parametrizada tal que, para algunos valores de [...]

En la próxima clase hablaremos de la distancia de edición entre secuencias. 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).

. Punteros a cosas (curiosidades) mencionadas hoy en clase: algoritmo de coste lineal para el cálculo del k-ésimo elemento de un vector (y por tanto para el cálculo de la mediana) orígenes del algoritmo de Karatsuba premio Turing de este año su algoritmo (ojo, hay una errata en esa página; cuando en un párrafo de [...]

. Como vimos ayer en clase, el algoritmo voraz para devolver una cantidad de dinero con el menor número posible de monedas es correcto (es decir, calcula el número mínimo de monedas) para los sistemas de monedas “habituales”, como el del Euro o el Dólar, que suelen denominarse sistemas canónicos de monedas. Sin embargo, en general, [...]

  “Simplex is not a polynomial time algorithm. Certain rare kinds of linear programs cause it to go from one corner of the feasible region to a better corner and then to a still better one, and so on for an exponential number of steps. For a long time, linear programming was considered a paradox, [...]

Utilización de programación lineal para organizar la carga de un avión. Lo escribimos aquí hace ya un tiempo.

Recopilando tuits del TSP
19 mayo 2015 por Javier Campos en cosas de clase,TSP Comentarios

El problema del viajante de comercio se conoce en la literatura internacional como TSP (traveling salesman problem). Libro de William J. Cook: In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Página web del libro (incluye tabla de contenidos y PDF del primer capítulo). Libro de David L. Applegate, Robert E. Bixby, Vašek [...]

Encuestas de docencia
11 mayo 2015 por Javier Campos en cosas de clase,encuestas Comentarios

Desde hoy, 11 de mayo, hasta el próximo día 29, 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 curso próximo se impartirá por primera vez la asignatura optativa “Bioinformática“, de la especialidad de Computación. El próximo miércoles 29 de abril, a las 15:00 h., la presentará en clase (aula 12, edificio Ada Byron) la profesora Elvira Mayordomo. (Transparencias)