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

sguenos en twitter

. No es extraño que en entrevistas de trabajo relacionadas con la Computación aparezcan problemas resolubles mediante programación dinámica. Aquí hay algunos de ellos: What are the top 10 most popular dynamic programming problems among interviewers?  

Multiplicación de enteros en O(n log n)
27 marzo 2019 por Javier Campos en Anuncios,curiosidades,multiplicación Comentarios desactivados

A falta de ser revisado y confirmado por otros expertos, se ha publicado en la Web hace pocos días: “Integer multiplication in time O(n log n)”, por David Harvey y Joris Van Der Hoeven. Esto supondría un avance importante en relación con una conjetura realizada en 1971 por Schonhage y Strassen. Por supuesto, el interés [...]

. El algoritmo conocido como “de Karatsuba y Ofman” para multiplicar enteros de n cifras con un coste asintótico en O(nlog 3)  ( ≈ O(n1,59) )  aparece publicado en el artículo ”Multiplication of multidigit numbers on automata”, A. Karatsuba, Y. Ofman, en el nº 145, pp. 293-294, de las actas de la Academia de Ciencias de [...]

. Leer esta anotación: http://webdiis.unizar.es/asignaturas/AB/?p=1009

Un par de anotaciones sobre el problema del cambio en monedas
14 febrero 2017 por Javier Campos en cosas de clase,curiosidades,monedas,voraces Comentarios desactivados

. Aquí y aquí.

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

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

Prog. dinámica en entrevistas de trabajo
29 abril 2016 por Javier Campos en curiosidades,Problemas,programación dinámica Comentarios desactivados

. No es extraño que en entrevistas de trabajo relacionadas con la Computación aparezcan problemas resolubles mediante programación dinámica. Aquí hay algunos de ellos: What are the top 10 most popular dynamic programming problems among interviewers?

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

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