Experimento con cartas - búsqueda secuencial

De Gleducar, http://www.gleducar.org.ar

Fundamentación

Las computadoras hacen cosas increíbles. Pero actualmente es difícil para los alumnos entender cuáles son los procesos que una computadora sigue a fin de obtener los resultados que vemos. Con un sencillo experimento con cartas, los alumnos pueden simular el comportamiento de una computadora y entender cómo funciona en sus partes más básicas. Las cartas son los datos y el alumno se comporta como la computadora, que sigue una serie de instrucciones para obtener el resultado deseado. El análisis de los resultados nos lleva tanto a conceptos básicos de computación, tales como qué es un "programa", como a conceptos avanzados de ciencias de la computación, tales como "análisis de performance en el peor caso".

Este experimento ha sido propuesto para ser incluído en el Libro de Experimentos: Kits Didácticos de Ciencia [1] del Ministerio de Ciencia y Tecnología de la Provincia de Córdoba.

Niveles educativos

SECUNDARIA

Area curricular específica

Tecnología

Areas curriculares vinculadas

Informática, Matemática

Expectativas de logros

Que los alumnos entiendan el comportamiento interno de una computadora y puedan analizar el "costo computacional" de un programa simple.

Contenidos conceptuales

Programa de computadora, instrucciones, búsqueda secuencial de datos, instrucciones condicionales, análisis de programas, costo computacional.

Contenidos procedimentales

Durante este experimento los alumnos simularán el comportamiento de una computadora: mediante instrucciones simples y toma de decisiones, una computadora puede realizar actividades de utilidad para la sociedad. La serie de instrucciones que el alumno debe seguir forman el “programa” que la computadora ejecuta para obtener el resultado deseado, en este caso es buscar una carta en un mazo. Analizaremos también cuánto tiempo lleva buscar una carta, en promedio y en el peor caso.

Contenidos actitudinales

Los alumnos entenderán que siguiendo simples instrucciones, las computadoras pueden realizar las tareas que nos sorprenden diariamente. Entenderán también que los programas tienen un costo computacional que debe ser evaluado al desarrollarlos.

Didáctica de la actividad

• Repetir varias veces (mientras más, mayor valor estadístico tendrán los datos obtenidos) los siguientes dos pasos:

1. Organizar el material:
   • Mezclar el mazo completo.
   • Dejar el mazo en la mesa, con las cartas mirando hacia abajo.
   • Tener el papel y lápiz a mano.

   
   

   

   
   

2. Buscar una carta:
   • Un alumno debe decidir qué carta buscar (indicar solamente el valor, no el palo).
   • Un alumno procederá a buscar la carta en el mazo tomando la carta del tope del mazo, girándola para ver su valor, si no es la carta buscada, se pone a un costado y se repite el procedimiento. Si es la carta buscada se detiene el procedimiento.
   • Un tercer alumno toma nota de cuántas cartas son revisadas por el alumno que hace la búsqueda.

Análisis de resultados

Observando las notas sobre cuántas cartas son revisadas en cada búsqueda, los alumnos deben indicar:

1. ¿Cuántas cartas se revisaron en la búsqueda que requirió más revisiones?
2. ¿Cuántas cartas en promedio se revisaron en cada búsqueda?
3. ¿Cuántas cartas habría que revisar en el mejor de los casos, es decir, en la búsqueda que tome menos tiempo?
4. ¿Cuántas cartas habría que revisar en el peor caso, es decir, en la búsqueda que tome mayor tiempo?

Evaluación

Durante este experimento hemos simulado una computadora. El mazo de cartas representa a la memoria de una computadora, la mano sosteniendo la carta tomada del tope representa el “banco de registros” de la CPU (un lugar dedicado a almacenar los valores que el procesador puede leer y procesar) y nuestro cerebro representa el procesador, que revisa la carta y decide que acción tomar en base a su valor. Al seguir las instrucciones del paso 2 estamos simulando la ejecución de un “programa” de búsqueda en secuencia (o secuencial) de un valor en la memoria de la computadora.

El programa de búsqueda se podría escribir como:

	Tomar la carta del tope del mazo
	Si es la carta buscada
		entonces detener el programa
		si no, descartar esa carta
	Repetir los pasos anteriores hasta vaciar el mazo

Al tomar nota de cuántas cartas se revisan en cada ejecución, estamos contando aproximadamente cuántas instrucciones del programa se ejecutan. Esto nos permite analizar el “costo” de ejecutar un programa.

Si hicimos muchas búsquedas, seguramente las respuestas a las preguntas (1) y (2) fueron cercanas a 44 y 24, respectivamente. Es decir, la peor búsqueda fue cuando la carta buscada estaba al final del mazo (junto con otras tres del mismo valor) y la búsqueda promedio nos hizo revisar la mitad de las cartas del mazo. En computación se dice que el “costo promedio” para este programa es O(n/2) o “de orden n/2”, y que el peor caso es de O(n) o “de orden n”, con n la cantidad de datos que el programa tiene para procesar (o “la entrada”).

Algunas preguntas para evaluar la comprensión de los conceptos:

1. ¿Cuántos pasos (o instrucciones) ejecutará este programa en promedio si lo usáramos con mil datos? ¿Cuántos pasos ejecutaría en el peor caso?
2. ¿Por qué en Ciencias de la Computación prefieren contar el número de instrucciones ejecutadas en relación con el tamaño de los datos de entrada, en vez de simplemente ejecutar el programa en una computadora y calcular el tiempo total de ejecución?

Respuestas

1. Si utilizáramos este programa con mil datos, el usuario debería esperar que en promedio el programa ejecutase 500 pasos o “instrucciones”, pero debería ser consciente de que podría llegar a ejecutar, en el peor caso, hasta 1.000 pasos.
2. Porque el tiempo ejecución de un programa en una computadora depende, además del tamaño de la entrada, de la velocidad de la computadora. Es decir, de cuán rápido esa computadora ejecuta cada instrucción. Entonces los resultados de una ejecución en una computadora no son aplicables a otros modelos de computadoras. Por eso la cantidad de instrucciones ejecutadas (en promedio y en peor caso) es más adecuada. Así, el usuario solamente deberá calcular cuánto tarda su computadora para ejecutar cada instrucción y tendrá un valor aproximado de cuánto tarda el programa en ser ejecutado.

Recursos

Un mazo de cartas, papel y lápiz.