. . Los siguientes párrafos están extraÃdos de este informe de la Oficina Ejecutiva del Presidente de los Estados Unidos: Report to the President and Congress. Designing a digital future: Federally funded research and development in networking and information technology (página 71, diciembre, 2010). Progress in Algorithms Beats Moore’s Law Everyone knows Moore’s Law –a [...]
. Veremos en clase alguna de las ideas básicas del algoritmo del simplex (ver transparencias 54 a 70 de la asignatura, o transparencias 16 a 36 de estas otras del material adicional). No obstante, su implementación detallada dista de ser sencilla. Por ejemplo, en esta anotación del blog de Jeremy Kun puede encontrarse una descripción [...]
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.
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 [...]