PDF de programación - Visualización y Animación de Estructuras de Datos y Algoritmos

Sistemas Informáticos
Curso 2004-2005



Visualización y Animación de
Estructuras de Datos y Algoritmos



Laura Gutiérrez García
Esther Rico Redondo
Carmen Torrano Giménez

Dirigido por:
Prof. Clara María Segura Díaz
Dpto. Sistemas Informáticos y Programación



Facultad de Informática

Universidad Complutense de Madrid





Sistemas Informáticos
Curso 2004-2005


RESUMEN EN CASTELLANO E INGLÉS

El objetivo del proyecto es el desarrollo de una herramienta pedagógica, destinada a los
alumnos universitarios pertenecientes a las facultades de informática, que estén cursando las
asignaturas de estructuras de datos y esquemas algorítmicos. Esta herramienta se usará como
medio didáctico para facilitar el entendimiento de dichas asignaturas.

La herramienta desarrollada es una guía visual animada para comprender el funcionamiento de
estructuras de datos tales como: pilas, colas, colas de prioridad, árboles binarios de búsqueda y
árboles AVL; y de diversos problemas que se pueden resolver mediante esquemas algorítmicos
como divide y vencerás, voraz, ramificación y poda y programación dinámica.



The aim of the project is the development of a pedagogical tool for students of a computer
science degree who are attending subjects of data structures and algorithmic schemes. This tool will
be used as a didactic media in order to ease the understanding of such subjects.


The application being developed is an animated visual guide aimed to easily understand the
behaviour both of data structures such as stacks, queues, priority queues, binary trees and AVL
trees; and of problems than can be solved by using algorithmic schemes like divide and conquer,
greedy method, branch and bound, and dynamic programming.



Visualización y Animación de Estructuras de Datos y Algoritmos Página 2 de 216
Dpto. de Sistemas Informáticos y Programación



Sistemas Informáticos
Curso 2004-2005


LISTA PALABRAS CLAVE


Acción: unidad necesaria para llevar a cabo la visualización y animación de una estructura de datos
o algoritmo.
Algoritmo: conjunto de reglas que permiten obtener un resultado determinado a partir de ciertas
reglas definidas.
Animación: Conjunto de acciones destinadas a visualizar de forma animada el efecto producido
tras la ejecución de las mismas sobre las estructuras de datos y algoritmos.
Esquema Algorítmico: plantilla proporcionada por una metodología de programación para resolver
una colección de algoritmos de forma uniforme, que resuelven problemas específicos.
Estructuras de datos: colección de datos cuya organización se caracteriza por las funciones de
acceso que se usan para almacenar y acceder a elementos individuales de datos.
Simulación: secuencia de acciones que muestran el comportamiento de forma animada sin
necesidad de que el usuario introduzca los datos.
Visualización: efecto producido al mostrar en pantalla las estructuras de datos y algoritmos.



Visualización y Animación de Estructuras de Datos y Algoritmos Página 3 de 216
Dpto. de Sistemas Informáticos y Programación



Sistemas Informáticos
Curso 2004-2005


ÍNDICE


Resumen en castellano e inglés ............................................................................................. 2
Lista palabras clave ............................................................................................................... 3
Especificación de requisitos .................................................................................................. 3
1. Introducción ..................................................................................................................... 3
1.1. Propósito ................................................................................................................ 3
1.2. Alcance de la Aplicación ....................................................................................... 3
1.3. Referencias............................................................................................................. 3
1.4. Visión General del Documento.............................................................................. 3
2. Descripción General......................................................................................................... 3
2.1. Descripción de la Funcionalidades del Sistema..................................................... 3
2.1.1. Subsistemas de la Aplicación........................................................................ 3
2.1.2. Subsistema de Visualización y Animación de las Estructuras de Datos ...... 3
2.1.3. Subsistema de Visualización y Animación de los Esquemas Algorítmicos. 3
2.1.4. Subsistema de Documentación ..................................................................... 3
2.1.5. Subsistema de Simulación ............................................................................ 3
2.1.6. Subsistema de Ayuda.................................................................................... 3
2.2. Perfiles de Usuario................................................................................................. 3
2.3. Restricciones Principales ....................................................................................... 3
2.4. Suposiciones y Dependencias................................................................................ 3
2.4.1. Suposiciones. ................................................................................................ 3
2.4.2. Dependencias. ............................................................................................... 3
2.5. Requisitos Futuros ................................................................................................. 3
3. Requisitos Específicos ..................................................................................................... 3
3.1. Requisitos Funcionales .......................................................................................... 3
3.1.1. Subsistema de Visualización y Animación de las Estructuras de Datos ...... 3
3.1.1.3.1Árbol Binario de Búsqueda................................................................ 3
3.1.1.3.2Árbol AVL......................................................................................... 3
3.1.2. Subsistema Documentación de las Estructuras de Datos.............................. 3
3.1.3. Subsistema de Visualización y Animación de los Esquemas Algorítmicos. 3
3.1.4. Subsistema de Documentación de Algoritmos ............................................. 3
3.1.5. Subsistema de Simulación ............................................................................ 3
3.1.6. Subsistema de Ayuda.................................................................................... 3
3.2. Requisitos de Interfaces Externas .......................................................................... 3
3.2.1. Interfaces de Usuario .................................................................................... 3
3.2.2. Interfaces Hardware...................................................................................... 3
3.2.3. Interfaces Software ....................................................................................... 3
3.3. Requisitos no Funcionales ..................................................................................... 3
3.3.1. Requisitos de Rendimiento ........................................................................... 3
3.3.2. Requisitos de Seguridad................................................................................ 3
3.3.3. Requisitos Hardware..................................................................................... 3
3.3.4. Requisitos Software ...................................................................................... 3
3.3.5. Requisitos de Datos....................................................................................... 3
3.3.6. Requisitos de Desarrollo............................................................................... 3
4. Glosario............................................................................................................................ 3
4.1. Definiciones ........................................................................................................... 3
4.2. Acrónimos.............................................................................................................. 3

Visualización y Animación de Estructuras de Datos y Algoritmos Página 4 de 216
Dpto. de Sistemas Informáticos y Programación



Sistemas Informáticos
Curso 2004-2005

Casos de uso............................................................................................................................ 3
1. Comienzo de la Aplicación.............................................................................................. 3
Mostrar documento de bienvenida.........................