Ultima actualización: 7 de octubre de 2010.
Estructuras de Datos (curso 2010/11)
Ingeniería Técnica Informática de Gestión - Universidad de Valladolid

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.

 

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

Fechas límite

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

 

FechaConvocatoriaLugar
11/02/2009 (10:00)Examen convocatoria ordinariaAulas 03-04-05
13/07/2009 (9:00)Examen convocatoria extraordinariaAulas 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.

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.

Software

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.

ProfesorDespacho CorreoTutorías
César Vaca Rodríguez1D020 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.

 

 

(c) 2006 Departamento de Informática, Universidad de Valladolid

Para cualquier duda relativa a estas páginas o la información contenida en las mismas, póngase en contacto con el webmaster (cvaca [at] infor.uva.es) de la asignatura.