Curso 2015-2016

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, Diego S�ez Trumper
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.