Enseñanza de la Recursividad mediante Problemas Combinatorios Equivalentes
| Autor | Manuel Rubio Sánchez |
| Cargo del Autor | Universidad Rey Juan Carlos. Departamento de Lenguajes y Sistemas Informáticos I |
| Páginas | 41-54 |
Page 41
La recursividad es un concepto básico de programación, y por tanto necesario en el plan de estudios de una carrera en Informática. Juega un papel importante en la adquisición de competencias asociadas a la abstracción funcional y la descomposición de problemas a través del concepto de inducción. Sin embargo, los alumnos de Informática generalmente tienen dificultades para dominar la recursividad. Varios autores han intentado identificar factores (modelos conceptuales y computacionales, estilos cognitivos de aprendizaje, razonamientos sobre abstracción funcional) responsables de estos obstáculos [1,2,3,4]. Otros han propuesto métodos diseñados para paliar estos problemas mediante visualizaciones del árbol de recursión o activación [5,6], o a través de animaciones tridimensionales [7]. Estudios adicionales proponen metodologías docentes, como la presentación de conceptos en pasos graduales (primero gramáticas, luego lenguajes funcionales, y finalmente recursividad en lenguajes imperativos) [8].
La recursividad suele explicarse en los primeros cursos de programación con la ayuda de funciones matemáticas, como el factorial, la potencia, o los coeficientes binomiales. Una característica interesante que comparten estas funciones es su relación con la combinatoria (permutaciones, variaciones con repetición, y combinaciones). Sin embargo, la mayoría de libros de texto sólo se centran en sus definiciones recursivas, en lugar de aportar problemas (combinatorios) que puedan descomponerse de manera recursiva, y cuyas soluciones exhiban la misma estructura inherente a las funciones.
Page 42
[VER PDF ADJUNTO]
Fig. 1. Diferentes formas de hallar la solución a un problema combinatorio de conteo.
La Fig. 1 muestra cómo el número de permutaciones posibles de n elementos diferentes puede descomponerse mediante fn = n·fn-1, con f0=f1=1 (fn = n!). El caso base es trivial (para que coincida con la función factorial f0 debe ser interpretado como 1). En el caso recursivo, fijando un elemento en la primera posición, habrá fn-1 formas de ordenar n-1 elementos. Como hay n posibilidades de escoger el primer elemento, y es necesario sumar todas, fn = n·fn-1.
Dada la abundancia de ejemplos combinatorios básicos, existe una amplio abanico de valiosos problemas combinatorios para la enseñanza de la recursividad [9,10,11]. Otra rica clase de problemas combinatorios de conteo está relacionada con los números de Fibonacci [12,13,14]:
[VER PDF ADJUNTO]
Una colección de estos problemas se encuentra en [15]. Los más sencillos pueden descomponerse fácilmente según fn = fn-1 + fn-2, como el número de formas de subir una escalera de n peldaños, subiendo uno o dos en cada paso (problema Leonardo's leaps). Problemas más complejos necesitan utilizar otras identidades de números de Fibonacci (por ejemplo, pueden necesitar el cálculo de los términos pares o impares de la secuencia de Fibonacci, en cuyo caso la regla recursiva es fn = 3fn-1 - fn-2).
La combinatoria ofrece una fuente rica de problemas para transmitir conceptos asociados a la recursividad, como la inducción o la descomposición de problemas [10]. Aunque existen estrategias ampliamente conocidas para resolver estos problemas, como el uso de funciones generatrices o procedimientos recursivos, este artículo se centra el la ``equivalencia de problemas'', que en este contexto se refiere a la existencia de un isomorfismo (es decir, identidad estructural) entre dos problemas. La habilidad para reconocer problemas equivalentes es importante en las Matemáticas y en la Informática. Por ejemplo, es fundamental en el estudio de la NP-completitud. Los problemas NP-completos forman una de las clases de problemas más importantes e interesantes dentro del campo de la Informática. Aunque muchos de los problemas parecen ser sencillos, y aparentan ser similares a otros que pueden resolverse en tiempo polinómico, se cree que son intratables. Si podemos establecer la equivalencia o reducción entre cualquier problema NP-completo y un problema dado, este último también sería NP-completo, por lo que sería preferible buscar una buena aproximación que una solución exacta.
Page 43
De esta manera, independientemente del nivel de profundidad con la que los estudiantes de Informática estudien la teoría de la complejidad computacional, es importante que sepan reconocer las relaciones entre problemas y posibles equivalencias o reducciones. Este artículo propone el uso de una serie de problemas combinatorios asociados a números de Fibonacci, que pueden ser englobadas en varias clases de problemas equivalentes, con dos objetivos: (1) reforzar el aprendizaje de la recursividad (especialmente la descomposición de problemas y la inducción), y (2) introducir la equivalencia de problemas.
El resto del artículo se estructura de la siguiente manera. La Sec. 2 presenta el concepto de isomorfismo para problemas combinatorios de conteo, y cómo pueden resolverse utilizando la idea equivalencia entre problemas. La Sec. 3 describe varios conjuntos de problemas equivalentes de Fibonacci, analizando en detalle la estrecha relación entre varios problemas. Finalmente, la Sec. 4 contiene una discusión y las principales conclusiones.
[VER PDF ADJUNTO]
Fig. 2. Diferentes formas de hallar la solución a un problema combinatorio de conteo.
Existen numerosas técnicas (funciones generatrices, reglas recursivas, etc.) para resolver problemas combinatorios de conteo. En este artículo presentamos una forma alternativa para hallar su solución: demostrar la existencia de un isomorfismo (equivalencia) entre dos problemas...
Para continuar leyendo
Solicita tu prueba