UNA HERRAMIENTA PARA FACILITAR EL PROCESO DE ENSENANZA-APRENDIZAJE DE LASESTRUCTURAS DE DATOS

M. L. Perez(1), P. A. Hernandez(2), J. Escuadra(1), M. P. Rubio(2)

mlperez@usal.es, pedrohd@usal.es, mprc@usal.es, jeb@usal.es(1)Departamento de Informatica y Automatica

980545000 Ext. 3636(2)Departamento de Construccion y Agronomıa

980545000 Ext. 3622Escuela Politecnica Superior de Zamora, Universidad de Salamanca,

Campus Viriato, Avda. Requejo 33, 49022-Zamora, Espana.

RESUMEN

Este trabajo describe el material multimedia desarrollado para la asignatura Estructuras de Datos de la titulacionIngenierıa Tecnica Informatica de Gestion, que se imparte en la Escuela Politecnica Superior de Zamora.

El material desarrollado tiene estructura de pagina web. Este curso se ha utilizado como material de apoyo a la docenciay el proximo curso se pondra a disposicion de los alumnos, como herramienta de apoyo al aprendizaje.

PALABRAS CLAVE: auto-aprendizaje, material docente.

1. INTRODUCCION

La Union Europea ha experimentado en los ultimos anos un espectacular crecimiento, ası como un fortalecimiento endiferentes planos, tanto economico como polıtico. La libre circulacion de trabajadores y ciudadanos en los paıses de laUnion es hoy en dıa una realidad. Pero para que esto sea posible sin ningun tipo de discriminacion en cuanto al nivelde estudios de los ciudadanos de la Union, es necesario que existan unos criterios para la homologacion de tıtulos delos distintos paıses miembros. Como solucion al problema anterior, se propuso la construccion del denominado EspacioEuropeo de Educacion Superior (EEES).

La necesaria adaptacion de los actuales estudios universitarios al nuevo marco definido por el Espacio Europeo deEducacion Superior nos ha llevado a empezar a trabajar para realizar los cambios necesarios. Creemos que es necesarioacometer las reformas de las asignaturas y de los sitemas docentes tradicionales con tiempo suficiente, lo que evitaraactuar con precipitacion, ası como los errores que ello puede conllevar. Ademas, los resultados obtenidos puedenayudarnos a corregir las estrategias probadas y trabajar en su mejora, de modo que cuando se pongan en marcha lasnuevas titulaciones tengamos ya un importante trecho del camino de adaptacion andado.

Este trabajo presenta el material docente desarrollado para la asignatura Estructuras de Datos, incluida en el plan deestudios de Ingenierıa Tecnica Informatica de Gestion de la Escuela Politecnica Superior de Zamora. El desarrollode este material se engloba dentro de un proyecto que tiene como objetivo la adaptacion del material docente de laasignatura a los nuevos planes de estudio.

El trabajo comenzara justificando la importancia de las nuevas tecnologıas, como herramienta de apoyo tanto enel proceso de ensenanza como de aprendizaje. En segundo lugar se hace una pequena descripcion de la asignaturaconsiderada en el estudio, ası como de las dificultades que plantea esta a los alumnos. A continuacion se describenlos objetivos del proyecto dentro del cual se ha desarrollado el material multimedia que se describe en este trabajo.Por ultimo, se presentan los aspectos fundamentales del material multimedia desarrollado, ası como el esquema de lostemas cubiertos por el mismo.

2. LA APLICACION DE LAS NUEVAS TECNOLOGIAS A LA EDUCACION

La aplicacion de las nuevas tecnologıas en la educacion constituye un elemento fundamental en la Universidad. Laslecciones magistrales deben complementarse con otras tecnicas y utilizar herramientas de apoyo.

Por otra parte, al considerar el futuro marco de las titulaciones universitarias, hay que tener en cuenta que se reduciranotablemente el numero de horas de clase. Por tanto, deben buscarse nuevos metodos y herramientas que ayuden alalumno en el aprendizaje de las diferentes materias. En esta busqueda, las nuevas tecnologıas son un punto clave.

3. LAS ESTRUCTURAS DE DATOS EN LA ESCUELA POLITECNICA SUPERIOR DE ZAMORA

La asignatura Estructuras de Datos forma parte del plan de estudios conducente a la obtencion del tıtulo de IngenieroTecnico en Informatica de Gestion. El objetivo de la asignatura es presentar al alumno las estructuras de datosfundamentales y sus algoritmos de manipulacion.

La citada titulacion se puede cursar en la Escuela Politecnica Superior de Zamora desde el ano 2002. Por tanto, son yacuatro los cursos en los que se ha impartido, lo que nos ha permitido valorar los resultados obtenidos por los alumnos.

Esta asignatura, a diferencia de lo que ocurre en la mayor parte de los centros espanoles, se situa en primer curso.Ello hace necesario presentar a los alumnos conceptos que deberıan haber estudiado previamente. Este factor reduceconsiderablemente el tiempo disponible para impartir los aspectos fundamentales de la asignatura, ademas de dificultaral alumno la asimilacion de contenidos. Se describen tambien las tareas desarrolladas dentro del citado proyecto, paraenmarcar el lugar ocupado por el material multimedia.

3.1. La dificultad del estudio de las estructuras de datos

Observando detenidamente el programa propuesto por las recomendaciones curriculares internacionales, se apreciaclaramente la necesidad de estudiar numerosos algoritmos, relacionados con diferentes estructuras de datos. Por otraparte, hay que senalar que normalmente la asignatura Estructuras de Datos se aborda desde el punto de vista de los tiposabstractos de datos (TAD), por lo que se presenta una descripcion de los algoritmos desde un punto de vista abstracto.Esta descripcion, realizada en pseudocodigo o utilizando una especificacion algebraica, a menudo resulta mas difıcil decomprender para los alumnos, que preferirıan utilizar algun lenguaje de programacion. Por ello, la explicacion teoricadebe complementarse necesariamente con ejercicios practicos u otras herramientas, que permitan entender mejor elfuncionamiento de los algoritmos de manipulacion de las estructuras. La ensenanza de las Estructuras de Datos se suelecomplementar con la realizacion de practicas sobre ordenador, que permitan aplicar sobre datos reales los contenidostratados en las clases teoricas.

4. EL PROYECTO DESARROLLADO

4.1. Objetivo del proyecto

Entre los objetivos del proyecto que ha permitido generar el material docente que aquı se presenta figuraban:

• Adaptar el material docente de la asignatura Estructuras de Datos, perteneciente a la titulacion Ingenierıa TecnicaInformatica de Gestion, de la Escuela Politecnica Superior de Zamora, para que se ajuste a los requisitos del EspacioEuropeo de Educacion Superior.

• Adaptar los contenidos de la asignatura a las recomendaciones curricular internacionales establecidas por ACM/IEEE[1], lo que permitira disenar una asignatura mas parecida a la de otros centros nacionales y europeos que cursan lamisma titulacion.

• Preparar material que facilite el trabajo personal del alumno, como establecen los acuerdos del Espacio Europeode Educacion Superior. Esto supone adaptar un material que actualmente se utiliza como apoyo a las leccionesmagistrales, de forma que pase a ser util como herramienta de apoyo al trabajo personal del alumno.

• Que los alumnos puedan disponer de un material que les servira como herramienta de apoyo en el estudio de laasignatura, fomentando el autoaprendizaje y la posibilidad de consulta del mismo cuando y donde lo deseen.

Por todo lo expuesto, se planteo como parte de este proyecto la posibilidad de desarrollar un material docente parala materia Estructuras de Datos, que este adaptado a los requisitos impuestos por la convergencia europea de lastitulaciones universitarias.

El material desarrollado se ha puesto a prueba en las clases de la asignatura del presente curso, lo que ha permitidoevaluar su utilidad, revisarlo y definir puntos de posible mejora. El material que se presenta no es una herramientacerrada, sino que vamos a seguir trabajando en ella para mejorarla y ampliarla todo lo que nos sea posible. El proximocurso se pondra a disposicion de los alumnos, con lo que se espera obtener comentarios y crıticas que nos permitanhacer adaptaciones, ampliaciones o mejoras.

4.2. Tareas realizadas

Para conseguir estos objetivos, se han realizado los siguientes trabajos:

• Se han analizado las recomendaciones internacionales recogidas en el informe Computing Currıcula 2001, deACM/IEEE [1], relativas a los estudios de informatica. Estas recomendaciones son seguidas a nivel internacionalpara la elaboracion de planes de estudios y temarios de asignaturas relacionadas con el estudio de la informatica.El analisis detallado de este documento ha permitido fijar los siguientes aspectos relativos a las Estructuras deDatos: objetivos a cubrir, contenidos a tratar, secuenciacion de los contenidos y distribucion temporal. Consideramosque este documento aporta informacion fundamental de cara a disenar asignaturas homogeneas en Europa, lo quesimplificara la comparabilidad de los estudios cursados por los alumnos de la Union.

• Se ha estudiado la informacion disponible sobre la materia Estructuras de Datos en diversos centros universitariosespanoles que se consideran representativos. Dicha informacion se ha tomado de las paginas web de los centroscorrespondientes. Los datos recopilados permiten tener una vision del trabajo realizado en otras universidades decara a la adaptacion al Espacio Europeo de Educacion Superior, pudiendo aprovechar experiencias de otros centrospara nuestra propia adaptacion. Se han podido comprobar los temarios tratados, la distribucion de creditos teoricosy practicos, ası como la asignacion de creditos ECTS a la asignatura. Tambien se ha contrastado el aspecto referentea la bibliografıa mas utilizada en los centros analizados.

• Con la informacion obtenida de las dos fuentes anteriores, se han definido los contenidos de la asignatura, enmarcadaya en el Plan de Estudios de Ingenierıa Tecnica Informatica de Gestion de la Escuela Politecnica Superior de Zamora.

• Se ha desarrollado un material docente de uso en clase que incluye la descripcion en forma de pseudocodigo detodos los algoritmos de manipulacion de estructuras de datos que se deben tratar en la asignatura.

• El material docente de uso en clase mencionado en el apartado anterior tambien se pondra a disposicion de losalumnos para que puedan utilizarlo para el estudio de la asignatura.

• Se ha desarrollado un material multimedia que pondra a disposicion de todos los alumnos los contenidos tratadosen la asignatura, incluyendo tanto los algoritmos como pequenos ejemplos. Esta herramienta no solo servira comoapoyo al trabajo personal del alumno en la asignatura, sino que tambien podra ser utilizada por el profesor en susclases, y estara disponible para cualquier persona interesada en la materia. El material multimedia permitira analizarcontenidos de la materia, repasar conceptos tratados en clase,... Cada alumno podra dedicar el tiempo que estimenecesario al estudio de los conceptos fundamentales de la asignatura, ya que la herramienta de trabajo estara a sudisposicion todo el tiempo que lo desee.

5. MATERIAL MULTIMEDIA DESARROLLADO

5.1. Herramientas de desarrollo

El material ha sido desarrollado utilizando Microsoft FrontPage y Macromedia Flash. Dado que se incluyen anima-ciones realizadas en Flash, es necesario disponer en el navegador del plug-in de Macromedia Flash para visualizarcorrectamente el contenido. Si el usuario no dispone de dicho plug-in, podra descargarselo pinchando en el enlace quese incluye en la ventana de presentacion de la aplicacion.

5.2. Caracterısticas del material

El objetivo planteado al comenzar el desarrollo de este material era el siguiente:

• desarrollar un material que sirva tanto al profesor como al alumno. Para el profesor, servira como herramienta deapoyo a la docencia. Para el alumno, servira como herramienta de apoyo en el proceso de aprendizaje.

• se cubriran todos los temas tratados en la parte teorica de la asignatura, una vez adaptada esta segun las recomen-daciones del informe Computing Curricula.

• se incluira una descripcion de cada estructura de datos y sus algoritmos de manipulacion fundamentales. Dichadescripcion no pretende ser exahustiva, sino todo lo contrario. Se intentaran describir los conceptos claves, puesel alumno dispone de numerosas referencias bibliograficas para ampliar estos conceptos. Por tanto, la idea es fijarconceptos clave con explicaciones cortas y reforzar las explicaciones con ejemplos graficos.

• los graficos y las animaciones seran un elemento fundamental del material desarrollado, para facilitar al alumno lacomprension de los contenidos expuestos.

El material desarrollado se ha estructurado en forma de pagina web. La aplicacion comienza mostrando una ventanade presentacion (Figura 1).

Figura 1. Ventana de presentacion

Desde la ventana de presentacion se pasa a la ventana principal de la aplicacion, que incluye los temas tratadosestructurados en modulos (Figura 2). Existe un menu en la parte derecha, desde el que se accede a los temas tratadosen la asignatura.

Una vez seleccionado el modulo elegido se pasa a la ventana principal de descripcion de contenidos. Dicha ventana sedivide en tres partes: la superior, que muestra informacion sobre el tema que se va a revisar, la izquierda, que muestraun menu de opciones que se pueden consultar, y la derecha, que es la zona mas grande y en la que se visualizaran loscontenidos del tema seleccionado.

5.3. Temas cubiertos

El punto de referencia para la seleccion de los temas cubiertos por el material multimedia es el temario propuestopara la asignatura en la guıa academica de la Escuela Politecnica Supeior de Zamora [2]. Los contenidos tratados seestructuran en 4 modulos. La Tabla 1 muestra los temas cubiertos en cada uno de dichos modulos.

El primer modulo describe el objetivo de la aplicacion e introduce la notacion y la definicion de algunos conceptostratados a lo largo de los restantes modulos (Figura 3).

El segundo modulo se centra en el estudio de las tecnicas de Busqueda y ordenacion. Se dedica un tema al estudio dela busqueda y ordenacion en arrays (Tabla 2) y otro a la busqueda y ordenacion sobre ficheros (Tabla 3).

Figura 2. Pantalla inicial

MODULO I - Introduccion a la asignatura IntroduccionConceptos generales

MODULO II - Busqueda y ordenacion InternaExternaListas

MODULO III - Estructuras de datos lineales PilasColas

MODULO IV - Estructuras de datos no lineales GrafosArboles

Tabla 1. Modulos y temas asociados

Figura 3. Pantalla inicial del modulo I

DefinicionOperaciones basicasAlgoritmos de busqueda Lineal

BinariaAlgoritmos de ordenacion Insercion directa

Insercion binariaSeleccion directaIntercambio directoSacudidaShellQuickSortMergeSort

Tabla 2. Puntos tratados en el tema relativo a busqueda y ordenacion interna

DefinicionOperaciones basicasAlgoritmos de clasificacion Mezcla directa

Mezcla naturalMezcla equilibradaOrdenacion de raız

Algoritmos de busqueda Sobre archivos ordenadosSobre archivos desordenados

Tabla 3. Puntos tratados en el tema relativo a busqueda y ordenacion externa

Figura 4. Una pantalla del tema relativo a busqueda y ordenacion interna

Figura 5. Una pantalla del tema relativo a busqueda y ordenacion externa

El tercer modulo describe estructuras de datos lineales. Se incluye como primer tema el que analiza las listas (Tabla 4),por lo que los temas relativos a pilas (Tabla 5) y colas (Tabla 6) se simplifican.

DefinicionOperaciones basicasTipos de representacion vectorial

mediante memoria dinamicaOperaciones para representacion vectorial

para representacion mediante memoria dinamicaListas ordenadas

Tabla 4. Puntos tratados en el tema relativo a listas

DefinicionOperaciones basicasTipos de representacion vectorial

mediante memoria dinamicaOperaciones para representacion vectorial

para representacion mediante memoria dinamica

Tabla 5. Puntos tratados en el tema relativo a pilas

El ultimo modulo describe estructuras de datos no lineales. En primer lugar se analizan los grafos (Tabla 7). LaFigura 9 muestra parte del menu asociado a este tema. A continuacion, se tratan los arboles binarios (Tabla 8). LaFigura 10 muestra una pantalla asociada a este ultimo tema.

5.4. Graficos y animaciones

Se incluyen graficos que describen las estructuras de datos, como el que se muestra en la Figura 11, ası como lasoperaciones realizadas, como el que se muestra en la Figura 12.

Tambien se incluyen animaciones de algunos algoritmos. La Figura 13 muestra la estructura dada a las pantallas desdelas que se puede acceder a animaciones. Desde la parte izquierda se puede iniciar la animacion correspondiente y desdela parte derecha se puede obtener el pseudocodigo del algoritmo que se va a animar. Esta opcion permite al alumno

Figura 6. Una ventana del tema relativo a listas

DefinicionOperaciones basicasTipos de representacion vectorial

mediante memoria dinamicaOperaciones para representacion vectorial

para representacion mediante memoria dinamica

Tabla 6. Puntos tratados en el tema relativo a colas

Figura 7. Pantalla del tema referente a colas

Figura 8. Pantalla del tema referente a pilas

DefinicionRepresentacion Matriz de adyacencia

Listas de adyacenciaOperaciones en la representacion matricial Creacion

Anadir arcoAnadir aristaComprobacion de la existencia de un verticeComprobacion de la existencia de un arcoComprobacion de la existencia de una aristaEliminar arcoEliminar arista

Operaciones en la representacion mediante listas de adyacencia CreacionComprobacion de la existencia de un verticeComprobacion de la existencia de un arcoComprobacion de la existencia de una aristaAnadir verticeAnadir arcoAnadir aristaEliminar verticeEliminar arcoEliminar aristaEliminar listas de adyacencia

Recorridos Recorrido en anchuraRecorrido en profundidad

Tabla 7. Puntos tratados en el tema relativo a grafos

Figura 9. Una pantalla del tema relativo a grafos

Arboles DefinicionTerminologıa

Arboles binarios Definiciones y propiedadesRepresentacionOperaciones basicasRecorrido

Arboles de expansion de coste mınimo Definicion del problemaAlgoritmo de KruskalAlgoritmo de Prim

Arboles binarios de busqueda Construccion del arbolBusquedas

Arboles binarios equilibrados (AVL) Construccion del arbolBusquedas

Montıculos binarios Montıculo de maximos y montıculo de mınimosAlgoritmo Heapsort

Arboles hilvanados Construccion del arbolRecorrido del arbol

Tabla 8. Puntos tratados en el tema relativo a arboles binarios

disponer de una copia impresa del algoritmo (Figura 14), que durante la animacion solo se mostrara de forma parcial,el funcion de la operacion que se este animando.

En las Figuras 15, 16 y 17 se aprecian varios pasos de la evolucion de la animacion de un algoritmo de busqueda.

6. CONCLUSIONES

Este trabajo presenta un material multimedia desarrollado con el objetivo de facilitar al alumnado la comprension delas estructuras de datos fundamentales y sus algoritmos de manipulacion. Su utilizacion durante el presente curso comoherramienta de apoyo a la docencia ha sido muy bien valorada por los alumnos. Dichos alumnos han destacado lainclusion de descripcion de los conceptos fundamentales. Tambien han valorado positivamente la descripcion graficamediante ejemplos, que apoya a la descripcion teorica de los diferentes algoritmos.

Figura 10. Una pantalla del tema relativo a arboles

Figura 11. Figura explicativa asociada a la representacion de un grafo mediante listas de adyacencia

AGRADECIMIENTOS

Este trabajo ha sido financiado por la fundacion memoria de D. Samuel Solorzano Barruso, de la Universidad deSalamanca, mediante el proyecto titulado “Adaptacion al Espacio Europeo de Educacion Superior del material docenteutilizado en la asignatura Estructuras de Datos de la Escuela Politecnica Superior de Zamora”.

REFERENCIAS

[1] Computing Curricula 2001 (Computer Science). Report of the ACM/IEEE-CS Joint Curriculum Task Force. IEEE[2] Guia academica de la Escuela Politecnica Superior de Zamora, 2005-2006, Universidad de Salamanca, 2005.

Figura 12. Representacion grafica de una lista lineal doblemente enlazada

Figura 13. Acceso a las animaciones de algoritmos de busqueda

Figura 14. Pseudocodigo de un algoritmo

Figura 15. Un paso de animacion de un algoritmo de busqueda

Figura 16. Un paso de animacion de un algoritmo de busqueda

Figura 17. Un paso de animacion de un algoritmo de busqueda