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