domingo, 30 de noviembre de 2014

Por qué el pensamiento computacional (VI). Iteración.-


Siempre que hablamos de iteración pensamos en procedimientos repetitivos como los que utilizamos cuando aprendimos o cuando enseñábamos BASIC, Pascal, LOGO, o C++, y más recientemente Java o Phyton. Lo asociamos a bucles, a instrucciones FOR TO, while, do-while, repeat,… y a diagramas de flujo. En definitiva, era difícil hablar de iteración sin pensar en la construcción de algoritmos repetitivos. Sin embargo pocas veces pensamos que hay aprendizajes básicos, en las primeras etapas de desarrollo, donde se pone en marcha un sistema de pensamiento de este tipo. Pensemos por ejemplo en la adquisición que hacen los niños de las ideas sobre fracciones, números racionales, o incluso en los números reales, en la representación decimal , en la notación decimal de números reales, y en su representación ¿qué son sino más que procedimientos iterativos? También podríamos pensar en sistemas de medición, de magnitudes de peso, masa, volumen, superficie,… ¿qué son estos procesos sino sistemas de representación conceptual iterativas?

Son particularmente importantes las aportaciones en este sentido de Mack (2001); Olive & Vomvoridi  (2006).  E igualmente las de Steffe & Olive (2010) para el desdoblamiento de operaciones, que juega un papel crítico en la construcción de esquemas  de fracciones por los estudiantes, tales como el esquema de fracción iterativo. Otras investigaciones en este sentido fueron las de Hackenberg, (2007) y  Steffe (2004).

Jesse L.M. Wilkins, Anderson Norton y Steven J. Boyce (2011) prueban empíricamente la validez de unos esquemas iterativos llamados partitive unit fraction scheme (PUFS), y de forma más general partitive fraction scheme (PFS),  para el aprendizaje de fracciones. Aunque este estudio ha sido criticado por Norton & Wilkins (2010), debido a la existencia de caracterizaciones del esquema divergentes.


La iteración es una componente pues importante del pensamiento computacional, con una extensa proyección en otras representaciones cognitivas y en procedimientos que son la base de importantes actividades y tareas, como por ejemplo lo que hemos mencionado en relación con la medida y la representación de magnitudes y valores.

Pero no sólo es relevante a ese nivel, la iteración es la base de procedimientos complejos y está en la resolución de problemas con más alcance o más impacto que lo que supone su definición en una primera aproximación.

Hay un problema conocido por el problema del viajante (TSP por las siglas de Traveling Salesman Problem). Sucintamente consiste en,  dada una lista de poblaciones, ¿cuál es la ruta más corta posible que pasa por cada localidad exactamente una vez y termina en el lugar de salida?. Hay muy variados métodos de resolución y todos son iterativos. El primero es el procedimiento a mazazos, también llamado “búsqueda de fuerza bruta”  (Brute-force search). Como el nombre sugiere se trata de obtener como itinerarios posibles todas las permutaciones de las ciudades, con la distancia recorrida en cada caso, y obtener el mínimo de ellas. Es un método exacto y factible, con muy poca programación, en un ordenador. Es un ejemplo de método iterativo. Tiene problemas de tiempo porque es una función de un factorial, pero hay algoritmos para abreviar el tiempo.
Este es un método heurístico. Se podría pues, como vimos, incluir en varias categorías en cuanto a tipo de pensamiento. Casi nunca son puros.

Hay otros métodos heurísticos también recursivos como es el del vecino más cercano (NN, nearest neighbor)  (también llamado algoritmo voraz), que como el propio nombre indica en cada caso elige la ciudad más cercana sin visitar como su próximo movimiento. 
Luego hay métodos algorítmicos con hamiltonianos y todo eso.

Pero lo importante para nuestro propósito de ver la importancia del a iteración en metódos basados en grafos es al menos traer la referencia de los métodos op:
El intercambio par a par simple,  o técnica 2-opt, que supone en cada iteración la eliminación de dos aristas que se cortan  y su reemplazo por con dos aristas diferentes, que no se crucen, y que reconecten los fragmentos creados por la eliminación de las aristas por este método, obteniendo así un camino más corto.

Éste es un caso especial del método general heuristica k-opt o heurística Lin-Kernighan. Donde en un recorrido dado se eliminan k aristas que se cortan en al menos un punto por un conjunto que no se corta en ningún punto.




Este problema y los algoritmos que se han desarrollado apartir de él han permitido un enfoque interesante  para otro problema, el del embarque en aviones, a Jason Steffen (2008), y al desarrollo de un algoritmo muy práctico y de indudable interés económico para la secuencia de embarque de pasajeros en los aeropuertos.




El cambio que supone en la práctica modificar la forma en que la gente embarca en los aviones, el ahorro de tiempo multiplicado por el número de embarques que se producen en todo el mundo, a lo que se unen los tiempos de espera en vuelos combinados, suponen una solución de gran envergadura directa, a la economía de tiempo, y de dinero,de sueldos, de energía,... Y esto sólo si lo planteamos directamente. Pero es que además hay un ahorro indirecto y un bienestar añadido: El que supone que la gente llegue a tiempo a su trabajo, a su negocio, a sus vacaciones o a estar con su familia. Ventajas que son muy de tener en cuenta..., todo por una cuestión de iteracción. Y como consecuencia de una forma de pensar que primero se planteó exclusivamente como pensamiento computacional.



Referencias.-

Mack, N. K. (2001). Building on informal knowledge through instruction in a complex content domain: Partitioning, units, and understanding multiplication of fractions. Journal for Research in Mathematics Education, 32(3), 267–296.

Olive, J., & Vomvoridi, E. (2006). Making sense of instruction on fractions when a student lacks necessary fractional schemes: The case of Tim. Journal of Mathematical Behavior 25(1), 18–45.

Steffe, L. P., & Olive, J. (2010). Children’s fractional knowledge. Springer: New York.

Hackenberg, A. J. (2007). Units coordination and the construction of improper fractions: A revision of the splitting hypothesis. Journal of Mathematical Behavior, 26(1), 27–47.

Steffe, L. P. (2004). On the construction of learning trajectories of children: The case of commensurate fractions. Mathematical Thinking and Learning, 6(2), 129–162

Steffen, J. H. (2008). Optimal boarding method for airline passengers. Journal of Air Transport Management14(3), 146-150. http://www.sciencedirect.com/science/article/pii/S0969699708000239

Wilkins, J. L. M., & Norton, A. (2011). The splitting loope. Journal for Research in Mathematics Education, 42(4), 386–416

Wilkins, J. L., Norton, A., & Boyce, S. J. (2013). Validating a Written Instrument for Assessing Students' Fractions Schemes and Operations. Mathematics Educator22(2), 31-54.

No hay comentarios:

Publicar un comentario en la entrada