Estructuras de Datos Tipos Abstractos de Datos (TAD) Curso 2004 Segundo Curso de Ingeniería Técnica Informática (Sistemas)

Se orienta la asignatura desde el punto de vista de la Abstracción, considerando la utilización de este concepto y sus derivados en el desarrollo de sistemas de información (reutilización, Orientado a Objetos ...). El objetivo que se intenta transmitir a los alumnos, a través del planteamiento de una jerarquía de Tipos Abstractos de datos que, sirviendo como modelo de actuación, les permita adquirir habilidades para la utilización de técnicas de encapsulación y ocultación de información, y que sea la base para que los desarrollos por ellos enfrentados tengan mayor claridad y calidad.

El estudio de las Estructura de Datos (ED), las especificaciones de las mismas, sus características y manejo, se presenta de forma plena en la orientación antes marcada:

• Dado que las EDs son los elementos base de la definición tipos abstractos de datos (TAD) y de todo el paradigma Orientado al objeto.

• Dado que las EDs son derivables y concebibles como un "mecano" o kit de herramientas de utilidad en la construcción de software mas complejo, por lo que la reutilización y encasuplamiento son técnicas de tanta utilidad como la algorítmica clásica en el diseño y planteamiento de sistemas de calidad.

• Por ultimo, las EDs concebidas como elementos aislados, con misiones y requerimientos muy cerrados y puntuales, permitirán al alumno centrarse en las características de los mismos, teniendo que ampliar posteriormente su punto de vista con el fin de utilizar esos elementos puntuales en casos prácticos. Así queda perfectamente fijado los dos principios de actuación que están implícitos en cualquier sistema de desarrollo de sistemas de información: Análisis y Generalización, ambos en las las áreas de Especificación, diseño e Implementación.

Con este planteamiento la asignatura se puede ver como el desarrollo de una jerarquía de tipos abstractos de datos, como EDs que tienen en su interior la funcionalidad para ser manejados, y dicha funcionalidad forma una interfaz que permite el dialogo con otros TADs o clientes.

Por lo tanto las características y algorítmica referente al manejo de estos TAD han de ser estudiadas y comentadas, así como los medios necesarios para este estudio.

Se hace necesario definir un marco o lenguaje cuasi-formal, para poder realizar el dialogo y la transmisión de información a este respecto, siendo esto la causa de que en los primeros momentos de la asignatura, y juntamente con un repaso de las técnicas básicas de algorítmica, se planteen normativas de representación, especificación y seudocódigo que permitan el dialogo alumno-profesor.

Tras una introducción a los conceptos de abstracción, se plantean los medios y técnicas a utilizar (conceptos de algorítmica, seudocódigo, manejo de memoria dinámica, formalismos, ...) para posteriormente introducir el concepto de TAD y los primeros ejemplos del mismo. La segunda parte estudia la jerarquía propuesta, TAD lineales, árboles, Conjuntos y tablas, ...., para terminar con una aplicación de los TAD a las técnicas de Búsqueda y Ordenación. En un ultimo apartado se plantean las particularidades del manejo de estructuras de datos en soportes magnéticos.

El seguimiento de los conocimientos adquiridos por el alumno se realizará a partir de practicas tutoradas a realizar en "pizarra", con temas de interés en los que las estructuras de datos y su manejo tiene importancia. En el programa se señalan estas practicas como "aplicaciones" y se resumen en el apartado de "practicas".
Se planteará, asimismo, una practica de especificación, para valorar la utilización por los alumnos del lenguaje de especificación planteado en el curso, así como el manejo del seudocódigo en la implementación de las operaciones sobre los TAD's.

Como complemento, los alumnos realizarán una practica de especificación e implementación completa de un TAD, con la misión de fijar los conocimientos que se desarrollan a lo largo del curso y que por lo tanto implicara la practica totalidad de conocimientos del curso. Esta practica, dada su misión, es de desarrollo obligatorio y necesario.

1. Generalidades
   1. Primeras definiciones y Formalismos, Abstracción.
   2. Definición de Encapsulación.
   3. Tipos Abstractos de datos.
2. Algoritmos y Estructuras de datos (ED). La eficiencia de los algoritmos
   1. Análisis de algoritmos
   2. Medidas asintóticas. Órdenes de complejidad
   3. Reglas prácticas para el cálculo de la eficiencia.
   4. Algoritmos de Ordenación
3. TAD Lineales: Lista y derivados
   1. Lista (visión estática)
   2. Lista Dinámica
   3. Lista doblemente Enlazada
   4. Lista Ordenable
   5. Lista Ordenada
4. Pilas y Colas
   1. Pilas
   2. Aplicación: Evaluación de expresiones
   3. Aplicación: Eliminación de la recursividad
   4. Colas
   5. Aplicación: Simulaciones
   6. Bicolas
   7. Colas de prioridad
5. TAD Arbol. Arboles Generales y derivados
   1. TAD Nodo
   2. Arbol general
   3. Arbol Binario
   4. Recorridos
   5. Arbol de expresiones
   6. Arbol enhebrado
   7. Arbol estrictamente binario
   8. Arbol Binario de Búsqueda
   9. Código de Huffman
   10. Arbol AVL
   11. Montículo
6. Grafos
   1. Definiciones
   2. TAD
   3. Implementaciones
   4. Recorridos
   5. Árboles de extensión mínimos
   6. Caminos mínimos
   7. Estructuras unión-pertenencia
7. Dispersión
   1. TAD
   2. Dispersión cerrada
   3. Dispersión abierta
   4. Técnicas de Hasing y Rehasing
   5. Conjuntos y Tablas
      • Conjunto
      • Diccionario
      • Tabla Hash
8. Ficheros.
   1. Particularidades de sistema secundarios de Almacenamiento
   2. Los Ficheros como TAD
   3. TAD FileSystem
   4. Registro Físico
   5. Fichero
   6. Arboles B y B+
      1. Árbol B
      2. Árbol B*
      3. Árbol B+
   7. Especializaciones del TAD Fichero
      1. Fichero Secuencial
      2. Fichero Relativo
      3. Fichero Directo
      4. Ficheros Temporales y Overflow
      5. Ficheros Índice

Anotaciones Sobre JAVA

• Introducción a JAVA 

Implementaciones del TAD "Skip List" Lista con saltos:

• http://www.iam.unibe.ch/~wenger/DA/SkipList/
• http://www.csl.mtu.edu/~trjozwow/slList.html

Estructuras lineales:

• Catalogo de estructuras 
• Cuestiones para discusión y repaso

Estructuras arbóreas:

• Catalogo de estructuras 
• Cuestiones para discusión y repaso
• Ordenación por Montículo
  (HeapSort), Código y Simulación  
  • Implementación en Pascal
  • Implementaciones en Java y Pascal
  • http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html 
• HUFFMAN
  • http://www.compressconsult.com/huffman/ (no funciona)
  • http://www.ece.wpi.edu/infoeng/textbook/node94.html 
  • http://swww.ee.uwa.edu.au/~plsd210/ds/huffman.html (no funciona)
  • http://www.ics.uci.edu/~dan/pubs/DC-Sec4.html 
  • Todas las referencias posibles -> 
    http://datacompression.info/index.shtml

Familia de árboles B:

• Simulación de Funcionamiento Árbol B
  (http://sky.fit.qut.edu.au/~maire/baobab/baobab.html)
• Otra simulación
  (http://www.geocities.com/SiliconValley/Program/2864/File/btree.html)

Propuesta para el 2004

Documentación de utilidad

Seudocódigo y notación algorítmica.

 

Calculo de los tiempos de ejecución.

Buenas Practicas de Programación.

Plantilla para especificación seudoformal.

Textos de los temas de "Introducción" (Formato Zip).

 

Textos del tema "Recursividad" (Formato Zip).

 

Textos del tema "Estructuras Arbóreas" (Formato Zip).

 

Textos del tema "Montículos" (Formato Zip).

 

Textos del tema "Árboles Multicamino" (Formato Zip).

Textos del tema "Tablas Dispersión" (Formato Zip, 2 ficheros).

 

Difinición de TAD's

TClave (Algebraica, Cuasiformal)

TDatos (Algebraica, Cuasiformal)

TEnlaceSimple

TEnlaceMultiple (Algebraica, Cuasiformal)

TNodo (versión simple).

TNodo (versión general, Cuasiformal).

TLista

TLista (Algebraica, Lista Base).

TLista (Algebraica, Lista Indexada).

TLista (Algebraica, Lista con Cursor/Iterador).

TLista (Algebraica, Lista Ordenada).

TLista (CuasiFormal).

Lista Con Saltos (Teoría, Especificación y Implementación).

TPila (Algebraica).

TPila (como herencia directa de TLista, Cuasiformal).

TCola (Algebraica).

TCola (como herencia directa de TLista, Cuasiformal).

TArbolBinario (Cuasiformal, implementación genérica base de otros TAD expecializados ).

TABBusqueda (Cuasiformal, como expecialización de TArbolBinario ).

TArbolB (Cuaisformal)

TElementoIndice.

TNodoIndice.

Algoritmia y Bases Teóricas
		Introducción a la programación -- Tomo II -- Estructuras de datos G. Clavel, J Blondi -- Masson, 1985 392 pgs. -- Español
		Fundamentos de Algoritmia G. Brassard, P. Bratley -- Prentice Hall, 1997 597 pgs. -- Español
		El arte de programar Ordenadores -- Volumen III -- Clasificación y Búsqueda D.E. Knuth -- E. Reverte, 1987 774 pgs. -- Español
		Fundamentos de Programación L. Joyanes Aguilar, L. Rodriguez [et al.] -- McGraw Hill, 1996 228 pgs. -- Español
		Diseño de Programas. Formalismo y Abstracción R. Peña Mari -- Prentice Hall, 1993 255 pgs. -- Español
Estructuras de datos Clasicas
		Handbook of Algorithms and Data Structures (In Pascal y C) GH. Connet, R.Baeza-Yates -- Addison-Wesley, 1991 (2ª ed.) 425 pgs. -- Ingles
		Estructuras de datos y Algoritmos A.V.Aho, J.Hofcroft, J.D.Ullman -- Addison-Wesley, 1988 438 pgs. -- Español
		Estructuras de datos en Pascal A. Tenenbaum, M.J. Augenstein -- Prentice Hall, 1983 560 pgs. -- Español
		Estructuras de datos y Algoritmos M.A. Weiss -- Addison-Wesley, 1985 488 pgs. -- Español
		Estructuras de datos en C A.M. Tenenbaum, Y. Langsam, M.A. Augenstein -- Prentice Hall, 1993 696 pgs. -- Español
		Pascal y Estructuras de datos N.Dale, S.C. Lilly -- McGraw Hill, 1989 784 pgs. -- Español
		Estructuras de datos S. Lipschutz -- McGraw Hill, 1983 390 pgs. -- Español
		Data Structures. An Object-Oriented Approach W.J Collins -- Addison-Wesley Publishing, 1992 625 pgs. -- Ingles
		Estructuras de datos y Algoritmos (realización en Pascal) M. Collado Machuca [et al.] -- Diaz de santos, 1987 342 pgs. -- Español
		Data Structures & Program Desing in C R. Kruse/C.L. Tondo/B. Leung -- Pretice Hall International, 1997 670 pgs. -- Ingles
		Estructuras de datos y Diseño de programas R. Kruse -- Pretice Hall International, 1984 488 pgs. --Español
Estructuras de Datos y C++
		Algorithms and data structures in C++ L. Ammeraal -- John Wiley & Son, 1996 350 pgs. -- Ingles
		Algoritmos en C++ R. Sedgewick-- Addison-Wesley, 1995 720 pgs. -- Español
		Algorithms, data Structures, and problem Solving with C++ M.A. Weiss -- Addison-Wesley, 1996 820 pgs. -- Ingles
		Classic Data Structures in C++ T.A. Bud-- Addison-Wesley, 1994 540 pgs. -- Ingles
Estructuras de datos y Java
		A Practical Introduction to Data Structures And Algorithm Analysis. Java Edition C.A. Shaffer -- Prentice Hall, 1998 500  pgs. -- Ingles
		Data Structures & Problem Solving using Java M. A. Weiss -- Addison-Wesley, 1998 780 pgs. -- Ingles -- Codigo en: http://www.aw.com/cseng/titles/0-21-54991-3/ http://www.cs.fiu.edu/~weiss

http://www.dcc.uchile.cl/~rbaeza/handbook/hbook.html
versión electrónica y en línea de uno de los libros sobre estructuras de datos de mayor interés (Baeza-Yates).

http://hissa.nist.gov/dads/terms.html
Glosario completo de términos sobre ED, TAD y Algorítmica, con enlaces a los principales sitios con más información sobre el tema.

http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/ds_ToC.html
Un buen sitio con información, simulaciones y una orientación adecuada del tema de TAD y ordenación

http://www.dcs.port.ac.uk/~lesterc/sete1/notes/DS.html
Otro curso sobre estructuras y algorítmica de calidad e interés.

http://www.geocities.com/david_ees/Algoritmia/curso.htm
Un curso, elemental, de algoritmia, sencillo y de utilidad, ejemplo de información e este tipo en la WEB.

http://gva1.dec.usc.es/~pardo/WEB_C/ED/proyecto/tda.htm
Un sitio con información precisa sobre TAD, muy adaptado a la asignatura y con simulaciones e implementaciones de los TAP Básicos de interés real y académico

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/index.html
"Algorithms and Data Structures Research & Reference Material". Muchas implementaciones, algoritmos y material de referencia

http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
Animaciones e implementaciones de algoritmos de ordenación

http://epaperpress.com/s_man.html
Algunos algoritmos e información, siempre relativa a una serie de libros publicados

http://arianna.dei.unipd.it/books/java/cgc/jdsl/
Una librería de estructuras de datos en Java, con animaciones, estructuras de visualización y otras utilidades

 

---

Enlaces no revisados

http://www.farmingdale.edu/~porciem/bcs270f98.html
Material para un curso de estructuras, con algunos enlaces a material de interés.

http://www.polar.sunynassau.edu/~sherd/cmp211.htm
Enlace a un tutorial de Pascal y estructuras desarrolladas con el mismo.

http://www.cs.unm.edu/~crowley/papers/sds/sds.html
Estructuras para el manejo de textos.

http://www.dcs.st-and.ac.uk/~kh/papers/pseudoknot/section3_5.html
alguna información referente al manejo de estructuras.

http://www.cas.uc.edu/~ciminero/Courses/484/484.html y http://www.cas.uc.edu/~montjoy/Courses/484/484.html
material para cursos de estructuras de datos.

http://www.cs.toronto.edu/~andrew/csc270/lectures/c-3+4/sld001.html
Transparencias de un curso de introducción a las estructuras de datos.

http://vsfys1.fi.uib.no/htbin/helpgate/help/@helplib/POSIX/DATA_STRUCTURES/
manejo de estructuras de datos en PERL.

http://www.cs.uakron.edu/~bdauriol/courses/DataStructuresAndAlgorithmsI/Lab04/Lab04.html
material para un laboratorio de estructuras de datos.

http://www.cs.iastate.edu/~leavens/T-Shirts/ComS228-T-Shirts.html
Camisetas para una asignatura de introducción a las estructuras de datos.

http://auriga.atnf.csiro.au/library/COMPUTING/starlink/sun95.htx/node47.html
notas sobre estructuras de datos.

http://lml.ls.fi.upm.es/ftp/pub/funcional/www/Problemas/problemas/node35.html#SECTION002310000000000000000
Sobre manejo de TAD's (en español).

http://lml.ls.fi.upm.es/epd/prac9697/prac3/prac3.html y http://lml.ls.fi.upm.es/epd/prac9596/prac4/prac4.html
Practicas con TAD's, (En Español)

http://www.lsi.us.es/colabora/fieware/programas/tad.html
Un manual completo de un librería de TAD's De interés y en español)

http://www.rwc.uc.edu/cook/adt/adt_example.htm
Dos ejemplos de desarrollo de TAD's.

José Manuel Rodríguez Rodríguez
Profesor Asociado del Dpto. Informática
Universidad de Valladolid
jmrr@infor.uva.es
josemanuel.rodriguez@ccyl.es

Página actualizada a 25 de abril de 2001