María José Ferreiro Ramos
María Teresa García Horcajadas (Coordinadora)
Daniel Molina Cabrera
Francisco Periáñez Gómez
Joaquín Pizarro Junquera
Jesús Román Álvarez-Ossorio

El objetivo general de la asignatura es el estudio de una metodología de
programación basada en la creación de tipos abstractos de datos que facilite la
construcción de programas y el diseño de estructuras de datos adecuadas para
procesarlos eficientemente. Para alcanzar este objetivo general se definen los
siguientes objetivos específicos:

•Conocer los mecanismos de abstracción y su importancia para la resolución de
problemas.

•Conocer los conceptos de programación basada en tipos abstractos y de
reutilización de los módulos de software.

•Comprender la necesidad de separación entre los niveles de especificación,
implementación y aplicación en el desarrollo de módulos software.

•Desarrollar programas, basándose en tipos abstractos de datos, de forma
independiente de la implementación de éstos.

•Conocer los tipos abstractos de datos Pilas, Colas y Listas, sus
implementaciones más comunes y su utilidad.

•Organizar un determinado volumen de datos de la forma más racional posible en
función de los requisitos del problema a resolver.

•Saber analizar, especificar y documentar tipos abstractos de datos.

•Ser capaz de implementar de diferentes formas una especificación de software
dada. El alumno debe saber escoger entre diferentes implementaciones
alternativas de una abstracción de datos, y razonar sobre la solución escogida
en función de los recursos necesarios (tiempo de ejecución, espacio requerido,
etc.).

•Saber resolver problemas utilizando los TAD mas apropiados.

Teoría: Tipos abstractos y estructuras de datos lineales.

Tema 1. Tipos abstractos de datos.
1.1. Conceptos, terminología y ejemplos.
1.2. Tipos abstractos de datos.
1.3. Modularidad.
1.4. Uso de TAD.
1.5. Ejemplo: Especificación e implementación del TAD Número Racional.
1.6. Ejemplo: Uso del TAD Número Racional.

Tema 2. Pilas.
2.1. Concepto de pila.
2.2. Especificación de operaciones.
2.3. Diferentes representaciones del TAD pila.
2.3.1. Estáticas.
2.3.2. Dinámicas.
2.4. Aplicaciones.

Tema 3. Colas.
3.1. Concepto de cola.
3.2. Especificación de operaciones.
3.3. Diferentes representaciones del TAD cola.
3.3.1. Estáticas: lineal y circular.
3.3.2. Dinámicas.
3.4. Aplicaciones.

Tema 4. Listas.
4.1. Concepto de lista.
4.2. Especificación de operaciones.
4.3. Diferentes representaciones del TAD lista.
4.3.1. Implementación mediante vectores.
4.3.2. Implementación mediante punteros.
4.4. Otras estructuras enlazadas.
4.4.1. Listas con cabecera.
4.4.2. Listas doblemente enlazadas.
4.5. TAD lista circular.
4.6. Aplicaciones de las listas.

Tema 5. Ficheros.
5.1. Introducción.
5.2. Conceptos básicos.
5.3. Organización secuencial.
5.3.1. Especificación del TAD fichero secuencial.
5.3.2. Implementación del TAD fichero secuencial.
5.4. Organización directa o aleatoria.
5.4.1. Especificación del TAD fichero directo.
5.3.2. Implementación del TAD fichero directo.
5.5. Organización secuencial indexada.
5.3.1. Especificación del TAD fichero secuencial indexado.
5.3.2. Implementación del TAD fichero secuencial indexado.

Prácticas: Resolución de problemas de programación utilizando tipos abstractos
de datos lineales.

Las prácticas de la asignatura se dedicarán a la resolución de problemas de
programación aplicando los principios de descomposición de problemas,
abstracción, especificación e implementación de tipos abstractos de datos
utilizando las características de modularidad que proporcione el lenguaje de
programación.
En cada tema del programa de prácticas se propondrán diversos problemas
pensados para incidir sobre los siguientes puntos:
• Crear diferentes tipos abstractos de datos y realizar distintas
implementaciones de cada tipo.
• Practicar con el uso eficiente de los distintos tipos abstractos de datos,
eligiendo los más adecuados para cada problema concreto.
• Trabajar con las especificaciones de los tipos sin hacer referencia a su
implementación.
• Practicar con la implementación más adecuada de cada tipo abstracto de
datos según el problema a resolver.
Tema 1. Memoria dinámica y ficheros en C.
Tema 2. Tipos abstractos de datos
Tema 3. Pilas
Tema 4. Colas
Tema 5. Listas

Las clases teóricas se basarán fundamentalmente en las explicaciones del
profesor sobre el temario, así como en la realización de ejercicios prácticos
(sobre pizarra) asociados al mismo.
Se incentivará la participación activa del alumnado en las clases,
realizando en grupos desarrollos de especificaciones e implementaciones de TAD,
provocando el profesor un debate abierto sobre cada uno de los temas que se
traten, motivando a los alumnos para que propongan soluciones alternativas a
los problemas planteados y su posterior discusión.
En las clases prácticas se proporcionará al alumno guiones de prácticas en
los que se incluirán cuestiones teóricas y una serie de problemas de
programación, que se resolverán empleando un lenguaje de programación
estructurada. los alumnos asistirán a clase con dichos guiones, que los tendrán
disponibles en el campus virtual con suficiente antelación, y con los problemas
planteados, de forma que en clase se discutirá en grupo la resolución de dichos
problemas y el profesor explicará aquéllos problemas que plantean mayor
dificultad, finalmente, cada alumno resolverá los problemas del guión con la
supervisión del profesor.

Nº de Horas (indicar total): 112,5

• Clases Teóricas: 30  
• Clases Prácticas: 28  
• Exposiciones y Seminarios:  
• Tutorías Especializadas (presenciales o virtuales):
  • Colectivas: 2  
  • Individules:  
• Realización de Actividades Académicas Dirigidas:
  • Con presencia del profesorado:  
  • Sin presencia del profesorado:  
• Otro Trabajo Personal Autónomo:
  • Horas de estudio: 48,5  
  • Preparación de Trabajo Personal:  
  • ...

    Esas 48.5 horas de
    estudio están
    repartidas de la
    siguiente forma:
    18 horas de
    estudio de la
    teoría, 9 h. de
    estudio de la
    práctica, 21.5 h.
    de realización de
    problemas, además
    de las clases
    prácticas, que
    también realizan
    problemas con la
    supervisión del
    profesor y
    dirigidos por él.

     
• Realización de Exámenes:
  • Examen escrito: 4  
  • Exámenes orales (control del Trabajo Personal):  

Evaluación continua.

El alumno realizará sus prácticas siguiendo las instrucciones de los
guiones de prácticas que se le proporcionarán a lo largo del curso. En algunas
sesiones de prácticas se  realizarán controles consistentes en pruebas escritas
sobre el contenido de las mismas. Estos controles se realizarán durante la
primera parte de la sesión de prácticas y se harán de forma aleatoria, siendo
un total de tres a lo largo del curso. La evaluación de estos controles dará
lugar a la nota de prácticas, que será la media aritmética de las
calificaciones individuales de todos ellos. La nota de prácticas formará parte
de la calificación final en la asignatura (35%). No obstante, para que la
evaluación de prácticas sea tenida en cuenta se considera obligatoria la
asistencia regular a las clases prácticas.
El alumno podrá decidir si quiere hacer evaluación continua, o no, en el
momento de la realización del primer control de prácticas. Si decide hacer la
entrega de dicho control, se comprometerá a la evaluación continua y por tanto,
deberá cumplir todas las condiciones exigidas para la misma, de forma que si
alguno de los controles restantes no los hiciera, la nota del mismo para hacer
la media sería de 0 puntos.
En la convocatoria de junio, el alumno realizará un examen escrito que constará
de dos partes, una teórica y otra práctica. La primera constará de una serie de
preguntas de respuesta corta, que contará un 30 % de la nota final, y la
segunda incluirá un problema que supondrá un 35% dando lugar a la siguiente
calificación:

Nota final = Teoría (30%) + Problema (35%) + Evaluación Continua (35%)

Evaluación no continua:

Para aquéllos alumnos que por algún motivo no puedan realizar la evaluación
continua, o bien, así lo decidan cuando se realice el primer control, se
realizará un examen final escrito que constará de dos partes, una teórica y
otra práctica. La primera constará de una serie de preguntas de respuesta corta
y la segunda incluirá diversos problemas para los que el alumno deberá aportar
una solución fundamentada en el contenido teórico de la asignatura, así como
implementar dicha solución. El examen se puntuará en una escala de 0 a 10,
ponderando al 30% la teoría y al 70% los problemas.

Nota: la evaluación continua sólo tiene validez para la convocatoria de junio.

Alonso, J.A.; Argudo, J.F.; García, M.T.
Estructuras de Datos I.
Depto. Lenguajes y Sistemas Informáticos, UCA, 2003.
Ammernal, L.
Programs and Data Structures in C. Wiley, 1991.
Aho, A.; Hopcroft, J.; Ullman, J.
Estructuras de datos y algoritmos. Addison-Wesley, 1988.
Fernández-Valdivia, J.; Garrido, A.; García, M.
Estructuras de datos. Un enfoque práctico usando C. 1998.
Folk, M.J.; Zoellick, B.
Estructuras de Archivos. Addison-Wesley, 1992.
Heileman, G. L.
Estructuras de Datos, Algoritmos y Programación Orientada a Objetos.
McGraw-Hill, 1996.
Horowith, E.; Shanni, S.
Fundamentals of data structures in Pascal. Computer Science Press, 1990.
Knuth, D.
El arte de programar ordenadores. Ed. Reverté, 1987.
Kruse, R. L.; Leung, B. P.; Tondo, C. L.
Data Structures and Program Design in C. Prentice-Hall, 1991.
Langsam, Y; Augenstein, M. J.; Tenenbaum, A. M.
Estructuras de Datos con C y C++. Prentice-Hall, 1997.
Liskov, B.; Guttag, J.
Abstraction and specification in program development. MIT Press, 1989.
Schildt, H.
C: Manual de Referencia. McGraw-Hill, 1990.
Standish, T.A.
Data Structures, Algorithms and Software Principles in C.
Addison-Wesley, 1995.
Weiss, M.
Data Structures and Algorithm Analysis in C. Addison-Wesley, 1996.
Wirth, N.
Algoritmos + Estructuras de datos = Programas. Ed. del Castilllo, 1980.
Wirth, N.
Algoritmos y Estructuras de datos. Prentice-Hall, 1986.