Profesorado

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

Situación

Prerrequisitos

•Entender 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 pequeña-mediana envergadura, expuesto, en
términos de una
especificación más o menos formal, y de decidir cuál de las
posibles
soluciones es la más apropiada para un entorno determinado.
•Saber utilizar coherentemente funciones.
•Conocer el mecanismo de paso de parámetros y utilizarlo
correctamente.
•Conocer los tipos de datos básicos que ofrece cualquier
lenguaje de
programación.

Para ello es aconsejable que el alumno haya cursado
previamente la
asignatura de Introducción a la Programación.

Contexto dentro de la titulación

Esta asignatura se imparte en el segundo cuatrimestre del primer
curso de la
titulación y en ella el alumno estudia 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
instalarse 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.
- Comunicación 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 Pilas, Colas y Listas,
  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 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.

Programa

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

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,
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.

Distribución de horas de trabajo del alumno/a

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

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

Técnicas Docentes

Realización de trabajos en grupo.

Criterios y Sistemas de Evaluación

Evaluación no continua:

Puesto que esta asignatura deja de tener docencia la evaluación
no puede ser continua.
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

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.