enseñanza de la recursividad mutua: un caso de … · combinatorios conejos de fibonacci ......

Ensenanza de la Recursividad Mutua:Un Caso de Estudio

Manuel Rubio Sanchez

LITE, DLSI I, Universidad Rey Juan Carlos

27 de mayo, 2008

SITIAE’08: Seminario de Investigacionen Tecnologıas de la Informacion

Aplicadas a la Educacion

Ensenanza de laRecursividad

Mutua: Un Casode Estudio

SITIAE’08

Contenido

Ensenanza de laRecursividadMutua

Torres de HanoiCıclicas

ProblemasCombinatorios

Conejos de Fibonacci

Steven and Todd

Control de AguasResiduales

Experimentos yResultados

Discusion yConclusiones

Contenido

Ensenanza de la Recursividad Mutua

Problemas Combinatorios

Experimentos y Resultados

Discusion y Conclusiones

Manuel Rubio Sanchez 27 de mayo, 2008 2/35

SITIAE’08

Contenido

Steven and Todd

Contenido

SITIAE’08

Contenido

Steven and Todd

Contenido

SITIAE’08

Contenido

Steven and Todd

Contenido

SITIAE’08

Contenido

Steven and Todd

Contenido

SITIAE’08

Contenido

Steven and Todd

Cuestiones sobre la ensenanza de larecursividad mutua

Dificultad¿Es realmente mas difıcil que la recursividad directa?

Importancia¿Es importante de cara al aprendizaje de larecursividad?

Percatacion¿Los alumnos saben reconocerla?

Aplicacion¿Ayuda a la hora de disenar algoritmos?

Ejercicios didacticos¿Que ejercicios podemos plantear a los alumnos?

SITIAE’08

Contenido

Steven and Todd

SITIAE’08

Contenido

Steven and Todd

SITIAE’08

Contenido

Steven and Todd

SITIAE’08

Contenido

Steven and Todd

SITIAE’08

Contenido

Steven and Todd

Escasez de ejemplos

Ejemplo

Paridad de un numero entero no-negativo

es impar(n) =

{FALSO si n = 0es par(n − 1) si n > 0

es par(n) =

{VERDADERO si n = 0es impar(n − 1) si n > 0

¡Suele ser el unico ejemplo de recursividad mutua en libros ycursos de introduccion a la programacion!

SITIAE’08

Contenido

Steven and Todd

Escasez de ejemplos

Ejemplo

Paridad de un numero entero no-negativo

es impar(n) =

{FALSO si n = 0es par(n − 1) si n > 0

es par(n) =

{VERDADERO si n = 0es impar(n − 1) si n > 0

¡Suele ser el unico ejemplo de recursividad mutua en libros ycursos de introduccion a la programacion!

SITIAE’08

Contenido

Steven and Todd

Torres de Hanoi Cıclicas

Enunciado

Variante de la Torres de Hanoi, en la que los discos solopueden moverse en una “direccion”

SITIAE’08

Contenido

Steven and Todd

Torres de Hanoi CıclicasMovimiento en el sentido de las agujas del reloj

SITIAE’08

Contenido

Steven and Todd

Torres de Hanoi CıclicasMovimiento en el sentido contrario al de las agujas del reloj

SITIAE’08

Contenido

Steven and Todd

Torres de Hanoi CıclicasPseudocodigo basado en recursividad mutua

Reloj(n,X,Y,Z)

si n>0

AntiReloj(n-1,X,Z,Y)Mueve el disco n de X a YAntiReloj(n-1,Z,Y,X)

AntiReloj(n,X,Z,Y)

si n>0

AntiReloj(n-1,X,Z,Y)Mueve el disco n de X a YReloj(n-1,Z,X,Y)Mueve el disco n de Y a ZAntiReloj(n-1,X,Z,Y)

SITIAE’08

Contenido

Steven and Todd

Contenido

SITIAE’08

Contenido

Steven and Todd

Problemas combinatorios para la ensenanzade la recursividad

Soluciones recursivasAlgunos admiten soluciones recursivas sencillasRelacion con: factorial, potencia, coeficientesbinomiales, numeros de Fibonacci. . . )

Problemas realesEl enfasis no recae sobre definiciones matematicasRefuerzan la descomposicion de problemas y lainduccion

Proponemos varios problemas relacionados connumeros de Fibonacci

Modelado mas sencillo e intuitivo utilizando recursividadmutuaDemostraciones mas sencillas

SITIAE’08

Contenido

Steven and Todd

SITIAE’08

Contenido

Steven and Todd

SITIAE’08

Contenido

Steven and Todd

SITIAE’08

Contenido

Steven and Todd

SITIAE’08

Contenido

Steven and Todd

SITIAE’08

Contenido

Steven and Todd

SITIAE’08

Contenido

Steven and Todd

SITIAE’08

Contenido

Steven and Todd

SITIAE’08

Contenido

Steven and Todd

Problema de los conejos de Fibonacci

Enunciado

Calcular el tamano de una poblacion de conejos en undeterminado mes segun las siguientes reglas:

Al principio del primer mes, una pareja de conejosrecien nacidos – un macho y una hembra – soncolocados en un prado;

los conejos tardan un mes en madurar y nunca mueren;

los conejos maduros tardan otro mes en generar unanueva pareja de conejos recien nacidos;

la hembra siembre da a luz a un macho y a una hembra,desde el segundo mes en adelante, los cuales solo sereproduciran entre ellos.

SITIAE’08

Contenido

Steven and Todd

Problema de los conejos de FibonacciProceso de crecimiento

SITIAE’08

Contenido

Steven and Todd

SITIAE’08

Contenido

Steven and Todd

SITIAE’08

Contenido

Steven and Todd

SITIAE’08

Contenido

Steven and Todd

SITIAE’08

Contenido

Steven and Todd

SITIAE’08

Contenido

Steven and Todd

Fn = Fn−1 + Fn−2

SITIAE’08

Contenido

Steven and Todd

Problema de los conejos de FibonacciDistinguir entre bebes y adultos: recursividad mutua

Fn = Fn−1 + Fn−2

= Adultosn + BebesnManuel Rubio Sanchez 27 de mayo, 2008 14/35

SITIAE’08

Contenido

Steven and Todd

Problema de los conejos de FibonacciUtilizando una tabla tambien se aprecia la recursividad mutua

SITIAE’08

Contenido

Steven and Todd

Problema de los conejos de FibonacciAlgoritmo

Bebesn =

{1 si n = 1Adultosn−1 si n 6= 1

Adultosn =

{0 si n = 1Adultosn−1 + Bebesn−1 si n 6= 1

Adultosn + Bebesn = Fn

SITIAE’08

Contenido

Steven and Todd

Problema de los conejos de FibonacciGeneralizacion

{βb si n = 1βr +An−1 si n ≥ 2

{αb si n = 1αr +An−1 + Bn−1 si n ≥ 2

An + Bn + αr + βr = An+1 + βr = Bn+2 =

= βbFn + (βr + αb)Fn+1 + αrFn+2 − αr

SITIAE’08

Contenido

Steven and Todd

Problema de los conejos de FibonacciModelado alternativo

Fn = 1 +n−2∑i=1

{1 si n = 1, 21 + Hn−2 si n ≥ 3

{0 si n = 0Fn + Hn−1 si n ≥ 1

SITIAE’08

Contenido

Steven and Todd

Problema Steven and Todd

Enunciado

Considerese la secuencia α = {a1, a2, . . . , ak}, de unsubconjunto de los n primeros enteros positivos, que hansido ordenados de manera ascendente(1 ≤ a1 < a2 < · · · < ak ≤ n).

Calcular el numero total tn de secuencias α que empiezan enun numero impar, y posteriormente alternan en paridad. Esdecir,

α = {impar,par, impar,par, . . .}?

La solucion al problema es:

tn = tn−1 + tn−2 = Fn+2

SITIAE’08

Contenido

Steven and Todd

Problema Steven and ToddDemostracion formal en la literatura

Claramente tn = (numero de α que contienen n) + (numero de α queno contienen n) = tn−1 + (numero de α que no contienen n). Quedapor demostrar que tn−2 = (numero de α que no contienen n).Supongamos que n es par. Ahora hay dos tipos de α que contienen n (ypor tanto terminan en n), y dos secuencias de paridad alternante β queson contadas por tn−2:

(I) α = {a1, a2, . . . , par, n − 1, n}, acabado una pareja impar-par.

(II) α = {a1, a2, . . . , impar, n}, donde el ultimo impar es ≤ n − 3.

(III) β = {a1, a2, . . . , par}, donde el ultimo par es ≤ n − 2.

(IV) β = {a1, a2, . . . , impar}, donde el ultimo impar es ≤ n − 3.

Claramente, eliminando el n − 1 y el n de una α del tipo (I) da una β

de tipo (III), y a la inversa. Analogamente, eliminando el n de una α del

tipo (II) da una β de tipo (IV), y a la inversa. La solucion, por tanto, es

inmediata.

SITIAE’08

Contenido

Steven and Todd

Problema Steven and ToddModelado mediante recursividad mutua

Decide(n) =

{1 si n < 1

Nombra(n) + Decide(n − 2) si n ≥ 1

Nombra(n) =

{1 si n = 1

Decide(n − 1) si n > 1

Version modificada pero analoga en la que los numerosdescienden

SITIAE’08

Contenido

Steven and Todd

Problema del Control de Aguas Residuales

An = 3An−1 − An−2 = F2n

Modelado del flujo de agua entre ciudades: →, ←, ×

La secuencia ←→ no esta permitidaManuel Rubio Sanchez 27 de mayo, 2008 22/35

SITIAE’08

Contenido

Steven and Todd

Problema del Control de Aguas Residuales

f×(n) = f→(n) =

{1 si n = 1

f×(n − 1) + f→(n − 1) + f←(n − 1) si n > 2

f←(n) =

{1 si n = 1

f×(n − 1) + f←(n − 1) si n > 2

An = f→(n) = f×(n) = F2n

SITIAE’08

Contenido

Steven and Todd

Contenido

SITIAE’08

Contenido

Steven and Todd

Evaluacion pedagogica

Recursividad (lineal, por cola, multiple, mutua)

5 primeros niveles de la taxonomıa de Bloom

58 alumnos (21, CS2; 33, CS3; 3, CS4; 1, CS5), todoscon conocimientos previos de recursividad

SITIAE’08

Contenido

Steven and Todd

Evaluacion pedagogicaNivel de conocimiento

SITIAE’08

Contenido

Steven and Todd

Evaluacion pedagogicaNivel de aplicacion

{n %2 si 0 ≤ n < 10

((n %10) %2) + An/10 si n ≥ 10

Bn,m =

{n si m = 0

Bm,n %m si m > 0

Cn,m =

{0 si n = 0 o m = 0

(Cn−1,m + Cn,m−1 + n + m)/2 si n > 0 y m > 0

{1 si n = 0

En/2 si n > 0En =

{0 si n = 0

Dn−1 si n > 0

SITIAE’08

Contenido

Steven and Todd

Evaluacion pedagogicaNivel de aplicacion

SITIAE’08

Contenido

Steven and Todd

Evaluacion pedagogicaNivel de sıntesis

(1) Hallar el cociente de la division entera utilizandorecursividad no final.

(2) Hallar el cociente de la division entera utilizandorecursividad por cola (final).

(3) Hallar el valor de un coeficiente binomial.

(4) Hallar la solucion al siguiente problema:

SITIAE’08

Contenido

Steven and Todd

Evaluacion pedagogicaNivel de sıntesis

SITIAE’08

Contenido

Steven and Todd

Evaluacion pedagogicaProblema (4)

Implementaciones correctas en el post-test:

problema (4) mutua lineal

no de implementaciones correctas 26 6

no de implementaciones incorrectas 9 12

Recursion mutua vs. lineal en ambos tests:

post-testproblema (4) mutua lineal blanco

mutua 19 2 0pre-test lineal 10 10 1

blanco 6 6 4

SITIAE’08

Contenido

Steven and Todd

Evaluacion pedagogicaProblema (4)

Implementaciones correctas en el post-test:

problema (4) mutua lineal

no de implementaciones correctas 26 6

no de implementaciones incorrectas 9 12

Recursion mutua vs. lineal en ambos tests:

post-testproblema (4) mutua lineal blanco

mutua 19 2 0pre-test lineal 10 10 1

blanco 6 6 4

SITIAE’08

Contenido

Steven and Todd

Contenido

SITIAE’08

Contenido

Steven and Todd

Conclusiones

Se han propuesto varios problemas combinatoriosSe ha hecho enfasis en la descomposicion de problemasy el concepto de induccion

La recursividad mutua no es tan difıcil como puedeparecer a la hora de

• Evaluar funciones matematicas simples

• Disenar algoritmos para resolver problemassencillos

Es importante que los estudiantes vean larecursividad mutua en mas profundidad

Para que puedan reconocerla y aplicarla

Alumnos de segundo curso pueden asimilaradecuadamente la recursividad mutua

(En un curso de programacion imperativa)

SITIAE’08

Contenido

Steven and Todd

Conclusiones

SITIAE’08

Contenido

Steven and Todd

Conclusiones

SITIAE’08

Contenido

Steven and Todd

Conclusiones

SITIAE’08

Contenido

Steven and Todd

Discusion

Otros estudios pedagogicosNo conocemos trabajos sobre la ensenanza de larecursividad mutua

Otros problemas utiles para la ensenanza de larecursividad

Torres de Hanoi cıclicas

Marco de trabajo de aprendizaje basado enproblemas

Por ejemplo, junto con otros problemas combinatorios

Punto de vista alternativo y enriquecedor de larecursividad

Puede mejorar la comprension y asimilacion de lainduccion, la abstraccion funcional y la descomposicionde problemas

SITIAE’08

Contenido

Steven and Todd

Discusion

SITIAE’08

Contenido

Steven and Todd

Discusion

SITIAE’08

Contenido

Steven and Todd

Discusion

Ensenanza de la Recursividad Mutua:Un Caso de Estudio

Manuel Rubio Sanchez

LITE, DLSI I, Universidad Rey Juan Carlos

27 de mayo, 2008

SITIAE’08: Seminario de Investigacionen Tecnologıas de la Informacion

Aplicadas a la Educacion

¡Muchas gracias! ¿Alguna pregunta?

enseñanza de la recursividad mutua: un caso de … · combinatorios conejos de fibonacci ......

Documents