Enseñanza de los algoritmos de programación exhaustivos desde un modelo docente constructivista

Esta obra se distribuye con la licencia Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional (CC BY-NC-ND 4.0.) 2439 Enseñanza de los algoritmos de programación exhaustivos desde un modelo docente constructivista Andrés Jiménez Ramírez Enseñanza de los algoritmos de programación exhaustivos desde un modelo docente constructivista Teaching of the exhaustive programming algorithms from a constructivist educational model Andrés Jiménez Ramírez ORCID: https://orcid.org/0000-0001-8657-992X Universidad de Sevilla Departamento de Lenguajes y Sistemas Informáticos ajramir[email protected] DOI: http://dx.doi.org/10.12795/9788447222865.139 Pp.: 2439-2456 Esta obra se distribuye con la licencia Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional (CC BY-NC-ND 4.0.) 2440 Enseñanza de los algoritmos de programación exhaustivos desde un modelo docente constructivista Andrés Jiménez Ramírez Resumen Dentro del Grado de ingeniería informática – ingeniería de computadores se ha desarrollado un ciclo de mejora de 8 horas donde se enseña la programación con algoritmos exhaustivos dentro de la asignatura Análisis y Diseño de Datos y Algoritmos. Este ciclo de mejora contempla un proceso metodológico donde las actividades de ideación y debate toman especial relevancia. El artículo contiene el mapa de contenidos y los cuestionarios inicial y final que sirven para comprobar si se ha producido aprendizaje en los alumnos. Tanto las sensaciones del profesor como los resultados de las escaleras de aprendizaje fueron positivos, aunque se identificaron punto de mejora para futuros ciclos de mejora. Palabras clave: Análisis y diseño de datos y algoritmos, Ingeniería del Software, Experimentación docente universitaria, Innovación docente, Algoritmos exhaustivos. Abstract Within the Degree of Software Engineering – Computer Engineering, an improvement cycle of 8 hours has been developed where programming with exhaustive algorithms is taught within the subject Analysis and Design of Data and Algorithms. This improvement cycle contemplates a methodological process where ideation and discussion activities take special relevance. The article contains the content map and the initial and final questionnaires that are used to check if the students’ learning has taken place. Both the teacher’s feelings and the results of the learning ladders were positive, although points for improvement were identified for future improvement cycles. Keywords: Analysis and design of data and algorithms, Software engineering, University teaching experimentation, Teaching innovation, Exhaustive algorithms. Esta obra se distribuye con la licencia Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional (CC BY-NC-ND 4.0.) 2441 Enseñanza de los algoritmos de programación exhaustivos desde un modelo docente constructivista Andrés Jiménez Ramírez Descripción del contexto Esta asignatura, Análisis y Diseño de Datos y Algoritmos, se imparte en 2º del Grado de Ingeniería de Computadores. Las sesiones son los lunes a las 8:30 y son de 1 hora y 50 minutos de duración. El grupo se compone de unos 15 alumnos. La mayoría de los alumnos están presentes desde el principio de la clase, pero algunos van llegando durante la primera media hora. Este ciclo comienza con la asignatura ya avanzada e incluye 4 sesiones. El tema de «Algoritmos genéticos» se terminó en la clase anterior dejando planteado un ejercicio para la siguiente clase. En la primera sesión se plantea enseñar a resolver ese problema concluyendo el tema de «Algoritmo Genéticos» y empezar con el tema de «Programación Dinámica y Backtracking» que se mantendrá durante las siguiente 4 sesiones. El resto del documento se organiza como sigue. En la sección 1 se presenta el diseño del ciclo de mejora para lo cual se han tomado como referencia algunos estudios en el campo de la innovación en la docencia universitaria (Rivero y Porlán, 2017; Finkel 2008) y experiencias similares realizada por profesores de la Universidad de Sevilla (Navarro Medina y Porlán, 2020). En la sección 2 se describe la aplicación del propio ciclo de mejora. Finalmente, la sección 3 incluye la evaluación personal que ha surgido de realizar esta experiencia. Diseño previo del CIMA Mapa de contenidos El mapa de contenidos de la figura 1 se describe con este resumen: — Para resolver problemas del tipo del caballo o la mochila hay que atacar dos objetivos: (1) Generalizar el problema y (2) modelar el algoritmo. — Generalizar implica decidir qué atributos tiene el problema e indicar cuáles los definen y cuáles están relacionados con el tamaño de este. — Para modelar el problema, hemos de saber si buscamos la mejor solución, o una aproximación. Aquí hay que pensar sobre el tiempo, la memoria y la precisión de los diferentes algoritmos. — Para los algoritmos exhaustivos tenemos tres técnicas similares en las cuales hay que discutir si podemos usar heurísticas para que el algoritmo vaya más rápido. En el caso concreto en que la generalización resultase compleja, solo se podría usar la técnica de programación dinámica. — Para los algoritmos aproximados, vemos la técnica voraz que es una simplificación de Backtracking. 2442 Enseñanza de los algoritmos de programación exhaustivos desde un modelo docente constructivista Andrés Jiménez Ramírez Esta obra se distribuye con la licencia Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional (CC BY-NC-ND 4.0.) Figura 1. Mapa de contenidos. Esta obra se distribuye con la licencia Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional (CC BY-NC-ND 4.0.) 2443 Enseñanza de los algoritmos de programación exhaustivos desde un modelo docente constructivista Andrés Jiménez Ramírez Más precisamente, el anterior mapa muestras 4 grandes bloques de color. En primer lugar, en el bloque amarillo, se muestran las 2 preguntas/ problemas principales que rigen el mapa y que motivan los dos contenidos procedimentales principales (los óvalos): la generalización de problemas y el modelado de algoritmos. Por un lado, con respecto a la generalización de problemas, se plantean tres conceptos factuales que, a su vez, están relacionado con este contenido procedural: hay que saber cuáles son los «atributos» en la generalización y cuáles tiene que usarse para definir el concepto de «igualdad» y «tamaño» de problemas. Por otro lado, con respecto al modelo de algoritmos, se plantea el desafío de saber decidir cuándo se ha de usar uno exhaustivo frente a uno aproximado. En segundo lugar, en el bloque azul, se muestran los contenidos relacionados concretamente con los algoritmos exhaustivos. Los tres algoritmos que se estudian en la asignatura, y que se entienden como contenido conceptual (las cajas), son los grafos virtuales, el Backtracking (también llamado Vuelta atrás) y la programación dinámica (Kennedy, 1986; Golomb y Baumert, 1965). Hay un concepto avanzado que solo se aplica a la programación dinámica que son los «problemas no reducibles», de ahí que su sombra roja solo solape con este tipo de algoritmo. Con respecto a los tres algoritmos anteriores, se plantea como contenido procedimental, el saber cómo generar heurísticas y, dentro de este contenido, son relevantes los conceptos de «admisibilidad» y «eficiencia» de la heurística. El hecho de que el algoritmo de grafos virtuales este sombreado en gris indica que ese contenido es parte de otra parte de la asignatura, aunque está relacionada con esta. En tercer lugar, en el bloque verde se visualizan los algoritmos aproximados, tan solo el algoritmo voraz se ve en esta parte de la asignatura, el algoritmo genético se ve en otro momento y por eso está sombreado. Por último, en el bloque naranja rayado con el texto «Actitudes» de fondo se han dejado aquellos conceptos actitudinales que son relevantes para esta parte de la asignatura y que se aplican, sobre todo, al hecho de elegir un tipo de algoritmo a la hora de resolver un problema dado. Modelo metodológico El modelo metodológico de la figura 2 tiene como base el modelo metodológico constructivista (Bain, 2007), y potencia más el trabajo de ideación del alumno previo a la muestra de la solución posible por parte del docente, de manera que permita generar actividades de contraste. Esta obra se distribuye con la licencia Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional (CC BY-NC-ND 4.0.) 2444 Enseñanza de los algoritmos de programación exhaustivos desde un modelo docente constructivista Andrés Jiménez Ramírez Figura 2. Modelo metodológico posible. Secuencia de actividades La secuencia detallada de las actividades que se proponen para este ciclo de mejora se divide en 4 días como se muestran en las tablas 1-4. Es importante destacar que, aunque las clases fueran de 1 hora y 50 minutos, no todos los días suman dicha cantidad por tener algún margen de tiempo. Tabla 1. Secuencia de actividades del día 1 1 Cuestionario Inicial 20 min Los alumnos responden individualmente el cuestionario, preguntando sus dudas si hace falta. Conocer el punto de partida del alumno. Que el alumno reflexione. 2 CP Contextualización: programación dinámica y problema de la mochila 25 min Presentar el tema actual y contar los orígenes que llevan a la programación dinámica. Así como describir cómo se puede plantear la resolución del problema de la mochila desde esa perspectiva. Que los alumnos vean cómo se idea el algoritmo de programación dinámica y prepararlos para la abstracción metodológica. Programación Dinámica, Problema de la mochila y Generalización de problemas. 3 IA Ideación del alumno a través de taller conceptual 45 min Realizar el taller: «creación de mi algoritmo de programación dinámica» en grupos. Que los alumnos hagan suyo este algoritmo y recapaciten sobre sus detalles. Programación Dinámica y Generalización de problemas Esta obra se distribuye con la licencia Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional (CC BY-NC-ND 4.0.) 2445 Enseñanza de los algoritmos de programación exhaustivos desde un modelo docente constructivista Andrés Jiménez Ramírez 4DA-AC Debate entre alumnos con incorporación de ideas del profesor 20 min Exposición por grupos de las conclusiones del taller y debate entre ellos. El profesor va reconduciendo la discusión hacia los puntos más conflictivos y poniendo en sobre el debate, si no sale, contenidos actitudinales. Que los alumnos se esfuercen en defender sus algoritmos y aprendan las debilidades detectadas por otros compañeros además de recapacitar sobre sus ideas preconcebidas. Programación Dinámica, Generalización de problemas y Actitudes sobre precisión, tiempo y memoria. Tabla 2. Secuencia de actividades del día 2 5 CR Conclusiones de la programación dinámica 10 min Conclusión, por parte del profesor, de los elementos más relevantes discutidos anteriormente. Que los alumnos verifiquen y validen lo aprendido en el taller. Programación Dinámica, Generalización de problemas y Actitudes sobre precisión, tiempo y memoria. 6 E Evaluación 15 min Evaluación rápida sobre conceptos clave. Que los alumnos verifiquen y validen lo aprendido en el taller. 7 CP Contextualización: Marco de trabajo en la asignatura 45 min Describir cómo se trabaja en la asignatura con los algoritmos exhaustivos como la programación dinámica. Introducir también los componentes de ese marco de trabajo para Backtracking. Que los alumnos asimilen una forma de trabajar común que es la que se usa en la asignatura y, además, entiendan los conceptos básicos de Backtracking y el problema del caballo. Programación Dinámica, Backtracking y Modelado. 8 IA Ideación de los alumnos sobre modelado 35 min Organizar a los alumnos en grupos para que trabajen sobre el modelado de los algoritmos para el problema del caballo y de la mochila usando el marco de trabajo de la asignatura. Que los alumnos entiendan que ambos problemas son similares cuando se abstraen con modelos muy similares. Programación Dinámica, Backtracking y Modelado. Esta obra se distribuye con la licencia Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional (CC BY-NC-ND 4.0.) 2446 Enseñanza de los algoritmos de programación exhaustivos desde un modelo docente constructivista Andrés Jiménez Ramírez Tabla 3. Secuencia de actividades del día 3 9DA-AC Debate entre alumnos con incorporación de ideas del profesor 30 min Discusión sobre las diferentes alternativas de modelado de problemas. El profesor va reconduciendo la discusión hacia los puntos más conflictivos y poniendo sobre el debate, si no sale, contenidos actitudinales. Que los alumnos vean que hay diferentes alternativas a la hora de modelar y que entiendan que afectan a la velocidad y consumo de memoria. Modelado, Actitudes sobre tiempo y memoria. 10 CP Contextualización sobre otros posibles problemas 20 min Descripción de otros problemas similares al del caballo y la mochila que pueden ser resueltos mediante Backtracking y programación dinámica (e.g., el de los saltos o las jarras, ver Anexo). Hacer ver, además, que estos algoritmos repiten demasiados cálculos. Poner a los alumnos en predisposición para ver esos problemas como ejemplos particulares de los anteriores. Modelado, Generalización de problemas, Actitudes sobre tiempo y memoria. 11 IA Ideación sobre modelado y eficiencia 30 min Organizar a los alumnos en grupo para que resuelvan el problema de las jarras y los saltos y, además, para que busquen dónde los algoritmos de Backtracking y programación dinámica repiten más cálculos, proponiendo alternativas para evitarlo. Que los alumnos se ejerciten en diferentes generalizaciones de problemas y modelado de algoritmos y piensen por primera vez en heurísticas que puedan aumentar la eficiencia. Modelado, Generalización de problemas, Heurísticas, Actitudes sobre tiempo y memoria. 12 DA-AC Debate entre alumnos con incorporación de ideas del profesor 20 min Discusión sobre las generalizaciones y modelos y, luego, sobre las propuestas de heurísticas. El profesor va reconduciendo la discusión hacia los puntos más conflictivos y poniendo sobre el debate, si no sale, contenidos actitudinales. Que los alumnos vean que hay diferentes alternativas a la hora de modelar y también a la hora de proponer heurísticas. Modelado, Generalización de problemas, Heurísticas, Actitudes sobre tiempo y memoria. Tabla 4. Secuencia de actividades del día 4 13 CP Contextualización: Algoritmos aproximados 15 min Describir contextos donde la precisión no es tan relevante como la velocidad, planteado como un problema en sí. Que los alumnos entiendan que los algoritmos exhaustivos no son la «panacea» y deben existir otros. Algoritmos aproximados, Actitudes sobre precisión y tiempo. 14 IA Ideación de los alumnos sobre algoritmos voraces 35 min Organizar a los alumnos en grupos para que trabajen sobre posibles modificaciones del algoritmo de Backtracking para que consigan obtener soluciones aproximadas para los problemas anteriores sin tener que cambiar la generalización de estos. Esta obra se distribuye con la licencia Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional (CC BY-NC-ND 4.0.) 2447 Enseñanza de los algoritmos de programación exhaustivos desde un modelo docente constructivista Andrés Jiménez Ramírez Que los alumnos hagan suyo el algoritmo voraz y lo vean como una simplificación del Backtracking. Voraz. 15 DA-AC Debate entre alumnos con incorporación de ideas del profesor 20 min Discusión sobre las diferentes alternativas de algoritmos voraces. El profesor va reconduciendo la discusión hacia los puntos más conflictivos y poniendo sobre el debate, si no sale, contenidos actitudinales. Que los alumnos puedan ver y evaluar diferentes alternativas de algoritmos voraces junto a sus limitaciones. Voraz, Actitudes sobre precisión, tiempo y memoria. 16 CR Conclusiones de algoritmos exhaustivos y aproximados 20 min Conclusión, por parte del profesor, de los elementos más relevantes de los algoritmos exhaustivos de las clases anteriores y los aproximados de la clase de hoy. Que los alumnos verifiquen y valides lo aprendido. Todo. 19 E Cuestionario final 20 min Los alumnos responden individualmente el cuestionario sin hacer preguntas. Conocer el punto de nivel de aprendizaje al que han llegado los alumnos. Cuestionario Inicial y Final Con el objetivo de valorar si se ha producido aprendizaje por parte del alumno, se pretende realizar un cuestionario al principio y al final de las actividades planteadas. Dichas preguntas están formuladas de tal manera que el alumno se siente cómo a la hora de responder. Para ello, se formulan en lenguaje coloquial y, además, pueden usar un pseudónimo a la hora de responder. Dicho pseudónimo sirve para anonimizar las repuestas del alumno, pero permite un análisis individual a posteriori. Las preguntas que se plantean para los cuestionarios inicial y final son las siguientes: 1. ¿Cómo sería un algoritmo que resolviera un problema como «los pasos que tiene que dar un caballo para que visite todas las casillas de un tablero sin repetirlas»? 2. ¿Cuántos pasos daría tú algoritmo para un tablero de 4x3? Arguméntalo 3. ¿Qué opciones de moverse tiene el caballo en cada paso? 4. Si conoces el nombre de algunos algoritmos que permitan resolver problemas como este, nómbralos o descríbelos si no te acuerdas del nombre. 5. ¿Se te ocurre cómo podrías adaptar ese algoritmo para el problema de «maximizar el valor de una mochila, considerando un conjunto Esta obra se distribuye con la licencia Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional (CC BY-NC-ND 4.0.) 2454 Enseñanza de los algoritmos de programación exhaustivos desde un modelo docente constructivista Andrés Jiménez Ramírez De los 17 alumnos que respondieron los cuestionarios, solo 8 respondieron a los dos. Esto se pudo identificar gracias a que se le pidió un pseudónimo que utilizaron en ambos casos. Es por ello por lo que algunos niveles aparecen con 0 % tanto en el inicial como final, ya que los alumnos que no respondieron a ambos han sido filtrados. En la figura 3 puede observarse un análisis individualizado por alumno de cada una de las preguntas. Figura 3. Mapa de niveles inicial y final de los alumnos que respondieron ambos cuestionarios. Aunque se observa una mejoría sustancial general en el aprendizaje del alumno, también pueden identificarse algunos casos en los que parece haberse empeorado. Analizando las respuestas, vemos que algunos alumnos han respondido vagamente a la pregunta en el cuestionario final, no incluyendo detalles que sí habían incluido en el inicial. Por ejemplo, el alumno 2 responde inicialmente a la pregunta 2: «Daría (siempre que tenga solución), el número de casillas del tablero -1» que es una respuesta Esta obra se distribuye con la licencia Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional (CC BY-NC-ND 4.0.) 2455 Enseñanza de los algoritmos de programación exhaustivos desde un modelo docente constructivista Andrés Jiménez Ramírez de nivel 3. Sin embargo, esta es su respuesta en el cuestionario final: «Daría 11 pasos, tantos como casillas tenga el tablero quitando la inicial» que es una respuesta de nivel 2 (cf. tabla 5). Observando las respuestas a las preguntas 7 y 8, se ve como el nivel superior, el 2, es raramente alcanzado. Esto es debido a que estas preguntas, en sí, son de carácter avanzado y no todos los alumnos llegan aún a entenderlo al completo. El aprendizaje ocurre, no obstante, al verse incrementado el número de alumnos en el nivel intermedio, el 1. En general, puede decirse que se observa un claro aprendizaje ya que los niveles bajos se ven reducidos en beneficio de los niveles altos, es decir, los alumnos están ahora en una escala de aprendizaje superior al que estaban inicialmente. Observándose los valores medios, también puede concluirse que, salvo pequeñas excepciones: 1. Las 8 preguntan demuestran que se ha producido un incremento en el aprendizaje de la clase en general. 2. Las respuestas de los alumnos individualmente demuestran que en todos se ha producido aprendizaje. Evaluación del CIMA Personalmente, a nivel global, este CIMA lo considero positivo. Al ser más largo ha permitido estructurar los contenidos de una manera más estratégica. Aunque mi sensación es que se han dado menos contenidos que con el modelo transmisivo tradicional, aunque sí que sé que los alumnos los han asimilado mejor. Por otro lado, me ha servido para conocer que los alumnos nos tenían los conocimientos que los profesores de la asignatura damos por hecho que tienen, por lo que no están del todo preparados para recibir lo que se les planteaba dar. Con respecto a las debilidades de este CIMA, aunque se había previsto tener cierto margen de tiempo en cada sesión, este ha resultado insuficiente. Las actividades no estaban del todo bien dimensionadas y me he visto obligado a partir en varias sesiones lo que, a priori, estaba diseñado para una. No obstante, esto ha supuesto alguna sorpresa positiva en algún caso ya que los alumnos mantenían la «tarea» fuera del aula. Como mejora del CIMA planteo: — Ampliar los tiempos de debate tras las actividades de ideación integrándolas con las actividades de conclusiones, ya que muchas de las cosas que se trataban en las conclusiones tenían más sentido tratarlas directamente cuando se discutían en el debate. — Añadir actividades que puedan ser realizadas fuera del tiempo del aula con el objetivo de que el alumno llegue preparado a clase. Esta obra se distribuye con la licencia Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional (CC BY-NC-ND 4.0.) 2456 Enseñanza de los algoritmos de programación exhaustivos desde un modelo docente constructivista Andrés Jiménez Ramírez — Buscar lecturas o extractos de lecturas que los alumnos puedan procesar durante o antes de la sesión como fuente externa. — Buscar recursos de imagen o vídeo que permitan al alumno ver de una manera gráfica los estados y evolución de los algoritmos que se enseñan en este bloque de la asignatura. Referencias bibliográficas Bain, K. (2007). Lo que hacen los mejores profesores universitarios. Valencia: Universitat de València. Finkel, D. (2008). Dar clase con la boca cerrada. Valencia: Universitat de València. Kennedy, J.O.S. (1986) Introduction to Dynamic Programming. En: Dynamic Programming (pp. 27-49). Dordrecht: Springer. Navarro Medina, E. y Porlán, R. (2020). Ciclos de mejora en el aula. Año 2019. Experiencias de innovación docente de la Universidad de Sevilla. Sevilla: Editorial de la Universidad de Sevilla. https://doi.org/10.12795/9788447221912. Rivero, A. y Porlán, R. (2017) La evaluación en la enseñanza universitaria. En R. Porlán (Coord.), Enseñanza universitaria. Cómo mejorarla (pp. 73-91). Madrid: Ediciones Morata. Golomb, S.W. y Baumert, L.D. (1965). Backtrack Programming. Journal of ACM, 12 (4), 516-524. https://doi.org/10.1145/321296.321300. Vygotsky, L. (1989). El desarrollo de los procesos psicológicos superiores. Barcelona: Crítica.