Justificación
¿Por qué lo hacemos?
Uno de los resultados del trabajo aquí presentado es la identificación de dificultades y malas concepciones de los alumnos sobre algoritmos de optimización. La experiencia presentada propone una organización precisa de las prácticas, consistente en pedir a los alumnos la resolución del mismo problema mediante distintas técnicas de diseño. De esta forma, los alumnos no tienen que esforzarse en comprender un nuevo problema con cada práctica, facilitando que se concentren en la técnica de diseño correspondiente. Además, disponen de un intervalo de tiempo razonable para recopilar un conjunto de algoritmos diferentes.
En nuestro caso, cada práctica permite estudiar el diseño e implementación de cada técnica, mientras que en la última práctica de la asignatura se estudia cada técnica solamente desde el punto de vista de su resultado, resaltando su carácter de técnica exacta (es decir, óptima) o inexacta (es decir, subóptima). La última práctica es distinta porque su objetivo principal no es desarrollar un algoritmo sino comparar los algoritmos desarrollados en prácticas anteriores.
Desarrollo
Objetivos
El objetivo principal de la actividad didáctica propuesta es:
“Mejorar la comprensión de las técnicas de diseño de algoritmos de optimización más comunes mediante la experimentación.”
Los objetivos parciales de la realización de la actividad son:
- Diseñar y evaluar una organización adecuada de las prácticas de la asignatura.
- Evaluar la usabilidad de OptimEx.
- Evaluar la comprensión por los alumnos de las diferencias entre técnicas de diseño de algoritmos de optimización que permiten obtener soluciones óptimas y subóptimas.
Organización de las prácticas
Los alumnos debían realizar cinco prácticas obligatorias y cuatro trabajos optativos de profundización sobre algunas partes del temario. Las prácticas fueron:
- Reimplementación de un algoritmo voraz.
- Desarrollo de un algoritmo de vuelta atrás y otro de ramificación y poda.
- Eliminación de redundancia en un algoritmo con recursividad múltiple.
- Desarrollo de un algoritmo de programación dinámica.
- Desarrollo de un algoritmo heurístico y comparación con algoritmos exactos.
La práctica 5 es la más interesante ya que cierra la asignatura dando una visión global de la misma, por lo que a continuación nos centramos en ella. El enunciado de la práctica repetía la especificación del problema de selección de actividades ponderadas, ya conocido por los alumnos. A los alumnos se les exigía que utilizaran OptimEx para comparar la optimidad de al menos 3 algoritmos. Se les proporcionaba un algoritmo voraz basado en orden creciente de duración. Un segundo algoritmo debían tomarlo los alumnos de su práctica 1 y adaptarlo al nuevo problema. Por último, podían tomar otros algoritmos desarrollados en las prácticas 2 y 4. Suponiendo que los algoritmos estuvieran correctamente desarrollados, la respuesta esperada era que los algoritmos de vuelta atrás, ramificación y poda o programación dinámica eran óptimos mientras que los algoritmos voraces, no.
La práctica podía hacerse individualmente o en parejas. La sesión presencial duró 2 horas.
Materiales
Materiales
Los alumnos se podían descargar del campus virtual el material necesario:
- Enunciado de la práctica.
- Herramienta interactiva OptimEx y una pequeña guía de usuario (de 2 páginas).
- Parte de los materiales necesarios para la experimentación: una clase Java con un algoritmo voraz y un fichero con 100 datos de entrada.
La memoria de la práctica debía entregarse en el plazo de una semana y debía tener la siguiente estructura:
- Identificación de la técnica de diseño y código de los algoritmos utilizados.
- Tabla con los resultados de la experimentación.
- Conclusiones.
A los alumnos del grupo presencial también se les entregó al final de la sesión de prácticas un cuestionario de usabilidad sobre la herramienta OptimEx. Su cumplimentación era voluntaria y anónima.
La herramienta interactiva OptimEx
OptimEx es el acrónimo de “OPTIMization EXperimentation”. El objetivo de OptimEx es permitir al alumno experimentar con distintos algoritmos para un mismo problema de optimización, comparándolos y determinando su optimidad o suboptimidad. En este último caso, también se calcula su desviación respecto a la solución óptima. OptimEx permite experimentar con cualquier algoritmo codificado en Java, siempre que los algoritmos a comparar estén codificados en una sola clase y que su cabecera sólo contenga tipos de datos predefinidos.
Fig. 1. Interfaz de usuario de OptimEx tras experimentar con cuatro algoritmos para el problema de la selección de actividades ponderada
Fig. 2. Tabla de resumen tras experimentar con 4 algoritmos y 100 datos de entrada para el problema de la selección de actividades ponderada.
Resultados
Metodología de Análisis
Los aspectos analizados finalmente fueron: errores y dificultades de los alumnos, actitudes y autoconocimiento, y malas concepciones sobre la materia (algoritmos de optimización).
Equipo docente
-
J. Ángel Velázquez
Licenciado en Informática (1985) y Doctor en Informática (1990) por la Universidad Politécnica de Madrid, España. Ha sido profesor desde 1985 en la Facultad de Informática de la Universidad Politécnica de Madrid. En 1997 se incorporó a la Universidad Rey Juan Carlos. Actualmente está adscrito a la Escuela Técnica Superior de Ingeniería Informática, siendo Catedrático de Universidad y director del Laboratorio de Tecnologías de la Información en la Educación (LITE). Es autor de más de un centenar de publicaciones nacionales e internacionales en libros, revistas y congresos. Sus áreas de investigación son innovación docente en programación, software educativo para la enseñanza de la programación y visualización del software. El Prof. Velázquez es miembro de IEEE Computer Society, IEEE Education Society, ACM y ACM SIGCSE. Actualmente es Presidente de la Asociación para el Desarrollo de la Informática Educativa (ADIE), sociedad científica integrada en la Confederación de Sociedades Científicas de España (COSCE).