Profesorado

José Antonio Alonso de la Huerta (Coordinador)
José Fidel Argudo Argudo
Mª Teresa García Horcajadas
Jesús Román Álvarez-Ossorio

Situación

Prerrequisitos

•Dominar el funcionamiento y la utilidad de la gestión dinámica de memoria.
•Saber especificar precisa y certeramente los algoritmos, mediante predicados
pre/post.
•Ser capaz de codificar de una manera correcta mediante el uso de estructuras
de control claras, bucles, sentencias condicionales, etc. según convenga a la
claridad y finalidad del segmento de código.
•Ser capaz de confeccionar, en lenguaje C, algoritmos correctos que resuelvan
un problema de mediana envergadura, descrito en términos de su especificación,
y de decidir cuál de las posibles soluciones es la más apropiada para un
entorno determinado.
•Dominar el mecanismo de paso de parámetros y utilizarlo correctamente.
•Dominar los tipos de datos básicos que ofrece cualquier lenguaje de
programación.
•Dominar el diseño recursivo como técnica de desarrollo de programas.
•Dominio profundo de las estructuras de datos lineales y ficheros.

Para ello es necesario que el alumno haya cursado previamente con
aprovechamiento las asignaturas "Introducción a la Programación", "Estructura
de Datos I" y "Metodología de la Programación" de primer curso.

Contexto dentro de la titulación

Esta asignatura es continuación de Estructura de Datos I (primer curso,
segundo cuatrimestre) y ambas asignaturas se dedican al 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.

Recomendaciones

Sería recomendable que el alumno dispusiera de un ordenador personal donde
instalar el compilador de C utilizado en las prácticas, con objeto de
obtener un mejor aprovechamiento de los contenidos impartidos en la asignatura.

Competencias

Competencias transversales/genéricas

- Capacidad de análisis y síntesis.
- Capacidad de expresión oral y escrita.
- Resolución de problemas.
- Trabajo en equipo.
- Capacidad de organización.
- Razonamiento crítico.
- Preparación y presentación de documentación.

Competencias específicas

• Cognitivas(Saber):

  •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.
  •Conocer los tipos abstractos de datos árboles y grafos, sus
  implementaciones más comunes y su utilidad.
  •Saber analizar, especificar y documentar tipos abstractos de datos.

• Procedimentales/Instrumentales(Saber hacer):

  •Desarrollar programas, basándose en tipos abstractos de datos, de
  forma independiente de la implementación de éstos.
  •Organizar un determinado volumen de datos de la forma más racional
  posible en función de los requisitos del problema a resolver.
  •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.).
  •Resolver problemas utilizando los TAD mas apropiados.

• Actitudinales:

  - Aprendizaje autónomo.
  - Planificación de las actividades a desarrollar.
  - Toma de decisiones.
  - Innovación y creatividad.
  

Objetivos

El objetivo general de esta 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:

1. Dominio de la metodología de diseño de tipos de datos: abstracción,
especificación e implementación.
2. Estudio de tipos abstractos de datos no lineales (árboles y grafos) y
algoritmos de tratamiento.
3. Análisis de las ventajas e inconvenientes de las diferentes
implementaciones de tipos abstractos de datos.
4. Encapsulamiento en módulos de programación de tipos abstractos de datos y
utilización en base a su especificación y no a su implementación.

Programa

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

Tema 1. Árboles.
1.1. Concepto de árbol. Definiciones básicas.
1.2. Árboles binarios.
1.2.1. Especificación de operaciones.
1.2.2. Implementación vectorial de árboles binarios.
1.2.3. Implementación mediante un vector de posiciones relativas.
1.2.4. Implementación usando celdas enlazadas.
1.3. Árboles generales.
1.3.1. Especificación de operaciones.
1.3.2. Implementación mediante listas de hijos.
1.3.3. Implementación usando celdas enlazadas.
1.4. Recorridos de árboles. Algoritmos recursivos e iterativos.
1.4.1. Preorden.
1.4.2. Inorden.
1.4.3. Postorden.
1.4.4. Recorrido por niveles.
1.5. Árboles binarios de búsqueda.
1.6. Árboles equilibrados AVL.
1.7. Árboles parcialmente ordenados (montículos). Colas con prioridad.
1.8. Árboles B.

Tema 2. Grafos.

2.1. Concepto de grafo. Definiciones básicas.
2.2. Diferentes representaciones de grafos.
2.2.1. Matriz de adyacencia  y matriz de costes.
2.2.2. Listas de adyacencia.
2.3. Recorridos de grafos. Búsqueda.
2.3.1. En profundidad.
2.3.2. En anchura.
2.4. Algoritmos de caminos de coste mínimo.
2.4.1. Algoritmo de Dijkstra.
2.4.2. Algoritmo de Floyd.
2.4.3. Algoritmo de Warshall.
2.5. Algoritmos de árboles de extensión de coste mínimo.
2.5.1. Algoritmo de Prim.
2.5.2. Algoritmo de Kruskal.

Prácticas: Resolución de problemas de programación utilizando tipos abstractos
de datos no 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.
• Seleccionar entre los algoritmos conocidos los adecuados para resolver
cada problema propuesto.

Práctica 1. Entrada y salida de árboles
Práctica 2. Problemas de árboles binarios I
Práctica 3. Problemas de árboles binarios II
Práctica 4. Problemas de árboles generales
Práctica 5. Problemas de árboles binarios de búsqueda
Práctica 6. Problemas de árboles parcialmente ordenados y otros árboles
Práctica 7. Problemas de grafos I
Práctica 8. Problemas de grafos II
Práctica 9. Problemas de grafos III

Metodología

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,
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.
A lo largo del curso 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.
El alumno realizará las prácticas bajo la supervisión del profesor y por su
cuenta empleando un lenguaje de programación estructurada.

Distribución de horas de trabajo del alumno/a

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

• Clases Teóricas: 28  
• 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: 2  
  • Sin presencia del profesorado: 9,5  
• Otro Trabajo Personal Autónomo:
  • Horas de estudio: 40  
  • Preparación de Trabajo Personal:  
  • ...
     
• Realización de Exámenes:
  • Examen escrito: 3  
  • Exámenes orales (control del Trabajo Personal):  

Técnicas Docentes

Criterios y Sistemas de Evaluación

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.

Recursos Bibliográficos

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.
García, M.T.; Argudo, J.F.; Alonso, J.A.
Estructuras de Datos en C.
Depto. Lenguajes y Sistemas Informáticos, UCA, 2001.
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.