Departamento de Informática

   

Estructuras de Datos - I. T. Informática de Sistemas - Curso 2005-06

 

Área: Lenguajes y Sistemas Informáticos Titulación: I. T. Informática de Sistemas, segundo curso. Carga: Cuatrimestral de 7,5 créditos. Profesores: César Vaca Rodríguez

 

Novedades

 

12/09/2006: Calificaciones del examen extraordinario. Revisión el viernes 15 de 10:00 a 11:30. También puede consultar la solución del examen.

14/06/2006: Ya están disponibles los resultados del examen ordinario. Podeis consultarlos en el siguiente enlace. 31/05/2006: Transparencias del tema 4 4/05/2006: Transparencias de la segunda parte de la asignatura 4/05/2006: Referencias para la resolución de la segunda práctica: Apuntes de Grafos y extracto de las transparencias referentes a Montículos 4/05/2006: Enunciado de la segunda práctica 30/03/2006: Casos de prueba de la primera práctica: Caso n = 5, Tiempo óptimo = 270.9 Caso n = 6, Tiempo óptimo = 326.6 Caso n = 7, Tiempo óptimo = 404,4 Caso n = 8, Tiempo óptimo = 491.9 Caso n = 9, Tiempo óptimo = 529.4 Caso n = 10, Tiempo óptimo = 672.5 Caso n = 12, Tiempo óptimo = 822.9 Caso n = 13, Tiempo óptimo = 907.8 Caso n = 15, Tiempo óptimo = 933.7 Caso n = 20, Tiempo óptimo = 1214.8 Caso n = 25, Tiempo óptimo = 1595.6 Caso n = 30, Tiempo óptimo = 1940.1 Caso n = 50, Tiempo óptimo = 3013.1 Caso n = 99, Tiempo óptimo = 6377.7 16/03/2006: Enunciado de la primera práctica

 

Objetivos

 

La asignatura se inicia con el estudio de las técnicas básicas para el análisis y diseño de algoritmos y el estudio de los algoritmos de ordenación como ejemplo de uso de las técnicas anteriores. A continuación se introduce el concepto de Tipo Abstracto de Datos (TAD) y se enumeran los TADs fundamentales. El resto de la asignatura se divide en temas donde se estudian representaciones de datos y algoritmos y su aplicación a los TADs fundamentales. Conocer las técnicas básicas para realizar análisis de algoritmos. Utilizar correctamente las distintas técnicas de diseño de algoritmos. Familiarización y uso del concepto de Tipo Abstracto de Datos (TAD). Conocimiento de los TADs fundamentales. Comprensión de distintas implementaciones, incluyendo los algoritmos más relevantes, para cada uno de los TADs estudiados. Diseño de implementaciones eficientes para nuevos TADs.

 

Temario de la asignatura

 

Tema 1: Análisis de algoritmos Medida de algoritmos. Notación asintótica. Relaciones de Recurrencia. Tema 2: Diseño de algoritmos Recursividad Divide y vencerás. Fuerza bruta y Backtracking. Programación dinámica. Algoritmos voraces. Tema 3: Algoritmos de Ordenación Introducción Estrategias clásicas (inserción, selección e intercambio) Estrategias avanzadas (fusión, rápida y montículos) Estrategias especiales (recuento, residuos-recuento, residuos-partición) Tema 4: Tipos Abstractos de Datos Modelo de TAD TADs básicos Tema 5: Listas TADs de listas, listas ordenadas, pilas, colas y colas de prioridad. Representaciones y Algoritmos. Análisis. Tema 6: Arboles Definiciones. TAD arbol. Implementaciones del TAD arbol. Recorridos. Arb. binarios. Definiciones. Montículos. Propiedades. Uso como representación del TAD Cola de Prioridad. Arb. bin. de búsqueda. Propiedades. Uso de los ABB como representación de varios TADs. Arb. AVL Propiedades. Implementación de los Arb. AVL. Tema 7: Tablas de dispersión Definiciones y objetivos. Dispersión abierta. Dispersión cerrada. Análisis. Tema 8: Grafos Definiciones. Representaciones de Grafos. Arboles de extensión mínima. Algoritmos. Problema del camino mínimo. Algoritmos. Tema 9: Ficheros Introducción y objetivos. Algoritmos de ordenación externa. Representación mediante Arboles B.

Hoja de problemas Transparencias tema 4 Transparencias temas 5..7 Apuntes del tema 8

 

Bibliografía

 

Estructuras de datos en Java., M.A. Weiss.. Addison Wesley, 2000. Introduction to Algorithms. T.H. Cormen, C.E. Leiserson, R.L. Rivest. MIT Press, 1998. A Practical Introduction to Data Structures and Algorithm Analisys. Java Edition. C.A. Shaffer. Prentice-Hall, 1998. Data Structures and Algorithms in Java. M.T. Goodrich, R. Tamassia. Willey, 1998. Diseño de Programas. Formalismo y Abstracción. R. Peña Marí. Prentice Hall, 1997. Fundamentos de Algoritmia G. Brassard, P. Bratley. Prentice-Hall, 1997. Estructuras de Datos y Algoritmos. A.V. Aho, J.E. Hopcroft, J.D. Ullman. Addison-Wesley, 1988. Estructuras de Datos y Algoritmos. M.A. Weiss. Addison Wesley, 1995. Estructuras de Datos, Algoritmos y Programación Orientada a Objetos. G. L. Heileman. McGraw Hill, 1998. Fundamentals of Computer Algorithms E. Horowitz, S. Sahni. Computer Science Press.

 

Prácticas

 

Las prácticas serán opcionales, aunque contribuyen a la calificación final (ver apartado Evaluación). Se podrán realizar en grupos de 1, 2 o 3 personas, aunque el número de integrantes de un grupo puede influir en la calificación (ver apartado Evaluación). Para crear (o modificar) grupos se debe contactar con el profesor, ya sea personalmente o por correo electrónico. A partir del 30 de abril de 2006 ya no se permite la creacion de nuevos grupos. Solo hay una entrega de prácticas. Enunciado de la primera práctica Enunciado de la segunda práctica

 

Tutorías

 

Además de la atención en el despacho, en el horario de tutorías, los alumnos pueden contactar con los profesores mediante correo electrónico en las direcciones cvaca@infor.uva.es . También puede expresar sus opiniones en el foro de la asignatura

 

Evaluación

 

La calificación de la asignatura consta de una parte práctica (evaluada mediante las dos prácticas de la asignatura) y una parte teórica (evaluada mediante el examen de teoría) Prácticas: Cada práctica recibe una puntuación (llamemosla x) entre 0 y 1. Si una persona pertenece a un grupo de prácticas compuesto por m miembros, su nota de prácticas será xm (es decir, si la puntuación obtenida es 1.0, la nota es 1.0 independientemente del tamaño del grupo. Si la puntuación es 0.7, la nota será 0.7 si presenta la práctica individualmente, 0.5 si la presenta en pareja y 0.34 si la presenta en trio). En lo que sigue llamaremos t a la nota obtenida en el examen (sobre 10) y p1, p2 a las notas obtenidas en cada una de las prácticas (ambas sobre 1). En la convocatoria ordinaria la nota de la asignatura es 0.8*t+p1+p2. En la convocatoria extraordinaria la nota de la asignatura es max(0.8*t+p1+p2, 0.9*t+p1, 0.9*t+p2, t). Es decir, para aquellos que no entregaron prácticas la nota es la del examen, y para los que si entregaron se tiene en cuenta la nota de prácticas siempre que no les perjudique.

 

Información adicional

 

Turbo Pascal 7.0 Bibliotecas de Algoritmos y Estructuras de Datos

 

Datos de esta página

 

URL de esta página: http://www.infor.uva.es/~cvaca/asigs/eds.html Actualizado el 16 de marzo de 2006