Curso 2013-14

Estructuras de Datos y Algoritmos

Titulación:	Código:	Tipo:
Grado en Ingeniería Informática	21417	Obligatoria 2º curso
Grado en Ingeniería Telemática	21769	Optativa
Grado en Ingeniería en Sistemas Audiovisuales	21655	Optativa

 

Créditos ECTS:

4

Dedicación:

100 horas

Trimestre:

1º

 

Departamento:	Dpto. de Tecnologías de la Información y las Comunicaciones
Coordinador:	Ricardo Baeza Yates
Profesorado:	Ricardo Baeza Yates
Idioma:	Castellano
Horario:
Campus:	Campus de la Comunicación - Poblenou

 

Presentación de la assignatura

Estructuras de Datos y Algoritmos forma parte del grupo de asignaturas del área de Lenguajes de Programación, junto con las asignaturas: Fundamentos de la Programación (de primer curso, durante los 2n y 3er trimestres) y Programación Orientada a Objetos (de segundo curso, durante el 1er trimestre y en paralelo con la nuestra). Mientras estas dos últimas asignaturas del grupo son comunes a los tres grados (Ingeniería en Informática, Ingeniería en Telemática e Ingeniería en Sistemas Audiovisuales), nuestra asignatura es una especialización por tan sólo la Ingeniería en Informática. De esta manera, la asignatura parte de la voluntad de empezar a plantear a los alumnos una mentalidad de analistas de problemas y no sólo de programadores. No obstante, las capacidades y habilidades de programación de las
estructuras de datos y los tipos abstractos de datos son importantes en esta asignatura.

La asignatura presupone haber adquirido unos conocimientos y habilidades básicos de programación en la asignatura de Fundamentos de la Programación de primer curso. Los dos trimestres de esta asignatura habrán dado un dominio en las técnicas y tipos elementales de programación y estructuras de control de
flujo. A Estructuras de Datos y Algoritmos profundizará concentrándose en las formas de estructurar la información utilizada en un programa, en cómo poder gestionar esta información y en cómo conseguirlo de forma que no pueda tener efectos colaterales en la resto del programa. Además veremos la forma de evaluar su implementación óptima tanto en ocupación de espacio de memoria como en tiempo de ejecución de las operaciones y algoritmos con los que gestionaremos datos.

Las estructuras elementales que se verán serán las Estructuras Lineales, las Estructuras en Árbol y las Estructuras Asociativas. La programación de estas estructuras y sus algoritmos se realizará en
lenguaje C, ya aprendido durante Fundamentos de la Programación. Además la asignatura promoverá de forma especial la capacidad de analizar un
problema desde el punto de vista de la información utilizada y gestionada en este, y de cómo se puede diseñar y programar la mejor solución en cuanto a las estructuras de datos y sus operaciones de gestión. En este sentido el aprendizaje del alumno estará muy encaminado a resolver problemas que presenten escenarios lo más cercanos posibles a
casos reales.

Objetivos de aprendizaje

La asignatura quiere, en último término, que el alumno adquiera una primera visión de las tareas asociadas con el analista informático. Es decir, quiere conseguir que un alumno pueda partir de la
descripción verbal / textual de un problema a ser resuelto informáticamente y pueda diseñar y desarrollar los Tipos Abstractos de Datos (TADs) que lo resuelven, a partir de los siguientes pasos
esenciales:

* Comprender y especificar formalmente las necesidades funcionales del problema, es decir, especificar la firma de los TADs (tipos abstractos de datos) necesarios.

* Seleccionar y diseñar las estructuras de datos que serán utilizados en los TADs, optimizando el empleo en memoria y la complejidad temporal
de ejecución.

* Realizar un esquema completo de las estructuras de datos seleccionados.

* Implementar de forma óptima los TADs diseñados para incorporarlos a la aplicación que resuelve el problema inicial.

El alumno debe ser capaz, además, de poder entender por sí solo nuevas estructuras de datos más complejas que vaya encontrando en el
futuro y de poder incorporar en su repertorio para el análisis y resolución de problemas.

Todo ello ha de enlazar con la filosofía de diseño de programas descendente de la asignatura previamente realizada Fundamentos de la Programación y debe mostrar los claros vínculos con la asignatura paralela Programación
Orientada a Objetos.

 

Prerequisitos

Esta asignatura requiere de los conocimientos y habilidades adquiridos en la asignatura de Fundamentos de la Programación (de primer curso, durante el 2 º y 3 º trimestres). Esencialmente, la asignatura presupone haber adquirido unos conocimientos y habilidades básicos de programación que habrán dado un dominio en las técnicas y tipos elementales de programación y estructuras de control de flujo.

 

Competencias

A continuación se detallan aquellas competencias que los alumnos de Estructuras de Datos y Algoritmos deberán haber adquirido al finalizar la asignatura. Estas competencias están relacionadas con el análisis, diseño y desarrollo de estructuras de datos y las operaciones para su gestión, en programas de tamaño medio.

Competencias transversales

Competencias específicas

Instrumentales CG1: Capacidad de síntesis El alumno debe ser capaz de escribir soluciones con los elementos esenciales, de forma simple, elegante y tan eficiente como sea posible. CG2 : Capacidad de análisis El alumno debe ser capaz de analizar un problema concreto y proponer soluciones adecuadas para resolverlo. Interpersonales CG3 : Capacidad de comprender necesidades de terceros en la resolución de problemas El alumno a ser consciente de que como profesional tendrá que analizar y solucionar problemas planteados por terceros y por tanto los deberá saber escuchar y entender. CG4 : Dialogar y trabajar en equipo El trabajo de un informático raramente es en solitario dada la complejidad del desarrollo de aplicaciones de gran formato, y por eso es importante que el alumno ya se vaya acostumbrando a trabajar en grupo. Sistémicas CG5: Capacidad de aplicar el conocimiento a la práctica El alumno debe ser capaz de aplicar los conocimientos adquiridos en la resolución de problemas concretos, eligiendo la técnica que mejor se ajuste a cada caso. CG6: Interés por la calidad El alumno debe mostrar atención en la calidad de su trabajo.

Conocimientos (Saber) CE1: Conocimiento del concepto de Tipo Abstracto de Datos sus componentes (Conjunto de Apoyo y Interfaz o Firma) y aquellos conceptos que lleva implicados (encapsulamiento, independencia de implementación, reutilización, robustez, etc.) Y como están definidos formalmente (conjunto de operaciones constructoras, conjuntos puro / impuros , etc . ) CE2: Conocimiento de las estructuras de datos básicos. Concretamente: estructuras lineales (pilas, colas y listas), estructuras en árbol (árboles binarios de búsqueda, árboles balanceados o AVL, árboles parcialmente ordenados), estructuras asociativas (mesas, tablas de hash, mesas con AVLs), colas con prioridad (pilones o heaps) . CE3: Conocimiento de cómo se pueden combinar estas estructuras básicas para formar otros más complejos CE4 : Conocimiento de los algoritmos asociados a las estructuras. Operaciones básicas de gestión (creación, inserción, modificación, borrado, etc.); Algoritmos de búsqueda , funciones de hash, etc. CE5 : Conocimiento de los conceptos de funciones de complejidad o coste espacial y de ejecución. Esencialmente función del caso peor O ( ). Habilidades (Saber hacer) CE6: Capacidad de análisis y abstracción de las necesidades estructurales y funcionales de un problema. CE7: Especificación formal de problemas informáticos, concretamente de sus necesidades estructurales y de sus necesidades funcionales. CE8: Adecuación de las estructuras de datos básicos a ciertos problemas arquetípicos. CE9: Aplicación de las estrategias elementales de Implementación de los tipos abstractos de datos, optimizando el empleo en memoria y la complejidad temporal de ejecución. CE10: Capacidad de comprensión de nuevas estructuras de datos y de su aplicación

 

Evaluación

Siguiendo el espíritu del EEES, los alumnos serán evaluados mediante una fórmula mixta de forma continuada y de forma global final mediante
un examen.


Notas de Seminarios (NS): los alumnos irán siendo evaluados a partir de ejercicios realizados en clase durante las sesiones de seminarios. Estos
ejercicios de seminarios, que se realizarán de forma individual en clases reducidas, permitirán a los profesores hacer un seguimiento más preciso del alumno para conocer mejor y poder evaluar con más conocimiento las diversas fases del curso (seminarios, prácticas y examen). La nota de seminarios sólo se tendrá en cuenta si el alumno asiste a todos o como máximo en falla uno.


Notas de Prácticas (NP): los alumnos realizarán 4 prácticas a lo largo del curso, las cuales se empezarán durante la hora de clase y terminarán
fuera de clase. Estas se realizarán en equipos de 3 alumnos para que aprendan a trabajar en equipo. Se evaluarán para cada entrega que el equipo realice y la nota será la misma para los tres miembros del equipo. La evaluación se hará siempre que la práctica compile correctamente y ejecute sin errores de sistema. En este caso, la práctica se evaluará en base a la adecuación de la
solución al problema y los criterios de eficiencia de la solución, claridad y limpieza del código, documentación del código y funcionamiento con los juegos de datos aportados por los profesores. Las 4 prácticas harán media para obtener una nota global de prácticas.


Nota de Examen (NE): a final de la asignatura, los alumnos realizarán un examen que constará de tres partes: (a) una parte de tipo test que evaluará conceptos generales, (b) una parte con dos cuestiones de respuesta corta y / o de ejercicio de cálculo de funcionamiento de estructuras de datos,
y finalmente (c) un problema largo que evaluará la capacidad de analizar un problema, diseñar las estructuras de datos adecuadas, especificar formalmente la solución y los tipos abstractos de datos con las operaciones de la interfaz y el
esquema de las estructuras, y analizando la complejidad en espacio y en tiempo.

• Productos escritos (no recuperables): Notas de Seminarios (NS)
• Pruebas de ejecución (no recuperables): Notas de Prácticas (NP)
• Prueba escrita (recuperable): Nota de Examen (NE)

Autoevaluación: El alumno dispondrá de una colección de ejercicios con soluciones para irse auto-evaluando lo largo del curso. Estos ejercicios serán voluntarios y no contarán en la nota final.


Nota Final (NF): la nota final será calculada de la siguiente forma :


NF = NE * 0,5 + NP * 0,3 + NS * 0,2

Condiciones:

• NS será 0,0 si se ha fallado la asistencia a más    de un seminario
• NF se calcula sólo si: NE>= 5,0, NP>= 5,0 y NS >=5,0
Contrario NF= mínimo (NE, NP, NS)

 

Contenidos

 Bloque de contenido 1. Introducción a los Tipos Abstractos de Datos

Conceptos	Procedimentos	Actitudes
1. Introducción a las Estructuras de Datos 2. Breve contexto histórico 3. Necesidad de los Tipos Abstractos de Datos 4. Definición de los Tipos Abstractos de Datos 5. Noción de Coste Espacial y Temporal -> Función de Orden de Coste: O () 6. Beneficios de los Tipos Abstractos de Datos	1. Ejemplo de problemas de no utilización de los Tipos Abstractos de Datos.	1. Abstracción   2. Comprensión matemática

 

Bloque de contenido 2. Estructuras Lineales

Conceptos	Procedimentos	Actitudes
1. Aproximación Estructural a las Estructuras Lineales 2. Introducción a la Especificación formal de Tipos Abstractos de Datos a partir de las Est. lineales 3. Implementación de las Est. lineales 4. Comparativa de las Est. Lineales.	1. Analogía de las Estructuras Lineales funcionamiento de actividades cotidianas 2. Formalización de las operaciones de la interfaz de los tipos abstractos de datos: operaciones constructoras, modificadores y consultoras 3. Implementación estática y dinámica de las Est. lineales 4. Complejidad en Tiempo y Espacio de las Est. Lineales.	1. Abstracción   2. Análisis

 

Bloque de contenido 3. Estructuras en Árbol

Conceptos	Procedimentos	Actitudes
1. Propiedades, terminología y conceptos asociados a los árboles. 2. Recorridos de Árboles Binarios. 3. Estructuras de Árboles Binarios (AB). 4. Árboles Binarios de Búsqueda (ABC). 5. ABCs balanceados: Árboles Adelson-Velskii Landis (AVL) 6. Árboles Parcialmente Ordenados (APO)	1. Algoritmos de recorridos de Árboles Binarios. 2. Especificación Formal de AB. 3. Implementación Dinámica de AB. 4. Implementación Estática de AB. 5. Operaciones de balanceo de AVL. 6. Operaciones de inserción, modificación y borrado. 7. Complejidad en Espacio y Tiempo los Árboles.	1. Abstracción   2. Análisis

 

Bloque de contenido 4. Estructuras Asociativas

Conceptos	Procedimentos	Actitudes
1. Estructuras Asociativas: Tablas 2. Concepto de Clave y relación Clave-Valor, Búsqueda por Clave, etc. 3. Aproximación de Tablas con Listas: Eficiencia 4. Tablas de Hash: Conceptos, Propiedades, Eficiencia. 6. Fórmulas de Hashing. 7. Gestión de Desbordamiento de Hashing: Encadenamiento, Direccionamiento Abierto, etc. 8. Tablas con AVL: Conceptos, Eficiencia. .	1. Especificación Informal: Operaciones Generales   2. Implementación de Tablas de Hash.     3. Implementación de Tablas con AVL.	1. Abstracción   2. Análisis

 

Bloque de contenidos 5. Colas con Prioridad y Heaps

Conceptes	Procediments	Actituds
1. Diferencias funcionales respecto a la Cola normal. 2. especificación Informal 3. Funcionamiento a partir de Árboles Parcialmente Ordenados y Completos à Heaps.	1. Operaciones con Árbol Parcialmente Ordenado: Inserciones (Flotación), Consulta, Borrados (Hundido) 2. Implementación Estática a partir de APO con Pilones (Heaps) 3. Algoritmo de búsqueda y ordenación: Heapsort.	1. Abstracción   2. Análisis

 

Bloque de contenido 6. Análisis de Problemas

Conceptos	Procedimentos	Actitudes
1. Comprensión y especificación formal de las necesidades funcionales de un problema. 2. Selección y diseño de las estructuras de datos que serán utilizados en los Tipos Abstractos de Datos, optimizando el empleo en memoria y la complejidad temporal de ejecución. 3. Repaso y consolidación del todos los TADs vistos.	1. Especificación formal de la firma de los TADs necesarios. 2. Realizar un esquema completo de las estructuras de datos seleccionados. 3. Implementar de forma óptima los TADs diseñados para incorporarlos a la aplicación que resuelve el problema inicial. l.	1. Abstracción   2. Análisis

 

 

Metodología

Las actividades de aprendizaje se dividen de la siguiente forma:


• Sesiones de Teoría: los profesores presentan una serie de conceptos y técnicas, así como ejemplos de uso. Los alumnos deberán repasar, fuera de horas de clase, los apuntes tomados en clase para consolidar estos contenidos.


• Sesiones de Seminario: los alumnos, en grupos reducidos, resolverán ejercicios que ayudarán a consolidar los conceptos teóricos así como hacer de enlace hacia los trabajos prácticos. La realización es en solitario y durante la clase. Estos ejercicios serán supervisados ​​de cerca por los profesores para aclarar cualquier duda y ayudar al alumno en esta consolidación.


• Sesiones de Prácticas: los alumnos, en equipos de tres, deberán resolver aspectos prácticos de resolución de problemas de la asignatura. Básicamente ejercitarán las técnicas de programación de las estructuras de datos y de las operaciones de gestión, pero también deberán saber analizar la forma más óptima de hacerlo. Estas prácticas se empezarán en aula de ordenadores pero se tendrán que acabar de realizar for de horas de clase dada la intensidad que requieren esta problemas prácticos.


• Ejercicios de Autoevaluación: estos ejercicios pertenecen a una lista accesible desde el aula global para que los alumnos, fuera de horas de clase, puedan hacer un seguimiento de su aprendizaje de cada bloque de la asignatura.

 

Recursos

Fuentes de información para el aprendizaje. Bibliografía básica (soporte papel y electrónico)

- AHO, A.V. y otros. Fecha Structures and Algorithms . Addison- Wesley, 1983.

- FRANCH GUTIÉRREZ, X. Estructuras de datos . Especificación , diseño e implementación . Ediciones UPC, 1994.

Fuentes de información para el aprendizaje. Bibliografía complementaria (soporte papel y electrónico)

- WEISS, M. Fecha Structures and Algorithm Analysis in C. Benjamin Cummings, 1993.

- PEÑA , R. Diseño de programas. Prentice Hall , 2 ª Edición, 1999.

Fuentes de información para el aprendizaje . Bibliografía de refuerzo ( soporte papel y electrónico )

- NYHOFF , L. TADs, Estructuras de datos y resolución de problemas con C + + (2 ª Edición), Pearson / Prentice Hall, 2005.

Recursos didácticos. Material docente de la asignatura

- Transparencias de la asignatura en formato Power Point

- Lista de Problemas de la Asignatura

Recursos didácticos. Materiales y herramientas de soporte

- Web de la asignatura donde se recogerán enlaces interesantes, información puntual de enunciados y entrega de prácticas, soluciones de ejercicios, etc.