Volver

Escuela Técnica Superior de Informática

Universidad Autónoma de Madrid

Estructura de Datos y de la Información II

Resumen:

La asignatura EDI II es el segundo curso en estructuras de datos y algoritmos, continuacion de EDI I. La primera parte del curso (aproximadamente un tercio del total) cubre algoritmos de grafos: busqueda (incluyendo aplicaciones a deteccion de ciclos, ordenacion topologica, e identificacion de componentes fuertemente conectados), caminos minimos, y arboles abarcadores. La segunda parte se centra en metodos de gestion de ficheros: organizacion y costes de acceso a dispositivos de disco, organizacion de ficheros en registros, compresion, ordenacion, indices simples, arboles B, y hashing para ficheros. El curso tiene un importante componente de programacion, requiriendose de los alumnos la implementacion de muchas de estas tecnicas en C.

1. Algoritmos de grafos
   

   Grafos: Tipos, representación y aplicaciones.
   Búsqueda en grafos: anchura primero y profundidad primero.
   Detección de ciclos y ordenación topólogica.
   Caminos más cortos: Dijsktra y Bellman-Ford.
   Minimum spanning trees: Prim.
   

   
   

2. Ficheros externos
   

   Memoria secundaria: organización y costes de acceso.
   Procesamiento de ficheros: operaciones fundamentales en C.
   Organización de ficheros: registros y headers.
   Compresión de ficheros.
   Indices para ficheros.
   Ordenación de ficheros.
   Arboles B y B+.
   Hashing.
   

   
   

Bibliografía

• Folk, M y Zoellick, B.: 'File structures', Addison-Wesley, Reading, MA, 1992
  
• Cormen, Leiserson, Rivest: 'Introduction to algorithms', The MIT Press-Mc Graw Hill, 1990