Presentación

Esta es la página principal de la Asignatura Estructuras de Datos en la Ingeniería Técnica de Informática de Gestión (código 16504, Plan 1996) en la Universidad de Valladolid.

Tablón de anuncios

Atención: El contenido de esta sección se actualizará a lo largo del curso.

 

Fecha	Aviso
07/10/2010	Enunciado de la práctica de la asignatura.
07/10/2010	Transparencia del primer tema.

Fechas límite

Atención: El contenido de esta sección puede cambiar.

 

Fecha	Convocatoria	Lugar
11/02/2009 (10:00)	Examen convocatoria ordinaria	Aulas 03-04-05
13/07/2009 (9:00)	Examen convocatoria extraordinaria	Aulas 102-103-104

También puede consultar las convocatorias de exámenes e información asociada en la página de la Escuela

.

Documentación

En esta sección se incluye toda la documentación que los profesores de la asignatura proporcionan como complemento o apoyo a la docencia presencial impartida. Nunca se debe considerar como la única fuente de información, unos "apuntes" oficiales o el sustituto de un buen libro (al respecto, consúltese la subsección sobre Bibliografía de la asignatura).

Atención: A medida que avance el curso se irán depositando más archivos o modificando alguno de los existentes, estos cambios se indicarán en el tablón de anuncios.

Puede encontrar documentación adicional en la sección Histórico.

Teoría

Nota: Si alguien desea que deposite alguno de los documentos siguientes en reprografía, que me lo haga saber.

• Hoja de Problemas.
• Transparencias del Tema 2
• Transparencias del Tema 3
• Transparencias del Tema 4
• Transparencias del Tema 5
• Transparencias del Tema 6
• Transparencias del Tema 7
• Apuntes del Tema 8

Puede consultar el temario de la asignatura en esta sección.

Laboratorios

A medida que avance el curso se añadirán los enunciados de las prácticas y documentación adicional.

• Enunciado de la segunda práctica
• Enunciado de la primera práctica
• Fichero del corpus

Software

• Programillas usados en la docencia:
• Problema de las N-Reinas
• Demostración métodos de ordenación (1)
• Demostración métodos de ordenación (2)
• Evaluación de representaciones del TAD Partición
• Representaciones basadas en árboles binarios (Nota: no se ha implementado la operación de borrado en árboles rojo-negro)
• Turbo-Delphi (versión gratuita)
• Para nostálgicos: Turbo Pascal 7.0
• Página oficial de Smart Eiffel
• Página oficial de Java

Profesores

Los profesores de estas asignaturas, durante el curso 2008-09, son los siguientes:

 

Grupo	Profesor
1T (Teoría)	César Vaca Rodríguez
1L (Laboratorio)	César Vaca Rodríguez
2L (Laboratorio)	César Vaca Rodríguez

Localización y tutorías

 

Los alumnos pueden contactar con los profesores, además de durante su horario de tutorías en sus respectivos despachos, a través del correo electrónico.

Profesor	Despacho	Correo	Tutorías
César Vaca Rodríguez	1D020	cvaca [at] infor.uva.es	ver

Temario

La parte teórica de la asignatura se estructura de la siguiente manera:

 

UNIDAD I. ANÁLISIS Y DISEÑO DE ALGORITMOS

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. Teorema de la ordenació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)

UNIDAD II. TIPOS ABSTRACTOS DE DATOS

Tema 4.- Tipos Abstractos de Datos (TAD). Definiciones Concepto de contenedor Colecciones e Iteradores Relaciones entre elementos TADs Contenedores

UNIDAD III. ESTRUCTURAS DE DATOS

Tema 5.- Vectores y listas enlazadas. Representaciones contiguas y enlazadas. Representaciones lineales y circulares. Uso y eficiencia para distintos TADs.

Tema 6.- Árboles. Definiciones. Propiedades. Implementaciones del TAD Directorio. Árboles binarios: Definiciones y propiedades. Montículos. Árboles binarios de búsqueda. Árboles AVL.

Tema 7.- Tablas de dispersión. Definiciones y objetivos. Dispersión abierta (encadenamiento) Dispersión cerrada (exploración) Análisis de eficiencia.

Tema 8.- Grafos. Definiciones. Propiedades. Representaciones: Listas y tablas de adyacencia. Árboles de extensión mínima: Algoritmos de Kruskal y Prim. Camino mínimo: Algoritmos de Floyd y Dijkstra.

Tema 9.- Ficheros. Introducción. Ordenación externa. Árboles B+

Bibliografía:

• A.V. Aho, J.E. Hopcroft, J.D. Ullman. Estructuras de Datos y Algoritmos. Addison Wesley, 1988.
• R. Peña Marí. Diseño de Programas. Formalismo y Abstracción. Prentice Hall, 1997.
• G. Brassard, P. Bratley. Fundamentos de Algoritmia. Prentice Hall, 1997.
• M.A. Weiss. Estructuras de Datos y Algoritmos. Addison Wesley, 1995.
• G.L. Heileman. Estructuras de Datos, Algoritmos y Programación Orientada a Objetos. McGraw-Hill, 1998.

Bibliografía Complementaria:

• M.A. Weiss. Data Structures and  Problem Solving Using Java. Addison Wesley, 1998
• C.A. Shaffer. A Practical Introduction to Data Structures and Algorithm Analisys. Java Edition. Prentice Hall, 1998.
• M.T. Goodrich, R. Tamassia. Data Structures and Algorithms in Java. Willey, 1998.
• E. Horowitz, S. Sahni. Fundamentals of Computer Algorithms. Computer Science Press.

Descripción de la asignatura

Títulación:	Ingeniería Técnica en Informática de Gestión
Tipo:	Troncal (Plan de Estudios de 1996)
Curso:	Segundo
Cuatrimestre:	Primero
Área:	Lenguajes y Sistemas Informáticos
Departamento:	Informática (Arquitectura, Ciencia de la Computación y Lenguajes)
Créditos:	7.5 (4.5 teoría, 1.5 prácticas en aula, 1.5 prácticas de laboratorio)

Descriptor

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.

Objetivos

• 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

Programa de Teoría:

Puede consultar el temario en la siguiente sección.

Programa de Prácticas:

Se desglosa en créditos impartidos en el aula y en laboratorios.

Los créditos de laboratorio consistirán en la resolución de una o varias prácticas. Para la realización de las prácticas de laboratorio se usarán los equipos situados en los laboratorios del Centro, de acuerdo con unos determinados horarios y división en subgrupos.

Metodología (actividades):

Los créditos de teoría y prácticas en aula se desarrollarán en el aula, a base de clases magistrales, resolución de ejercicios y problemas y otras actividades.

Para los créditos de prácticas en laboratorio, los alumnos se organizarán en subgrupos (2 en el curso actual). Cada subgrupo acudirá 1 día por semana, según indica el horario, al laboratorio indicado. Allí, podrá trabajar en grupos de 3 alumnos a lo sumo, resolviendo las prácticas propuestas.

Método y criterios de evaluación

En la convocatoria ordinaria, la calificación de la asignatura será la suma del 80% de la nota obtenida en el examen de teoría y el 20% de la nota obtenida en la práctica.

En la convocatoria extraordinaria, para aquellos que no hayan presentado práctica (o la hayan presentado pero el tener en cuenta su calificación pueda perjudicarles) la calificación de la asignatura será la nota del examen de teoría.

Histórico

En esta sección se mantiene información asociada a cursos anteriores. Respecto a los exámentes, esta documentación se aporta únicamente a título informativo y para beneficio del alumno. No obstante, no ha de ser interpretada de manera incorrecta. En particular, no se puede asumir que la "estructura" aparente de algún examen de años anteriores vaya a ser necesariamente repetida en los exámenes del curso actual.

 

• Ejemplo de uso de pilas
• Problema de diseño de algoritmos
• Practica del curso 2005/06
• Practica del curso 2004/05
• Practica del curso 2003/04
• Examen del curso 2005/06
• Examen del curso 2003/04
• Examen del curso 2001/02
• Examen del curso 2000/01
• Apuntes (obsoletos, de Programación II) de Eiffel