. En la técnica de divide y vencerás, un ejemplar del problema se divide en ejemplares más sencillos del mismo problema que se resuelven separadamente (son ejemplares, de alguna manera, independientes) y sus soluciones se combinan para crear una solución del ejemplar del problema original. En el próximo esquema algorítmico que veremos en clase, programación dinámica, los subproblemas [...]

. Sobre el algoritmo RSA que veremos en clase, recordamos esta anotación anterior con algunas curiosidades: http://webdiis.unizar.es/asignaturas/AB/?p=1078

. Además de los ejercicios de la hoja 3, se ha planteado en clase el ejercicio que aparece en la transparencia nº 87 de algoritmos voraces. Se trata de plantear un algoritmo de coste lineal para decidir si un conjunto de tareas es independiente (usando la equivalencia 2 del Lema de la transparencia nº 87). [...]

. Podría pensarse que el coste de la creación de un montículo (heap) con n elementos está en O(n log n), dado que hay que insertar n datos y cada inserción, en el caso peor, sería O(log n). Pues bien, haciendo el “cálculo fino” (penúltima transparencia de este fichero) puede demostrarse que realmente ese coste está en O(n). Puede [...]

En relación con el problema de fiabilidad de sistemas visto ayer en clase (transparencias 65 a 69 de programación dinámica), tal como discutimos, es necesario garantizar que haya al menos un dispositivo en cada fase (mi ≥ 1,  i = 1…n). Nótese que la ecuación en recurrencias es “hacia atrás”, y por lo tanto el [...]

. Tras detectar hoy en clase que conocíais el concepto de orden de crecimiento inferior (O(-)), pero que no conocíais los de orden de crecimiento superior (Ω(-)) y orden de crecimiento exacto (Θ(-)) de una función, incluyo aquí unas transparencias y este enlace a unos apuntes breves del profesor J.L. Balcázar. (estas dos transparencias y [...]

Hoy estudiaremos en clase el problema del viajante de comercio (TSP, Travelling Salesman Problem), un conocidísimo problema NP-difícil, y veremos una solución de programación dinámica. Hay una página web del Georgia Tech (Georgia Institute of Technology) dedicada a este problema (ver este enlace) que contiene mucho material útil e interesante. Aunque también contiene cosas inútiles… por [...]

En el episodio 74 (código de producción 413) de la serie Numb3rs, Colby muestra un mapa sobre la mesa de Charlie: la ciudad de Los Ángeles con 11 posiciones marcadas con chinchetas. Colby.— It’s a pretty basic GPS, no data on the times or the routes. Charlie.—Just the ten most recent destinations he typed in. Colby.— Gives us eleven points, [...]

. Hoy veremos en clase un problema de comparación de secuencias de caracteres (transparencias 41 a 47 de programación dinámica), concretamente el problema de la distancia de edición entre dos secuencias. La solución de este problema (y de otros similares) tiene aplicaciones en diversos ámbitos, entre ellos la biología computacional, así como, de forma mucho [...]

. En la técnica de divide y vencerás, un ejemplar del problema se divide en ejemplares más sencillos del mismo problema que se resuelven separadamente (son ejemplares, de alguna manera, independientes) y sus soluciones se combinan para crear una solución del ejemplar del problema original. En programación dinámica, los subproblemas en que se divide el [...]