Los algoritmos voraces son relativamente fáciles de entender en comparación con otros esquemas algorítmicos como la ramificación y poda o la programación dinámica. No obstante, encierran una dificultad que le es propia. A saber, cuando nos acogemos a una estrategia voraz debemos demostrar de una manera más o menos formal que la estrategia es válida. Entre los problemas más liosos se encuentran los de planificación temporal. Dentro de este tipo de problemas hay, a su vez, dos modelos típicos: el de uno o varios procesadores que atienden la ejecución de una serie de tareas y cuyo objetivo es minimizar el tiempo medio de permanencia en el sistema; y el de planificar la ejecución de un conjunto de tareas con plazo límite de expiración, de tal manera que se maximice el beneficio obtenido, independientemente de que queden tareas fuera de la planificación. Obviamente, se trata de problemas tipo que luego pueden ser traducidos a múltiples contextos. Hoy os traigo unas diapositivas explicativas de estas dos categorías de problema. Son para un nivel medio-avanzado. Una vez más, están especialmente pensados para los alumnos de Programación III de la U.N.E.D.
26-12-2007: Las transparencias han sido resubidas después de corregir pequeños gazapos en los algoritmos. Ahora también podéis descargar los algoritmos implementados en Java. Se trata de una carpeta con un proyecto BlueJ que incluye, para el ejemplo de las transparencias, las dos posibilidades de implementación de la planificación con plazo fijo.
No hay comentarios:
Publicar un comentario