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

sguenos en twitter

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

El algoritmo del simplex
20 mayo 2016 por Javier Campos en cosas de clase,programación lineal,simplex Comentarios desactivados

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

Sistema de bicicletas de uso compartido
6 mayo 2016 por Javier Campos en cosas de clase,curiosidades,ramificación y poda Comentarios desactivados

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

Problemas de programación dinámica
25 abril 2016 por Javier Campos en cosas de clase,Problemas,programación dinámica Comentarios desactivados

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

Distancia de edición
15 abril 2016 por Javier Campos en Bioinformática,cosas de clase,programación dinámica,robótica Comentarios desactivados

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

Linear programming in polynomial time
26 mayo 2015 por Javier Campos en cosas de clase,curiosidades,Historia,programación lineal Comentarios desactivados

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

Un ejemplo de programación lineal
21 mayo 2015 por Javier Campos en cosas de clase,programación lineal Comentarios desactivados

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 desactivados

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