Programación Básica con Laberintos

Contenido

1. Fundamentación

La cultura popular, alimentada por las películas y los libros de ciencia ficción, le da a la computadora una imagen de "cerebro mágico" que todo lo sabe y todo lo puede. La realidad es que las computadoras son máquinas electrónicas, sin capacidad de entender o razonar, que sólo responden a instrucciones simples.

Sin embargo, una inteligente combinación de instrucciones simples, un programa, puede lograr que las computadoras se comporten en la forma pseudo-inteligente y compleja que conocemos.

Esta actividad está pensada para desmitificar a la computadora por medio de un simple lenguaje de computación que permite resolver laberintos. Este lenguaje, accesible a alumnos del nivel EGB3 y del Polimodal, permite ver a la computadora como una máquina que sólo obedece órdenes simples, pero, al mismo tiempo, permite escribir un programa que en forma aparentemente inteligente resuelve cualquier laberinto.

2. Niveles educativos

EGB3, Polimodal

3. Espacios Curriculares que intervienen

Informática

4. Áreas curriculares vinculadas

Literatura, Historia.

5. Expectativas de logro

6. Contenidos Conceptuales

7. Contenidos Procedimentales

8. Contenidos Actitudinales

9. Didáctica de la actividad

_Explicación de los laberintos y el ente que los recorre_

El laberinto es una matriz con celdas, que pueden estar vacías (se puede pasar) u ocupadas por una pared (no se puede pasar). Hay una entrada al laberinto, al menos una salida y un camino de celdas vacías que conecta la entrada con la salida.

El ente tiene una posición en una celda vacía del laberinto (al comenzar está en la celda de entrada) y una orientación (Norte, Sur, Este u Oeste), hacia la cual puede avanzar. Este ente puede representar una persona, una computadora, una tortuga al estilo del lenguaje LOGO, etc.

El objetivo es escribir un programa que lleve al ente desde la celda de entrada hasta la salida del laberinto.

Ejemplo de laberinto con una entrada, una salida y, al menos, dos caminos entre ellas, con el ente posicionado en la celda de entrada y orientado hacia el Este:

Imagen: lab 2

_Explicación breve del lenguaje de programación_

Este lenguaje es simple y esta basado en el lenguaje LOGO. Tiene dos instrucciones básicas, las cuales cambian el estado del ente. Es decir, pueden cambiar la posición u orientación del ente:

Estas instrucciones pueden utilizarse para escribir un programa que resuelva el laberinto del ejemplo anterior.

para solucion_1
paso
paso
paso
paso
der
der
der
paso
paso
paso
paso
der
paso
paso
fin

Imagen: lab 2


Hay varias soluciones a este laberinto, algunas lógicas, otras no. La solución que dimos es la más simple. La siguiente figura muestra otra solución simple. El programa que obtiene esta solución queda como ejercicio para el lector.

Imagen: lab 3

_Creación de subprogramas_

Como se ve en el ejemplo anterior, para que el ente haga un giro hacia la izquierda, el programa debe repetir tres veces la instrucción DER. Podemos utilizar subprogramas para crear nuevas instrucciones a partir de las instrucciones ya existentes, y así poder escribir programas más cortos y legibles.

Un subprograma (al igual que un programa) se crea escribiendo un nombre, dos puntos, una serie de instrucciones y la directiva FIN. Una vez creado un subprograma, su nombre puede ser usado como una instrucción por cualquier otro (sub)programa.

Por ejemplo, podemos crear la instrucción IZQ, que ordena al ente girar a la izquierda, utilizando la instrucción ya existente DER. También podemos crear una instrucción DOS_PASOS, basada en la instrucción PASO.

para izq
der
der
der
fin
para dos_pasos
paso
paso
fin

Entonces el programa de la primera solución puede escribirse en una forma más concisa y clara:

para solucion_1
dos_pasos
dos_pasos
izq
dos_pasos
dos_pasos
der
dos_pasos
fin

Este programa va a ejecutar exactamente igual que la primera versión, ya que cuando la computadora lea la instrucción IZQ va a ejecutar el subprograma IZQ, es decir, va a ejecutar la instrucción DER tres veces. Igualmente al encontrar la nueva instrucción DOS_PASOS.

_Introducción del concepto de repetición_

Uno de los conceptos más importantes en computación es el concepto de repetición de una serie de instrucciones.

En la primera solución, en vez de indicarle al ente que avance cuatro pasos, podemos escribir un programa que haga avanzar al ente hasta encontrar una pared. Es decir, que le indique al ente ejecutar un PASO repetidamente, hasta que cierta condición deje de cumplirse. Para ello necesitamos introducir condiciones o predicados lógicos en nuestro lenguaje, e instrucciones que controlen si esas condiciones se verifican o no (son verdaderas o falsas).

PARED? es una función lógica (o condición) que retorna VERDADERO sólo si en la siguiente casilla apuntada por la orientación del ente hay una celda ocupada por una pared.

NO condición: es la operación lógica de negación, que retorna VERDADERO sólo si la "condición" retorna FALSO.

MIENTRAS [condición] [instrucciones]: es una instrucción (en realidad, un constructor de instrucciones) que permite escribir programas que repiten las "instrucciones" mientras la "condición" sea verdadera.

Por ejemplo, podemos crear un subprograma que haga avanzar el ente hasta que encuentre una pared:

para avanzar
mientras [no pared?] [paso]
fin

Podemos utilizar este subprograma para reescribir la primera solución de manera que el ente avance hasta la pared, gire y luego avance hasta la otra pared:

Imagen: lab 5

La nueva versión de nuestra solución queda escrita de una forma muy simple y lógica desde el punto de vista humano: caminar hasta la pared, girar a la izquierda, caminar hasta la siguiente pared, girar hacia la derecha y caminar dos pasos para salir:

para solucion_1
avanzar
izq
avanzar
der
dos_pasos
fin

Otra función lógica (o condición) muy útil es ADENTRO?, la cual retorna VERDADERO sólo si el ente está aún adentro del laberinto.

_Práctica y contextualización_

Durante esta etapa se crean distintos laberintos de distinta complejidad y se escriben programas que los resuelvan. Esta actividad puede hacerse sin computadoras, dibujando los laberintos en hojas cuadriculadas, en el pizarrón o en el suelo, y haciendo que un alumno del grupo responda ciegamente a las instrucciones del programa. Sin embargo, el lenguaje LOGO puede usarse para crear los laberintos y ejecutar los programas. Para ello se puede utilizar el programa MSWLogo y escribir los programas en forma similar a como se han escrito en el archivo laberinto.txt.

Esta etapa se puede coordinar con otras áreas curriculares el estudio de laberintos: en la historia y mitología, en la literatura, en la arquitectura, en los juegos (incluso en los videojuegos) y su simbología. Análisis, construcción y resolución de otros tipos de laberintos (3D, por ejemplo). Recomiendo la lectura de "La casa de Asterión" y "Abenjacán el Bojarí, muerto en su laberinto", cuentos ambos de Jorge Luis Borges.

_El programa que resuelve CUALQUIER laberinto_

Hemos visto que la computadora es una máquina electrónica simple que solamente puede obedecer órdenes muy simples. Pero esas órdenes combinadas en un programa pueden resolver problemas complicados. En esta etapa vamos a ver cómo una combinación inteligente de estas instrucciones básicas puede hacer que la computadora se comporte en una forma que parezca inteligente. Vamos a escribir un programa que resuelva cualquier laberinto, lo cual nos evita tener que escribir un programa para cada laberinto.

Para resolver automáticamente cualquier laberinto (con las características de los presentados aquí: dos dimensiones, una entrada, al menos una salida y al menos un camino entre ellas) lo que se debe hacer es seguir permanentemente la pared de la derecha (o de la izquierda, pero siempre la misma) desde la entrada hasta la salida.

Primer paso: escribir un subprograma que permita al ente "tantear" la pared en una celda a la que recién ingresó, comenzando por su derecha y siguiendo hacia la izquierda hasta encontrar una celda a la que pueda acceder.

para tantear
der
mientras [pared?] [izq]
fin

Paso final: escribir un programa que permita al ente ir tanteando por la próxima celda más a su derecha y, cuando encuentra una celda libre, avanzar.

para solucion_universal
mientras [adentro?] [
tantear
paso
]
fin

Al ejecutar este programa en el laberinto del ejemplo, el ente realizará el siguiente recorrido, que no es el más corto, pero resuelve el problema.

Imagen: lab 6

Este programa resuelve CUALQUIER laberinto, haciendo que la computadora parezca lo suficientemente inteligente como para "descubrir" siempre una salida para cualquier laberinto. Sin embargo, como hemos visto, la computadora no tiene conciencia de qué está haciendo, sólo sigue instrucciones simples.

10. Referencia

Esta actividad está basada en el artículo de Farhad Mavaddat, "Another Experiment with Teaching of Programming Languages", publicado en ACM SIGCSE Bulletin, vol. 13, nro 2, Junio de 1981.

11. Evaluación

Observar las actuaciones/simulaciones físicas de los alumnos y comentar sobre las diferencias en los comportamientos de un humano y una computadora.

12. Elementos complementarios

Para poder aplicar esta actividad con la computadora hay que utilizar el programa MSWLogo.

El archivo laberinto.txt contiene un programa que, usando MSWLogo, crea laberintos al azar y los resuelve utilizando el programa visto en esta actividad.

13. Recursos

MSWLogo

14. Licencia

Este es un documento libre.

Autores: Ricardo Medel, Daniel Ajoy

Creative Commons License
Esta obra está licenciada bajo una Licencia Creative Commons Atribución-Compartir Obras Derivadas Igual 2.5 España.

15. Preguntas, Dudas, Comentarios, Peticiones

Nombre:
Ciudad y País:
Email:
 

16. Enlaces

Página Principal


Generado con PureJoy.
Fecha: 02:52 - Mar 10, 2015