Requisitos previos

Para poder cursar con razonables posibilidades de éxito esta asignatura es
requisito haber superado las dos asignaturas de programación de primer curso
(Introducción a la Programación y Metodología de la Programación).

También es necesario haber cursado la asignatura Análisis de Algoritmos y
Estructuras de Datos (segundo curso, primer cuatrimestre) y cursar la asignatura
del mismo cuatrimestre Programación Orientada a Objetos.

Cualquier matrícula efectuada que incumpla estos requisitos obviamente es
responsabilidad exclusiva del estudiante.

Recomendaciones

Para poder seguir la asignatura razonablemente es aconsejable:

- Conocer los aspectos relacionados con la descomposición de problemas, el diseño
modular y la abstracción operacional.
- Saber especificar de manera informal los algoritmos mediante precondiciones y
postcondiciones.
- Ser capaz de definir algoritmos de una manera correcta mediante el uso de
estructuras de control, bucles, sentencias condicionales, etc. según convenga a
la finalidad, eficiencia y claridad del código.
- Conocer los mecanismos de transferencia de parámetros y utilizarlos
correctamente.
- Conocer y usar correctamente los tipos de datos básicos que ofrecen los
lenguajes de programación y especialmente, los tipos estructurados: cadenas de
caracteres, vectores, matrices, registros y ficheros.
- Dominar el uso de punteros y la gestión dinámica de memoria.
- Ser capaz de implementar, en un lenguaje de programación de alto nivel,
programas de pequeño y mediano tamaño haciendo uso de la descomposición modular
del software.
- Saber elegir y diseñar adecuadamente casos de prueba para los programas y
funciones implementados.
- Distinguir y saber resolver sumas aritméticas y geométricas. Reconocer otras
sumas notables: la armónica y la expresión del número e mediante serie de
potencias.
- Conocer las nociones básicas de combinatoria (combinaciones y permutaciones) y
los rudimentos de la probabilidad discreta: variable aleatoria discreta, noción
de probabilidad, hipótesis de equiprobabilidad, media y media ponderada.
- Conocer los mecanismos de abstracción en programación y su importancia para la
resolución de problemas.
- 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 conceptos de programación basada en tipos abstractos y de
reutilización de los módulos de software.
- Conocer el concepto de recursividad y sus tipos y saber implementar algoritmos
recursivos para resolver problemas.
- Saber separar perfectamente los aspectos computacionales puros de los efectos
colaterales como la E/S y reconocer la importancia de que la E/S, los interfaces
gráficos, etc., no deben mezclarse ni ensuciar las funciones que implementan los
algoritmos y las estructuras de datos.
- Saber analizar algoritmos, así como expresar, interpretar y comparar los
resultados de los análisis en notación asintótica.
- Saber realizar análisis empíricos de los algoritmos, utilizando técnicas de
medida del tiempo en un computador.
- Saber resolver ecuaciones de recurrencia sencillas y algunos casos notables.

Profesorado

Nombre	Apellido 1	Apellido 2	C.C.E.	Coordinador
José Antonio	Alonso	de la Huerta	Profesor Titular Escuela Universitaria	S
José Fidel	Argudo	Argudo	TEU	S
Mª TERESA	GARCÍA	HORCAJADAS	PROFESORA TITULAR DE ESCUELA UNIVERSITARIA	N

Competencias

Se relacionan aquí las competencias de la materia/módulo o título al que pertenece la asignatura, entre las que el profesorado podrá indicar las relacionadas con la asignatura.

Resultados Aprendizaje

Actividades formativas

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 el
desarrollo de especificaciones e implementaciones
de TAD, y 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 orientado a objetos. 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
que puedan plantear mayor dificultad; finalmente,
cada alumno programará en el ordenador las
soluciones de los problemas del guión.

Estas actividades se corresponden con las horas
de trabajo personal del alumno, incluyendo las
horas de estudio de los contenidos teóricos y
prácticos de la asignatura, así como la
realización de problemas y trabajos propuestos.

Examen final

Evaluación

Criterios Generales de Evaluación

- Adecuación de la solución a la especificación del problema.
- Elección de los tipos abstractos de datos apropiados.
- Uso correcto de los TADs según su especificación.
- Elección adecuada de la implementación de cada TAD.
- Presentación, claridad y eficiencia de la solución.

Procedimiento de Evaluación

Procedimiento de calificación

Para la primera convocatoria se seguirá un sistema de evaluación continua. En el
resto de convocatorias, ya que no habrá docencia, se aplicará el sistema de
evaluación final.

Evaluación continua:
A lo largo del curso, en fechas publicadas con antelación, se realizarán una o
más pruebas para la evaluación de los resultados de las actividades de
aprendizaje. El resultado obtenido en estas pruebas tendrá un peso del 30% en la
calificación final del alumno. El 70% restante corresponderá al resultado del
examen final.
Solamente en casos de fuerza mayor que hayan impedido al alumno presentarse a
las pruebas mencionadas éste podrá solicitar al profesor coordinador de la
asignatura el cambio al sistema de evaluación final.

Evaluación final:
Aquellos alumnos que se sometan a evaluación final realizarán el examen final
establecido para la evaluación continua y además se les hará una prueba especial
para evaluar los resultados de las actividades de aprendizaje.
La nota correspondiente a la evaluación del alumno se compone del 70% del
examen final y el 30% de la prueba especial.

Descripcion de los Contenidos

            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.

        

            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.

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
        

Bibliografía

Bibliografía Básica

Aho, A.; Hopcroft, J.; Ullman, J.
   Estructuras de datos y algoritmos.
   Addison-Wesley, 1988.
Alonso, J.A.; Argudo, J.F.; García, M.T.
   Estructuras de Datos en C.
   Depto. Lenguajes y Sistemas Informáticos, UCA, 2003.
Fernández-Valdivia, J.; Garrido, A.; García, M.
   Estructuras de datos. Un enfoque práctico usando C. 1998.
Garrido, A.; Fernández-Valdivia, J.
   Abstracción y Estructura de Datos en C++. Delta Publicaciones. 2013.
Heileman, G. L.
   Estructuras de Datos, Algoritmos y Programación Orientada a Objetos.
   McGraw-Hill, 1996.
Langsam, Y; Augenstein, M. J.; Tenenbaum, A. M.
   Estructuras de Datos con C y C++.
   Prentice-Hall, 1997.

Bibliografía Específica

Hernández Figueroa, Z. J. y otros
   Fundamentos de Estructuras de Datos. Soluciones en Ada, Java y C++.
   Paraninfo, 2005
Nyhoff, Larry R.
   TADs, estructuras de datos y resolución de problemas con C++.
   Prentice-Hall, 2006.
Standish, T.A.
   Data Structures, Algorithms and Software Principles in C.
   Addison-Wesley, 1995.
Stroustrup, Bjarne.     
   The C++ programming language. Special edition.     
   Addison-Wesley. 2000.     
Stroustrup, Bjarne.
   Programming: Principles and practice using C++.
   Addison-Wesley. 2008.
Weiss, M.
   Data Structures and Algorithm Analysis in C.
   Addison-Wesley, 1996.

El presente documento es propiedad de la Universidad de Cádiz y forma parte de su Sistema de Gestión de Calidad Docente. En aplicación de la Ley 3/2007, de 22 de marzo, para la igualdad efectiva de mujeres y hombres, así como la Ley 12/2007, de 26 de noviembre, para la promoción de la igualdad de género en Andalucía, toda alusión a personas o colectivos incluida en este documento estará haciendo referencia al género gramatical neutro, incluyendo por lo tanto la posibilidad de referirse tanto a mujeres como a hombres.