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), así como muy recomendable 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.

Documento	Primer Apellido	Segundo Apellido	Nombre	Categoria
12370109	ALONSO	DE LA HUERTA	JOSÉ ANTONIO	PROFESOR TITULAR ESCUELA UNIVERSITARIA
24230778W	ARGUDO	ARGUDO	JOSE FIDEL	PROFESOR TITULAR ESCUELA UNIV.
45337574C	CABRERA	SANCHEZ	JUAN FRANCISCO	PROFESOR/A SUSTITUTO/A INTERINO/A
24233198F	GARCÍA	HORCAJADAS	Mª TERESA	PROFESORA TITULAR DE ESCUELA UNIVERSITARIA

Id. Compentencia	Orden	ID	Resultado formación y aprendizaje	Competencia
19288	2	CG09	Capacidad para resolver problemas con iniciativa, toma de decisiones, autonomía y creatividad. Capacidad para saber comunicar y transmitir los conocimientos, habilidades y destrezas de la profesión de Ingeniero Técnico en Informática.	COMPETENCIA GENERAL
19303	2	CG08	Conocimiento de las materias básicas y tecnologías, que capaciten para el aprendizaje y desarrollo de nuevos métodos y tecnologías, así como las que les doten de una gran versatilidad para adaptarse a nuevas situaciones.	COMPETENCIA GENERAL
19348	3	C06	Conocimiento y aplicación de los procedimientos algorítmicos básicos de las tecnologías informáticas para diseñar soluciones a problemas, analizando la idoneidad y complejidad de los algoritmos propuestos	COMPETENCIA ESPECÍFICA
19349	3	C07	Conocimiento, diseño y utilización de forma eficiente los tipos y estructuras de datos más adecuados a la resolución de un problema.	COMPETENCIA ESPECÍFICA
33116	2	CB2	Que los estudiantes sepan aplicar sus conocimientos a su trabajo o vocación de una forma profesional y posean las competencias que suelen demostrarse por medio de la elaboración y defensa de argumentos y la resolución de problemas dentro de su área de estudio	COMPETENCIA GENERAL
33118	2	CB4	Que los estudiantes puedan transmitir información, ideas, problemas y soluciones a un público tanto especializado como no especializado	COMPETENCIA GENERAL
33119	2	CB5	Que los estudiantes hayan desarrollado aquellas habilidades de aprendizaje necesarias para emprender estudios posteriores con un alto grado de autonomía	COMPETENCIA GENERAL

ID/ Orden	Resultado
1	Desarrollar programas, basándose en tipos abstractos de datos, de forma independiente de la implementación de éstos.
2	Organizar un determinado volumen de datos de la forma más racional posible en función de los requisitos del problema a resolver.
3	Implementar de diferentes formas una especificación de software dada. El alumno aprenderá a 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.).
4	Resolver problemas utilizando los TAD mas apropiados.

Total de actividades de docencia presencial:

Total de otras actividades:

Total de la asignatura:

Tipo actividad formativa	Código	Descripción	Horas	Detalle
1	01	Teoría	24	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.
2	02	Prácticas, seminarios y problemas	12	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.
3	03	Prácticas de informática	24	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.
10	10	Actividades formativas no presenciales	86,00	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.
12	12	Actividades de evaluación	4,00	Examen final

Procedimientos de Evaluación

ID/ Orden	Tarea / Actividad	Medios, Técnicas e Instrumentos	Ponderación
1	Pruebas de evaluación de resultados de actividades de aprendizaje	Tests de respuesta múltiple. Rúbricas	10 %
2	Pruebas escritas	Exámenes escritos teórico-prácticos. Verificación de la corrección de las soluciones aportadas por el alumno.	90 %

Criterios de Evaluación

MODALIDADES DE EVALUACIÓN
===========================

Para la primera convocatoria (junio) se seguirá un sistema de evaluación continua. En el resto de convocatorias (diciembre, febrero y septiembre, ya que no habrá docencia, se aplicará el sistema de evaluación global.

No obstante, según lo previsto en la normativa de evaluación de la UCA, el alumno podrá solicitar la evaluación global para la convocatoria de junio, en los plazos y términos establecidos por la ESI en su procedimiento de evaluación global de las asignaturas.

Evaluación continua:
===============

A lo largo del curso se realizarán varios cuestionarios online a través del campus virtual, para la evaluación de los resultados de las actividades de aprendizaje (EAA). 

Al finalizar el curso, los alumnos realizarán una prueba escrita (PE) con un componente de teoría y otro de problemas.

La nota correspondiente a la evaluación continua (NEC) del alumno será obtenida de la siguiente forma:

   NEC = 0,1 * EAA + 0,90 * PE

Evaluación final:
============

Se realizará un examen final escrito con contenidos teóricos y prácticos de la asignatura, en las fechas establecidas en las convocatorias oficiales del curso académico, que supondrá el 100% de la calificación final.

La copia total o parcial de las pruebas de evaluación, así como cualquier otro tipo de fraude detectado por los profesores, conllevará que se califique con 0 puntos a todos los implicados, sea cual fuere su papel, sin perjuicio de las acciones que la Inspección General de Servicios determine según la gravedad de la infracció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.

ID/ Orden	Temario	Descripción
1	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 en profundidad y anchura. 1.5. Búsqueda. 1.5.1. Árboles binarios de búsqueda. 1.5.2. Árboles de búsqueda equilibrados. 1.5.3. Árboles B. 1.5.4. Tablas hash. 1.6. Árboles parcialmente ordenados (montículos). Colas con prioridad.
2	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.
3	PRÁCTICAS: Resolución de problemas de programación utilizando tipos abstractos de datos no lineales. Práctica 1. Problemas de árboles binarios I Práctica 2. Problemas de árboles binarios II Práctica 3. Problemas de árboles generales Práctica 4. Problemas de árboles binarios de búsqueda Práctica 5. Problemas de árboles parcialmente ordenados y otros árboles Práctica 6. Problemas de grafos I Práctica 7. Problemas de grafos II Práctica 8. Problemas de grafos III

ID/ Orden

Temario

Descripción

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 en profundidad y anchura.
1.5. Búsqueda.
1.5.1. Árboles binarios de búsqueda.
1.5.2. Árboles de búsqueda equilibrados.
1.5.3. Árboles B.
1.5.4. Tablas hash.
1.6. Árboles parcialmente ordenados (montículos). Colas con prioridad.

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. Problemas de árboles binarios I
Práctica 2. Problemas de árboles binarios II
Práctica 3. Problemas de árboles generales
Práctica 4. Problemas de árboles binarios de búsqueda
Práctica 5. Problemas de árboles parcialmente ordenados y otros árboles
Práctica 6. Problemas de grafos I
Práctica 7. Problemas de grafos II
Práctica 8. 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, 2005Nyhoff, 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.

UniversidaddeCádiz

Programa Docente de 21714016 - ESTRUCTURAS DE DATOS NO LINEALES